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.
http://www.primenumbers.net/prptop/searchform.php?form=10^n%2B2971&action=Search
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 p 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 4 ‘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.
35839 + 10^4270, 35839 + 10^7162, 35839 + 10^7450, 35839 +
10^10082
143329 + 10^5265, 143329 + 10^6173
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
|
