login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A264117 Largest integer which cannot be partitioned using only parts from the set {perfect powers excluding the n smallest}. 1

%I

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 24 08:04 EDT 2023. Contains 361455 sequences. (Running on oeis4.)