conjecture for A064097 failed

Thu Jul 21 23:56:29 CEST 2005

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