Colloquium: “Addition chains”

Marshall University Math Colloquium
September 26, 2003

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?