The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 26 08:39 EDT 2020. Contains 334620 sequences. (Running on oeis4.)