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,1

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

Links

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

Example

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.

Prog

(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

Crossrefs

Cf. A002804.

Sequence in context: A029493 A063321 A176660 * A157095 A281266 A165432

Adjacent sequences: A185184 A185185 A185186 * A185188 A185189 A185190

Keyword

nonn

Author

J. Lowell, Feb 19 2011

Extensions

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

Status

approved