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?
Solution
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
555716492779494777393832543125
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.
***
|
