Problems & Puzzles: Puzzles

Puzzle 856. Cascade of primes 4k+1 As you know the primes of the form 4k+1 are always expressed in a unique manner as a sum of two perfect squares A & B. P=4k+1=A^2+B^2 (*) Evidently A & B must be of opposite parity. Consequently A+B is odd and then A+B may be another prime Q type 4m+1 and so on... P=prime 4+1=A^2+B^2 such that A+B could be Q= prime 4m+1=... (**) (**) suggest a cascade of primes P, Q,... such that P>Q>... One outstanding example of a cascade of 4th level,  is given by the following four primes of Fermat type: 65537, 257, 17 and 5, because: P=65537=256^2+1^1 256+1=257=16^2+1^2 16+1=17= 4^2+1^2 4+1=5=2^2+1^2 Nice example, but... 65537 is not the minimal prime P producing a cascade of 4 levels. From now on we will only be interested in minimal P primes 4k+1 that produce a cascade of L levels. I devised a way to produce this kind of minimal primes P, and my largest P prime produces a cascade twelve levels. The prime P of this cascade is... Well, I will better reveal it next week. I'm pretty sure that many of  you will find it by you own. Q. Find the minimal P for a 12 level cascade.

---

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

***

Jan wrote:

The requested number is:

 

24693751610071319593889782433745672384759452670683314449974714857939125820439417579
59355817127682686474772607884237079883953006430643174014844883990708887841350306230
2029457809800189340405350970922847034990163179268667887482506599743716789397515788
1496988668341709130453439501034641953351073784740335440952328617368663504216370610
8104234533181647970359090339030462044331659576508687679568063459907536438815467831
7604413685780202455141489613598149718413132519633911957355081583144228001667061878
7245718843741886316193405625115779126092897353273411873392261203154371577301395620
5030643772670558191861429099180156811309088286219411704138043887157289625560608095
6957036301406477142583345252172948016908188892872791895439870203793358851721525436
9760118987181248168976378676731037421372990813439927616140011232953682926112207742
956827762839515404797033

 

and has 846 digits.

 

I also found a solution for a chain having length 16, the largest number has 13522 digits (probable prime).

 

Instead of giving the whole chain, I’ll describe the method employed.

From p=p[n] to q=p[n+1] we split p as close to the middle as possible: p=(p-h)/2+(p+h)/2  whence q=1/2 (p^2+h^2).

So q increases if h (odd) increases. Once a chain with the required length is found, above relation (applied in the other direction, with h=1) can be used to find upperbounds for every step in the recursion process, pruning our tree as we go and cutting down computing time considerably.

 

My solution starts with p=5, the 15 values for h are: [1,3,9,5,53,5,5,327,711,1241,655,343,55,14727,14421].

Which explains (partly) why the procedure is quite fast for small lengths (<=14) and becomes much slower for larger lengths.

 

***

Emmanuel wrote:

Your  P is :

 

2469375161007...4797033
 

I used PRIMO to prove it's primality (in +/+ 10 minutes)
 

It is possible to find the smallest prime  Q  that is mapped on  P :

 

30489068...860369
 

The primality was proved by PRIMO in 3hours, 9 minutes and 29 seconds

***

Michael wrote:

I have the following solution for Prime Puzzle 856:

2469375161007...4797033 

For smaller values I found:

1 5
2 13
3 89
4 4001
5 8004013
6 32032112053489
7 513028101303637640198536573
8 131598916363607742489274389297905849499116105409292177
9 865913739403791282690094645723964889487804770638938794176678239432036658024197
4817713102774970628076753129

***