Shortest Addition Chains

[Alec Mihailovs]

Achim Flammenkamp's web page 

http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html

contains a link to a file add25.bits.gz (about 3.34MB) with 
2bit-packed numbers 0<=a(n)<=3 such that 

A003313(n) = floor(log_2(n)) + ceil(log_2(nu(n))) + a(n)

where nu(n) is the sum of digits of n in base 2; for n from 1 to 
2^25 = 33,554,432, calculated by Achim Flammenkamp and 
Neill Clift. 

When I wanted to check my calculations for n=27782, instead 
of modifying ddt.c (link on the web page cited above) , I used 
Python (in the interactive mode) and today I rewrote it as a 
Python script, 

#-----------lookup.py----------
from sys import argv
from struct import unpack
from math import log, floor, ceil
f=open("./add25.bits",'rb')
n=int(argv[1])-1
f.seek(n/4)
r=unpack('B',f.read(1))[0]
f.close()
a=(r>>2*(n%4))%4
n+=1
a+=floor(log(n,2))
u=0
while n>0:
    u+=n%2
    n=n>>1

print int(a+ceil(log(u,2)))
#-------------EOF-------------

It should be put in the same directory as the uncompressed 
add25.bits file (8MB). It can be run from the cmd in Windows 
(after cd to that directory, otherwise the path in f should be 
written in the full form) as 

python lookup.py 27782

for example, or with any other integer from 1 to 2^25 instead 
of 27782. 

I wonder if that could be incorporated in the OEIS in some form.
Perhaps, as a search form on the A003313 page.

Alec Mihailovs
http://mihailovs.com/Alec/