A173419 Length of shortest computation yielding n using addition, subtraction and multiplication (starting from 1).

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

Offset: 1

Author

Charles R Greathouse IV, Feb 17 2010, Apr 22 2010

Keywords

• nice
• nonn

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

Examples

			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.
		

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

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!).

Programs

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

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).

a(n) <= A005245(n) <= A003313(n) <= A014701(n) <= 2*A000523(n). - Charles R Greathouse IV, Feb 07 2022