login
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