Problems & Puzzles: Puzzles

Puzzle 555.- q=p(i) mod [p(i+1)]

JM Bergot sent the following puzzle, as a follow up to Puzzle 552:

Find primes q that satisfies q=p(i) mod [p(i+1)] for i=1 to k 

C. Rivera found the smallest q solutions for k= 1 to 8

Q1- Can you find the smallest prime for each k= 9, 10,...

Q2- Can you find the smallest integer for each k= 11, 12,...

Contributions came from Torbjörn Alm, Farid Lian, Seiji Tomita, Jan van Delden, W. Edwin Clark, J. K. Andersen, JC Rosa, Emmanuel Vantieghem.

***

Torbjörn wrote:

Q1 : Prime solution(k) = integer (k) + n*prod(involved prims moduli) for k=9, 10, ...
q(prime)
9 +10152454583
10 +10152454583
11 +27286379112263
12 +4509412212537503
13 +58057458593326463
14 +3420327120832524173
15 +178049025375964084613
16 +23055638276363375485073
17 +1049809665258712924748453
18 +110949022999023044736072443
19 +7819962464608765026553459733
20 +50781406384364585021044444763
21 +23022321264360814205971470881843
22 +856392316005595097351834370401513
23 +5396489082723284570397442676278943
24 +5662357060412964367985225391799556723
25 +1621865499786221380119909830671360561793
...
50 +7029312339827196797768080063792831591256437314
0052583293573150638169922764185159476408457830723


Q2: Integer solutions k=11, 12,...

q(integer)
11 +1313795640428
12 +97783391392958
13 +5726413266646343
14 +38433316595821418
15 +15103232990013860963
16 +943894249589930135768
17 +52858423703753671390658
18 +932521283899305953765183
19 +8790842834979573009644273
20 +10051725785115560870423121293
21 +498807892976103850677879002933
22 +55198768937767543284962316423143
23 +5396489082723284570397442676278943
24 +1051221132521927518479021097136044583
25 +108260131455988534269498270948062701838
...
50 +1391962526553093686057568326412971272364922177
781234253663153338255441160251347069712001134538

***

Farid wrote:

***

Seiji wrote:

Search range: 9<=k<20

k     q(prime)                         q(integer)

9    10152454583                       447914738
10   10152454583                       10152454583
11   27286379112263                    1313795640428
12   4509412212537503                  97783391392958
13   58057458593326463                 5726413266646343
14   3420327120832524173               38433316595821418
15   178049025375964084613             15103232990013860963
16   23055638276363375485073           943894249589930135768
17   1049809665258712924748453         52858423703753671390658
18   110949022999023044736072443       932521283899305953765183
19   7819962464608765026553459733      8790842834979573009644273

For k=500, q(prime) has 1525 digits and q(integer) has 1523 digits.

***

Jan wrote:

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

 

The values of n(<=3200) for which the chinese remainder r[n] itself is prime are (answers to Q1 and Q2):

n   digits

1         1

5         4

10      11

23      34

30      48

267   728

403 1184

406 1194
626 1978

891 2974

 

Around n=2850 the number of digits of r[n] supersede 10000. Testing becomes time consuming.

 If n=400 r[400] has 1172 digits (Q2) and r[400]+2374*p[400]#/2 is prime and has 1177 digits (Q1).

The two missing values in the given table are equal: 10152454583 (r[10])

 

 i.e.: returned prime by Maple XIV.

***

W. Edwin wrote:

Using Maple's built-in Chinese Remainder procedure "chrem"
one can solve any problem of the form:

Given any n integers
    f(i), i = 1,...,n,
and pairwise relatively prime integers
    m(i), i = 1,...,n,
find the (unique) smallest non-negative integer q such that
    q = f(i) mod m(i), i = 1,...,n.


If n is not too big this can be done rapidly. For example,
if n = 200, q can be found in less than one second for Puzzle
555. Then, to find the smallest prime solution q, let
M = m(1)*m(2)*...*m(n) and seek the smallest j = 0,1, 2,...
such that q+j*M is prime. Usually this can also be done
rapidly if n is not too big.

