

A216999


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


10



1, 3, 6, 13, 38, 153, 867, 6930, 75986, 1109442, 20693262, 477815647
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

A straightline 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 straightline 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).


LINKS



MATHEMATICA

extend[p_] := Module[{q = Tuples[p, {2}], new},
new = Flatten[Table[{Total[t], Subtract @@ t, Times @@ t}, {t, q}]];
Union[ Sort /@ DeleteCases[ Table[If[! MemberQ[p, n], Append[p, n]], {n, new}], Null]]] ;
P[0] = {{1}};
P[n_] := P[n] = DeleteDuplicates[Flatten[extend /@ P[n  1], 1]];
S[n_] := DeleteDuplicates[Flatten[P[n]]];
Length /@ S /@ Range[6]


CROSSREFS



KEYWORD

nonn,more,hard,nice


AUTHOR



EXTENSIONS

a(9)a(11) (Michael Collier verified independently the 1109442, 20693262 values) by Gil Dogon, Sep 27 2013


STATUS

approved



