cp's OEIS Frontend

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.

%I A071848 #28 Aug 17 2024 22:26:37
%S A071848 2,3,5,10,13,22,38,85,138,246,547,1121,2792,6379,15021,20870,48309,
%T A071848 161629
%N 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.
%C A071848 Joe Crump's page indicates that a(9) = 195 if noninteger subexpressions are permitted. - _David W. Wilson_, Jan 14 2007
%H A071848 Gilles Bannay, <a href="https://web.archive.org/web/20061201125224/http://gilles.bannay.free.fr/jeux_us.html">Countdown Problem</a>
%H A071848 Joe Crump, <a href="http://web.archive.org/web/20070630090158/http://www.immortaltheory.com/NumberTheory/nines.htm">The Nine 9s</a>
%H A071848 <a href="/index/Fo#4x4">Index entries for similar sequences</a>
%e A071848 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 A071848 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 A071848 (Python)
%o A071848 from functools import lru_cache
%o A071848 def a(n):
%o A071848     @lru_cache()
%o A071848     def f(m):
%o A071848         if m == 1: return {n}
%o A071848         out = set()
%o A071848         for j in range(1, m//2+1):
%o A071848             for x in f(j):
%o A071848                 for y in f(m-j):
%o A071848                     out.update([x + y, x - y, y - x, x * y])
%o A071848                     if y and x%y == 0: out.add(x//y)
%o A071848                     if x and y%x == 0: out.add(y//x)
%o A071848         return out
%o A071848     k, s = 1, set.union(*(f(i) for i in range(1, n+1)))
%o A071848     while k in s: k += 1
%o A071848     return k
%o A071848 print([a(n) for n in range(1, 14)]) # _Michael S. Branicky_, Jul 28 2022
%Y A071848 Cf. A060315.
%K A071848 hard,more,nonn
%O A071848 1,1
%A A071848 Koksal Karakus (karakusk(AT)hotmail.com), Jun 09 2002
%E A071848 Definition corrected by _David W. Wilson_, Jan 14 2007
%E A071848 Definition changed (to reflect wording of the example) by Jason Taff (jtaff(AT)jburroughs.org), Apr 07 2010
%E A071848 a(14)-a(15) corrected and a(16) from _Michael S. Branicky_, Jul 28 2022
%E A071848 a(17)-a(18) from _Sean A. Irvine_, Aug 17 2024