Problems & Puzzles: Puzzles

Puzzle 552.- p=k mod [prime(k)]

JM Bergot sent the following puzzle.

One suddenly notices about prime 1523 that

1523=1 mod[P(1)]
1523=2 mod[P(2)]
1523=3 mod[P(3)]
1523=4 mod[P(4)]
1523=5 mod[P(5)]
but 1523 is not 6 mod[P(6)]

Q1- Can you find a prime with a larger sequence like the above one?

Contributions using the Chinese Remainder Theorem came from Farid Liam, Seiji Tomita, Jan van Delden, Emmanuel Vantieghem, Antoine Verroken, Fred Schalekamp, Torbjörn Alm, W. Edwin Clark, Farideh Firoozbakht, J-C Colin, Giovanni Resta, Ken Wilke, JC Rosa, Justin LeBeau, J. K. Andersen & Wilfrid Keller.

***

Farid wrote:

k,p
2,5
3,23
4,53
5,1523
6,29243
7,299513
9,188677703

and other larger solutions.

***

Seiji Tomita largest solution was for k=189.

***

Jan wrote:

Define r[n]=chrem([1,2,..,n],[p[1],p[2],...,p[n]]). A solution exists by the Chinese Remainder Theorem (smaller than p[n]#) since the p[i] are (relatively) prime.
Either r[n] is prime and we have a solution, or we add multiples of p[n]# to find one. There is always a solution (infinitely many) by Dirichlet's theorem on arithmetic progressions.

 

The values of n(<=300) for which the chinese remainder r[n] itself is prime are 2,3,4,5,6,7,9,18,23,27,63,105,164,189,214.

The solution for n=300 is equal to r[300]+471.p[300]# and has 836 decimals.

 

[If one remembers the value of r[n],p[n] and p[n]#  then r[n+1] can be calculated fast].

***

Emmanuel Vantieghem found all prime soutions for k=1 to 40:

k=40, p=340973765639317251145829115284647301902138204130069980971062142900083

(compare the Liam's solution:

k=40, p=7793958064666812384125724582854789400177184940320256877138774920663)

***

Antoine wrote:

1.       primes with a sequence of length 6 : 29243 , 59273 , 89303 , 179393 , 299513 , 449663 …

2.       primes with a sequence of length 7 : 299513 , 810023

***

Fred wrote:

The smallest solution for length 6 is 293,243 
For length 7: 299,513
For length 8: 14,083,283
For length 9: 188,677,703 

***

Torbjörn Alm wrote:

Size: 6, 29243
Size: 7, 299513
Size: 8, 14083283

***

W. Edwin Clark wrote:

Using Maple's built-in Chinese Remainder solver
"chrem" and primality tester "isprime" it is easy
to find such primes, for example, if n = 100 the prime
p =
195566184792309376828104078377470600459489876020\\
736815143657708647542222377168812948416689522053\
829434098768006966734794854889956202629096681005\
803909622866439498250970029045463323531561857338\
15194402421672010856771866753

***

Farideh wrote:

c is a 3396-digit probable prime an d for k = 1, 2, 3, ... , 1000

we have c = k mod[p(k)].

c =

4873295030893981951406606862303505100134673574 ...45870916258656879230930985759205211213

...

According to the Chinese Remainder Theorem (CRT) and definitions of Range, Prime ,

Apply, Times & ChineseRemainder in Mathematica I found p1, p2 & p3 as the smallest

prime (probable prime) for k = 1000, 2000 & 3000.

 

p1 = ChineseRemainder[Range[1000], Prime[Range[1000]]]+718*Apply[Times,Prime[Range[1000]]]

p2 = ChineseRemainder[Range[2000], Prime[Range[2000]]]+226*Apply[Times,Prime[Range[2000]]]

p3 = ChineseRemainder[Range[3000], Prime[Range[3000]]]+3123*Apply[Times,Prime[Range[3000]]]

 

Number of digits of p1, p2 & p3 are respectively 3396, 7485 & 11832.

 

***

J-C Colin wrote:

p, the minium prime such as p = i @ [prm(i)],  for i = 1 to k

 

k	p
5	1523
6	29243
7	299513
8	14083283
9	188677703

 

I have calculated up to p= 5 017 526 243 and found  no other k record.

 P552.txt contains details.

***

Giovanni wrote:

For example, the smallest prime  P which produce a sequence of length 1000,
P == 1 (mod 2)
....
P == 1000 (mod 7919)
is a large prime with 3396 digits.

P = 48732950308939819514066...05211213.

***
 

Ken wrote:

For i = 19, n(19) = 4966347076439519105374253, p(19) = 67, prod(19) = 7858321551080267055879090,  n(20) =  169991099649125127278835143 which is not prime. Since prod(20) = 557940830126698960967415390 using Dirichlet’s Theorem we have 169991099649125127278835143 + 557940830126698960967415390 * 5 =  2959695250282619932115912093 which is prime and 2959695250282619932115912093 == i ( mod p(i) ) for i = 1,2,..., 20.

Later he informed he got results up to prime 101.

***

JC Rosa wrote:

29243=k mod (prime(k)) for k=1 to 6

299513=k mod (prime(k)) for k=1 to 7

14083283=k mod (prime(k)) for k=1 to 8

188677703=k mod (prime(k)) for k=1 to 9

63993238523=k mod (prime(k)) for k=1 to 10

206326489583=k mod (prime(k)) for k=1 to 11

17053407660503=k mod (prime(k)) for k=1 to 12

1686719487992753=k mod (prime(k)) for k=1 to 13 

***

Justin wrote:

There are many primes resulting in longer sequences than that for 1523. It is very easy to extend from length n to length n+1. In this case, as 1523 is already 1 mod 2, 2 mod 3, 3 mod 5, 4 mod 7, and 5 mod 11, any candidate for n=6 must be a multiple of 2 * 3 * 5 * 7 * 11 = 2310 above our starting value. Using this knowledge, along with Mathematica in my case, we can extend to n=100 in just a matter of seconds, and n = 500 in about 1 hour, 20 minutes. Here are a few of the values that I found:

n = 6, p = 29243 = 12 x 2310 + 1523
n = 7, p = 299513 = 9 x 30030 + 29243
n = 8, p = 14083283 = 27 x 510510 + 299513
… n = 500, p ~= 1.088086527 x 10^1522 

If anybody is interested in the entire listing of the first 500 values, the text document can be found at the link below.

http://www.ticsplace.com/puzzles/puzzle552.txt

***

JK Andersen wrote:

A053664 gives the smallest number m such that m = i mod prime(i) for 1<=i<=n.
The number is prime for n = 2, 3, 4, 5, 6, 7, 9, 18, 23, 27, 63, 105, 164, 189, 214. It is prp for n = 1467, 3666, 3838, and no others below 10000.
The prp's have 5260, 14818 and 15599 digits. PrimeForm/GW made prp tests and Primo proved the smaller primes.

Let k be the smallest number such that k*2^27229+1 = i mod prime(i) for 1<=i<=4001.
Then k has 16345 digits and k*2^27229+1 is a 24541-digit prime proven by PrimeForm/GW.

****

Wilfrid Keller wrote:

I casually noted your Puzzle 552 asking for a prime  p
such that  p = k mod(prime(k))  for k = 1, 2, ..., r
and  p <> r+1 mod(prime(r+1))  for some  r > 5.

I took great pleasure in quickly realizing that the
_smallest_ prime with that property can explicitly be
determined for every  r > 1. Here are the first of such
primes:

  r    prime  p
  2    5
  3    23
  4    53
  5    1523
  6    29243
  7    299513
  8    14083283
  9    188677703
 10    63993238523
 11    206326489583
 12    17053407660503
 13    1686719487992753
 14    47324259017074253
 15    1591090096154137793
 16    248161892914139193203
 17    15239174792421559769003
 18    40235059344426324076913
 19    28541311729680320273011523
 20    2959695250282619932115912093
 21    63217304903966107716596774213
 22    4991508657413098029941776914083
 23    181961970861150107964391427391233
 24    561284509434029713806130453230243023
 25    3247152343721076950889641202183732053
 26    3616072151846348448539000706071045493743
 27    22012198936167639959644002739631127176273
 28    21392489963208545941841154782814433358199383
 29    5382552199619162322789720991028224106854247213
 30    198399700003939068285800272682755012782602335913
 31    89686464387026186716524879284042863531243241204603
 32    2666980659438835420115156129058763841257901570247263
 33    2711559744259524328133451282849052527192304994918744393
 34    47525302310250144630225127598577561273104967975427157213
 35    22069733286977869103083028784096795747421674870363179522123
 36    2807974182490612359653004029045872070725760747701619257797593
 37    136647777967638331693013804349067120873032747784941406448392133
 38    107677155438868822647225745751722369525528047517370472770635196933
 39    1053326119514924894727101071546848395802251026076765349227030481773
 40    340973765639317251145829115284647301902138204130069980971062142900083

Hint: Use the Chinese remainder theorem (Reference: Knuth,
Vol. 2, 2nd edition, page 270, "constructive proof") and
Dirichlet's theorem on primes in arithmetic progressions.

For large values of  r  it might take some time (and patience)
to rigorously prove the primality of the PRP determined in
that way. Note that, for example, the (minimal) PRP obtained
for  r = 600  has 1883 digits.

***

J-C Rosa wrote:

When p is a palprime I have found the following solutions:

 

3=1  mod (p(1))

5=k  mod (p(k)) for k=1 to 2

353=k  mod (p(k)) for k=1 to 3

35753=k  mod (p(k)) for k=1 to 4

3709073=k  mod (p(k)) for k=1 to 5

300576161675003=k  mod (p(k)) for k=1 to 6

301978666879103=k  mod (p(k)) for k=1 to 7

305969343969503=k  mod (p(k)) for k=1 to 8

3710759721279570173=k  mod (p(k)) for k=1 to 9

307872042929240278703=k  mod (p(k)) for k=1 to 10

***