cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 10 results.

A217032 Minimum number of steps to reach n! starting from 1 and using the operations of multiplication, addition, or subtraction.

Original entry on oeis.org

0, 1, 3, 4, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 12, 13, 13
Offset: 1

Views

Author

Stan Wagon, Sep 24 2012

Keywords

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. This sequence lists the smallest number of steps needed to reach n!. A 10-step solution for 12 is {1, 2, 4, 6, 24, 30, 720, 900, 924, 518400, 12!}, found by Stan Wagon; John Guilford found all such, and proved that 10 is minimal for 12! - edited by Stan Wagon, Nov 07 2012
This sequence describes the difficulty of computing the factorial in Valiant's model. If it is of polynomial growth -- that is, there exists some c such that a(n) < (log n)^c for all n -- then the factorial is said to be easy to compute, and consequently "the Hilbert Nullstellensatz is intractable, and consequently the algebraic version of 'NP != P' is true" (Shub & Smale). - Charles R Greathouse IV, Sep 24 2012
During Al Zimmermann's contest (see link), Ed Mertensotto generated all sequences of 12 steps and found no better solutions. Hence a(13)-a(17) are optimal. Solutions of 13 steps were found for a(18) and a(19) during the contest. Hence, they are optimal too. - Dmitry Kamenetsky, Apr 22 2013

Examples

			The entry for 9! is 8 because of the straight-line program {1, 2, 3, 9, 8, 72, 70, 7!, 9!}; subtraction is essential to getting 9! in 8 steps. The entry for 10! is 9 because of the straight-line program {1, 2, 3, 5, 7, 12, 144, 6!, 7!, 10!}, which does not use subtraction.

Links

Crossrefs

Cf. A216999, A217031, A173419, A003065, A141414.

Formula

a(n) = A173419(n!) >= A217031(n). - Charles R Greathouse IV, Sep 24 2012

Extensions

a(12) from Charles R Greathouse IV, Oct 04 2012
a(13)-a(19) from Ed Mertensotto, Mar 20 2013

A214872 The number of subsets of positive integers of cardinality n, produced as the steps in a computation starting with 1 and using the operations of multiplication, addition, or subtraction.

Original entry on oeis.org

1, 2, 8, 59, 663, 10609, 225219, 6057298, 199290037, 7805646133, 356263294786, 18626811747385
Offset: 1

Views

Author

Gil Dogon, May 03 2013

Keywords

Comments

A straight-line program (SLP) is a sequence that starts at 1 and has each entry obtained from two preceding entries by addition, multiplication, or subtraction. The length of the SLP is defined as that of the sequence without the first 1. An SLP is said to be positive if all numbers in the sequence are positive, and reduced if there is no repetition in the sequence. Two SLPs are considered equivalent if their sequence consists of the same numbers (only difference is sequence order). This OEIS sequence gives the number of reduced positive SLPs with n steps.
For most purposes only positive SLPs can be considered, as for every general SLP sequence, applying absolute value to all the steps will produce a positive SLP.
This OEIS sequence can also be thought of as defining the size of the search space that needs to be traversed when trying to compute other SLP related OEIS sequences as given in the cross references below.

Examples

			a(1) = 1 and the SLP is (1,2).
a(2) = 2 and the positive SLPs are (1,2,3) (1,2,4).
a(3) = 8 and the positive SLPs are (1,2,3,4) (1,2,3,5) (1,2,3,6) (1,2,3,9) (1,2,4,5) (1,2,4,6) (1,2,4,8) (1,2,4,16).
Notice that also (1,2,4,3) is a legal positive reduced length 3 SLP sequence but it is equivalent to (1,2,3,4) hence is not enumerated.

Links

Crossrefs

Cf. A217032, A216999, A217031, A173419, A141414.

Formula

a(n) >= a(n-1) * 2 * (n-1) and a(2)=2 Hence a(n) >= 2^(n-1)*(n-1)! .
The recurrence above is true since if the maximum of an SLP sequence of length n-1 is added to all elements except itself, and multiplied with all elements except the first 1 (including itself), then 2n-2 different extensions of the original SLP sequence are produced, resulting in 2n-2 reduced SLP's of length n.

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.

Original entry on oeis.org

1, 3, 6, 16, 58, 321, 2585, 30198
Offset: 0

Views

Author

Hugo Pfoertner, Jun 18 2017

Keywords

Examples

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

Links

Crossrefs

Cf. A216999, A288760, A288849.

Extensions

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

A288760 Number of distinct nonnegative 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}.

Original entry on oeis.org

1, 3, 6, 24, 300, 37761, 451572162
Offset: 0

Views

Author

Hugo Pfoertner, Jun 15 2017

Keywords

Comments

The conjectured value of a(6)=451572162 needs independent verification.
For an explanation of the difference from a straight-line program (SLP) see comment in A288759. A288850 provides the corresponding cardinalities of the sets that can be obtained by an n-step SLP.

Examples

			The sets of numbers >=0 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/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 }.

Links

Crossrefs

Cf. A214872, A216999, A288759, A288850.

Extensions

Wrong a(6) removed by Hugo Pfoertner, Jun 19 2017
a(6) from Markus Sigg, Jul 01 2017

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

Original entry on oeis.org

