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-3 of 3 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.

A217490 Let t be the length of the shortest computation yielding a positive multiple of n! using addition, subtraction and multiplication. Then a(n) is the least k > 0 such that k*n! can be computed in t steps.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 13, 26, 11830, 1183, 1, 561, 48048, 3432, 3718, 3718, 956689100690500088178176, 187, 8983799529705, 6061484504517072231744, 26002249020, 1181920410, 8006931102170352452004696490160949546032818169320135140000
Offset: 1

Views

Author

Charles R Greathouse IV, Oct 04 2012

Keywords

Comments

Least k > 0 such that A173419(k*n!) = A217031(n).
Related to the algebraic version of the P =? NP problem, see A173419 and A217031.
a(n) = 1 if and only if A217031(n) = A217032(n).

Examples

			a(1) = 1 since A173419(1!) = 0.
a(2) = 1 since A173419(2!) = 1.
a(3) = 1 since A173419(3!) = 3.
a(4) = 1 since A173419(4!) = 4.
a(5) = 2 since A173419(2*5!) = 5.
a(6) = 1 since A173419(6!) = 6.
a(7) = 13 since A173419(13*7!) = 6.
a(8) = 26 since A173419(26*8!) = 7.
a(9) = 11830 since A173419(11830*9!) = 7.
a(10) = 1183 since A173419(1183*10!) = 7.
a(11) = 1 since A173419(11!) = 9.
a(12) = 561 since A173419(561*12!) = 9.
a(22) = 1181920410
Because of the following 12 step computation:
1, 2, 4, 16, 256, 18, 324, 104976, 104720, 10993086720, 120847955633440358400, 10992982000, 1328479401015208457964748800000
The last number is 1181920410 * 22!

Formula

Trivial bound: 1 <= a(n) <= 2^(2^(A217031(n))/n! <= 2^(2^(2n-2))/n! . Can this be improved?

Extensions

Extended until a(23) doing full enumeration of all 12 step computations, from Gil Dogon, May 02 2013
Showing 1-3 of 3 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.