A182002 Smallest positive integer that cannot be computed using exactly n n's, the four basic arithmetic operations (+, -, *, /), and the parentheses.

2, 2, 1, 10, 13, 22, 38, 91, 195, 443, 634, 1121, 3448, 6793, 17692

Offset

1,1

Links

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

Example

a(2) = 2 because two 2's can produce 0 = 2-2, 1 = 2/2, 4 = 2+2 = 2*2, so the smallest positive integer that cannot be computed is 2.
a(3) = 1 because no expression with three 3's gives 1.

Maple

f:= proc(n, b) option remember;
      `if`(n=1, {b}, {seq(seq(seq([k+m, k-m, k*m,
      `if`(m=0, NULL, k/m)][], m=f(n-i, b)), k=f(i, b)), i=1..n-1)})
    end:
a:= proc(n) local i, l;
      l:= sort([infinity, select(x-> is(x, integer) and x>0, f(n, n))[]]);
      for i do if l[i]<>i then return i fi od
    end:
seq(a(n), n=1..8); # Alois P. Heinz, Apr 13 2012

Prog

(Python)
from fractions import Fraction
from functools import lru_cache
def a(n):
    @lru_cache()
    def f(m):
        if m == 1: return {Fraction(n, 1)}
        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: out.add(Fraction(x, y))
                    if x: out.add(Fraction(y, x))
        return out
    k, s = 1, f(n)
    while k in s: k += 1
    return k
print([a(n) for n in range(1, 10)]) # Michael S. Branicky, Jul 29 2022

Crossrefs

Cf. A005245, A005520, A003313, A076142, A076091, A061373, A005421, A064097, A025280, A003037, A117618.

Cf. A171826, A171827, A171828, A171829, A258068, A258069, A258070, A258071.

Sequence in context: A306149 A134896 A105620 * A184251 A262348 A307093

Adjacent sequences: A181999 A182000 A182001 * A182003 A182004 A182005

Keyword

nonn,more

Author

Ali Dasdan, Apr 05 2012

Extensions

a(11)-a(12) from Alois P. Heinz, Apr 22 2012

a(13)-a(14) from Michael S. Branicky, Jul 29 2022

a(15) from Michael S. Branicky, Jul 27 2023

Status

approved