For example for the case of Puzzle 555:
  q = p(i) mod p(i+1), i = 1,...,n.
With n = 200,  Maple finds in .016 seconds the smallest
prime solution q =
18130718076296649604375735572232925326908574329543\
87568301276979633355785175906787878142889793645773\
75241777159435708065857656075947762057642890320549\
63503246605702869281594606998276364195487747775584\
57952847037593062595594016085893928545561098424160\
21369326565054653458938450295111143383035658151930\
55539873180287832693498236712171987951747198336692\
61797860111643477203352660120089234179842810965463\
92754139770438112858732967964226324832981055831003\
65261777544100534543807200584817615594390001829218\
378845052685491243

***

J. K Andersen wrote:

Let qp(k) = smallest q (prime) for k, and qi(k) = smallest q (integer).
The Chinese remainder theorem can compute thousands of qi(k) in seconds.
qp(k) is always of form qp(k) = qi(k) + n*p(k+1)#/2, for some integer n.
Dirichlet's theorem says there always exist primes qp(k).

If qp(k) = qi(k) then n = 0. This occurs for
k = 1, 5, 10, 23, 30, 267, 403, 406, 626, 891, and no others up to 10000.
Primo proved the terms up to k = 406. The last two are prp.

PrimeForm/GW found prp qp(k) for all k <= 1000. Primo has proved for k <= 250.
The n values for k = 1 to 1000 are in puzz_555-n.txt:
http://users.cybercity.dk/~dsl522332/math/puzz_555-n.txt

This PARI/GP script uses them to write qp(k) and qi(k) for all k <= 1000:
v=readvec("puzz_555-n.txt"); r=Mod(0,1); m=1;
for(k=1,#v, p=prime(k); p2=prime(k+1); n=v[k]; m=m*p2;\
r=chinese(r,Mod(p,p2)); q=lift(r); write("puzz_555-q.txt",k"  "q+n*m"  "q))

The output lines for k = 6 to 12:
6  1473743  197468
7  25978223  1728998
8  113275433  1728998
9  10152454583  447914738
10  10152454583  10152454583
11  27286379112263  1313795640428
12  4509412212537503  97783391392958

The table in the puzzle is missing a digit in qp(6) and qi(9).

Let n(k) be the n value giving the smallest prp qp(k). PrimeForm/GW found:
n(1000) = 1023, n(2000) = 5452, n(3000) = 5076, n(4000) = 4340, n(5000) = 107.
The five prp's have 3400, 7490, 11837, 16348, 20981 digits.

***

Rosa wrote:

About the questions Q1 and Q2 , I found the following solutions:

 

k           q(prime)                  q (integer)

 

9        10152454583              447914738

10      10152454583              10152454583

11      27286379112263         1313795640428

12     4509412212537503       97783391392958

 

remark: for k=6 and q prime the smallest solution is 1473743 instead of 147373

            and for k=9 and q integer the smallest solution is 447914738 instead of 44791473.

 

I have also found the smallest solutions when q is a palindromic number or a palprime

for k=1 to 9.

 

k                q(palprime)                  q (palindromic integer)

1                  2                                        2

2                  353                                    8

3                  383                                    383

4               3365633                               3035303

5               3365633                               3035303

6              3124423244213                     857343758

7              3654733374563                     3334963694333

8              38604007070040683              371427878724173

9                   ?                                     3061540843480451603

 

***

Emmanuel wrote:

To solve Puzzle 555, I also used the Chinese Residue Theorem and Dirichlet's theorem on primes in arithmetic progressions to obtain th following list of triples  m, q, p  such that  q  is the least positive integer which is congruent to  p_i  modulo  p_(i+1)  for  i = 1, 2, ... , m  and  p  is the least prime which satifsfies all these congruences :
 

2, 2, 2

3, 8, 23

4, 68, 173

5, 1118, 2273

6, 2273, 2273

7, 197468, 1473743

8, 1728998, 25978223

9, 1728998, 113275433

10, 447914738, 10152454583

11, 10152454583, 10152454583

12, 1313795640428, 27286379112263

13, 97783391392958, 4509412212537503

14, 5726413266646343, 58057458593326463

