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
23, 55, 87, 94, 119, 178, 271, 312, 335, 403, 501, 551, 598, 717, 861, 861, 903, 1022, 1119, 1248, 1463, 1535, 1688, 2031, 2067, 2416, 2535, 2976, 3064, 3164, 3407, 3552, 3552, 4023, 4143, 4416, 4633, 4663, 5424, 5424, 5688, 6000, 6455 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

It appears, but has not been proved, that for n>28, a(n) < a(n-1) + A001597(n).

LINKS

Table of n, a(n) for n=1..43.

Martin Y. Champel, Table of n, a(n) for n = 1..281

EXAMPLE

a(1) = 23 as 23 cannot be obtained by any combination of {4, 8, 9, 16} but the 4 following integers can:

24 (6*4) a combination of {4, 8, 9, 16},

25 (1*25) a combination of {4, 8, 9, 16, 25},

26 (1*8+2*9) a combination of {4, 8, 9, 16, 25},

27 (1*27) a combination of {4, 8, 9, 16, 25, 27} so all following integers can.

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.

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.

PROG

(Python 2.7)

from copy import *

from math import *

sol ={}

def a(n):

....global sol

....if n in sol: return sol[n]

....k = n**2 + 100

....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:]

....p0 = yt[0]

....if n-1 in sol and n > 28: p1 = sol[n-1] + 2 * p0

....else: p1 = 7 * p0 + 400

....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:]

....st = []

....while st != yt:

........st = deepcopy(yt)

........yt = sorted(list(set(yt + [i+j for i in yt for j in yt if i>=j if i+j < p1])))

....d = 0

....f = yt[0] + 1

....t = f

....for i in range(1, len(yt)):

........if yt[i] == f:

............d += 1

............f += 1

............if d == yt[0] + 1:

................yt = yt[:yt.index(t+1)]

................sol[n] = yt.pop() + 1

................return sol[n]

........else:

............t = f

............f = yt[i]+1

............d = 0

CROSSREFS

Cf. A001597.

Sequence in context: A053236 A118603 A303891 * A033657 A305283 A166144

Adjacent sequences: A264114 A264115 A264116 * A264118 A264119 A264120

KEYWORD

nonn

AUTHOR

Martin Y. Champel, Nov 03 2015

STATUS

approved

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 January 28 14:40 EST 2023. Contains 359895 sequences. (Running on oeis4.)