A086833

[Pfoertner, Hugo]

-----Original Message-----
From: David Wilson [mailto:davidwwilson at comcast.net] 
Sent: Thursday, March 23, 2006 12:38
To: Pfoertner, Hugo; seqfan at ext.jussieu.fr
Subject: Re: A086833


I would guess Hugo is correct in his interpretation that the sequence was 
intended to give the smallest final addend among the shortest addition
chains 
for n, which is a potentially interesting concept.  I presume the author is
not 
a native English speaker, which may account for the obscure description, and

that the example and value for a(23) are errors, a condition not unknown in
the 
OEIS.  It might be enlightening to compute the sequence of actual smallest 
final addends among minimal addition chains for n and compare this sequence
to 
the sequence given.

--------------------------

My problem with this is that I don't have a program that computes _all_
possible shortest addition chains for a given n. Donald Knuth's ACHAIN-ALL
(from http://www-cs-faculty.stanford.edu/~knuth/programs.html )
http://www-cs-faculty.stanford.edu/~knuth/programs/achain-all.w
computes only selected chains. Its comment says:
"@*Intro. This program, hacked from {\mc ACHAIN4}, finds all canonical
addition chains of minimum length for a given integer."

Taking the output of ACHAIN-ALL (using a length table computed by ACHAIN4) I
get the following values for the minimal final addend:

n=2: [1 2] -> 2-1=1
n=3: [1 2 3] -> 3-2=1
n=4: [1 2 4] -> 4-2=2
n=5: [1 2 4 5] -> 5-4=1
n=6: [1 2 3 6],[1 2 4 6] -> 6-4=2
n=7: [1 2 3 6 7], [1 2 4 6 7] -> 7-6=1
n=8: [1 2 4 8] -> 8-4=4
n=9: [1 2 3 6 9], [1 2 4 8 9] -> 9-8=1
n=10: [1 2 4 5 10], [1 2 4 8 10] -> 10-8=2
n=11: [1 2 3 4 8 11], [1 2 3 6 9 11], [1 2 4 5 10 11], [1 2 4 8 10 11] ->
11-10=1
n=12: [1 2 3 6 12], [1 2 4 6 12], [1 2 4 8 12] -> 12-8=4
n=13: [1 2 3 5 10 13], [1 2 3 6 12 13], [1 2 4 6 12 13], [1 2 4 8 12 13] ->
13-12=1
n=14: [1 2 3 6 7 14], ..., [1 2 4 8 12 14] -> 14-12=2
n=15: [1 2 4 5 10 15], [1 2 3 6 12 15] -> 15-12=3
n=16: [1 2 4 8 16] -> 16-8=8
n=17: [1 2 4 8 16 17] -> 17-16=1

The corresponding sequence would be 1 1 2 1 2 1 4 1 2 1 4 1 2 3 8 1 ...
If that had been the intent of the author at least the unique terms for
n=2^k should coincide. But A086833(2^k)=k instead of 2^(k-1). Therefore we
have to continue guessing ....

Hugo Pfoertner