A288849 -id:A288849

Search: a288849 -id:a288849

Displaying 1-3 of 3 results found.

page 1

A216999

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

+10
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. A003065, A141414, A173419, A288849, A288850.

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

A288850

Number of distinct nonnegative rational numbers that can be obtained in n steps by a straight-line program (SLP) starting at 1 using addition, subtraction, multiplication and division.

+10
4

1, 3, 6, 16, 58, 321, 2585, 30198

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

LINKS

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

Hugo Pfoertner, Distribution of values generated by n-step SLPs, Illustration.

EXAMPLE

The sets of numbers obtainable at the n-th step are:

S(0) = { 1 },

S(1) = { 0, 1, 2 },

S(2) = { 0, 1/2, 1, 2, 3, 4 },

S(3) = { 0, 1/4, 1/3, 1/2, 2/3, 1, 3/2, 2, 5/2, 3, 4, 5, 6, 8, 9, 16 }.

CROSSREFS

Cf. A216999, A288760, A288849.

KEYWORD

nonn,hard,more

AUTHOR

Hugo Pfoertner, Jun 18 2017

EXTENSIONS

a(7) from Alois P. Heinz, Jun 18 2017

STATUS

approved

A288759

Number of distinct rational numbers that can be obtained in n steps by applying addition, subtraction, multiplication and division to any two potentially identical numbers from the complete set of numbers created in n-1 steps, starting with the set {1}.

+10
2

1, 3, 8, 38, 555, 74423, 902663448

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

This is different from a straight-line program (SLP), which can only use numbers created in the path to its own result at level n-1. A288849 provides the cardinalities of the sets that can be created by the related SLPs.

LINKS

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

EXAMPLE

The sets of numbers obtainable at the n-th step are:

S(0) = { 1 },

S(1) = { 0, 1, 2 },

S(2) = { -2, -1, 0, 1/2, 1, 2, 3, 4 },

S(3) = { -8, -6, -5, -4, -7/2, -3, -5/2, -2, -3/2, -1, -2/3, -1/2, -1/3, -1/4, 0, 1/8, 1/6, 1/4, 1/3, 1/2, 2/3, 3/4, 1, 4/3, 3/2, 2, 5/2, 3, 7/2, 4, 9/2, 5, 6, 7, 8, 9, 12, 16 }.

CROSSREFS

Cf. A214872, A216999, A288760, A288849.

KEYWORD

nonn,more,hard

AUTHOR

Hugo Pfoertner, Jun 15 2017

EXTENSIONS

a(6) from Hugo Pfoertner and Markus Sigg, Aug 06 2017

STATUS

approved

page 1

Search completed in 0.012 seconds