Problems & Puzzles: Puzzles

Puzzle 556.- Follow up to Puzzle 554

W. Edwin Clark sent the following puzzle, as a follow up to Puzzle 554:

Q1. For which primes p is p + 10^n composite for all natural numbers n?

One solution is, p = 3*k-1 then for n > 0, p + 10^n is divisible by 3.

Q2. Are there other solutions like that?

In addition to such primes, I found the following primes p for which p + 10^n is composite for 0 < n < 3000.

2971, 9811, 15817, 25609, 35839, 48247, 56473, 70729, 97987, 99991, 107449, 119107, 127711, 135937, 143329, 149269, 177979, 191071, 206623, 219187, 219517.

However, I cannot see any reason that p + 10^n should always be composite for these primes.

Q3. Maybe someone can.

Contributions came from JK Andersen, Giovanni Resta, Jan van Delden, Seiji Tomita, W. Edwin Clark, Emmanuel Vantieghem & Farideh Firoozbakht.

***

Andersen wrote:

48247, 56473, 135937 and 149269 never produce primes. They all have the
covering set {7, 11, 13, 37}. For example, 48247 + 10^n is divisible by:
7 if n == 4 (mod 6)
11 if n == 1 (mod 2)
13 if n == 2 (mod 6)
37 if n == 0 (mod 3)
This covers all possibilities of n modulo 6.

shows that Mike Oakes found the prp 2971 + 10^175608.

I found these prp's with PrimeForm/GW:
9811 + 10^30897
15817 + 10^16005
25609 + 10^9656
35839 + 10^4270
70729 + 10^6235
107449 + 10^6406
119107 + 10^12589
127711 + 10^3206
143329 + 10^5265
219517 + 10^4288

Assuming all prp's are really prime, this shows that 48247 is the smallest
prime p for which p + 10^n is never prime.
This is a base 10 variation of the dual Sierpinski problem.

I have found no prp's or covering sets for
97987, 99991, 177979, 191071, 206623, 219187.
I guess they all produce large primes.

...

Update: 99991 + 10^26312 is a prp. The others are composite for n < 30000.

***

Resta wrote:

Apart from the primes of form 3k-1,
the primes p for which I can prove that p+10^m is
composite for every m>0 are 48247, 56473, 135937 and 149269.
(the values of p=5 and p=11 are trivial)

Indeed, it can be shown easily that:

For every m = 6k+0  48247 + 10^m is divisible by 37
For every m = 6k+1, 48247 + 10^m is divisible by 11
For every m = 6k+2, 48247 + 10^m is divisible by 13
For every m = 6k+3  48247 + 10^m is divisible by 11*37
For every m = 6k+4, 48247 + 10^m is divisible by 7
For every m = 6k+5, 48247 + 10^m is divisible by 11

For every m = 6k+0  56473 + 10^m is divisible by 11
For every m = 6k+1, 56473 + 10^m is divisible by  7
For every m = 6k+2, 56473 + 10^m is divisible by 11*37
For every m = 6k+3  56473 + 10^m is divisible by 13
For every m = 6k+4, 56473 + 10^m is divisible by 11
For every m = 6k+5, 56473 + 10^m is divisible by 37

For every m = 6k+0  135937 + 10^m is divisible by 11*37
For every m = 6k+1, 135937 + 10^m is divisible by 7
For every m = 6k+2, 135937 + 10^m is divisible by 11
For every m = 6k+3  135937 + 10^m is divisible by 37
For every m = 6k+4, 135937 + 10^m is divisible by 11
For every m = 6k+5, 135937 + 10^m is divisible by 13

For every m = 6k+0  149269 + 10^m is divisible by 11
For every m = 6k+1, 149269 + 10^m is divisible by 13
For every m = 6k+2, 149269 + 10^m is divisible by 11*37
For every m = 6k+3  149269 + 10^m is divisible by 7
For every m = 6k+4, 149269 + 10^m is divisible by 11
For every m = 6k+5, 149269 + 10^m is divisible by 37

I think that 48247 is probably the smallest
prime with this property (apart those of the form 3k-1),
despite I have still to find a prime of form, say, 2971+10^m.

Of the remaining values (cited in the puzzle) some
can ruled out extending the search beyond m>3000.

