Problems & Puzzles: Puzzles

 Puzzle 857. A second cascade of primes 4k+1. Emmanuel Vantieghem suggested the following follow-up to Puzzle 856: We define the function  f  by :   f ( k ) = 0  when  k  is not a prime of the form  4m+1            = 2ab + 1 when k is a prime of the form  4m+1, a & b are the unique numbers such that  p = a^2 + b^2 (a < b).   Our aim is to make chains      p, f(p), f(f(p)), ...               of (different !) primes, as long as possible for a minimal starting prime p.   Since it easy to show that  p >= f(p), such a sequence either ends in zero or it ends on a prime  q  such that  f(q) = q  (i.e. : q = 5, 13, ... , which are the primes of the form  n^2 + (n+1)^2 ).    Some examples :  759973 -> 740653 -> 114973 -> 18253 -> 18229 -> 541 -> 421 ( ->  421)  531253 -> 519373 -> 228853 -> 161773 -> 10453 -> 1429 -> 1381 -> 1021 -> 661 ( -> 301 -> 0) Q. Send your largest cascade of primes 4k+1 according to these new definitions by Emmanuel.

Contributions came from Jan van Delden, Emmanuel Vantieghem and Michael Hürter

***

Jan wrote:

A chain of length 17:

638013214239030725545259857 (27 digits), 404000112922567243633, 11703061692392806993, 82103371033, 3994859593, 161392369, 130778281, 57487561, 27686881, 24861121, 6959761, 3082801, 2444401, 2268841, 2263801, 2142001, 2097481

I first searched for the longest chain with minimal starting prime p, and came up with the subchain, length 12, starting at 161392369.

In the second step I found the minimal starting p ending on this prime after 5 more steps.  So the first prime of this chain might not be minimal for a chain having length 17.

The primes involved can become rather large. For instance the following prime also defines a chain of length 17 ending on the same prime:

6009205372789295248420935668048029774131035855872889517556500612894045696
6398306329151535377496841528450360114622163848257

***

Emmanuel wrote:

Here is my cascade of  22  primes :

31545718261764157134692851511711846392057988377 (47 digits)
-> 252865785622610099268267555975604301353
-> 1840285411288780836029060076103954129
-> 19404394395344081706721
-> 8518781585948840190241
-> 51538468729261835641 (20 digits)
-> 2407193796822916561
-> 203420267176274881
-> 143424792481
-> 9284997481
-> 9188977081
-> 2644328881
-> 57487561
-> 27686881
-> 24861121
-> 6959761
-> 3082801
-> 2444401
-> 2268841
-> 2263801
-> 2142001
-> 2097481
( -> 1321321 -> 0 ->0 -> ... )

***

Michael wrote:

I have the following results for
n = 2 to n = 23 primes of type 4k+1 ( a cascade of only 22 primes)
for n = 2 to n = 14 I checked that the prime is minimal.

N             Prime
--------------------
2 53
3 173
4 1429
5 1597
6 8893
7 29917
8 118093
9 531253
10 24199477
11 115365829
12 161392369
13 946232593
14 1954864657
15 2221992775657
16 1501256901012601
17 59598067310599717
18 10099124134703797393 (20 digits)
19 669202931224933581595837
20 2231409524747412148590396111232141
21 2231932256746846907055815397628381
22 836109498196456845875490408060913088137036406201447231914573 (60 digits)
23 4065497829971192852885728611545617740636798200430307756885727107124653

***

Emmanuel added on Dec 6, 2016:

At the time I submitted my cascade, I was almost convinced that the first prime was minimal.
But when I saw the results of Jan and Michael, reasonable doubt came up.
So, I remade my computations in such a way that now I'm sure that my solution was not minimal.
As a matter of fact, I found a 23 primes cascade :

149172716659703659213297422640329712953217
-> 12099688650324688968668103045607614193
-> 11487118307550560664784913589052510969
-> 42876888150434052973459919973016921
-> 33705905571268669976792858692557481
-> 7031965605758664339776091952244521
-> 248295920404475618157548087881
-> 1623255678955050222529829281
-> 3853435225785707882041
-> 10815509128000081
-> 324264641521
-> 314582278321
-> 25902808801
-> 806229241
-> 549556801
-> 16454881
-> 15569401
-> 12743641
-> 6978841
-> 2317561
-> 1921921
-> 903841
-> 196561 ( ->129481 -> 0 ).

Moreover, I'm now almost sure that the first prime in this cascade is not minimal.
I think that the minimality condition is practically impossible to check for primes of that size. The only way to show that some starting prime p is minimal might be this : check the cascade length for all primes < p. This can be done only for 'small'  p ...

Nevertheless, it can be a challenge to find a smaller prime that starts a cascade of length 23.

***

 Records   |  Conjectures  |  Problems  |  Puzzles