Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-05T06:43:10.975Z Has data issue: false hasContentIssue false

A REMARK ON PRIMALITY TESTING AND DECIMAL EXPANSIONS

Published online by Cambridge University Press:  19 March 2012

TERENCE TAO*
Affiliation:
Department of Mathematics, UCLA, Los Angeles, CA 90095-1555, USA (email: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We show that for any fixed base a, a positive proportion of primes become composite after any one of their digits in the base a expansion is altered; the case where a=2 has already been established by Cohen and Selfridge [‘Not every number is the sum or difference of two prime powers’, Math. Comput.29 (1975), 79–81] and Sun [‘On integers not of the form ±pa±qb’, Proc. Amer. Math. Soc.128 (2000), 997–1002], using some covering congruence ideas of Erdős. Our method is slightly different, using a partially covering set of congruences followed by an application of the Selberg sieve upper bound. As a consequence, it is not always possible to test whether a number is prime from its base a expansion without reading all of its digits. We also present some slight generalisations of these results.

MSC classification

Type
Research Article
Copyright
Copyright © Australian Mathematical Publishing Association Inc. 2012

References

[1]Allender, E., Saks, M. and Shparlinski, I. E., ‘A lower bound for primality’, J. Comput. System Sci. 62 (2001), 356366.CrossRefGoogle Scholar
[2]Chen, Y.-G., Feng, R. and Templier, N., ‘Fermat numbers and integers of the form a k+a l+p α’, Acta Arith. 135 (2008), 5161.CrossRefGoogle Scholar
[3]Cohen, F. and Selfridge, J. L., ‘Not every number is the sum or difference of two prime powers’, Math. Comput. 29 (1975), 7981.CrossRefGoogle Scholar
[4]Crocker, R., ‘On the sum of a prime and two powers of two’, Pacific J. Math. 36 (1971), 103107.CrossRefGoogle Scholar
[5]Erdős, P., ‘On integers of the form 2k+p and some related problems’, Summa Brasil. Math. 2 (1950), 113123.Google Scholar
[6]Erdős, P. and Shorey, T. N., ‘On the greatest prime factor of 2p−1 for a prime p and other expressions’, Acta Arithm. 30 (1976), 257265.CrossRefGoogle Scholar
[7]Fileseta, M., Kozek, M., Nicol, C. and Selfridge, J., ‘Composites that remain composite after changing a digit’, J. Comb. Number Theory 2 (2010), 2536.Google Scholar
[8]Hardy, G. H. and Littlewood, J. E., ‘Some problems of “partitio numerorum” III: On the expression of a number as a sum of primes’, Acta Math. 44 (1923), 170.CrossRefGoogle Scholar
[9]Harman, G., ‘Primes with preassigned digits’, Acta Arith. 125 (2006), 179185.CrossRefGoogle Scholar
[10]Heath-Brown, D. R. and Puchta, J.-C., ‘Integers represented as a sum of primes and powers of two’, Asian J. Math. 6 (2002), 535565.CrossRefGoogle Scholar
[11]Łuszczki, Z., ‘On the prime factors of ∏ xn=1(a τ n+1)’, Funct. Approx. Comment. Math. 2 (1976), 115120.Google Scholar
[12]Mauduit, C. and Rivat, J., ‘Sur un problème de Gelfond: la somme de chiffres des nombres premiers’, Ann. of Math. (2) 171 (2010), 15911646.CrossRefGoogle Scholar
[13]Montgomery, H. and Vaughan, R., Multiplicative Number Theory I. Classical Theory, Cambridge Studies in Advanced Mathematics, 97 (Cambridge University Press, Cambridge, 2007).Google Scholar
[14]Murata, L. and Pomerance, C., ‘On the largest prime factor of a Mersenne number’, in: Number Theory, CRM Proceedings Lecture Notes, 36 (American Mathematical Society, Providence, RI, 2004), pp. 209218.CrossRefGoogle Scholar
[15]Orno, P.et al., ‘Problems’, Math. Mag. 52 (1979), 179184.CrossRefGoogle Scholar
[16]Pan, H., ‘On the number of distinct prime factors of nj+a hk’, arXiv:0907.1940.Google Scholar
[17]Pan, H., ‘On the integers not of the form p+2a+2b’, Acta Arith. 148 (2011), 5561.CrossRefGoogle Scholar
[18]Shparlinski, I., Cryptographic Applications of Analytic Number Theory (Birkhaüser, Basel, 2003).CrossRefGoogle Scholar
[19]Sloane, N. J. A., ‘The On-Line Encyclopedia of Integer Sequences’, published electronically atwww.research.att.com/∼njas/sequences/, 2007.Google Scholar
[20]Sun, Z. W., ‘On integers not of the form ±p a±q b’, Proc. Amer. Math. Soc. 128 (2000), 9971002.CrossRefGoogle Scholar
[21]van der Dries, L. and Moschovakis, Y., ‘Is the Euclidean algorithm optimal among its peers?’, Bull. Symbolic Logic 10 (2004), 390418.CrossRefGoogle Scholar
[22]Woods, A., ‘Subset sum “cubes” and the complexity of prime testing’, Theor. Comp. Sci. 322 (2004), 203219.CrossRefGoogle Scholar
[23]Yuan, P., ‘Integers not of the form c(2a+2b)+’, Acta Arith. 115 (2004), 2328.CrossRefGoogle Scholar