cp's OEIS Frontend

A216999 Number of integers obtainable from 1 in n steps using addition, multiplication, and subtraction.

%I A216999 #34 Aug 06 2024 07:20:12
%S A216999 1,3,6,13,38,153,867,6930,75986,1109442,20693262,477815647
%N A216999 Number of integers obtainable from 1 in n steps using addition, multiplication, and subtraction.
%C A216999 A straight-line program is a sequence that starts at 1 and has each entry obtained from two preceding entries by addition, multiplication, or subtraction.  S(n) is the set of integers obtainable at any point in a straight-line program using n steps.  Thus S(0) = {1}, S(1) = {0,1,2}, S(2) = {-1,0,1,2,3,4}; the sequence here is the cardinality of S(n).
%H A216999 Peter Borwein and Joe Hobart, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.119.07.584">The extraordinary power of division in straight line programs</a>, American Mathematical Monthly 119:7 (2012), pp. 584-592.
%H A216999 Michael Shub and Steve Smale, <a href="https://citeseerx.ist.psu.edu/pdf/a16554b6837219fab950b3628e6d5bc485565311">On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP = P"</a>, Duke Mathematical Journal 81:1 (1995), pp. 47-54.
%t A216999 extend[p_] :=  Module[{q = Tuples[p, {2}], new},
%t A216999   new = Flatten[Table[{Total[t], Subtract @@ t, Times @@ t}, {t, q}]];
%t A216999   Union[ Sort /@  DeleteCases[ Table[If[! MemberQ[p, n], Append[p, n]], {n, new}], Null]]] ;
%t A216999 P[0] = {{1}};
%t A216999 P[n_] := P[n] = DeleteDuplicates[Flatten[extend /@ P[n - 1], 1]];
%t A216999 S[n_] := DeleteDuplicates[Flatten[P[n]]];
%t A216999 Length /@ S /@ Range[6]
%Y A216999 Cf. A003065, A141414, A173419, A288849, A288850.
%K A216999 nonn,more,hard,nice
%O A216999 0,2
%A A216999 _Stan Wagon_, Sep 22 2012
%E A216999 a(9)-a(11) (Michael Collier verified independently the 1109442, 20693262 values) by _Gil Dogon_, Sep 27 2013