Selected topics in addition chains

Date

1974

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

W. R. Utz conjectured that lowercase l = lowercase l + 1. D. Knuth found four counterexamples to Utz's conjecture. He then modified it to lowercase l > lowercase l and more generally lowercase l > lowercase l. This dissertation contains an infinite number of counterexamples to Knuth's modification of the Utz conjecture. A conjecture is proposed by this author that has the theorems of Utz, Subbarao, and Knuth concerning addition chains as corollaries: If lowercase l = lambda + k, then nu < 2[raised k]. Knuth introduced a sequence c, exhibited the first few terms of the sequence, and proposed an asymptotic limit theorem. In this paper an asymptotic limit theorem is proven for c: If lim (c(r))/([Phi][raised r]) = 1, then [Phi] = 2.

Description

Keywords

Citation