A note on the Aiello–Subbarao conjecture on addition chains

Abstract

Given a positive integer x, an addition chain for x is an increasing sequence of positive integers 1 = c(0); c(1), ... , c(n) = x such that for each 1 <= k <= n, c(k) = c(i) + c(j) for some 0 <= i <= j <= k-1. In 1937, Scholz conjectured that for each positive integer x, l(2x-1) <= l(x)+x-1 where l(x) denotes the minimal length of an addition chain for x. In 1993, Aiello and Subbarao stated the apparently stronger conjecture that there is an addition chain for 2(x)-1 with length equals to l(x) + x-1. We note that the Aiello-Subbarao conjecture is not stronger than the Scholz (also called the Scholz-Brauer) conjecture.