This site is supported by donations to The OEIS Foundation.

 Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS". Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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). LINKS Peter Borwein and Joe Hobart, The extraordinary power of division in straight line programs, American Mathematical Monthly 119:7 (2012), pp. 584-592. 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. 47-54. 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.