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, 3, 5, 10, 13, 22, 38, 85, 138, 246, 547, 1121, 2792, 6379, 15021, 20870, 48309, 161629

Offset: 1

Author

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

Keywords

• hard
• more
• nonn

Comments

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

Examples

			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.
		

Links

• Gilles Bannay, Countdown Problem
• Joe Crump, The Nine 9s
• Index entries for similar sequences

Crossrefs

Cf. A060315.

Programs

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
print([a(n) for n in range(1, 14)]) # Michael S. Branicky, Jul 28 2022

Extensions

Definition corrected by David W. Wilson, Jan 14 2007

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

a(14)-a(15) corrected and a(16) from Michael S. Branicky, Jul 28 2022

a(17)-a(18) from Sean A. Irvine, Aug 17 2024