cp's OEIS Frontend

A264117 Largest integer which cannot be partitioned using only parts from the set {perfect powers excluding the n smallest}.

%I A264117 #48 May 22 2025 10:21:43
%S A264117 23,55,87,94,119,178,271,312,335,403,501,551,598,717,861,861,903,1022,
%T A264117 1119,1248,1463,1535,1688,2031,2067,2416,2535,2976,3064,3164,3407,
%U A264117 3552,3552,4023,4143,4416,4633,4663,5424,5424,5688,6000,6455
%N A264117 Largest integer which cannot be partitioned using only parts from the set {perfect powers excluding the n smallest}.
%C A264117 It appears, but has not been proved, that for n>28, a(n) < a(n-1) + A001597(n).
%H A264117 Martin Y. Champel, <a href="/A264117/a264117_4.txt">Table of n, a(n) for n = 1..281</a>
%e A264117 a(1) = 23 as 23 cannot be obtained by any combination of {4, 8, 9, 16} but the 4 following integers can:
%e A264117 24 (6*4) a combination of {4, 8, 9, 16},
%e A264117 25 (1*25) a combination of {4, 8, 9, 16, 25},
%e A264117 26 (1*8+2*9) a combination of {4, 8, 9, 16, 25},
%e A264117 27 (1*27) a combination of {4, 8, 9, 16, 25, 27} so all following integers can.
%e A264117 a(2) = 55 as 55 cannot be obtained by any combination of {8, 9, 16, 25, 27, 32, 36, 49} but the 8 following integers can.
%e A264117 a(3) = 87 as 87 cannot be obtained by any combination of {9, 16, 25, 27, 32, 36, 49, 64, 81} but the 9 following integers can.
%o A264117 (Python) # Python version 2.7
%o A264117 from copy import *
%o A264117 from math import *
%o A264117 sol ={}
%o A264117 def a(n):
%o A264117     global sol
%o A264117     if n in sol:  return sol[n]
%o A264117     k = n**2 + 100
%o A264117     yt = sorted(list(set([b**a for a in range(2, 1+int(log(k)/log(2))) for b in range(1, 1+int(k**(1./a)))])))[n:]
%o A264117     p0 = yt[0]
%o A264117     if n-1 in sol and n > 28:  p1 = sol[n-1] + 2 * p0
%o A264117     else: p1 = 7 * p0 + 400
%o A264117     yt = sorted(list(set([b**a for a in range(2, 1+int(log(p1)/log(2))) for b in range(1, 1+int(p1**(1./a)))])))[n:]
%o A264117     st = []
%o A264117     while st != yt:
%o A264117         st = deepcopy(yt)
%o A264117         yt = sorted(list(set(yt + [i+j for i in yt for j in yt if i>=j if i+j < p1])))
%o A264117     d = 0
%o A264117     f = yt[0] + 1
%o A264117     t = f
%o A264117     for i in range(1,len(yt)):
%o A264117         if yt[i] == f:
%o A264117             d += 1
%o A264117             f += 1
%o A264117             if d == yt[0] + 1:
%o A264117                 yt = yt[:yt.index(t+1)]
%o A264117                 sol[n] = yt.pop() + 1
%o A264117                 return sol[n]
%o A264117         else:
%o A264117             t = f
%o A264117             f = yt[i]+1
%o A264117             d = 0
%Y A264117 Cf. A001597.
%K A264117 nonn
%O A264117 1,1
%A A264117 _Martin Y. Champel_, Nov 03 2015