login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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.
1
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,5
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).
FORMULA
Trivial bound: 1 <= a(n) <= 2^(2^(A217031(n))/n! <= 2^(2^(2n-2))/n! . Can this be improved?
EXAMPLE
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!
CROSSREFS
Sequence in context: A063558 A174170 A264373 * A317384 A247601 A013020
KEYWORD
nonn,hard,more
AUTHOR
EXTENSIONS
Extended until a(23) doing full enumeration of all 12 step computations, from Gil Dogon, May 02 2013
STATUS
approved