They are (smallest m such that p+10^m is a probable prime):
p          m
25609  9656
35839  4270
70729  6235
107449  6406
119107 12589
127711  3206
143329  5265
219517  4288

I'm still performing tests on the remaining values, especially
on those less than 48247, that is 2971, 9811 and 15817.

Other primes p for which p+10^m is always composite are:
358159, 371359, 371491, 425083, 491371, 527869, 580381, 584167,
675841, 802603, 806389, 898063, 972313,...
For all these primes it can be used an argument as that above,
based on divisibility by 7, 11, 13 and 37.

...

I finally found the (probable) prime 9811+10^30897.

This proves that 48247 and 56473 are the two smallest
primes p (not of the form 3k-1) for which p+10^m is always
composite.

Summarizing, the exponents for the values below  56473 are:
p          m
2971  175608
9811   30897
15817   16005
25609    9656
35839    4270

I'm testing the remaining values
(97987, 99991, 177979, 191071, 206623, 219187)
In particular, if I find an exponent m also for p=97987 and p=99991,
then the next two good primes (after 48247 and 56473)
are indeed 135937 and 149269.

***

Jan wrote:

Q1/Q2:

We must have that 10^n+p is composite for all n, for p prime. Of course one could take p=2 or p=5.

An easy situation would be that 10^k+p=0 mod q[k], with the q[k] cyclic. For instance if p=-1 mod 3, we could use q[k]=3 for all k (period 1).
In the list given by W. Edwin Clark the following four values for p are hopefull: 48247, 56473, 135937 and 149269. The first is 1 mod 11, the rest are -1 mod 11 and show a period of 6.

For each of these the prove that 10^n+p is always composite is similar. For instance for p=135937

We have:

10^(1+6k)+p = 0 mod 7    or 3^(1+6k)+p mod 7= 3+p mod 7=0 mod 7 since phi(7)=6 [Or one could use 7|10^6-1].
10^(3+6k)+p = 0 mod 37  or 10^(3+6k)+p mod 37 = 10^3*(10^(6k)-1)+10^3+p mod 37 = 10^3+p mod 37 = 1+p mod 37 = 0 mod 37, since 37|10^3-1
10^(5+6k)+p = 0 mod 13  or 10^(5+6k)+p mod 13 = 10^5*(10^(6k)-1)+10^5+p mod 13 = 10^5+p mod 13 = 4+p mod 13 = 0 mod 13, since 13|10^6-1

and the even values of n have 10^n+p=0 mod 11.

Leading to the following congruences mod 222222:

Search for

p=10 mod 11 (and 1 mod 6) and
[10,10^3,10^5] mod (7,13,37) equal to -p mod (7,13,37) in any of the 6 permutations, resulting in:

p should be [56473,135937,149137,149269,175009,202861] mod 222222

or

p=1 mod 11 (and 1 mod 6) and
[10^2,10^4,10^6] mod (7,13,37) equal to -p mod (7,13,37) in any of the 6 permutations, resulting in:

p should be [9175,46927,48247,83425,137149,139723] mod 222222

