login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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 lg n, where lg is the binary logarithm.

a(n) >= lg lg n + 1.

a(n) >= lg n/lg lg 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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 20 14:58 EST 2019. Contains 320327 sequences. (Running on oeis4.)