Shortest Addition Chains

[Alec Mihailovs]

From: David Wilson 

DW> Can anyone help this person?
DW> I don't have my addition chain code any more.

From: Marco Tozzi 

MT> Hi, I'm an italian student, 
MT> I'm trying to find the shortest addition chain for 27782 
MT> (to calculate n^27782 with the fewest number of multiplications). 
MT> I found one addition chain of length 19 but I'm not sure this is 
MT> a shortest one. Could you help me?
MT> Thank you in advance.

The shortest chain has length 18. Here it is: 

1+1=2, 2+1=3, 3+3=6, 6+6=12, 12+12=24, 24+3=27, 27+27=54, 
54+54=108, 108+108=216, 216+1=217, 217+217=434, 
434+434=868, 868+868=1736, 1736+1736=3472, 
3472+3472=6944, 6944+6944=13888, 13888+3=13891, 
13891+13891=27782
 
Alec Mihailovs 
http://mihailovs.com/Alec/