A076142

[Max]

franktaw at netscape.net wrote:
> Here's another incorrect conjecture (although this one is at least 
> marked as a conjecture).  This basically states that a totally additive 
> sequence (A064097) which is always >= the length of the shortest 
> addition chain (A003313), never exceeds it by more than 1.  

Where did you find that conjecture?
It was mentioned in the description of A003313 and A064097 some time ago but then was removed shortly after my letter (quoted below).

Max

-------- Original Message --------
Subject: conjecture for A064097 failed
Date: Thu, 21 Jul 2005 14:56:29 -0700
From: Max <relf at unn.ac.ru>
To: seqfan at ext.jussieu.fr
CC: Benoit Cloitre <abcloitre at modulonet.fr>

I believe that the conjecture
0<=A064097(n)-A003313(n)<=1
is half trivial and half wrong.

It trivially follows from the definition of A003313 that
0<=A064097(n)-A003313(n)

On the other hand, we can show that if
A064097(n) - A003313(n) = d
then
A064097(n^k) - A003313(n^k) >= k*d

 From the definition of A064097 it follows that
A064097(n^k) = k*A064097(n)

If 1=a_0, a_1, ..., a_m=n is the shortest addition chain for n (of length m), then there is a chain
1=a_0, a_1, ..., a_m=n,
a_{m+1}=n*a_1, ..., a_{2m}=n*a_{m}=n^2,
a_{2m+1}=n^2*a_1, ..., a_{3n}=n^2*a_{m}=n^3,
..., a_{km}=n^k
for n^k of length km.
Hence, A003313(n^k) <= k * A003313(n).

Therefore,
A064097(n^k) - A003313(n^k) >= k*A064097(n) - k*A003313(n) = k*d

In particular, since
A064097(23) - A003313(23) = 7 - 6 = 1
we have
A064097(23^2) - A003313(23^2) >= 2
contradicting the conjecture.
Actually, there is an addition chain
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 528, 529
implying A003313(23^2) <= 11 and
A064097(23^2) - A003313(23^2) >= 3.

Please remove the failed conjecture from A003313 and A064097 descriptions.
It also makes sense to add the inequality
A003313(n^k) <= k * A003313(n)
to A003313 description.

Thanks,
Max

%I A064097
%S A064097 0,1,2,2,3,3,4,3,4,4,5,4,5,5,5,4,5,5,6,5,6,6,7,5,6,6,6,6,7,6,7,5,7,6,7,
%T A064097 6,7,7,7,6,7,7,8,7,7,8,9,6,8,7,7,7,8,7,8,7,8,8,9,7,8,8,8,6,8,8,9,7,9,8,
%U A064097 9,7,8,8,8,8,9,8,9,7,8,8,9,8,8,9,9,8,9,8,9,9,9,10,9,7,8,9,9,8,9,8,9,8
%N A064097 A quasi-logarithm defined inductively by a(1) = 0 and a(p) = 1 + a(p-1) if p is prime and a(n*m) = a(n) + a(\
   m) if m,n > 1.
%C A064097 Note that this is the logarithm of a completely multiplicative function. - Michael Somos
%F A064097 Conjectures: for n>1, log(n) < a(n) < (5/2)*log(n); lim n ->infinity sum(k=1,n,a(k))/(n*log(n)-n) = C = 1.8(\
   4)....; 0<=A064097(n)-A003313(n)<=1. - Benoit Cloitre, Oct 30 2002.
%o A064097 (PARI) oo=200; an=vector(oo); a(n)=an[n]; for(n=2,oo,an[n]=if(isprime(n),1+a(n-1), sumdiv(n,p, if(isprime(p)\
   ,a(p)*valuation(n,p))))); for(n=1,100,print1(a(n)","))
%Y A064097 Similar to A061373 which uses the same recurrence relation but a(1) = 1.
%Y A064097 Cf. A003313, A076142, A076091, A061373, A005245.
%Y A064097 Sequence in context: A070241 A066412 A003313 this_sequence A014701 A056239 A100197
%Y A064097 Adjacent sequences: A064094 A064095 A064096 this_sequence A064098 A064099 A064100
%K A064097 nonn
%O A064097 1,3
%A A064097 Thomas Schulze (jazariel(AT)tiscalenet.it), Sep 16 2001
%E A064097 More terms from Michael Somos, Sep 25 2001




%I A003313 M0255
%S A003313 0,1,2,2,3,3,4,3,4,4,5,4,5,5,5,4,5,5,6,5,6,6,6,5,6,6,6,6,7,6,7,5,6,6,7,
%T A003313 6,7,7,7,6,7,7,7,7,7,7,8,6,7,7,7,7,8,7,8,7,8,8,8,7,8,8,8,6,7,7,8,7,8,8,
%U A003313 9,7,8,8,8,8,8,8,9,7,8,8,8,8,8,8,9,8,9,8,9,8,9,9,9,7,8,8,8,8
%N A003313 Length of shortest addition chain for n.
%C A003313 Equivalently, minimal number of multiplications required to compute n-th power.
%D A003313 Bahig, Hatem M.; El-Zahar, Mohamed H.; Nakamula, Ken; Some results for some conjectures in addition chains, \
   in Combinatorics, computability and logic, pp. 47-54, Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, Lon\
   don, 2001.
