|
|
A071848
|
|
a(n) = smallest positive integer that cannot be obtained using the number n at most n times and the operations +, -, *, /, where intermediate subexpressions must be integers.
|
|
2
|
|
|
2, 3, 5, 10, 13, 22, 38, 85, 138, 246, 547, 1121, 2792, 6379, 15021, 20870
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Joe Crump's page indicates that a(9) = 195 if noninteger subexpressions are permitted. - David W. Wilson, Jan 14 2007
|
|
LINKS
|
|
|
EXAMPLE
|
a(3) = 5 because using 3 at most thrice we can have 3/3=1, 3-(3/3)=2, 3=3, 3+(3/3)=4 but we cannot obtain 5 this way.
a(14) != 3967 since 3967 = 3969 - 2 = 21 * 189 - 2 = (7 + 14) * (14*14 - 7) - 2 = (14/((14+14)/14) + 14) * (14*14 - 14/((14+14)/14)) - (14+14)/14.
|
|
PROG
|
(Python)
from functools import lru_cache
def a(n):
@lru_cache()
def f(m):
if m == 1: return {n}
out = set()
for j in range(1, m//2+1):
for x in f(j):
for y in f(m-j):
out.update([x + y, x - y, y - x, x * y])
if y and x%y == 0: out.add(x//y)
if x and y%x == 0: out.add(y//x)
return out
k, s = 1, set.union(*(f(i) for i in range(1, n+1)))
while k in s: k += 1
return k
|
|
CROSSREFS
|
|
|
KEYWORD
|
hard,more,nonn
|
|
AUTHOR
|
Koksal Karakus (karakusk(AT)hotmail.com), Jun 09 2002
|
|
EXTENSIONS
|
Definition changed (to reflect wording of the example) by Jason Taff (jtaff(AT)jburroughs.org), Apr 07 2010
|
|
STATUS
|
approved
|
|
|
|