Problems & Puzzles: Puzzles

Puzzle 523. Increasing residues JM Bergot poses the following nice puzzle: P(401)=2749=343mod(401) P(402=2753=341mod(402) P(403)=2767=349mod(403) P(404)=2777=353mod(404) P(405)=2789=359mod(405) P(406)=2791=355mod(406) One sees four increasing residues 341, 349, 353, and 359. Can you find a starting P(n) which gives more than four increasing residues?

---

Contributions came from J-C Colin, Farideh Firoozbakht, Antoine Verroken, Torbjörn Alm, Flavio Torasso, Luis Rodríguez, Carlos Rivera, Giovanni Resta (the Champion of results for this puzzle) & Jan van Delden

***

J-C Colin

...

k=18         

prim ( 10073436 ) = 180820951 = 9572539 mod 10073436
prim ( 10073437 ) = 180820987 = 9572558 mod 10073437
prim ( 10073438 ) = 180821023 = 9572577 mod 10073438
prim ( 10073439 ) = 180821041 = 9572578 mod 10073439
prim ( 10073440 ) = 180821059 = 9572579 mod 10073440
prim ( 10073441 ) = 180821093 = 9572596 mod 10073441
prim ( 10073442 ) = 180821117 = 9572603 mod 10073442
prim ( 10073443 ) = 180821143 = 9572612 mod 10073443
prim ( 10073444 ) = 180821161 = 9572613 mod 10073444
prim ( 10073445 ) = 180821189 = 9572624 mod 10073445
prim ( 10073446 ) = 180821237 = 9572655 mod 10073446
prim ( 10073447 ) = 180821261 = 9572662 mod 10073447
prim ( 10073448 ) = 180821287 = 9572671 mod 10073448
prim ( 10073449 ) = 180821317 = 9572684 mod 10073449
prim ( 10073450 ) = 180821339 = 9572689 mod 10073450
prim ( 10073451 ) = 180821387 = 9572720 mod 10073451
prim ( 10073452 ) = 180821429 = 9572745 mod 10073452
prim ( 10073453 ) = 180821447 = 9572746 mod 10073453

...

k=29

prim( 64460853 ) = 1283889977 = 59133770 mod 64460853

prim( 64460854 ) = 1283889989 = 59133763 mod 64460854

prim( 64460855 ) = 1283889991 = 59133746 mod 64460855

prim( 64460856 ) = 1283890007 = 59133743 mod 64460856

prim( 64460857 ) = 1283890019 = 59133736 mod 64460857

prim( 64460858 ) = 1283890037 = 59133735 mod 64460858

prim( 64460859 ) = 1283890043 = 59133722 mod 64460859

prim( 64460860 ) = 1283890051 = 59133711 mod 64460860

prim( 64460861 ) = 1283890063 = 59133704 mod 64460861

prim( 64460862 ) = 1283890081 = 59133703 mod 64460862

prim( 64460863 ) = 1283890093 = 59133696 mod 64460863

prim( 64460864 ) = 1283890109 = 59133693 mod 64460864

prim( 64460865 ) = 1283890123 = 59133688 mod 64460865

prim( 64460866 ) = 1283890129 = 59133675 mod 64460866

prim( 64460867 ) = 1283890147 = 59133674 mod 64460867

prim( 64460868 ) = 1283890151 = 59133659 mod 64460868

prim( 64460869 ) = 1283890169 = 59133658 mod 64460869

prim( 64460870 ) = 1283890171 = 59133641 mod 64460870

prim( 64460871 ) = 1283890183 = 59133634 mod 64460871

prim( 64460872 ) = 1283890187 = 59133619 mod 64460872

prim( 64460873 ) = 1283890189 = 59133602 mod 64460873

prim( 64460874 ) = 1283890193 = 59133587 mod 64460874

prim( 64460875 ) = 1283890207 = 59133582 mod 64460875

prim( 64460876 ) = 1283890213 = 59133569 mod 64460876

prim( 64460877 ) = 1283890217 = 59133554 mod 64460877

prim( 64460878 ) = 1283890219 = 59133537 mod 64460878

prim( 64460879 ) = 1283890229 = 59133528 mod 64460879

prim( 64460880 ) = 1283890243 = 59133523 mod 64460880

prim( 64460881 ) = 1283890253 = 59133514 mod 64460881

 

***

Farideh wrote:

For n = 10073436 we have a starting P(n) which gives 18 increasing
residues as follows.

p(n) = 9572539 (mod n)
p(n+1) = 9572558 (mod n+1)
p(n+2) = 9572577 (mod n+2)
p(n+3) = 9572578 (mod n+3)
p(n+4) = 9572579 (mod n+4)
p(n+5) = 9572596 (mod n+5)
p(n+6) = 9572603 (mod n+6)
p(n+7) = 9572612 (mod n+7)
p(n+8) = 9572613 (mod n+8)
p(n+9) = 9572624 (mod n+9)
p(n+10) = 9572655 (mod n+10)
p(n+11) = 9572662 (mod n+11)
p(n+12) = 9572671 (mod n+12)
p(n+13) = 9572684 (mod n+13)
p(n+14) = 9572689 (mod n+14)
p(n+15) = 9572720 (mod n+15)
p(n+16) = 9572745 (mod n+16)
p(n+17) = 9572746 (mod n+17)


There exist many n's such that for each of them we have 4 corresponding
increasing consecutive residues.

Example :

P(1) = 0 (mod 1)
P(2) = 1 (mod 2)
P(3) = 2 (mod 3)
P(4) = 3 (mod 4)

P(22720) = 8607 (mod 22720)
P(22721) = 8608 (mod 22721)
P(22722) = 8609 (mod 22722)
P(22723) = 8610 (mod 22723)

P(24980) = 11997 (mod 24980)
P(24981) = 11998 (mod 24981)
P(24982) = 11999 (mod 24982)
P(24983) = 12000 (mod 24983)

...

There exist 972 such numbers n up to 10^8 which they are in the three sets :

{1},{22720,24980,27476,28622,29330,30637,36924,39527,40064}
& {4139313,4153079,4167888,...,10532481,10537764,10551761}.

I wanted to find a starting P(n) which gives 5 increasing consecutive residues. But I couldn't find it !

***

Antoine wrote:

8 increasing residues : P(121) = 461 = 98 mod (121)
463 = 97 mod (122)
467 = 98 mod (123)
479 = 107 mod (124)
487 = 112 mod (125)
491 = 113 mod (126)
499 = 118 mod (127)
503 = 119 mod (128)
509 = 122 mod (129)
521 = 1 mod (130)
 

***

Torbjörn wrote:

Size: 14
P(69597) = 876853 = 41689 mod(69597)
P(69598) = 876871 = 41695 mod(69598)
P(69599) = 876893 = 41705 mod(69599)
P(69600) = 876913 = 41713 mod(69600)
P(69601) = 876929 = 41717 mod(69601)
P(69602) = 876947 = 41723 mod(69602)
P(69603) = 876971 = 41735 mod(69603)
P(69604) = 877003 = 41755 mod(69604)
P(69605) = 877027 = 41767 mod(69605)
P(69606) = 877043 = 41771 mod(69606)
P(69607) = 877057 = 41773 mod(69607)
P(69608) = 877073 = 41777 mod(69608)
P(69609) = 877091 = 41783 mod(69609)
P(69610) = 877109 = 41789 mod(69610)

***

Flavio wrote:

P(21) ==> IR=5,6
P(123) ==> IR=7,8,9
P(1598) ==> IR=10
P(22640) ==> IR=11
P(34367) ==> IR=12,13

***

Luis Rodriguez wrote:

Any arithmetic progression of consecutive primes will do.
Example: 121174811 + 30k ; k = 0,1,2,3,4,5

***

Carlos Rivera found for decreasing residues:

n=33

index         Prime          residue
202668636 4281396241 25354885
202668637 4281396253 25354876
202668638 4281396271 25354873
202668639 4281396277 25354858
202668640 4281396283 25354843
202668641 4281396299 25354838
202668642 4281396307 25354825
202668643 4281396311 25354808
202668644 4281396323 25354799
202668645 4281396337 25354792
202668646 4281396349 25354783
202668647 4281396359 25354772
202668648 4281396377 25354769
202668649 4281396397 25354768
202668650 4281396403 25354753
202668651 4281396409 25354738
202668652 4281396421 25354729
202668653 4281396439 25354726
202668654 4281396443 25354709
202668655 4281396461 25354706
202668656 4281396463 25354687
202668657 4281396473 25354676
202668658 4281396487 25354669
202668659 4281396499 25354660
202668660 4281396517 25354657
202668661 4281396533 25354652
202668662 4281396541 25354639
202668663 4281396557 25354634
202668664 4281396563 25354619
202668665 4281396583 25354618
202668666 4281396589 25354603
202668667 4281396593 25354586
202668668 4281396601 25354573

New question: ¿Why larger decreasing residues sequences are easier to come?

***

Giovanni wrote:

The largest sequence of strictly increasing residues
I found is formed by 30 numbers and starts at
P(572,323,175,837)=16,836,571,309,241

the 30 residues range from 239,199,209,968 to 239,199,210,675 for
P(572,323,175,866)=16,836,571,310,789.

Curiously, it is easier to find long
sequences of with strictly decreasing residues.

I searched only a little and I found one sequence of 47
numbers starting from P(129,546,862,714)=3,611,281,825,363
and ending at P(129,546,862,760)=3,611,281,825,927 with
residues going from 113,516,532,085 down to 113,516,531,407.

***

Jan wrote:

P(10073436)=180820951 is the first prime in the first sequence giving 18 increasing residues.

***

Later (Feb 12, 2010), Giovanni Resta found solutions to the asked question by Faride above.

I searched a bit longer, and I find the first increasing consecutive sequences of length 5 and 6. They are (n,p, p mod n)

382465944889 11091512796457 394676
382465944890 11091512796487 394677
382465944891 11091512796517 394678
382465944892 11091512796547 394679
382465944893 11091512796577 394680

and

382480573392 11091952105943 15477575
382480573393 11091952105973 15477576
382480573394 11091952106003 15477577
382480573395 11091952106033 15477578
382480573396 11091952106063 15477579
382480573397 11091952106093 15477580

Please give all of us a big clap to Giovanni for his findings!!!

***

Due that there are also sets like the following: four decreasing consecutive residues

index    Prime     residue
251647 3522877 251466
251648 3522889 251465
251649 3522901 251464
251650 3522913 251463

I have asked to Giovanni to found examples of 5 or more, as he has done with the Farideh question. It's supposed they should be easier to produce?. Time will say...

***

On May 1 , 2010 Giovanni wrote:

Right now my program printed out the values
for Farideh's request about problem 523.

N P P mod N
2636913033479 81744304069397 31548
2636913033480 81744304069427 31547
2636913033481 81744304069457 31546
2636913033482 81744304069487 31545
2636913033483 81744304069517 31544

and

N P P mod N
2636916241319 81744406799491 3318602
2636916241320 81744406799521 3318601
2636916241321 81744406799551 3318600
2636916241322 81744406799581 3318599
2636916241323 81744406799611 3318598
2636916241324 81744406799641 3318597

Clearly, it is much more probable to find such sequences
where the residues are small (if the residues are
large even finding two consecutive residues is very
improbable).
To have small residues one has to look where
P is "almost" a multiple of N.
For the first case above, indeed, we have
81744304069397 / 2636913033479 = 31.00000001196...

So, to have a little chance to find a longer
sequence, I think that my program should
run up to the point where P/N is about 32.
So, if now I'm about at N = 2.6*10^12,
I need probably to reach N=6.9*10^12 to have
a ratio of 32. I'm not sure I can arrive there...

***