login
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

%I #28 Aug 17 2024 22:26:37

%S 2,3,5,10,13,22,38,85,138,246,547,1121,2792,6379,15021,20870,48309,

%T 161629

%N 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.

%C Joe Crump's page indicates that a(9) = 195 if noninteger subexpressions are permitted. - _David W. Wilson_, Jan 14 2007

%H Gilles Bannay, <a href="https://web.archive.org/web/20061201125224/http://gilles.bannay.free.fr/jeux_us.html">Countdown Problem</a>

%H Joe Crump, <a href="http://web.archive.org/web/20070630090158/http://www.immortaltheory.com/NumberTheory/nines.htm">The Nine 9s</a>

%H <a href="/index/Fo#4x4">Index entries for similar sequences</a>

%e 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.

%e 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.

%o (Python)

%o from functools import lru_cache

%o def a(n):

%o @lru_cache()

%o def f(m):

%o if m == 1: return {n}

%o out = set()

%o for j in range(1, m//2+1):

%o for x in f(j):

%o for y in f(m-j):

%o out.update([x + y, x - y, y - x, x * y])

%o if y and x%y == 0: out.add(x//y)

%o if x and y%x == 0: out.add(y//x)

%o return out

%o k, s = 1, set.union(*(f(i) for i in range(1, n+1)))

%o while k in s: k += 1

%o return k

%o print([a(n) for n in range(1, 14)]) # _Michael S. Branicky_, Jul 28 2022

%Y Cf. A060315.

%K hard,more,nonn

%O 1,1

%A Koksal Karakus (karakusk(AT)hotmail.com), Jun 09 2002

%E Definition corrected by _David W. Wilson_, Jan 14 2007

%E Definition changed (to reflect wording of the example) by Jason Taff (jtaff(AT)jburroughs.org), Apr 07 2010

%E a(14)-a(15) corrected and a(16) from _Michael S. Branicky_, Jul 28 2022

%E a(17)-a(18) from _Sean A. Irvine_, Aug 17 2024