cp's OEIS Frontend

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

%I A258097 #17 Aug 29 2021 12:01:41
%S A258097 1,3,9,26,68,198,536,1660,4769,15945,46240,165732,488268,1848866,
%T A258097 5852344
%N A258097 Number of nonnegative integers that can be computed using exactly n n's and the four basic arithmetic operations {+, -, *, /}.
%p A258097 a:= proc(n) option remember; local f; f:=
%p A258097        proc(m) option remember; `if`(m=1, {n}, {
%p A258097          seq(seq(seq([x+y, x-y, x*y, `if`(y=0, [][], x/y)
%p A258097          ][], y=f(m-j)), x=f(j)), j=1..m-1)})
%p A258097        end; forget(f);
%p A258097        nops([select(z->z>=0 and is(z, integer), f(n))[]])
%p A258097     end:
%p A258097 seq(a(n), n=1..9);
%t A258097 a[n_] := a[n] = Module[{f}, f[m_] := f[m] = If[m == 1, {n},
%t A258097      Union@ Flatten@ Table[Table[Table[{x + y, x - y, x*y,
%t A258097      If[y == 0, Nothing, x/y]}, {y, f[m-j]}], {x, f[j]}], {j, m-1}]];
%t A258097    Length[Select[f[n], # >= 0 && IntegerQ[#]&]]];
%t A258097 Table[a[n], {n, 1, 9}] (* _Jean-François Alcover_, Aug 29 2021, after _Alois P. Heinz_ *)
%o A258097 (Python)
%o A258097 from fractions import Fraction
%o A258097 from functools import lru_cache
%o A258097 def a(n):
%o A258097     @lru_cache()
%o A258097     def f(m):
%o A258097         if m == 1: return {Fraction(n, 1)}
%o A258097         out = set()
%o A258097         for j in range(1, m):
%o A258097             for x in f(j):
%o A258097                 for y in f(m-j):
%o A258097                     out.update([x + y, x - y, x * y])
%o A258097                     if y: out.add(Fraction(x, y))
%o A258097         return list(out)
%o A258097     return sum(num >= 0 and num.denominator == 1 for num in f(n))
%o A258097 print([a(n) for n in range(1, 10)]) # _Michael S. Branicky_, Aug 29 2021 after _Alois P. Heinz_
%Y A258097 Cf. A171826, A171827, A171828, A171829, A258068, A258069, A258070, A258071.
%K A258097 nonn,more
%O A258097 1,2
%A A258097 _Alois P. Heinz_, May 19 2015
%E A258097 a(13)-a(14) from _Giovanni Resta_, May 20 2015
%E A258097 a(15) from _Michael S. Branicky_, Aug 29 2021