On addition chains and progress on the Scholz conjecture
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910079857459200 |
|---|---|
| author | Agama, Theophilus |
| author_facet | Agama, Theophilus |
| contents | In this paper, we develop some new classes of methods to study the Scholz conjecture on addition chains. It turns out that the exponents of numbers of the form $2^n-1$ largely determine the length of the shortest addition chain for the number that leads to $2^n-1$. Using the carry analysis, we obtain improved upper bounds for the length of the shortest addition chains $\ell(2^n-1)$ producing $2^n-1$. In particular, we show that if $2^n-1$ has carry of degree at most $$ κ(2^n-1)=\frac{1}{2}\left(\ell(n)-\left\lfloor\frac{\log n}{\log 2}\right\rfloor+\sum \limits_{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor}\left\{\frac{n}{2^j}\right\}\right) $$ then $$ \ell(2^n-1)\leq n+1+\sum \limits_{j=1}^{\lfloor\frac{\log n}{\log 2}\rfloor}\bigg(\left\{\frac{n}{2^j}\right\}-ξ(n,j)\bigg)+\ell(n) $$ for all $n\in \mathbb{N}$ with $n\geq 4$, where $\ell(\cdot)$ denotes the length of the shortest addition chain that leads to $\cdot$, $\{\cdot\}$ denotes the fractional part of $\cdot$ and where $ξ(n,1):=\{\frac{n}{2}\}$ with $ξ(n,2)=\{\frac{1}{2}\lfloor \frac{n}{2}\rfloor\}$ and so on. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_07720 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | On addition chains and progress on the Scholz conjecture Agama, Theophilus General Mathematics 11B83, 11Y16 In this paper, we develop some new classes of methods to study the Scholz conjecture on addition chains. It turns out that the exponents of numbers of the form $2^n-1$ largely determine the length of the shortest addition chain for the number that leads to $2^n-1$. Using the carry analysis, we obtain improved upper bounds for the length of the shortest addition chains $\ell(2^n-1)$ producing $2^n-1$. In particular, we show that if $2^n-1$ has carry of degree at most $$ κ(2^n-1)=\frac{1}{2}\left(\ell(n)-\left\lfloor\frac{\log n}{\log 2}\right\rfloor+\sum \limits_{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor}\left\{\frac{n}{2^j}\right\}\right) $$ then $$ \ell(2^n-1)\leq n+1+\sum \limits_{j=1}^{\lfloor\frac{\log n}{\log 2}\rfloor}\bigg(\left\{\frac{n}{2^j}\right\}-ξ(n,j)\bigg)+\ell(n) $$ for all $n\in \mathbb{N}$ with $n\geq 4$, where $\ell(\cdot)$ denotes the length of the shortest addition chain that leads to $\cdot$, $\{\cdot\}$ denotes the fractional part of $\cdot$ and where $ξ(n,1):=\{\frac{n}{2}\}$ with $ξ(n,2)=\{\frac{1}{2}\lfloor \frac{n}{2}\rfloor\}$ and so on. |
| title | On addition chains and progress on the Scholz conjecture |
| topic | General Mathematics 11B83, 11Y16 |
| url | https://arxiv.org/abs/2108.07720 |