The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. 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 = {{1}}; P[n_] := P[n] = DeleteDuplicates[Flatten[extend /@ P[n - 1], 1]]; S[n_] := DeleteDuplicates[Flatten[P[n]]]; Length /@ S /@ Range CROSSREFS Cf. A003065, A141414, A173419, A288849, A288850. 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 27 12:30 EDT 2020. Contains 337380 sequences. (Running on oeis4.)