cp's OEIS Frontend

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

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