Problems & Puzzles: Puzzles

Puzzle 62.- The qs-sequence, (by T.W.A. Baumann)

Our new friend T.W.A. Baumann, sent (24/06/99) the following puzzle:

  • "Let's define qs(n) as the least natural number you can split up into two squares in n (and only n) different ways.[The first two members of this sequence are:]

    qs(1) = 2 = 1^2+1^2
    qs(2) = 50 = 1^2+7^2 = 5^2+5^2

  • 1.- Can you find qs(3),qs(4),...,qs(20)?"

    At the very beginning it's is not evident the relationship of this sequence with the prime numbers. Soon you'll discover the hidden relation… So, my additional question is:

    2.-Can you explain the sequence thus obtained?


    Question 1:
    Before 5 hours this puzzle was posted in the Web (Saturday 26/06/99) Jud McCranie sent the asked sequence sq(n) for n = 3 to 20 except n = 17 and n = 19. At that moment I had the same results and qs(17) also, but not the qs(19). I asked to Jud to verify my qs(17). He confirmed it until Sunday morning. Later, the same day (19:38 hrs) he got the elusive qs(19).

    This is the complete sequence:
    n, qs(n)
    1, 2
    2, 50
    3, 325
    4, 1105
    5, 8125
    6, 5525
    7, 105625
    8, 27625
    9, 71825
    10, 138125
    11, 5281250
    12, 160225
    13, 1221025
    14, 2442050
    15, 1795625
    16, 801125
    17, 446265625
    18, 2082925
    19, 41259765625
    20, 4005625

    The most evident fact of the qs(n) sequence is that all qs(n) are numbers whose prime factors are or 2 or 4k+1 primes. But this is not precisely an answer to question 2. The latest Sunday e-mail from Jud McCranie (21:00 hrs) says that he can also explain the question 2.

    Question 2:

    Jud McCranie discovered the Sunday 27/06/99 that basically this problem was posed time ago by Frank Rubin and solved by Joseph Culbertson. This is the story according to McCranie:

    "...I found a reference to the problem in the Journal of Recreational Mathematics (vol 11, pg 137).  The problem was posed by Frank Rubin and the published solution was by Joseph Culbertson, who adapted his solution from "Recreations in the Theory of Numbers", by Albert Beiler, pg 140-141.  I believe it is also discussed in chapter 20 of "An Introduction to the Theory of Numbers", by G. H. Hardy and E. M. Wright.  And it is also sequence A016032 in N. J. A. Sloane's integer sequences.  So here's a recap of the solution in JRM.

    A number which is the sum of two squares in n ways is of the form B(n) = 2^x *p1^b1 * p2^b2 * ... * pm^bm * q1^a1 * q2^a2 *... , where each p is a prime of the form 4i+1, each q is a prime of the form 4i+3, and each 'a' is even.  n is given by n = (b1+1)(b2+1)...(bm+1)/2, or that value plus 1 if B(n) is twice a square.  Since we are looking for the smallest solutions, consider a1 ... to...all be 0.  Also, x will be 0 unless all of the b's are even, in which case x can be 0 or 1.  Furthermore, the exponents of the q's will be in non-increasing order.  To find B(n) given n, consider the ways to factor 2n-1, 2n, and 2n+1 into factors that aren't necessarily prime.  These factors in decreasing order will be the exponents of the primes 5, 13, 17, 29, ... and the product will be the possible values of B(n), or B(n)/2 in the case of 2n-1. 

    I'll illustrate with the calculation of the elusive gs(19).  n=19, so consider
    factorizations of n2-1, 2n, and 2n+1 (37, 38, and 39):

    37: 37
    38: 38; 2*19
    39: 39; 3*13

    First 37-1 = 36, so 5^36 = B(19)/2, so 2*5^36 (2.91E25) is expressible as the sum of squares in exactly 19 ways.  However, this number is large and we are looking for the smallest solution.  For 38 and 39, we get the following numbers: 5^(38-1)=5^37; 5^(19-1)*13^(2-1)=5^18*13; 5^(39-1)=5^38; and 5^(13-1)*13^(3-1)=5^12*13^2.  Each of these numbers can be expressed as the sum of squares in exactly 19 ways.  The smallest of these is 5^12*13^2=41,259,765,625=gs(19).  A check confirms that there are 19 ways to form this number as the sum of 2 squares. This also answers part 2 of the problem...

    By his side, T.W.A. Baumann sent to me his empirical solution to this problem the Monday 28/06/99. This is his communication:

    "There are 3 kinds of primes
       1) 2
       2) (4k+1)-primes 5,13,17,29,...
       3) (4k-1)-primes 3,7,11,19,...
    [For the purpose of calculating n given QS(n)] we need [only] the first and the second kind. Definition: p1,p2,p3,... are different (4k+1)-primes in any order; e1,e2,e3,... are the exponents of p1,p2,p3,...
    f is the exponent of 2

    If     QS(n) = p1^e1*p2^e2*p3^e3*...*2^f
    then       n = int(((e1+1)*(e2+1)*(e3+1)*...+(f mod 2))/2)

    It's now easy to go from n to QS(n) but it's also necessary to minimize QS(n) - by choosing the right p1,p2,...,e1,e2, maybe 2 - in order to get qs(n).... Remark: I didn't prove this algorithm (perhaps you do) but I didn't get any deviations in my tests.

    As you can observe Baumann with his formula for calculating n given QS(n), arrived basically to the same formula established by Culbertson. But Culbertson provides a more specific procedure to calculate B(n) given n.

    Do you all think that the problem is over now...?
    Of course that not.... seems to say some of our friends:

    a) Jean Brette comments the following:
    The Culbertson conditions come from a theorem of Jacobi on   r(n) : the
    whole number of ways to split any integer in sum of two squares, according to order and signs :
    r(1) = 4  because  1 = 0^2 +1^2 = 1^2+0^2 = 0^2+(-1)^2 = (-1)^2+0^2. 
    r(15) = 0 and  r(25) =  12.

    This theorem says :    for  n 1,  r(n) = 4 ( d1(n) - d3(n) )
    where   d1(n) and  d3(n) are the numbers of divisors of  n  of the forms
    4k+1  and 4k+3 respectively. It explains(among other things)  why  the  a's must be even in the Culbertson conditions.

    b) T.W.A. Baumann has sent qs(1000) = 5^4*13^4*17^4*29*37*41*53 =
    = 3476230457396718125
    . Of course that I can not avoid the temptation to ask two more questions:

    3.- Can you verify if 3476230457396718125 is, or not, the least number with 1000 expressions of sum of squares - according to our new knowledge?
    4.- Can you calculate qs(1,000,000)?


    T. D. Noe wrote (22/11/2002):

    Question 3. Verify that 3476230457396718125 is the least number that can be represented as the sum of two squares in 1000 ways.

    I agree with T.W.A. Baumann. As mentioned above, we need to look at the factors of 2n-1, 2n, and 2n+1.

    Because 2n-1 = 1999 is prime, the minimal value of B(1999) is 5^(1999-1), which is greater than 10^1396.

    Because 2n+1 = 2001 = 29*23*3, which is the product of primes to the first power, the minimal value of B(2001) is 5^(29-1)*13^(23-1)*17^(3-1) = 34578943093454581699910746552050113677978515625.

    Because 2n = 2000 = 5*5*5*2*2*2*2, we presume that the minimal value of

    B(2000) is 5^4*13^4*17^4*29*37*41*53 = 3476230457396718125. Is it actually the minimal value? Yes, because the two other factorizations of 2000 that have fewer factors and non-increasing factors, 10*5*2*2*2 and 5*5*4*2*2, lead to larger values of B(2000). See note below.

    Answer: qs(1000) = 3476230457396718125

    Question 4. What is qs(1,000,000)? As above, we need to examine the factors of 2n-1, 2n, 2n+1. Note that 1,999,999 = 1657*71*17 and 2,000,001 = 666667*3. Both factorizations contain only primes raised to the first power, which means the minimal B(1,999,999) = 5^1656*13^70*17^16 and the minimal B(2,000,001) = 5^666666*13^2. These numbers have, respectively, 1256 and 465982 digits!

    Now consider 2,000,000 = 5*5*5*5*5*5*2*2*2*2*2*2*2. Because it has 13 prime factors, it will require at most the first 13 primes of the form 4k+1 to express the minimal B(2,000,000): 5^4*13^4*17^4*29^4*37^4*41^4*53*61*73*89*97*101*109 = 125262652593971298607146638685883361650570625, a 45-digit number. This is minimal because the two factorizations that have fewer factors and non-increasing factors (10*5*5*5*5*5*2*2*2*2*2*2 and

    5*5*5*5*5*5*4*2*2*2*2*2) lead to larger B(2,000,000).

    Answer: qs(1,000,000) = 125262652593971298607146638685883361650570625.


    In case you are interested, the analysis for 10^9 and 10^12 are similar to the 10^6 case, leading to qs(10^9) = 18673120847159681173805142515595425252847604936522555123589873094249270625

    and qs(10^12) = 1555361542078168420445947502160147769731361582036680404069563754723643779930


    Note: It is tempting to believe that the longest factorization always leads to the minimal B(m). This is not true. The easiest counter-example is 16, whose factorization 2*2*2*2 leads to a B(16) of 5*13*17*29 = 32045. However, because 5^2 < 29, the factorization 4*2*2 leads to the minimal

    B(16) of 5^3*13*17 = 27625. I have written a program that determines the minimal B(m) by examining a small number of factorizations of m. So what is the smallest r such that 10^r has a minimal B(10^r) that uses a factorization different from 5*...*5*2*...*2? Answer: r=110 because the 220th prime of the form 4k+1 is 3137, which is the first one greater than 5^5.


    Records   |  Conjectures  |  Problems  |  Puzzles