Internal structure of addition chains: well-ordering

DOI10.1016/J.TCS.2017.12.002MaRDI QIDQ1704595zbMATH OpenOpenAlexFDO

Authors Harry Altman

Publication date 12 March 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.1627

zbMATH Keywords

addition chainswell-ordering

Mathematics Subject Classification ID

Other combinatorial number theory (11B75) Other number representations (11A67)

Abstract: An addition chain for $n$ is defined to be a sequence $(a_0,a_1,ldots,a_r)$ such that $a_0=1$, $a_r=n$, and, for any $1lekler$, there exist $0lei,j<k$ such that $a_k=a_i+a_j$; the number $r$ is called the length of the addition chain. The shortest length among addition chains for $n$, called the addition chain length of $n$, is denoted $ell(n)$. The number $ell(n)$ is always at least $lo{g}_{2}n$; in this paper we consider the difference $delt{a}^{e}ll(n):=ell(n)-lo{g}_{2}n$, which we call the addition chain defect. First we use this notion to show that for any $n$, there exists $K$ such that for any $kgeK$, we have $ell(2^{k}n)=ell(2^{K}n)+(k-K)$. The main result is that the set of values of $delt{a}^{e}ll$ is a well-ordered subset of $[0,infty)$, with order type $omeg{a}^{o}mega$. The results obtained here are analogous to the results for integer complexity obtained in [1] and [3]. We also prove similar well-ordering results for restricted forms of addition chain length, such as star chain length and Hansen chain length.

Recommendations

• scientific article; zbMATH DE number 4120283
• On Addition Chains¹
• Calculating optimal addition chains
• A study of some addition chain problems
• Remarks on number theory III. On addition chains

Cites work

• scientific article; zbMATH DE number 6696432 (Why is no real title available?)
• scientific article; zbMATH DE number 3677903 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 4120283 (Why is no real title available?)
• scientific article; zbMATH DE number 1568491 (Why is no real title available?)
• scientific article; zbMATH DE number 3080556 (Why is no real title available?)
• A Lower Bound for the Scholz-Brauer Problem
• A lower bound for the length of addition chains
• Arithmetic of ordinals with applications to the theory of ordered Abelian groups
• Calculating optimal addition chains
• Integer complexity and well-ordering
• Lower Bounds for Lucas Chains
• Numbers with integer complexity close to the lower bound
• On addition chains l(mn) 1 (n)-b and lower bounds for c(r)
• The Scholz-Brauer problem in addition chains
• The Scholz-Brauer problem on addition chains
• Zum Scholz-Brauerschen Problem.

Cited in

(5)

• Integer complexity: the integer defect
• On Addition Chains¹
• Integer complexity: algorithms and computational results
• Arithmetical self-similar compact sets
• Remarks on number theory III. On addition chains

Describes a project that uses

Uses Software

• Integer-Complexity

This page was built for publication: Internal structure of addition chains: well-ordering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704595)