Inspection shows that 10^6-1 has 3 distinct factors (besides 3 and 11) exactly enough to cover our need for 3 remaining residue classes.
For another periodic solution one would have to find a integer k such that 10^(2k)-1 has k distinct factors besides 3 and 11. [I didn't find one].

Q3:
My guess would be that the other values for p that are given are induced by an algebraic factorisation or are "extremely lucky ones" and will fail for larger n.
For instance p=2971 only 10^(6k)+p needs to be checked, other n give 7,37 or 11 as a factor. Furthermore k=1 mod 5 would prove 271 as a factor, but that would still leave us with 4 residues mod 30.

Our best hope would be to find an algebraic factorisation for this expression "of some sort". For instance for p=99991 one could use x^k+x^5-x+1 to prove that x+1 is divisor for k odd and that x^2+1 is a divisor for k=2 mod 4 (which we already know), but we can't use this one to find divisor 7 for x=4 mod 6 or other divisors. Directly using x^k+p does not work.

***

Seiji Tomita wrote:

Q3.

q=48247+10^n is composite for all n.

(1). n=2m+1={1,3,5}:q is divisible by 11.
(2). n=6m+4={4}    :q is divisible by 7.
(3). n=6m+2={2}    :q is divisible by 13.
(4). n=3m={0,3}    :q is divisible by 37.
Above all set is {0,1,2,3,4,5},then q is always divisible by 7 , 11 , 13 or 37.

Similarly,all the elements of q={56473+10^n, 135937+10^n, 149269+10^n, 371359+10^n, 425083+10^n, 491371+10^n,
527869+10^n, 584167+10^n, 675841+10^n, 1026037+10^n, 1063897+10^n}
are composite for all n.

Q1.

Let p=37037*k+11210, 37037*k+9351, 37037*k+26038, 37037*k+28612,37037*k+9890, 37037*k+9175,
37037*k+19436, 37037*k+24826, 37037*k+1121,37037*k+17676, 37037*k+26861, 37037*k+989,
then p+10^n is composite for all n.

Q2.

For p=358159,371359,371491,425083,491371,527869,580381,584167,675841,802603,
806389,898063,972313,p+10^n is composite for all n where p < 10^6.

For p=2971,9811,15817,97987,99991,119107,177979,191071,206623,219187,
p+10^n is composite for 3000 <=n< 10000.

{25609+10^9656, 35839+10^4270, 70729+10^6235, 107449+10^6406, 127711+10^3206, 143329+10^5265, 219517+10^4288} are primes.

***

W. Edwin Clark wrote

At least two of the primes p listed in Puzzle 556 do not have
p + 10^n composite for all n. Namely,

If p = 35839 then p + 10^4270 is prime.
If p = 12711 then p + 10^3206 is prime.

[As always, I use Maple's isprime to determine primality].

On the  other hand, p + 10^n are composite for all n if p is one
of the primes 48247, 56473, 135937, 149269. This follows from the following theorem.

THEOREM. For any positive integer p, p + 10^n is composite
for all non-negative integers if the vector
[p mod 7, p mod 11, p mod 13, p mod 37]
is any one of the following:

a) [3, 1, 4, -1]
b) [-2, 1, -3, -1]
c) [-2, 1, -1, -10]
d) [-1, 1, -3, 11]
e) [-1, 1, 4, -10]
f) [3, 1, -1, 11]
g) [-3, -1, -4, -1]
h) [-3, -1, 1, 11]
i) [1, -1, -4, -10]
j) [1, -1, 3, 11]
k) [2, -1, 1, -10]
l) [2, -1, 3, -1]

PROOF. The key is to note first that for m in {7,11,13,37} we
have 10^6 = 1 (mod m) and hence 10^(6k) = 1 (mod m).

Suppose a) holds, that is,
[p mod 7, p mod 11, p mod 13, p mod 37] = [3,1,4,-1].
We claim that for every n, p + 10^n is divisible by
at least one of 7,11,13,37:

Suppose n is odd, then 10^n = (-1)^n = -1 (mod 11) and
since p = 1 (mod 11), we have p + 10^n = 0 (mod 11).

So now we only need to consider the case where n is even.
If n is even we have three cases: n = 6k, 6k+2 or 6k+4.

Since p = 3 (mod 7),  p + 10^(6k+4) = 3 + 10^4 (mod 7)
= 0 (mod 7). So p + 10^(6k+4) = 0 (mod 7).

Since p = 4 (mod 13),  p + 10^(6k+2) = 4 + 10^2 = 0 (mod 13)
So p + 10^(6k+2) = 0 (mod 13).

Since p = -1 (mod 37), p + 10^(6k) = -1 + 1 (mod 37) = 0
So p + 10^(6k) = 0 (mod 37).

This establishes the theorem for case a).

In b),...,f)  p = 1 mod 11 and so we can assume n is odd. Again
it suffices to treat the cases n = 6k, 6k+2,  6k+4. This can
be done in a manner similar to that for a) above.

In g),...,l),  p = -1 mod 11 so p + 10^n = 0 mod 11 for all
even n. For odd n, we have the cases 6k + 1, 6k + 3, 6k + 5 and
each of these cases follow in a manner similar to the proof
of case a).  QED.

COROLLARY. There are infinitely many primes p satisfying
each of the cases a),...,l) in the above theorem.

PROOF. [Use the Chinese Remainder Theorem and Dirichlet's Theorem
on primes in an arithmetic progression.]

REMARK 1: Via the Chinese Remainder Theorem one can replace the condition on the vectors in the above theorem by the condition
that p is congruent modulo 7*11*13*37 to one of the following numbers

