[math-fun] sums of three triangular numbers etc
It is known that every number is the sum of three triangular numbers (that was when Gauss said Eureka!), and https://oeis.org/A008443 counts the ways. It is believed that every number is the sum of three palindromes (see A261422 or A261132, which have remarkable graphs). Both triangular numbers and palindromes have about O(sqrt(N)) terms below N. My question is, what is the least dense sequence S that works? One might think that one only needs O(N^(1/3)) terms below N to get S+S+S = Z+ Are there specific examples known of sparser sequences that work, Richard? (I didn't find anything in UPINT) Also, is there a simple proof of Gauss's theorem that doesn't work backwards from the 4-squares theorem? Is there a constructive algorithm that takes a number n and produces three triangular numbers that add to n? Same questions for sums of r squares, for r=2,3,4,... Best regards Neil
On Aug 28, 2015, at 12:18 PM, Neil Sloane <njasloane@gmail.com> wrote:
My question is, what is the least dense sequence S that works? One might think that one only needs O(N^(1/3)) terms below N to get S+S+S = Z+ This seems pretty efficient (in base 3):
1 2 10 20 100 200 1000 1001 1002 2000 2001 2002 10000 10010 10020 20000 20010 20020 100000 100100 100200 200000 200100 200200 1000000 1000001 1000002 1001000 1001001 1001002 1002000 1002001 1002002 2000000 2000001 2000002 2001000 2001001 2001002 2002000 2002001 2002002 etc. -Veit
Quoting Neil Sloane <njasloane@gmail.com>:
It is known that every number is the sum of three triangular numbers (that was when Gauss said Eureka!), and https://oeis.org/A008443 counts the ways.
It is believed that every number is the sum of three palindromes (see A261422 or A261132, which have remarkable graphs).
Both triangular numbers and palindromes have about O(sqrt(N)) terms below N.
My question is, what is the least dense sequence S that works? One might think that one only needs O(N^(1/3)) terms below N to get S+S+S = Z+
Are there specific examples known of sparser sequences that work, Richard? (I didn't find anything in UPINT)
Veit has offered the standard example of an O(N^(1/k)) sequence S, for which S+S+... (k copies of S) = Z+. I don't know if thinner sequences exist -- obviously you still need O(N^(1/k)), but maybe you can get by with a smaller O() constant.
Also, is there a simple proof of Gauss's theorem that doesn't work backwards from the 4-squares theorem?
I've never seen a proof based on the 4-squares theorem. Got a pointer?
Is there a constructive algorithm that takes a number n and produces three triangular numbers that add to n?
The obvious search program does the job, but presumably you want better. My approach is solve the 3-square problem for 8n+3. The three squares are necessarily odd (in fact 8k+1). Subtract 1 from each and divide by 8 to get the three triangles. Example, N=14, 8N+3 = 115 = 81+25+9, and -1 & /8 gives 10+3+1. The same trick splits N into 3 pentagonal numbers, using 24N+3. (Pentagonals = (3K^2+-K)/2 = 0,1,2,5,7,..., the exponents of the reciprocal partition generating function.) A practical way to split N into X2+Y2+Z2 (always possible unless N = 8K+7 or 4^J * (8K+7)), albeit probabilistic: (a) preprocess N, removing as many powers of 4 as possible; if the remainder is 7 (mod 8) report FAIL. (b) set Z = floor(sqrtN) (c) count down through Zs, trying to split N-Z2 into X2+Y2. (d) reinsert any powers of 4 removed in step (a) by doubling X,Y,Z enough. The two-square splitting subroutine (for step c) is to try to factor N-Z2 over the complex integers as (X+iY)(X-iY). Remove factors of 2, and other small primes as convenient. The goal is to stop at a 4K+1 prime P (or 0 or 1). If, after removing the 2s, the result is 3mod4, or if your factoring effort reveals any 4K+3 divisor to an odd power, this step fails; try another Z. Now we have a possibly prime 4K+1 leftover piece; call it P. Starting with A=2 and counting up, compute A^((P-1)/2) modP, which will be either 1 or -1. We want -1. (If we don't get 1 or -1, then P isn't really prime, so try another Z.) Set W = A^((P-1)/4) modP, so that W2 = -1 modP. Then P divides W2+1. Do a complex GCD of P and W+i. (Use the obvious Euclidean Algorithm, computing quotients as the nearest complex integer to the exact quotient, and then computing the matching remainder.) The final result U+iV divides P, and in fact P = U2+V2. (Even if P is a rare composite that makes it through the A^((P-1)/2) = +-1 filter.) Bring in the previously removed factors of 2, 3^2, 5, 7^2, 11^2, 13, ... by multiplying U+iV by 1+i, 3, 2+i, 7, 11, 3+2i, ..., giving X+iY, and splitting N as X2+Y2+Z2.
Same questions for sums of r squares, for r=2,3,4,...
Usually, to split N into two squares, you need to know the factors. (I'm ignoring the obvious simple & slow search.) If there are no odd powers of 4K+3 primes, the above scheme works to split the 4K+1 primes, and you multiply the complex integer pieces. For 4+ squares, the simplest scheme is to (a) remove factors of 4, (b) loop, subtracting the largest possible square, until you reach a non-impossible 3-square problem. ---- For 3 and 4-square proofs of representations, I've seen a sketch that doesn't use much number theory, but I haven't checked it out: Somehow, find a rational solution of N = X2+Y2+Z2 (+W2). This gives a point on the radius sqrtN (hyper)sphere with rational coordinates. Now we apply an iteration to reduce the denominator: Find the closest integer point P (probably not on the sphere) to X,Y,Z(,W), and draw the line from P to X,Y,Z(,W). Calculate the other intersection of this line with the sphere. It will be rational, and is supposed to have a smaller denominator. Stop when D=1. ---- Returning to the sparse sequence theme: Every integer>=0 is the sum of four (or fewer) squares. This is also true if you delete 49 from the list of squares. Q: How much can you thin the squares, while preserving sum-of-four completeness? IIRC, 121 can also be deleted. Rich
Rich, just to answer a question you asked: First, I said:
Also, is there a simple proof of Gauss's theorem that doesn't work backwards from the 4-squares theorem?
>I've never seen a proof based on the 4-squares theorem. Got a pointer? Me: you gave the proof yourself in the same email. We know from proving the 4-squares theorem that numbers 8k+3 only need three squares, The three squares are necessarily odd (in fact 8k+1). Subtract 1 from each and divide by 8 to get the three triangles. QED This proof is in Grosswald's "Represenations of Integers as Sums of Squares" (Springer 1985) Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Fri, Aug 28, 2015 at 7:03 PM, <rcs@xmission.com> wrote:
Quoting Neil Sloane <njasloane@gmail.com>:
It is known that every number is the sum of three triangular
numbers (that was when Gauss said Eureka!), and https://oeis.org/A008443 counts the ways.
It is believed that every number is the sum of three palindromes (see A261422 or A261132, which have remarkable graphs).
Both triangular numbers and palindromes have about O(sqrt(N)) terms below N.
My question is, what is the least dense sequence S that works? One might think that one only needs O(N^(1/3)) terms below N to get S+S+S = Z+
Are there specific examples known of sparser sequences that work, Richard? (I didn't find anything in UPINT)
Veit has offered the standard example of an O(N^(1/k)) sequence S, for which S+S+... (k copies of S) = Z+. I don't know if thinner sequences exist -- obviously you still need O(N^(1/k)), but maybe you can get by with a smaller O() constant.
Also, is there a simple proof of Gauss's theorem that doesn't work backwards from the 4-squares theorem?
I've never seen a proof based on the 4-squares theorem. Got a pointer?
Is there a constructive algorithm that takes a number n and produces three triangular numbers that add to n?
The obvious search program does the job, but presumably you want better.
My approach is solve the 3-square problem for 8n+3. The three squares are necessarily odd (in fact 8k+1). Subtract 1 from each and divide by 8 to get the three triangles.
Example, N=14, 8N+3 = 115 = 81+25+9, and -1 & /8 gives 10+3+1.
The same trick splits N into 3 pentagonal numbers, using 24N+3. (Pentagonals = (3K^2+-K)/2 = 0,1,2,5,7,..., the exponents of the reciprocal partition generating function.)
A practical way to split N into X2+Y2+Z2 (always possible unless N = 8K+7 or 4^J * (8K+7)), albeit probabilistic: (a) preprocess N, removing as many powers of 4 as possible; if the remainder is 7 (mod 8) report FAIL. (b) set Z = floor(sqrtN) (c) count down through Zs, trying to split N-Z2 into X2+Y2. (d) reinsert any powers of 4 removed in step (a) by doubling X,Y,Z enough.
The two-square splitting subroutine (for step c) is to try to factor N-Z2 over the complex integers as (X+iY)(X-iY). Remove factors of 2, and other small primes as convenient. The goal is to stop at a 4K+1 prime P (or 0 or 1). If, after removing the 2s, the result is 3mod4, or if your factoring effort reveals any 4K+3 divisor to an odd power, this step fails; try another Z. Now we have a possibly prime 4K+1 leftover piece; call it P. Starting with A=2 and counting up, compute A^((P-1)/2) modP, which will be either 1 or -1. We want -1. (If we don't get 1 or -1, then P isn't really prime, so try another Z.) Set W = A^((P-1)/4) modP, so that W2 = -1 modP. Then P divides W2+1. Do a complex GCD of P and W+i. (Use the obvious Euclidean Algorithm, computing quotients as the nearest complex integer to the exact quotient, and then computing the matching remainder.) The final result U+iV divides P, and in fact P = U2+V2. (Even if P is a rare composite that makes it through the A^((P-1)/2) = +-1 filter.) Bring in the previously removed factors of 2, 3^2, 5, 7^2, 11^2, 13, ... by multiplying U+iV by 1+i, 3, 2+i, 7, 11, 3+2i, ..., giving X+iY, and splitting N as X2+Y2+Z2.
Same questions for sums of r squares, for r=2,3,4,...
Usually, to split N into two squares, you need to know the factors. (I'm ignoring the obvious simple & slow search.) If there are no odd powers of 4K+3 primes, the above scheme works to split the 4K+1 primes, and you multiply the complex integer pieces.
For 4+ squares, the simplest scheme is to (a) remove factors of 4, (b) loop, subtracting the largest possible square, until you reach a non-impossible 3-square problem.
----
For 3 and 4-square proofs of representations, I've seen a sketch that doesn't use much number theory, but I haven't checked it out: Somehow, find a rational solution of N = X2+Y2+Z2 (+W2). This gives a point on the radius sqrtN (hyper)sphere with rational coordinates. Now we apply an iteration to reduce the denominator: Find the closest integer point P (probably not on the sphere) to X,Y,Z(,W), and draw the line from P to X,Y,Z(,W). Calculate the other intersection of this line with the sphere. It will be rational, and is supposed to have a smaller denominator. Stop when D=1.
----
Returning to the sparse sequence theme: Every integer>=0 is the sum of four (or fewer) squares. This is also true if you delete 49 from the list of squares. Q: How much can you thin the squares, while preserving sum-of-four completeness? IIRC, 121 can also be deleted.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Neil Sloane -
rcs＠xmission.com -
Veit Elser