login
This site is supported by donations to The OEIS Foundation.

 

Logo

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

Table of n, a(n) for n=0..11.

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.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 21 16:08 EST 2017. Contains 295003 sequences.