%D A003313 Bergeron, F.; Berstel, J.; Brlek, S.; Duboc, C.; Addition chains using continued fractions. J. Algorithms 10\
    (1989), 403-412.
%D A003313 D. Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory, Dissertation, ETH Zurich\
    1996.
%D A003313 D. Bleichenbacher and A. Flammenkamp, An Efficient Algorithm for Computing Shortest Addition Chains, Preprin\
   t, 1997.
%D A003313 Brauer, Alfred, On addition chains. Bull. Amer. Math. Soc. 45, (1939). 736-739.
%D A003313 Downey, Peter; Leong, Benton; Sethi, Ravi; Computing sequences with addition chains. SIAM J. Comput. 10 (198\
   1), 638-646.
%D A003313 Elia, M. and Neri, F.; A note on addition chains and some related conjectures, in Sequences (Naples/Positano\
   , 1988), pp. 166-181, Springer, New York, 1990.
%D A003313 P. Erdos, Remarks on number theory. III. On addition chains. Acta Arith. 6 1960 77-81.
%D A003313 A. Flammenkamp, Drei Beitraege zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable\
    Numbers, Diplomarbeit, Bielefeld 1991.
%D A003313 Gashkov, S. B. and Kochergin, V. V.; On addition chains of vectors, gate circuits, and the complexity of com\
   putations of powers [translation of Metody Diskret. Anal. No. 52 (1992), 22-40, 119-120; 1265027], Siberian Adv. Math\
   . 4 (1994), 1-16.
%D A003313 Gioia, A. A.; Subba Rao, M. V.; Sugunamma, M.; The Scholz-Brauer problem in addition chains. Duke Math. J. 2\
   9 1962 481-487.
%D A003313 Gioia, A. A. and Subbarao, M. V., The Scholz-Brauer problem in addition chains, II, in Proceedings of the Ei\
   ghth Manitoba Conference on Numerical Mathematics and Computing (Univ. Manitoba, Winnipeg, Man., 1978), pp. 251-274, \
   Congress. Numer., XXII, Utilitas Math., Winnipeg, Man., 1979.
%D A003313 Graham, R. L.; Yao, A. C. C.; Yao, F. F., Addition chains with multiplicative cost. Discrete Math. 23 (1978)\
   , 115-119.
%D A003313 D. E. Knuth, The Art of Computer Programming, vol 2, Seminumerical Algorithms, 3rd edition, 1998, p. 465.
%D A003313 McCarthy, D. P., Effect of improved multiplication efficiency on exponentiation algorithms derived from addi\
   tion chains. Math. Comp. 46 (1986), 603-608.
%D A003313 Olivos, Jorge, On vectorial addition chains. J. Algorithms 2 (1981), 13-21.
%D A003313 Schoenhage, Arnold, A lower bound for the length of addition chains. Theor. Comput. Sci. 1 (1975), 1-12.
%D A003313 Thurber, Edward G. The Scholz-Brauer problem on addition chains. Pacific J. Math. 49 (1973), 229-242.
%D A003313 Thurber, Edward G. On addition chains ... and lower bounds for c(r). Duke Math. J. 40 (1973), 907-913.
%D A003313 Thurber, Edward G., Addition chains and solutions of l(2n)=l(n) and l(2^n-1)=n+l(n)-1. Discrete Math. 16 (19\
   76), 279-289.
%D A003313 Thurber, Edward G., Addition chains-an erratic sequence. Discrete Math. 122 (1993), 287-305.
%D A003313 Thurber, Edward G., Efficient generation of minimal length addition chains. SIAM J. Comput. 28 (1999), 1247-\
   1263.
%D A003313 W. R. Utz, A note on the Scholz-Brauer problem in addition chains. Proc. Amer. Math. Soc. 4, (1953). 462-463\
   .
%D A003313 Vegh, Emanuel, A note on addition chains. J. Combinatorial Theory Ser. A 19 (1975), 117-118.
%D A003313 Whyburn, C. T., A note on addition chains. Proc. Amer. Math. Soc. 16 1965 1134.
%H A003313 Achim Flammenkamp, <a href="http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html">Shortest addition ch\
   ains</a>
%H A003313 E. W. Weisstein, <a href="http://mathworld.wolfram.com/AdditionChain.html">Link to a section of The World of\
    Mathematics (1).</a>
%H A003313 E. W. Weisstein, <a href="http://mathworld.wolfram.com/ScholzConjecture.html">Link to a section of The World\
    of Mathematics (2).</a>
%F A003313 It seems that for n>1 : ln(n) < a(n) < (5/2)*ln(n); lim n ->infinity sum(k=1,n,a(k))/(n*ln(n)-n) = C = 1.8(4\
   )....; 0<=A064097(n)-A003313(n)<=1. - Benoit Cloitre Oct 30 2002
%Y A003313 Cf. A003064, A003065, A005766.
%Y A003313 Sequence in context: A057935 A070241 A066412 this_sequence A064097 A014701 A056239
%Y A003313 Adjacent sequences: A003310 A003311 A003312 this_sequence A003314 A003315 A003316
%K A003313 nonn,nice
%O A003313 1,3
%A A003313 njas
%E A003313 More terms from Jud McCranie (j.mccranie(AT)adelphia.net), Nov 01 2001