Marshall University Math Colloquium

September 26, 2003

“Addition chains”

John Drost

Marshall University

Abstract

If n is a positive integer, an addition chain for n is a list of numbers beginning with 1 and ending with n so that each number is the sum of two previous numbers in the list. For example, an addition chain for 15 is 1, 2, 4, 8, 12, 14, 15, which has 6 links, but another is 1, 2, 3, 6, 12, 15 which has 5 links. Given n, what is the shortest chain for it?