Problems & Puzzles: Puzzles

Puzzle 303. I'm such a square...

Rickey Bowers, Jr. has sent another interesting puzzle:

What Prime is the Next Minimal Sum of Squares?

All integers can be de-composed into a list of squares which sum to equal the initial integer. The minimal list of squares is derived sequentially by subtracting the largest square repeatedly. An example best illustrates (followed by Mathematica code to generate the Minimal Sum of Squares):

1973 = {44, 6, 1}
1936 = 44*44
36 = 6*6
1 = 1*1

Given this definition we now restrict the problem to the longest sequences produced by the smallest numbers, and we start to notice something very interesting…

   2 = {1,1}
  3 = {1,1,1}
  7 = {2,1,1,1}
 23 = {4,2,1,1,1}
167 = {12,4,2,1,1,1}

…which are all prime.

 Q1. Are there any more primes in this sequence?


Contributions came from Loris Cappelletti & Johann Wiesenbauer:

Cappelletti wrote:

If we consider the succession N0=1, N1=2,  N2=3,  N3=7, N4=23, N5=167, it’s not difficult to show that the smallest number producing a sequence of length k+2 is:

Nk+1 = ((Nk + 1)/2)2 + Nk , for k=>2

With this formula, I found the following terms of the succession up to N15, and none of them is a prime.

Johann Wiesenbauer wrote:

As for puzzle, in the first place, the term "minimal" sum of squares is very misleading. After all, what is minimal about it? A more appropriate notation might be "greedy" sum of squares as you use a greedy algorithm for the selection of squares.

Surprisingly enough, if a(n), n=1,2,3,... denotes the sequence at issue, where n is the number of squares in the representations, it obeys the simple recursion formula

a(n) = n for n<=3, a(n) = ((a(n-1)+3)/2)^2-2

This is mainly due to the fact that the recursion can also be written as

a(n) = ((a(n-1)+1)/2)^2+a(n-1)

where ((a(n-1)+1)/2)^2 is the biggest square contained in a(n) and after subtracting it from a(n) the rest becomes a(n-1). For example the first ten values of this sequence computed by Derive are

[1, 2, 3, 7, 23, 167, 7223, 13053767, 42600227803223, 453694852221687377444001767, ...] where only the blue & bolded numbers are primes.

I could prove that there are no other primes than those already found by the poster for n<=23. Just for the record, after that the first undecided cases are n=24,33,36,41,... (Derive can't cope with the huge resulting numbers as to a probabilistic primality test, but maybe someone of the readers can!)

Concluding I would be say that I haven't found further primes and I would rather guess that there aren't any. The situation reminds a little bit of the Fermat numbers where also the first numbers are primes and the number of digits about doubles when increasing the index by 1. At any rate, I look forward to other "solutions" of this nice problem.


See A006892 (CR)


Jens Kruse Andersen wrote:

The term with 24 squares has 426882 digits. PrimeForm/GW says:
74149346.....62941767 is composite: [372CC1BDC58E89C1] (128660.7472s+6.2095s)



Records   |  Conjectures  |  Problems  |  Puzzles