Problems & Puzzles:
Puzzle 856. Cascade of
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.
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:
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
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
My solution starts with p=5, the 15 values for h are:
Which explains (partly) why the procedure is quite fast for small
lengths (<=14) and becomes much slower for larger lengths.
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
I have the following solution for Prime Puzzle 856:
For smaller values I found: