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