989, 1121, 9175, 9351, 9890, 11210, 17676, 19436, 24826, 26038,
26861, 28612

REMARK 2. This puzzle is reminiscent of the Sierpinski numbers
http://en.wikipedia.org/wiki/Sierpinski_number
A common generalization would be to find all a, b and c such
that a*b^n+c is composite for all natural numbers n.
[Compare: http://www.primepuzzles.net/problems/prob_049.htm]

***

Emmanuel Vantieghem wrote:

The puzzle 556 is highly related to the Sierpinski problem.  Interresting links in that direction may be

http://www.utm.edu/staff/caldwell/preprints/2to100.pdf

and        http://www.emis.ams.org/journals/JIS/VOL10/Jones/jones67.pdf

There exist primes  p  with the following property :  there exists a finite set  S  of primes (a 'covering set')  such that for every natural number  n,  10^n + p  is divisible by at least one of the primes in  S.  The simplest example is any  p  of the form  3x-1 : the set  S  is then {3}.  The smallest   of the form  3x+1  I could find were  48247, 56473, 135937, 149269, 371359, 425083, 491371, 527869, 584167, 675841, 1026037, 1063897.  The covering set for all these primes is  { 7, 11, 13, 37 }.  All primes that are covered by that set must be of the form   p + k *7*11*13*37  and are infinite in number, by Dirichlet’s theorem on primes in arithmetic progressions.  All those primes  p have the property that all numbers  p+10^n  are composite for all  n.

There are also other primes that are covered by other sets.  I found  222384427, 544292233, 195890509, 205109587, 58905109, 751095883, 76255717, 323844289, all covered by  { 11, 73, 101, 137}  and of course any prime congruent to one of these primes modulo 11*73*101*137 (and of the form  3x+1).  Coverings by other sets, such as {11,37,101,137,9901,9999001} gave very big primes (1215111486752538979 was the smallest).

Anyhow, there are only   ‘covered’ primes, In W. Edwin Clark’s list.  For the remaining primes  2971, 9811, 15817, 25609, 35839, 70729, 97987, 99991, 107449, 119107, 127711, 143329, 177979, 191071, 206623, 219187 and 219517, I could not find some covering and my guess is that there is none.  Therefore, I extended the computations to  n = 10000.  Here is what I found :

25609+10^n   is (probable) prime for  n = 9656

35839+10^n   is (probable) prime for  n = 4270

70729+10^n   is (probable) prime for  n = 6235

107449+10^n  is (probalbe) prime for  n = 6406

127711+10^n  is (probalbe) prime for  n = 3206

143329+10^n  is (probable) prime for  n = 5262

219517+10^n  is (probable) prime for  n = 4288.

Maybe, with a lot of patience and a lot of computing time, the other ones will give primes too.  My conjecture is that  48247  is the smallest prime not of the form  3x-1  such that  48247+10^n  is composite for all  n …

***

Farideh wrote:

I think primes of the form 3k -1 are the only primes p that we can say p + 10^n  for all

positive integers is composite.

For the set A = {2971, 9811, 15817, 25609, 35839, 48247, 56473, 70729, 97987, 99991, 107449,

119107, 127711, 135937, 143329, 149269, 177979, 191071, 206623, 219187, 219517} that Edwin

wrote only  for this subset B = {2971, 9811, 15817, 48247, 56473, 97987, 99991, 119107, 135937,

149269, 177979, 191071, 206623, 219187} of primes p  ... there is no integer n less than 10000

such that p + 10^n is prime.

In fact all the following numbers are probable primes.

25609 + 10^9656

35839 + 10^4270, 35839 + 10^7162, 35839 + 10^7450, 35839 + 10^10082

70729 + 10^6235

107449 + 10^6406

127711 + 10^3206

143329 + 10^5265, 143329 + 10^6173

219517 + 10^4288

Note that if p is of the form 22*k - 1 then for all even natural numbers n, 11 divides p + 10^n

so p+10^n is composite and if p is of the form 22*k + 1 then for all odd  natural numbers n,

11 divides p + 10^n so p+10^n is composite. Now since all the terms of A are of these forms

most of  the numbers p +10^n for p in A are composite.

Also for some primes p, like p = 25609 we can easily show that if p + 10^n is prime then n is

of  the form 6*k + 2.

 Records   |  Conjectures  |  Problems  |  Puzzles