This site is supported by donations to The OEIS Foundation.

M. F. Hasler/Notes on Sums of powers

From OeisWiki
Jump to: navigation, search

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

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.

  1. 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
  2. One can also make this list "by hand" using the same idea (as sum of k terms which are m-th powers).
  3. 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)