1, 3, 7, 21, 83, 484, 4084, 49479
Offset: 0

Views

Author

Hugo Pfoertner, Jun 18 2017

Keywords

Examples

			The sets of numbers obtainable at the n-th step are:
S(0) = { 1 },
S(1) = { 0, 1, 2 },
S(2) = { -1, 0, 1/2, 1, 2, 3, 4 },
S(3) = { -3, -2, -3/2, -1, -1/2, 0, 1/4, 1/3, 1/2, 2/3, 1, 3/2, 2, 5/2, 3, 4, 5, 6, 8, 9, 16 }.

Crossrefs

Cf. A214872, A288759, A288850.
A216999 provides the corresponding results if division is not used.

Extensions

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

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

Original entry on oeis.org

1, 3, 8, 38, 555, 74423, 902663448
Offset: 0

Views

Author

Hugo Pfoertner, Jun 15 2017

Keywords

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.

Examples

			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.

Extensions

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

A229662 The number of subsets of integers of cardinality n, produced as the steps in a computation starting with 1 and using the operations of multiplication, addition, or subtraction.

Original entry on oeis.org

2, 5, 20, 149, 1852, 34354, 873386, 28671789, 1166062774, 56973937168, 3266313635225, 215667757729237
Offset: 1

Views

Author

Gil Dogon, Sep 27 2013

Keywords

Comments

A straight-line program (SLP) is a sequence that starts at 1 and has each entry obtained from two preceding entries by addition, multiplication, or subtraction. The length of the SLP is defined as that of the sequence without the first 1. An SLP is said to be reduced if there is no repetition in the sequence. Two SLPs are considered equivalent if their sequence defines the same set of integers. This OEIS sequence gives the number of reduced SLPs with n steps.

Examples

			a(1) = 2 and the SLPs are (1,2) (1,0)
a(2) = 5 and the SLPs are (1,2,3) (1,2,4) (1,2,-1) (1,0,-1) (1,0,2)

Crossrefs

Cf. A229673, A214872, A216999, A173419, A141414.

Formula

a(n) >= a(n-1) * 2 * (n-1) and a(2)=5 Hence a(n) >= 5*2^(n-2)*(n-1)! .

A229673 The number of subsets of nonzero integers of cardinality n, produced as the steps in a computation starting with 1 and using the operations of multiplication, addition, or subtraction.

Original entry on oeis.org

1, 3, 15, 126, 1667, 31966, 828678, 27535826, 1128945382, 55473589278, 3193471420236, 211517309562652
Offset: 1

Views

Author

Gil Dogon, Sep 27 2013

Keywords

Comments

A straight-line program (SLP) is a sequence that starts at 1 and has each entry obtained from two preceding entries by addition, multiplication, or subtraction. The length of the SLP is defined as that of the sequence without the first 1. An SLP is said to be reduced if there is no repetition in the sequence. Two SLPs are considered equivalent if their sequences define the same subset(only difference is sequence order). This sequence gives the number of SLPs with n steps in which 0 does not appear.
This sequence can also be thought of as defining the size of the search space that needs to be traversed when trying to compute other SLP related OEIS sequences such as A216999 or A229686. This is because 0 is never needed in the shortest SLP calculation of any other integer.
Michael Collier generated independently the values up to 1128945382.

Examples

			a(1) = 1 and the SLP is (1,2).
a(2) = 3 and the SLPs are (1,2,3), (1,2,4), and (1,2,-1).

Crossrefs

Cf. A229662, A216999, A173419, A214872, A229686.

Formula

a(n) >= 2^(n-1)*(n-1)!.

A229686 The negative number of minimum absolute value not obtainable from 1 in n steps using addition, multiplication, and subtraction.

Original entry on oeis.org

-1, -2, -4, -9, -29, -85, -311, -1549, -9851, -74587, -956633
Offset: 0

Views

Author

Gil Dogon, Sep 27 2013

Keywords

Comments

This is similar to A141414 but applied to negative numbers. It is the greatest negative number that requires an n step SLP (Stright Line Program) to compute it.

Examples

			For n=1 the value is -1 since -1 requires 2 steps SLP: 1,2,-1.
For n=2 the value is -2 since -2 requires 3 steps SLP: 1,2,3,-2.
For n=3 the value is -4 since -3 also requires only 3 steps but -4 requires 4: 1,2,4,5,-4.

Crossrefs

Cf. A141414, A216999, A214872.

A219906 Number of different straight line programs of length n.

Original entry on oeis.org

1, 3, 13, 82, 788, 12141, 302791, 11729499
Offset: 0

Views

Author

N. J. A. Sloane, Dec 13 2012

Keywords

Comments

See Borwein and Hobart (or A216999) for definition.

Links

Crossrefs

Cf. A173419, A216999, A217032.

Programs

  • Maple
    g:= f-> seq([f[], t], t={seq(seq({i+j, i-j, i*j}[], j=f), i=f)}):
F:= proc(n) F(n):= map(g, F(n-1)) end: F(0):= {[1]}:
a:= n-> nops(F(n)):
seq(a(n), n=0..5);  # Alois P. Heinz, Dec 14 2012

Extensions

Typo in a(4) corrected, a(6)-a(7) from Alois P. Heinz, Dec 14 2012
Showing 1-10 of 10 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.