INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A10

A NEGATIVE ANSWER TO TWO QUESTIONS ABOUT THE SMALLEST PRIME NUMBERS HAVING GIVEN DIGITAL SUMS

Tom Müller

Institut für Cusanus-Forschung an der Universität und der Theologischen Fakultät Trier, Domfreihof 3, 54290 Trier, Germany

                           muel4503@uni-trier.de

Received: 10/28/04, Revised: 5/22/05, Accepted: 5/23/05, Published: 6/20/05

Abstract

Denote by ρ(k) the smallest prime number with digital sum k (not a multiple of 3). Richard K. Guy asked whether the congruences ρ(k) ≡ 99 (mod 100) and ρ(k) ≡ 999 (mod 1000) hold for all k > 38, respectively k > 59. Counterexamples to this are given, inter alia, for k = 86 and k = 104. Moreover, several open problems and conjectures about ρ(k) are discussed.

1. Introduction

In his famous book about unsolved problems in Number Theory, Richard K. Guy [1] asks in section A3 the following three questions:

“If ρ(k) is the smallest prime with digital sum k, is ρ(k) ≡ 9 (mod 10) for k > 25? Is it ≡ 99 (mod 100) for k > 38? And ≡ 999 (mod 1000) for k > 59?”

We intend to show that the two latter congruences do not hold by constructing a counterexample in the following paragraph. The final section is concerned with some open problems and conjectures concerning the prime numbers ρ(k) for k not a multiple of 3.

2. Counterexamples

A first counterexample to two of the claims above is given for k = 86. Using some simple combinatorial methods, we find that the smallest number with digital sum 86 is

5 999 999 999  (1)

followed by the numbers

6 899 999 999,  (2)
6 989 999 999,  (3)
6 998 999 999,  (4)
6 999 899 999,  (5)
6 999 989 999,  (6)
6 999 998 999,  (7)
6 999 999 899,  (8)
6 999 999 989.  (9)

The integers (1) to (8) turn out to be composites, as they are divisible respectively by 7, 6089, 827, 19, 61, 31, 7 and 3011. The number (9) is prime. So ρ(86) = 6999999989 ≡ 989 (mod 1000) ≡ 89 (mod 100). Therefore the two latter questions above have to be answered with “no”, while the first one remains open. It might moreover be interesting to note that k = 86 is not the only known case for which the said congruences do not hold. Other examples are ρ(104) = 699999999989, ρ(137) = 4 · 10^{15} − 11, ρ(317) = 4 · 10^{35} − 11, ρ(400) = 6 · 10^{44} − 11 and ρ(580) = 6 · 10^{64} − 11. Perhaps there are many other primes of the form a · 10^{n} − 11 with a ∈ {1, 3, 4, 6, 7, 9} (the parameters a ∈ {2, 5, 8} give only multiples of 3), which lead to further examples. Lists of such primes can be found in the Online Encyclopedia of Integer Sequences [2] (the reference codes are respectively A092767, A102737, A102738, A102739, A102740 and A102741). Additionally, we have ρ(260) = 10^{29} − 101.

3. Open problems and conjectures

A number of open problems dealing with ρ(k) are waiting to be solved. Is there a k > 25 with ρ(k) ≡ 79, or ≡ 97 (mod 100)? Moreover, one might ask whether ρ(k) exists for every k not a multiple of 3. The answer to this is very probably positive, and therefore the above question could be changed into the following one (Question 1):

Does an integer m exist, such that the congruences ρ(k) ≡ 99 (mod 100) and ρ(k) ≡ 999 (mod 1000) hold for all k > m?

Let S(k) be the set consisting of the k smallest integers with digital sum k, and let N(k) be the number of integers in S(k) that end in “999”. We know that as k → ∞, \frac{N(k)}{k} → 1; however, as N(k) < k for all k > 10, we conjecture that there exist infinitely many values of k for which ρ(k) does not satisfy the congruences in Question 1. If this is true, the integer m does not exist.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A10 3

Acknowledgements Thanks are due to the friendly referee who pointed out a known sequence in the Online Encyclopedia of Integer Sequences. The author is grateful to the referee, Daniel O’Connell and Prof. Dr. Jürgen Müller for their help in finalizing this paper.

References

[1] Richard K. Guy, Unsolved problems in number theory, Springer Verlag, New York 2004 (3th edition), 15 [2] Neil J. A. Sloane, Online Encyclopedia of Integer Sequences, published electronically at

   http://www.research.att.com/njas/sequences/