Tao, Terence A remark on primality testing and decimal expansions. (English) Zbl 1251.11089 J. Aust. Math. Soc. 91, No. 3, 405-413 (2011). Following ideas of F. Cohen and J. L. Selfridge (for the base \(a=2\)) [Math. Comput. 29, 79–81 (1975; Zbl 0296.10029)] the present paper shows that, for any integer positive base \(a\), there exist primes \(p\) such that changing any of the digits in the base \(a\) expansion of \(p\) the resulting number is composite. As a consequence a deterministic primality test need to read all the digits in the base \(a\) expansion of a positive integer candidate to decide if \(a\) is prime or not.More generally the paper proves the following result (Theorem 1.2): Let \(K\) be a natural number. For all sufficiently large \(N\) a positive proportion of primes in the interval \([N, (1+1/K)N]\) verifies that all the numbers \(|kp\pm ja^i|\) are composite (\(a,j,k\in [1,K],\,\, i\in [1,K\log K])\).Section 1 introduces the problem and Section 2 gives the proof of Theorem 1.2. Instead of using a fully covering set of congruences (as Cohen and Selfridge) this proof take a partially covering using some special primes and then applies upper bound sieves. Finally Section 3 discusses possible variants and generalizations of Theorem 1.2. Reviewer: Juan Tena Ayuso (Valladolid) Cited in 5 ReviewsCited in 12 Documents MSC: 11Y11 Primality 11N36 Applications of sieve methods 11A07 Congruences; primitive roots; residue systems Keywords:primality testing; base \(a\) expansion; sieve theory; covering congruences Citations:Zbl 0296.10029 PDF BibTeX XML Cite \textit{T. Tao}, J. Aust. Math. Soc. 91, No. 3, 405--413 (2011; Zbl 1251.11089) Full Text: DOI arXiv OpenURL Online Encyclopedia of Integer Sequences: Weakly prime numbers (changing any one decimal digit always produces a composite number). Also called digitally delicate primes. Primes with property that when written in base two complementing any single bit yields a composite number. Complementing any single bit in the binary representation of these primes produces a composite number. K-bit primes p such that p-2^i and p+2^i are composite for 0<=i<=K-1. Number of ordered triples <p,s,t> satisfying p+F_s+L_t = n, where p is an odd prime, s >= 2 and F_s or L_t is odd. Number of ways to express n as the sum of an odd prime, a positive Fibonacci number and half of a positive Fibonacci number. Number of ways to express n as the sum of an odd prime, a positive Fibonacci number and an even Lucas number. Positive integers that can be written as the sum of a positive Pell number and twice a positive Pell number. Number of ways to express n as the sum of an odd prime, a positive Fibonacci number and twice a positive Fibonacci number. Numbers ending in 1, 3, 7 or 9 such that changing any one decimal digit produces a composite number. Number of primes (excluding n) that may be generated by replacing any decimal digit of n with a digit from 0 to 9. References: [1] DOI: 10.1007/978-3-0348-8037-4 [2] DOI: 10.1090/S0002-9939-99-05502-1 · Zbl 0959.11043 [3] DOI: 10.2307/2690284 [4] DOI: 10.4064/aa125-2-4 · Zbl 1246.11155 [5] Murata, Number Theory pp 209– (2004) [6] DOI: 10.1007/BF02403921 · JFM 48.0143.04 [7] Montgomery, Multiplicative Number Theory I. Classical Theory (2007) · Zbl 1142.11001 [8] Fileseta, J. Comb. Number Theory 2 pp 25– (2010) [9] DOI: 10.4007/annals.2010.171.1591 · Zbl 1213.11025 [10] Erdos, Acta Arithm. 30 pp 257– (1976) [11] Łuszczki, Funct. Approx. Comment. Math. 2 pp 115– (1976) [12] Erdos, Summa Brasil. Math. 2 pp 113– (1950) [13] Heath-Brown, Asian J. Math. 6 pp 535– (2002) · Zbl 1097.11050 [14] Crocker, Pacific J. Math. 36 pp 103– (1971) · Zbl 0215.34703 [15] DOI: 10.1090/S0025-5718-1975-0376583-0 [16] DOI: 10.4064/aa135-1-4 · Zbl 1180.11005 [17] DOI: 10.1006/jcss.2000.1725 · Zbl 1032.11058 [18] DOI: 10.4064/aa115-1-2 · Zbl 1096.11007 [19] DOI: 10.1016/j.tcs.2004.03.037 · Zbl 1098.68050 [20] DOI: 10.2178/bsl/1102022663 · Zbl 1095.03025 [21] DOI: 10.4064/aa148-1-4 · Zbl 1219.11150 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.