

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


REFERENCES

P. Borwein and J. Hobart, The extraordinary power of division in straight line programs, American Mathematical Monthly, 119 (2012), 584  592.


LINKS

Table of n, a(n) for n=0..11.
Michael Shub and Steve Smale, On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP = P", Duke Mathematical Journal 81:1 (1995), pp. 4754.


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

Cf. A173419, A003065, A141414.
Sequence in context: A062466 A053564 A264236 * A036781 A084816 A055738
Adjacent sequences: A216996 A216997 A216998 * A217000 A217001 A217002


KEYWORD

nonn,more,hard,nice


AUTHOR

Stan Wagon, Sep 22 2012


EXTENSIONS

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


STATUS

approved



