Problems & Puzzles:
Puzzles
Puzzle
554.
P+10^n
JM
Bergot sent the following puzzle.
One notices that
31+10=41
31+100=131
31+1000=1031 and all sums are primes.
Q Can one find a starting prime such that
adding powers of ten produces more primes, consecutive or not?
Contribituions came from Giovanni Resta,
Luis Rodríguez, Seiji Tomita, Farideh Firoozbakht, Jan van Delden, JK
Andersen, Torbjörn Alm, Jeff H Heleen, Farid Lian, W. Edwin Clark.
***
Giovanni wrote:
It is easy to see that there cannot be more
than 5 consecutive
powers of ten, since
(10,10^2,10^3,10^4,10^5,10^6) mod 7 = (3, 2, 6, 4, 5, 1)
so, if p is not 7, then at least one of p+10,p+100,...,p+10^6 is
divisible by 7.
The first primes p such that p+10,...,p+10^5 are all primes are
1399, 3457, 25339, 33403, 41131,...
If non consecutive powers are considered, it is difficult to choose
where to stop in checking.
For example, for prime p=863671 we have at least 31 primes of the
form p+10^k, obtained for
k=2, 4, 6, 10, 11, 14, 17, 18, 27, 28, 29, 34, 36, 38, 71, 87, 105, 152,
155, 164, 189, 192, 218, 269, 393, 503, 1127, 1670, 1760, 2012, 2489, ...,
?
what is the smallest p having 5 consecutive
p+10^x primes?
My bet is on 151, which gives primes for
x={2,3,4,5,6}.
There are no other p<151 giving 5 consecutive primes of the form
p+10^x for x<=2000.
If the seed number p is not required to be prime and it is a
multiple of 7, we can indeed obtain more than 5 consecutive powers.
For example, 847+10^x is prime for x=1,2,3,4,5,6.
15127+10^x is prime for x=1,...,7, and 54621+10^x is prime for x=1,...,9.
***
Luis wrote:
Until p < 26000000 I found only:
n prime
2 3
3 13
4 163
5 1399
***
Seiji wrote:
10 is a primitive root modulo 7.
So,{10^1 mod 7,10^2 mod 7,..,10^6 mod 7}={1,2,..,6}.
Then for every prime p, p+10^n=0 mod 7 for some integer n(1<=n<=6).
Therefore,maximum of n such that p+10^n for n(1<=n<=m) are all primes is
5.
***
Farideh wrote:
1399+10^k for k =
1,2,3,4 & 5 is prime. There is no prime p such that for
more than 5 integers
k, p +10^k is prime because at east one of them is a
multiple of 7 and
cannot all such six numbers are prime.
***
Jan wrote:
Smallest solutions
with p prime such that 10^k+p is prime for consecutive k with k from 0
to n (n<=5):
2
19,29
3,13,113
13,23,123,1023
163,173,1063,10063,100063
1399,1401,11399,101399,1001399
There are no
solutions when k is consecutive and k in a range from [k0,..,k0+n1]
with n>5.
Suppose there
exists a p such that the numbers 10^k+p are prime for k in a range
[k0,..,k0+5].
The first prime q
(besides the divisors of 10) for which the reduced residue set is
complete, i.e. all residues of 10^k+p mod q occur, is q=7 (the order
of 10 mod 7 is equal to phi(7)=6). We know that 10^k+p can't be 0 mod
7 (The only option would be 10^k+p=7 (prime) giving k=0 and p=6 (not
prime)). The residue of p mod 7=p0 (p<>7), p0<>0, therefore there
exists some k1 in [k0,..,k0+5] such that (10^k1+p0) mod 7=0 in
contradiction with our assumption that this number is prime.
***
JK Andersen wrote:
p = 1399 is the smallest prime such that
p+10^n is prime for n = 1 to 5.
There is no longer sequence because 7 always divides either p or one of
p+10^n
for n = 1 to 6.
The prime 525705314*499#+3457 gives a 215digit case for n = 1 to 5.
If p and p+10^n for n = 1 to 5 are all prime, then 7 divides p+10^n for n
= 6,
12, 18, ...
p = 133246745796776191 is the smallest prime such that p+10^n is prime for
all
n < 18 except 6 and 12.
Let q = 92223642160211916050635108351. Then q, q+10, q+100, q+1000 are
consecutive primes (not the smallest case). It looks challenging to
include
+10000 with consecutive primes.
If composite p is allowed then arbitrarily long sequences are admissible.
http://www.research.att.com/~njas/sequences/A124116 by Anton
Vrba says:
a(n) the smallest positive integer such that a(n)+10^k is prime for
k=1,2...n.
The first 11 terms are given:
1, 1, 9, 9, 559, 847, 15127, 54621, 54621, 5893321, 167459299
The next five terms for n = 12 to 16 are:
3595903759, 3595903759, 1040749968601, 688840705177051, 430442854738298199
***
Torbjörn wrote
I found primes of the asked form not
necessarily consecutive for the following p values (only details for the
last one)
Prime: 3 Primes: 4
Prime: 7 Primes: 5
Prime: 103 Primes: 6
Prime: 1087 Primes: 7
Prime: 1801 Primes: 8
Prime: 2884279 Primes: 9
Prime: 433777 Primes: 10
Prime: 270451 Primes: 11
270451+10=270461
270451+100=270551
270451+1000=271451
270451+10000=280451
270451+100000=370451
270451+10000000=10270451
270451+1000000000=1000270451
270451+10000000000000=10000000270451
270451+100000000000000=100000000270451
270451+1000000000000000=1000000000270451
270451+10000000000000000=10000000000270451
***
Jeff wrote:
For Puzzle 554, there are
many possible solutions.
Here I use powers of 10 from 10^1 to 10^100 to find
the first occurrence of k primes.
Nonconsecutive, 1st occurrence
start powers of 10 yielding
k prime a prime (range 1100)
3 43 1, 5, 37
4 73 1, 2, 8, 11
5 127 1, 2, 8, 26, 96
6 13 1, 2, 3, 17, 25, 81
7 7 1, 2, 4, 8, 9, 24, 60
8 31 1, 2, 3, 14, 18, 44, 54, 89
9 3 1, 2, 5, 6, 11, 17, 18, 39, 56
10 79 1, 2, 4, 7, 16, 18, 43, 60, 73, 91
11 103 1, 3, 4, 5, 7, 9, 10, 11, 27, 35, 85
12 1093 1, 2, 4, 6, 7, 13, 17, 18, 19, 42, 59, 66
13 3457 1, 2, 3, 4, 5, 7, 11, 14, 15, 16, 17, 20, 47
14 151 2, 3, 4, 5, 6, 20, 50, 56, 60, 65, 68, 77, 86, 95
15 27409 2, 3, 4, 6, 10, 20, 28, 30, 32, 35, 46, 54, 56, 98, 99
16 19429 4, 5, 8, 9, 11, 12, 16, 17, 21, 23, 32, 36, 38, 47, 76, 77
17 28393 1, 2, 4, 5, 6, 7, 8, 11, 13, 30, 34, 42, 52, 59, 64, 70,
97
Consecutive, 1st occurrence
start powers of 10 yielding
k prime a prime
3 13 1,2,3
4 163 1,2,3,4
5 1399 1,2,3,4,5
***
Farid wrote:
Power base Chain
long first prime last prime
2 4 3 19
4 10 13243063 14291639
6 9 3599111 13676807
8 2 3 67
10 5 1399 101399
12 3 5 1733
***
W. Edwin wrote:
My record is the prime
151:
151 + 10^n is prime for the following 26 values of n:
{2, 3, 4, 5, 6, 20, 50, 56, 60, 65, 68, 77, 86,
95, 158, 176, 233, 365, 406, 501, 555, 855, 1006,
1095, 1298, 1307}
[I use Maple's probabilistic primality tester isprime
to "verify" primality.]
***
