|
%I #19 Dec 15 2021 10:30:47
%S 23,50,160,466,1432,4362,12960,39138,117416,353274,1059824,3183570,
%T 9550712,28668522,86038336,258246082,774607176,2324083674,6973299600,
%U 20918850226,62758647832,188280137802,564857190624,1694571571874,5083681161192,15251177701306
%N Smallest number for which the greedy algorithm fails to find the sum of n-th powers with at most A002804 terms.
%C 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
%H Michael S. Branicky, <a href="/A185187/b185187.txt">Table of n, a(n) for n = 2..2095</a>
%e 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.
%e 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.
%o (Python) # exhaustive search
%o from sympy import integer_nthroot
%o def g(n): twon = (1 << n); return twon + 3**n//twon - 2
%o def greedy(k, n):
%o if k < (1 << n): return k
%o bigpow = integer_nthroot(k, n)[0]**n
%o m, r = divmod(k, bigpow)
%o return m + greedy(r, n)
%o def a(n):
%o k, gn = 2**n, g(n)
%o while greedy(k, n) <= gn: k += 1
%o return k
%o print([a(n) for n in range(2, 12)]) # _Michael S. Branicky_, Dec 15 2021
%o (Python) # direct computation based on formula
%o def a(n): return 23 if n == 2 else 3**n + (3**n//2**n-1)*2**n + (2**n-1)
%o print([a(n) for n in range(2, 28)]) # _Michael S. Branicky_, Dec 15 2021
%Y Cf. A002804.
%K nonn
%O 2,1
%A _J. Lowell_, Feb 19 2011
%E a(6) and beyond from _Michael S. Branicky_, Dec 15 2021
| 