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.

User: Gil Dogon

Gil Dogon's wiki page.

Gil Dogon has authored 4 sequences.

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.

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.

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

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