|
|
A182002
|
|
Smallest positive integer that cannot be computed using exactly n n's, the four basic arithmetic operations (+, -, *, /), and the parentheses.
|
|
11
|
|
|
2, 2, 1, 10, 13, 22, 38, 91, 195, 443, 634, 1121, 3448, 6793, 17692
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
LINKS
|
|
|
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:
|
|
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
|
|
CROSSREFS
|
Cf. A005245, A005520, A003313, A076142, A076091, A061373, A005421, A064097, A025280, A003037, A117618.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|