A185187 Smallest number for which the greedy algorithm fails to find the sum of n-th powers with at most A002804 terms.

23, 50, 160, 466, 1432, 4362, 12960, 39138, 117416, 353274, 1059824, 3183570, 9550712, 28668522, 86038336, 258246082, 774607176, 2324083674, 6973299600, 20918850226, 62758647832, 188280137802, 564857190624, 1694571571874, 5083681161192, 15251177701306

Offset: 2

Author

J. Lowell, Feb 19 2011

Keywords

• nonn

Comments

For n > 2, a(n) = 3^n + (floor(3^n//2^n) - 1)*2^n + (2^n - 1), with A002804(n)+1 terms in the greedy representation. - Michael S. Branicky, Dec 15 2021

Examples

			23 qualifies for a(2) because 23 as a sum of squares with the greedy algorithm is 16+4+1+1+1 (5 terms,) but A002804(2) = 4.
50 qualifies for a(3) because 50 as a sum of cubes with the greedy algorithm is 27+8+8+1+1+1+1+1+1+1 (10 terms,) but A002804(3) = 9.
		

Links

• Michael S. Branicky, Table of n, a(n) for n = 2..2095

Crossrefs

Cf. A002804.

Programs

Python

# exhaustive search
from sympy import integer_nthroot
def g(n): twon = (1 << n); return twon + 3**n//twon - 2
def greedy(k, n):
    if k < (1 << n): return k
    bigpow = integer_nthroot(k, n)[0]**n
    m, r = divmod(k, bigpow)
    return  m + greedy(r, n)
def a(n):
    k, gn = 2**n, g(n)
    while greedy(k, n) <= gn: k += 1
    return k
print([a(n) for n in range(2, 12)]) # Michael S. Branicky, Dec 15 2021

Python

# direct computation based on formula
def a(n): return 23 if n == 2 else 3**n + (3**n//2**n-1)*2**n + (2**n-1)
print([a(n) for n in range(2, 28)]) # Michael S. Branicky, Dec 15 2021

Extensions

a(6) and beyond from Michael S. Branicky, Dec 15 2021