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:

16+1=17= 4^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:




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 :

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 :
The primality was proved by PRIMO in 3hours, 9 minutes and 29 seconds


Michael wrote:

I have the following solution for Prime Puzzle 856:


For smaller values I found:

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



Records   |  Conjectures  |  Problems  |  Puzzles