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,1

Comments

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

Links

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

Gilles Bannay, Countdown Problem

Joe Crump, The Nine 9s

Index entries for similar sequences

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

Crossrefs

Cf. A060315.

Sequence in context: A084760 A186082 A103746 * A268176 A120938 A120610

Adjacent sequences: A071845 A071846 A071847 * A071849 A071850 A071851

Keyword

hard,more,nonn

Author

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

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

Status

approved