

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(n1). 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. 584592.
F. Cucker, M. Shub, and S. Smale, Separation of Complexity classes in Koiran's weak model, Theoretical Computer Science 133:1 (1994), pp. 314.
W. DeMelo and B. F. Svaiter, The cost of computing integers, Proc. Amer. Math. Soc. 124 (1996), pp. 13771378.
P. Koiran, Valiant's model and the cost of computing integers, Comput. Complex. 13 (2004), pp. 131146.
Carlos Gustavo T. de A. Moreira, On asymptotic estimates for arithmetic cost functions, Proceedings of the American Mathematical Society 125:2 (1997), pp. 347353.
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. 4754.
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, ij, i*j}[], j=f), i=f)} minus f):
F:= proc(n) F(n):= map(g, F(n1)) 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



