|
| |
|
|
A173419
|
|
Length of shortest computation yielding n using addition, subtraction and multiplication (starting from 1).
|
|
16
|
|
|
|
0, 1, 2, 2, 3, 3, 4, 3, 3, 4, 4, 4, 5, 4, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 4, 5, 4, 5, 5, 5, 5, 4, 5, 5, 5, 4, 5, 5, 5, 5, 6, 5, 6, 6, 5, 6, 6, 5, 5, 5, 6, 6, 6, 5, 6, 5, 6, 6, 6, 5, 6, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 5, 6, 6, 5, 5, 5, 4, 5, 5, 5, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 5, 6, 6, 5, 5, 6, 6, 6, 6, 6, 6, 6, 5
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
Let x_0 = 1 and x_m = n, with each x_k = x_i + x_j, x_k = x_i * x_j, or x_k = x_i - x_j for some 0 <= i,j < k. a(n) is the least such m.
Shub & Smale ask if there is a c such that a(n!) <= (log n)^c for all n.
If for any sequence of nonzero integers (m_i) there is no constant c such that a(n! * m_n) <= (log n)^c, then "the Hilbert Nullstellensatz is intractable, and consequently the algebraic version of 'NP != P' is true" (Shub & Smale).
Conjecture: if n is prime then a(n) >= a(n-1). The conjecture is true for n < 1800. - Dmitry Kamenetsky, Dec 26 2019
|
|
|
REFERENCES
|
R. K. Guy, Unsolved Problems Number Theory, Sect. F26.
|
|
|
LINKS
|
Alois P. Heinz, Table of n, a(n) for n = 1..1800
Peter Borwein and Joe Hobart, The extraordinary power of division in straight line programs, American Mathematical Monthly 119:7 (2012), pp. 584-592.
F. Cucker, M. Shub, and S. Smale, Separation of Complexity classes in Koiran's weak model, Theoretical Computer Science 133:1 (1994), pp. 3-14.
W. DeMelo and B. F. Svaiter, The cost of computing integers, Proc. Amer. Math. Soc. 124 (1996), pp. 1377-1378.
P. Koiran, Valiant's model and the cost of computing integers, Comput. Complex. 13 (2004), pp. 131-146.
Carlos Gustavo T. de A. Moreira, On asymptotic estimates for arithmetic cost functions, Proceedings of the American Mathematical Society 125:2 (1997), pp. 347-353.
Richard J. Mathar, Extended list of chain examples
Michael Shub and Steve Smale, On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP = P", Duke Mathematical Journal 81:1 (1995), pp. 47-54.
Al Zimmermann's Programming Contests, Factorials
Index to sequences related to the complexity of n
|
|
|
FORMULA
|
a(n) <= 2 log_2(n).
a(n) >= log_2(log_2(n)) + 1.
a(n) >= log_2(n)/log_2(log_2(n)) for almost all n, as proved by Moreira (improving DeMelo & Svaiter).
|
|
|
EXAMPLE
|
For n = 9, one sequence is (1, 1 + 1 = 2, 1 + 2 = 3, 3 * 3 = 9). Since no shorter sequence is possible, a(9) = 3.
For n = 96, one sequence is (1, 1 + 1 = 2, 2 + 2 = 4, 2 + 4 = 6, 4*4 = 16, 6*16 = 96); no shorter is possible so a(96) = 5.
|
|
|
MAPLE
|
g:= f->seq(f union {t}, t={seq(seq({i+j, i-j, i*j}[], j=f), i=f)} minus f):
F:= proc(n) F(n):= map(g, F(n-1)) end: F(0):= {{1}}:
S:= proc(n) S(n):= map(x->x[], F(n)) end:
a:= proc(n) local k; for k from 0 while not(n in S(k)) do od; k end:
seq(a(n), n=1..110); # Alois P. Heinz, Sep 24 2012
|
|
|
CROSSREFS
|
Records are essentially A141414.
Cf. A003313 (shortest chain using just addition), A005245 (number of 1s using just addition and multiplication), A217032(n):=A173419(n!).
Sequence in context: A045430 A067693 A322006 * A099053 A230697 A322163
Adjacent sequences: A173416 A173417 A173418 * A173420 A173421 A173422
|
|
|
KEYWORD
|
nice,nonn
|
|
|
AUTHOR
|
Charles R Greathouse IV, Feb 17 2010, Apr 22 2010
|
|
|
STATUS
|
approved
|
| |
|
|
