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.

***