A258097 Number of nonnegative integers that can be computed using exactly n n's and the four basic arithmetic operations {+, -, *, /}.

1, 3, 9, 26, 68, 198, 536, 1660, 4769, 15945, 46240, 165732, 488268, 1848866, 5852344

Offset: 1

Author

Alois P. Heinz, May 19 2015

Keywords

• nonn
• more

Crossrefs

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

Programs

Maple

a:= proc(n) option remember; local f; f:=
       proc(m) option remember; `if`(m=1, {n}, {
         seq(seq(seq([x+y, x-y, x*y, `if`(y=0, [][], x/y)
         ][], y=f(m-j)), x=f(j)), j=1..m-1)})
       end; forget(f);
       nops([select(z->z>=0 and is(z, integer), f(n))[]])
    end:
seq(a(n), n=1..9);

Mathematica

a[n_] := a[n] = Module[{f}, f[m_] := f[m] = If[m == 1, {n},
     Union@ Flatten@ Table[Table[Table[{x + y, x - y, x*y,
     If[y == 0, Nothing, x/y]}, {y, f[m-j]}], {x, f[j]}], {j, m-1}]];
   Length[Select[f[n], # >= 0 && IntegerQ[#]&]]];
Table[a[n], {n, 1, 9}] (* Jean-François Alcover, Aug 29 2021, after Alois P. Heinz *)

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):
            for x in f(j):
                for y in f(m-j):
                    out.update([x + y, x - y, x * y])
                    if y: out.add(Fraction(x, y))
        return list(out)
    return sum(num >= 0 and num.denominator == 1 for num in f(n))
print([a(n) for n in range(1, 10)]) # Michael S. Branicky, Aug 29 2021 after Alois P. Heinz

Extensions

a(13)-a(14) from Giovanni Resta, May 20 2015

a(15) from Michael S. Branicky, Aug 29 2021