15, 38433316595821418, 3420327120832524173

16, 15103232990013860963, 178049025375964084613

17, 943894249589930135768, 23055638276363375485073

18, 52858423703753671390658, 1049809665258712924748453

19, 932521283899305953765183, 110949022999023044736072443

20, 8790842834979573009644273, 7819962464608765026553459733

21, 10051725785115560870423121293, 50781406384364585021044444763

22, 498807892976103850677879002933, 23022321264360814205971470881843

23, 55198768937767543284962316423143, 856392316005595097351834370401513

24, 5396489082723284570397442676278943, 5396489082723284570397442676278943

25, 1051221132521927518479021097136044583, 5662357060412964367985225391799556723

26, 108260131455988534269498270948062701838, 1621865499786221380119909830671360561793

27, 5580525693880676515420986217639985733983, 1300760996255842997841573154707021939129323

28, 1180836878611216856978040546513560647148273, 70472992053676201047927181560695495153798963

29, 79455308465258698998605773914385745923179608, 4974817752777720082118438606675572415235631133

30, 11408722679588383614218790329733132037760567423, 770050034049610970529703741326781031876353055183

31, 801660088690028578317848947618324694369627742173, 801660088690028578317848947618324694369627742173

32, 115214252859681559967509423119860611088777357302478, 9318402636280667023466515871887069086849469287723503

33, 378162492385995430353195321656066567539082841028793, 288569433013225997373064940117337794837073893005070033

34, 828928065239801001015649461609241035342451662062647358, 406422117414506998735139591293431813358679005116680187503

35, 201121861077223602351200312094608042182669144726071309158, 21837765949696773743204898493024303536122635162965607000103

36, 74064148232571549945265549274578740935288070379405865564453, 7734928337954831579127533581060306786858583624699528364689393

37, 2327259498150883323234167911564498754442139704002971306483553, 1700335275196590635673750988133248220933205530802721887583117313

38, 1258145687775121950165803899533851418282485897704097169802743938, 90633505097402372665032069447243933170045938139598125127571810493

39, 41621211227606783563331214146886791564240174006946561408795225608, 3411937183803550528262642969800857293751707131128692325364667445053

40, 47707518537658811172882168901253041036786987139014493794498988043473, 880657037474284908077140645655734322291689535113388804029307407992023

41, 12958425062055363313188888558595712900487776480741816302434029497245998, 832997226455163755715431358923382534295939334961513324728602918936593473

42, 668989466176542077234982864850425170016849023265359023043369141048723978, 95122549590273663274838729224139961779838405804641495493584822133744474053

43, 132903973639912511753880227767855776423767028517191950081801403330822774083, 20750766812157112681745098004481343196396243994509011453937135713736409361883

44, 17142640815416602651996634893556482897901060525460443040762452209415431709018, 10661629777770884120414212592566312200644191606142887057393675173314059647325463

45, 7677194131895519395807983819387034896603175565315571184210615531882850988741413, 321241899325200506461102420254756436974512594254905558926644081858255174050638933

---

These results are obtained in a few seconds.  All primes  p  are proved primes.  Actually, I have the results for all  m <= 50  and it can take a quickly increasing time for greater  m.

***

Justin LeBeau wrote:

Q1.) The first few additions for the PRIME q values are:
k=9, q=10152454583

k=10, q=10152454583

k=11, q=27286379112263

k=12, q=4509412212537503

k=13, q=58057458593326463

k=14, q=3420327120832524173

k=15, q=178049025375964084613

k=16, q=23055638276363375485073

k=17, q=1049809665258712924748453

k=18, q=110949022999023044736072443

k=19, q=7819962464608765026553459733

k=20, q=50781406384364585021044444763

 

Q2.) The first few additions for the INTEGER q values are:

k=11, q=1313795640428

k=12, q=97783391392958

k=13, q=5726413266646343

k=14, q=38433316595821418

k=15, q=15103232990013860963

k=16, q=943894249589930135768

k=17, q=52858423703753671390658

k=18, q=932521283899305953765183

k=19, q=8790842834979573009644273

k=20, q=10051725785115560870423121293

***