cp's OEIS Frontend

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

%I A173419 #67 Aug 06 2024 07:19:43
%S A173419 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,
%T A173419 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,
%U A173419 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
%N A173419 Length of shortest computation yielding n using addition, subtraction and multiplication (starting from 1).
%C A173419 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.
%C A173419 Shub & Smale ask if there is a c such that a(n!) <= (log n)^c for all n.
%C A173419 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).
%C A173419 Conjecture: if n is prime then a(n) >= a(n-1). The conjecture is true for n < 1800. - _Dmitry Kamenetsky_, Dec 26 2019
%D A173419 R. K. Guy, Unsolved Problems Number Theory, Sect. F26.
%H A173419 Alois P. Heinz, <a href="/A173419/b173419.txt">Table of n, a(n) for n = 1..1800</a>
%H A173419 Peter Borwein and Joe Hobart, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.119.07.584">The extraordinary power of division in straight line programs</a>, American Mathematical Monthly 119:7 (2012), pp. 584-592.
%H A173419 F. Cucker, M. Shub, and S. Smale, <a href="http://www6.cityu.edu.hk/ma/doc/people/smales/pap96.pdf">Separation of Complexity classes in Koiran's weak model</a>, Theoretical Computer Science 133:1 (1994), pp. 3-14.
%H A173419 W. DeMelo and B. F. Svaiter, <a href="http://www.ams.org/journals/proc/1996-124-05/S0002-9939-96-03173-5/S0002-9939-96-03173-5.pdf">The cost of computing integers</a>, Proc. Amer. Math. Soc. 124 (1996), pp. 1377-1378.
%H A173419 P. Koiran, <a href="http://perso.ens-lyon.fr/pascal.koiran/Publis/tau.springer.pdf">Valiant's model and the cost of computing integers</a>, Comput. Complex. 13 (2004), pp. 131-146.
%H A173419 Carlos Gustavo T. de A. Moreira, <a href="http://w3.impa.br/~gugu/GU.ps">On asymptotic estimates for arithmetic cost functions</a>, Proceedings of the American Mathematical Society 125:2 (1997), pp. 347-353.
%H A173419 Richard J. Mathar, <a href="/A173419/a173419.txt">Extended list of chain examples</a>
%H A173419 Michael Shub and Steve Smale, <a href="https://citeseerx.ist.psu.edu/pdf/a16554b6837219fab950b3628e6d5bc485565311">On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP = P"</a>, Duke Mathematical Journal 81:1 (1995), pp. 47-54.
%H A173419 Al Zimmermann's Programming Contests, <a href="http://azspcs.com/Contest/Factorials">Factorials</a>
%H A173419 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F A173419 a(n) <= 2 log_2(n).
%F A173419 a(n) >= log_2(log_2(n)) + 1.
%F A173419 a(n) >= log_2(n)/log_2(log_2(n)) for almost all n, as proved by Moreira (improving DeMelo & Svaiter).
%F A173419 a(n) <= A005245(n) <= A003313(n) <= A014701(n) <= 2*A000523(n). - _Charles R Greathouse IV_, Feb 07 2022
%e A173419 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.
%e A173419 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.
%p A173419 g:= f->seq(f union {t}, t={seq(seq({i+j, i-j, i*j}[], j=f), i=f)} minus f):
%p A173419 F:= proc(n) F(n):= map(g, F(n-1)) end: F(0):= {{1}}:
%p A173419 S:= proc(n) S(n):= map(x->x[], F(n)) end:
%p A173419 a:= proc(n) local k; for k from 0 while not(n in S(k)) do od; k end:
%p A173419 seq(a(n), n=1..110);  # _Alois P. Heinz_, Sep 24 2012
%Y A173419 Records are essentially A141414.
%Y A173419 Cf. A003313 (shortest chain using just addition), A005245 (number of 1s using just addition and multiplication), A217032(n):=A173419(n!).
%K A173419 nice,nonn
%O A173419 1,3
%A A173419 _Charles R Greathouse IV_, Feb 17 2010, Apr 22 2010