This site is supported by donations to The OEIS Foundation.
M. F. Hasler/Notes on Sums of powers
This page collects some notes on (at least) two quite distinct problems that fit under this title, "sums of powers":
- #Numbers that are the sum of k nonzero m-th powers
- Numbers and in particular k-th powers that are the sum of distinct (smaller) positive k-th powers: #Sums of distinct k-th powers
- #Partial sums of powers of k
Contents
Numbers that are the sum of k nonzero m-th powers
- see also: Index to Sums of like powers (more complete index than the table below, collaborative work with G. Fischer, ...)
Sequences S(k,m) of numbers that are the sum of k positive m-th powers:
S(2,2) = A000404, A000408 = S(3, 2), S(4, 2) = A000414 = ∁ A000534 = {0, 1, 3, 5, 9, 11, 17, 29, 41} ∪ {2, 6, 14} · {4^m, m >= 0}, S(5, 2) = A047700 = ∁ A047701 = {1, 2, 3, 4, 6, 7, 9, 10, 12, 15, 18, 33}, ∁ S(6,2) = A180968 = {1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 16, 19} : see https://www.jstor.org/stable/2301257 A003325 = S(2, 3), A003072 = S(3, 3), A003327 .. A003335 = S(4 .. 12, 3), A003336 .. A003346 = S(2 .. 12, 4), A003347 .. A003357 = S(2 .. 12, 5), A003358 .. A003368 = S(2 .. 12, 6), A003369 .. A003379 = S(2 .. 12, 7), A003380 .. A003390 = S(2 .. 12, 8), A003391 .. A004801 = S(2 .. 12, 9), A004802 .. A004812 = S(2 .. 12, 10), A004813 .. A004823 = S(2 .. 12, 11).
Finite complements
It appears that for any m and k large enough, eventually all numbers are in the set S(k,m), i.e., the set of (positive) numbers which are NOT the sum of k positive m-th powers is finite.
T.2: For m = 2 (squares) it is known since Dubouis that
- for k >= 6 terms, the only integers not sum of k squares are 1, 2, ..., k-1 and numbers in k + B, B = {1, 2, 4, 5, 7, 10, 13};
- for k = 5 terms, the only numbers not sum of k positive squares are 1, 2, 3, 4 and numbers in 5 + B;
- and Descartes' conjecture: The only n not sum of 4 positive squares are {0, 1, 3, 5, 9, 11, 17, 29, 41} ∪ {2, 6, 14} · {4^m, m >= 0}.
Proof: see Gordon Pall, On Sums of Squares, DOI 10.2307/2301257 = https://www.jstor.org/stable/2301257
For n=3, see for example our contributions:
- S(7, 3): A003330(n) = n + 208 for all n > 2200: 2408 is the largest among only 208 positive integers not in this sequence, listed in A332107.
- S(8, 3): A003331(n) = n + 142 for all n > 478: 620 is the largest among only 142 positive integers not in this sequence, listed in A332108.
- S(9, 3): A003332(n) = n + 114 for all n > 357: 422 and 471 are the two largest of only 114 positive integers not in this sequence, listed in A332109.
- S(10,3): A003333(n) = n + 99 for all n > 275: 374 is the largest of only 99 positive integers (listed in A332110) not equal to the sum of 10 positive cubes.
- S(11,3): A003334(n) = n + 92 for all n > 229: 321 is the largest of only 92 positive integers (listed in A332111) not equal to the sum of 11 positive cubes.
Program
There are different ways to compute these sequences. Depending on k & m, one could prefer the one or the other.
- The first method consists of getting the list of these numbers as the powers with nonzero coefficients in (1 + x^1^m + x^2^m + x^3^m + ...)^k
- One can also make this list "by hand" using the same idea (as sum of k terms which are m-th powers).
- A different approach is to check recursively whether n-x^m can be written as sum of k-1 positive m-th powers not larger than x, with 1 <= x < sqrtn(n,m), as long as k > 1; for k = 1 just check whether m is an m-th power. Both lower and upper bounds can be optimized to make this as efficient as possible. For very large N this is faster than to produce all numbers up to N which may even be impossible.
PARI/GP code:
(A003330_upto(N, k=7, m=3)=[i|i<-[1..#N=sum(n=1, sqrtnint(N, m), 'x^n^m, O('x^N))^k], polcoef(N, i)])(160)
(The same function can be used to produce other sequences, e.g., A003330_upto(1000, 10) = A003333(1..900), etc.)
Proofs
To do: add the proof or references for the statement that for all m exists k* s.t. &compl; S(k,m) is finite for all k > k*.
Additional sequences not yet in OEIS
- list k* = k*(m) : the least k for which S(k,m) is finite
- for all k, list the largest number in the complement (or 0 if the complement is infinite). Could be a square array.
Sums of distinct k-th powers
Contributions to sequences
- A001661(n): largest number not equal to the sum of distinct (smaller) positive n-th powers
- A030052(n): Least number whose n-th power is the sum of smaller n-th powers (now known up to n=17, formerly up to n=15); related:
- A332065(n,.): { s | E*(s;n) = 0 }, where E*(s;n) := min_{Ac{1..s-1}} | s^n - Sum_A x^n | : A030052 is the 1st column
- A332097(n) = max_{s>0} E*(s;n) = max_{s>0} Awww(n,.)
- A332096(n,s) = E*(s;n), 1 <= s <= A332098(n)
- A332098(n) = max { s>0 | E*(s;n) > 0 } ; A332066(n) = number of these s = number of nonzero terms in A332096(n,.)
see also: AZsPCs "Sums of powers": http://azspcs.com/Contest/SumsOfPowers
Partial sums of powers of k
- (Contributions from 2012. - See also: [?...?][To do: add link to another wiki page about this])
Sequences of the form (k^n-1)/(k-1): A000225 (k=2: Mersenne), A003462, A002450, A003463, A003464, A023000, A023001, A002452,
- A002275 (k=10: repunits), A016123, A016125, A091030, A135519, A135518, A131865, A091045, A218721,
- A064108 (k=20), A218724-A218734 (21..31), A132469 (32), A218736-A218753 (33..49), A133853 (64), A094028 (100), A218723 (256).
About
History
(see the history tab for details - here only major changes are listed)
- Initial version written by MFH, 07:42, 23 August 2020 (EDT)