# Upper Bounds on Integer Complexity

Joshua Zelinsky111The author is grateful for a variety of institutions
supporting this research Work on this paper occurred when the author was an
Assistant Professor at the University of Maine, a Visiting Professor at
Birmingham Southern College, and when the author was a Lecturer at Iowa State
University.

###### Abstract

Define $\|n\|$ to be the _complexity_ of $n$, which is the smallest number of
$1$s needed to write $n$ using an arbitrary combination of addition and
multiplication. John Selfridge showed that $\|n\|\geq 3\log_{3}n$ for all $n$.
Richard Guy noted the trivial upper bound that $\|n\|\leq 3\log_{2}n$ for all
$n>1$ by writing $n$ in base 2. An upper bound for almost all $n$ was provided
by Juan Arias de Reyna and Jan Van de Lune. This paper provides the first non-
trivial upper bound for all $n$. In particular, for all $n>1$ we have
$\|n\|\leq A\log n$ where $A=\frac{41}{\log 55296}$.

Hopkins School

<EMAIL_ADDRESS>
Define _complexity_ of $n$, the smallest number of $1$s needed to write
$\|n\|$ using an arbitrary combination of addition and multiplication. We’ll
write this as $\|n\|$. For example, the equation

$6=(1+1)(1+1+1)$

shows that $\|6\|\leq 5$ and in fact $\|6\|=5$. We will also refer to this
function as the integer complexity of $n$.

Integer complexity was first discussed by Kurt Mahler and Jan Popken in 1953
[10]. It was later popularized by Richard Guy [7], who includes it as problem
F26 in his _Unsolved Problems in Number Theory_ [8]. Since then, many other
authors have explored the behavior of this function, [12] especially Juan
Arias de Reyna [4] and Harry Altman [3].

John Selfridge showed that $\|n\|\geq 3\log_{3}n$ for all $n$ and noted that
this lower bound was achieved whenever $n$ was a power of $3$. Altman and the
author [3] classified numbers whose integer complexity was close to this lower
bound.

Guy noted the trivial upper bound that $\|n\|\leq 3\log_{2}n$ for all $n>1$ by
writing $n$ in base 2. Prior to this paper, work has been done on providing an
upper bound for all $n$ except for a set of density zero. Let $C_{a}$ be the
infimum of all $c$ such that, for almost all $n$, we have $\|n\|\leq c\log n$.
Obviously, any such set of density zero must contain $1$.

It is a folklore result that from writing $n$ in base $2$ one has

$C_{a}\leq\frac{5}{2\log 2}=3.6067\cdots.$

Subsequently, John Isbell [7] pointed out that writing $n$ in base 24 yields

$C_{a}\leq\frac{265}{24\log 24}=3.474\cdots$

It is believed based on numerical evidence that the actual maximum of
$\frac{\|n\|}{\log n}$ occurs at $n=1439$ where

$\frac{\|1439\|}{\log 1439}=\frac{26}{\log 1439}=3.575\cdots.$

Thus, Isbell’s result involves values of $c$ which require a non-trivial
exceptional set. Whether Isbell’s exceptional set is finite or infinite
remains an open problem.

By writing $n$ in base $2^{9}3^{6}$ Juan Arias de Reyna and Jan Van de
Lune[11], proved that

$C_{a}\leq\frac{15903451}{2^{9}3^{6}\log(2^{9}3^{6})}=3.320\cdots.$

Unfortunately, the computations needed to extend to larger bases are
difficult. It is unclear whether using larger bases in this fashion is moving
to a specific constant. Even if one assumes that they are moving towards on
some specific constant, it is unclear if this constant is $C_{a}$.

Recently, Katherine Cordwell, Alyssa Epstein, Anand Hemmady, Steven J. Miller,
Eyvindur Palsson, Aaditya Sharma, Stefan Steinerberger, and Yen Nhi Truong Vu
[6] improved on the bound on $C_{a}$ and also presented a more efficient
algorithm for calculating $\|n\|$. By writing $n$ in base $2^{11}3^{9}$, they
showed that

$C_{a}\leq\frac{2326006662}{2^{11}3^{9}\log(2^{11}3^{9})}.$

Define $C_{M}$ to be the smallest number such that for all $n>1$, we have
$\|n\|\leq C_{M}\log x$. From Guy’s trivial bound, one immediately has

$C_{M}\leq\frac{3}{\log 2}=4.32808\cdots.$

Improving this bound has been an open problem until this paper.

We prove:

######  Theorem 1.

For all $n>1$ we have $\|n\|\leq A\log n$ where

$A=\frac{41}{\log 55296}=3.7544\cdots$

Note that $\frac{41}{\log 55296}=3.7544\cdots$ whereas the bound from just
using base 3 has the constant $\frac{3}{\log 2}=4.32808$. This is a larger
improvement than it initially looks, since as noted earlier we actually cannot
do better than $\frac{\|1439\|}{\log 1439}=3.575\cdots.$ Thus, in a certain
sense, our result cuts by more than half the worst possible value for
$\sup_{n>1}{\|n\|{\log n}}$ given the interval in which it must live.

Our constant is, of course, much larger than that of de Reyna and Van de Lune
which is the price we must pay for having a bound that does not have any
exceptional set.

Note that our result also gives us the slightly weaker but somewhat prettier
bound of $\|n\|\leq\frac{19}{5}\log n$. These results are substantially weaker
than:

######  Conjecture 2.

For all $n>1$, one has $\|n\|/\log n\leq 26/(\log 1439)$, with equality
obtained only at $n=1439$.

It is likely that $C_{s}=\limsup\|n\|/\log n$ is substantially lower than even
$\frac{26}{1439}$ but how much lower is also an open problem. Guy asked if one
always has $\|2^{a}3^{b}\|=2a+3b$. If this is is true then we would have an
automatic lower bound of $C_{s}\geq\frac{2}{\log 2}$ since one would have

$\frac{\|2^{a}\|}{\log 2^{a}}=\frac{2a}{a\log 2}=\frac{2}{\log 2}.$

For some progress towards answering this question, see [3]. Note that the
obvious conjecture for primes other than $2$ or $3$ is false. For example, we
have

$\|5^{6}\|=29<30=6\|5\|,$

and

$\|11^{2}\|=15<16=2\|11\|.$

In both these cases, the unexpectedly low complexity is arising from $n-1$
having many small prime factors.

There is a similar problem in the literature where one defines complexity in a
way which allows subtractions in addition to multiplication and addition. In
that case, the best known bound is in [5], which obtains a bound lower than
our constant.

Let us now discuss our method of proof for Theorem 1. The classical upper
bound works simply by writing $n$ in base 2. One might try writing $n$ in a
different base, but doing so does not help by itself. If one writes $n$ in
base $3$, one gets an upper bound of $\frac{5}{\log 3}\log n=(4.551\cdots\log
n)$. If one tries a larger base the situation gets even worse. Perhaps
surprisingly, the bound one gets for a given base $b$ is not monotonic in $b$.
For example, since one can write $6=(1+1)(1+1+1)$, writing in base 6 gives a
slightly better constant than base 5. Base 5 gives a constant of
$\frac{9}{\log 5}=5.592\cdots$, whereas base 6 gives a constant of
$\frac{10}{\log 6}=5.581\cdots$. In general though, every base other than $2$
will give by itself a worse upper bound. Our tactic is to use multiple bases.
We will write $n$ in terms of each base and then switch bases at the opportune
moment as we are writing $n$ in terms of smaller numbers. We will have
multiple options for what order to switch bases, and we will show that at
least one order will always work. Our method of proof to make this productive
will be essentially inductive.

######  Definition 3.

We will write $S(\alpha,n)$ to mean the statement “If for all $1<k<n$,
$\|k\|\leq\alpha\log k$ then $\|n\|\leq\alpha\log n$.”

The statement $S(\alpha,n)$ amounts to the induction step of a proof that for
all $n>1$, $\|n\|\leq\alpha\log n$. The standard proof that
$\|n\|\leq\frac{3}{\log 2}\log n$ by writing $n$ in base $2$ then amounts to
proving $S(\frac{3}{\log 2},n)$ for all $n>1$ by checking two cases, $n\equiv
0$ (mod 2) and $n\equiv 1$ (mod 2). Note that for some values of $\alpha$ and
$n$, this statement will be vacuously true if the initial hypothesis is false.

To prove our main theorem, we will assume that $S(\alpha,n)$ fails for
$\alpha\geq\frac{41}{\log 55296}$, and by using our base-switching argument
derive a set of linear inequalities for $v_{p}(n+1)$ for various primes $p$,
where $v_{p}(m)$ is the $p$-adic valuation of $m$. One key interpretation is
that $v_{p}(n+1)$ is exactly how many digits of $p-1$ that $n$ ends in when
written in base $p$.

Before we prove our main theorem, we will prove a slightly weaker version of
the main theorem that uses only bases $2$ and base $3$. In particular we prove
the following:

######  Theorem 4.

If

$\alpha\geq\frac{5}{\log 2+\frac{1}{2}\log 3}$

then for all $n>1$ we have $\|n\|\leq\alpha\log n$.

The proof of Theorem 4 has the advantage of illustrating all the major ideas
of the main theorem, but since it has a lot fewer moving parts, it is
substantially easier to follow before we tackle the main theorem.

This paper is divided into seven sections:

The first section establishes basic preliminaries and notation needed.

The second section proves Theorem 4, a weaker version of our main theorem
which uses only bases 2 and 3. This weaker bound should make the general
method clear. In that section we will derive two inequalities under the
assumption that $S(\alpha,n)$ fails. One of the inequalities corresponds to
first reducing using base 2 and then switching to base 3 at the right time.
The other corresponds to first reducing using base 3 and then switching to
base 2 at the right time. The first inequality will give a lower bound for
$v_{2}(n+1)$ in terms of $v_{3}(n+1)$ and the second inequality will give a
lower bound for $v_{3}(n+1)$ in terms of $v_{2}(n+1)$. We will show that for a
specific choice of $\alpha$ the resulting pair of inequalities do not have a
solution, and so we conclude that the induction step always works. This
amounts essentially to saying that we can either get a reasonably efficient
representation of $n$ by either first writing $n$ in base 2 and then switching
to base 3 or doing the reverse. To make this work, we will also need some
slight understanding of what happens modulo 5.

The fact that these reductions work can be thought of as essentially observing
that $-1/3$ is purely periodic in the 2-adics with part $01$, and that $-1/2$
is purely periodic in the 3-adics with repeating part just $1$. If a reader
prefers a more concrete interpretation, one can instead read these as
statements about $1/3$ in base 2 and $1/2$ in base 3, since in general $-1/n$
in the $p$-adics has the same expansion as $1/n$ in base $p$.

Why do these quantities matter? Let’s say that we have a number $n$ which is
uncooperative at being reduced using obvious base reductions. The obvious way
that a number can be maximally uncooperative for being reduced by a given base
$b$ is if all the last few digits are $b-1$ when written in base $b$, so when
one is trying to write the number in terms of smaller numbers by repeatedly
subtracting and then dividing by $b$, one has to subtract the largest possible
amount. To make this situation more concrete, let us fix for now $b=3$. Then
this amounts to saying that $n$ when written in base $3$ looks like
$(\cdots)\cdots 22222$ where the $(\cdots)$ represents other digits. Now, it
may be that n is uncooperative in multiple bases so $n$ in base $2$ looks like
$(\cdots)\cdots 111$. Now, we might hope that subtracting 1 and dividing by 2
would give us a number that was nice in base 3, but we are not that lucky. If
we take $\frac{n-1}{2}$ and write in base $3$ we will find that it still ends
in just as many 2s as $n$ did. This can be thought of as arising from the fact
that in the 3-adics we have $\cdots 222=-1$.

But if we keep subtracting $1$ and dividing by $2$, eventually we will have an
even number (after we do this $v_{2}(n+1)$ times) and then we can divide by 2.
If we have a number in base $3$ that is even and looks like $(\cdots)\cdots
22222$ in base 3 and we divide it by 2 we will get a number which in base 3
looks like $(\cdots)\cdots 111$ which is great from a perspective of reducing
using base 3. Observing that $(\cdots)\cdots 22222$ when we divide by 2 gives
us $(\cdots)\cdots 111$ is essentially the same as noting that $\cdots
111=-1/2$ in the 3-adics (or equivalently that $1/2$ is $0.111\cdots$ in base
3). The situation will be similar in other bases since the $p$-adic expansion
of $-1$ is just the digit $p-1$ repeating, and one will get corresponding
reductions based on the behavior of those fractions. We have other similar
paths corresponding to other fractions.

The third section establishes the main theorem. This will use essentially the
same method as in the second section but our set of primes is now larger. We
will look at the set of primes $2,3,5,7,13,17$ and use those as our bases. As
in the proof of the weaker theorem we will also need a few specific results
about certain other moduli, in particular $p=11$ and $p=19$.

The fourth section examines how far we can push our framework if certain
simplifying assumptions are made and will implicitly use the ideas from the
fourth section. In particular, in all the results in the second and third
sections we need to engage in specific case checking for certain small values
of $v_{p}(n+1)$ as well checking certain finite modulo conditions. This
section will look at how for how low a value of $\alpha$ one can still get
$S(\alpha,n)$ if one is allowed to assume that $v_{p}(n+1)$ is as large as we
want for a finite collection of $p$ of our choice.

The fifth section looks at more broad connections to various questions about
$p$-adic expansions and related questions. The sixth section is an appendix
where the details of some proofs are included.

##  1 Preliminaries

We will write $S(\alpha,n)$ to denote the statement “If for all $1<k<n$,
$\|k\|\leq\alpha\log k$ then $\|n\|\leq\alpha\log n$.” Note that for some
values of $\alpha$ and $n$, this statement will be vacuously true if the
initial hypothesis is false.

Note that, for a fixed $\alpha$, proving $S(\alpha,n)$ for all $n$ would
constitute proving the inductive step in a proof that $C_{M}\leq\alpha$. If
for a given $\alpha$ we can show that $S(\alpha,n)$ holds for all $n$, we can
conclude that $C_{M}\leq\alpha$. This will be our plan of attack.

Since we have $\frac{\|1439\|}{\log 1439}=\frac{26}{\log 1439}$, we cannot
hope to get a result better than $\alpha=\frac{26}{\log 1439}$. Under this
basis, we will restrict $\alpha$ to the interval $I_{0}=[\frac{26}{\log
1439},\frac{3}{\log 2})$. The upper end of the interval $I_{0}$ is chosen
using that we already have just from the standard base 2 result that
$S(n,\alpha)$ holds for all $n>1$ and $\alpha=\frac{3}{\log 2}$. Restricting
$\alpha$ to this range will allow us to simplify the presentation and proofs
of some results. On occasion, we will implicitly use that $\alpha$ is in
$I_{0}$ even when we have not stated so explicitly. We’ll write
$I_{1}=[\frac{26}{\log 1439},\frac{5}{\log 2+\frac{1}{2}\log 3})$, and write
$I_{2}=[\frac{26}{\log 1439},\frac{25}{6\log 2+2\log 3})$. Note that $I_{0}$
contains $I_{1}$ which contains $I_{2}$. We will sometimes restrict further
the range of $\alpha$ where we show $S(n,\alpha)$ to these two intervals. In
those cases, we will do so after we have proving $S(n,\alpha)$ for all
$\alpha$ to the right of that interval’s end point. This will allow us to
simplify some of the theorems and proofs, since we will be able to avoid
breaking into as many cases; some results would have many distinct cases if we
looked at all $\alpha$ in the $I_{0}$ range.

We will write $v_{p}(m)$ to be the largest integer $k$ such that $p^{k}|m$. On
occasion, we will abuse this notation and use it when $p$ is not prime. We
will, in general, use $v_{p}$ without an argument to denote $v_{p}(n+1)$. We
will write $F(x)$ to be the maximum of $\|n\|$ over $n\leq x$. We will write
$[p,q]n$ to be $\frac{n-p}{q}$ and note that when this is an integer we have

$\|n\|\leq\|p\|+\|q\|+\|\frac{n-p}{q}\|\leq
F\left(\frac{n}{q}\right)+\|p\|+\|q\|.$

We will write compositions of the $[p,q]$ operator in the obvious way. For
example, we have

$[1,2][2,3]n=\frac{\frac{n-2}{3}-1}{2}.$

Similarly, we will write $[p,q]^{k}(n)$ to denote repeating $[p,q]$ $k$ times.
For example, if $n\equiv 7$ (mod $8$), we can write
$n=2(2(2([1,2]^{3}n)+1)+1)+1$ and would have then $\|n\|\leq\|[1,2]^{3}n\|+9$.

We will for convenience set $\|0\|=0$.

We will only use $[a,b]$ when $a$ is a non-negative integer and $b$ is a
positive integer. Given non-negative $x_{i}$ and positive $y_{i}$ for $1\leq
i\leq k$ we say that

$[x_{1},y_{1}][x_{2},y_{2}]\cdots[x_{k},y_{k}]m$

is a _path_ or _reducing path_ or _reduction_ of length $k$. We say that a
path is _valid_ if

$[x_{1},y_{1}][x_{2},y_{2}]\cdots[x_{k},y_{k}]m$

is a positive integer.

We can use this notation to make our earlier observation about the behavior of
$-1$ in the $p$-adics more rigorous. Let $F$ be a field and let $b$ be a non-
zero element of that field, then we note that

$[b-1,b](-1)=-1.$

This amounts to observing that when we repeatedly subtract $b-1$ and divide by
$b$ this does not alter the values of $v_{p}$ for any prime $p$ where
$(p,b)=1$. Equivalently, if we have integers $m$ and $b$, and $(b,m)=1$, then
$[b-1,b](-1)\equiv-1$ (mod $m$).

We will write that we have _used_ a path
$[x_{1},y_{1}][x_{2},y_{2}]\cdots[x_{k},y_{k}]m$ to mean we are writing $m$ in
terms of $[x_{1},y_{1}][x_{2},y_{2}]\cdots[x_{k},y_{k}]m$. Using a path will
always carry with it the implicit claim that the path is valid.

We say that a specific path written down without any variables is _fixed_. For
example, $[1,6]7$ is a valid, fixed path. $[2,4][1,3]16$ is a fixed, invalid
path (since $\frac{3}{4}$ is not an integer). We will refer to sets of paths
written down in terms of $v_{i}$ as _unfixed paths_ or _variable paths_. For
example, $[1,2]^{v_{2}-1}n$ is a variable path which is valid for all $n$.

Also, note that for any prime $p$ we have that $[p-1,]^{v_{p}}n\not\equiv p-1$
(mod $p$) since if it were we would have $n$ ending in $v_{p}+1$ digits that
are all $p-1$ when written in base $p$. We will refer to _burning_ a prime $p$
to mean doing $[p-1,p]$.

######  Lemma 5.

If $n$ is composite, $S(\alpha,n)$ holds for all $\alpha$.

###### Proof.

Assume $n$ is composite, and assume moreover, that for all $1<k<n$ we have
$\|k\|\leq\alpha\log k$. We may write $m|n$ where $1<m<n$. Thus,
$\|n\|\leq\|m\|+\|\frac{n}{m}\|\leq\alpha\log
m+\alpha\log\frac{n}{m}=\alpha\log n$. ∎

######  Lemma 6.

For all $1<n<2\cdot 10^{6}$, we have $\|n\|\leq\frac{26}{\log 1439}\log n$.

###### Proof.

This is just straightforward computation. ∎

The next lemma is a straightforward calculation. Although it looks technical,
it essentially just says that we can bound a number’s complexity by writing it
in terms of repeatedly subtractions and divisions.

######  Lemma 7.

Assume that $k=[x_{\ell},y_{\ell}]\cdots[x_{1},y_{1}]n\geq 1$ is a valid
reduction and that for $1<k<n$ we have $\|k\|\leq\alpha\log k$, then

$\|n\|\leq\alpha\log\frac{n}{y_{1}y_{2}\cdots
y_{\ell}}+\sum_{j=1}^{\ell}(\|y_{k}\|+\|x_{k}\|)=\alpha\log
n+\sum_{j=1}^{\ell}(\|y_{k}\|+\|x_{k}\|-\alpha\log y_{j}).$

###### Proof.

We assume that $[x_{\ell},y_{\ell}]\cdots[x_{1},y_{1}]$ is a valid reduction
of $n$, and we will induct on $\ell$ to prove the above inequality. The
equality on the right hand of the above is trivial.

First assume that $\ell=1$. Then $k=[x_{1},y_{1}]n\geq 1$. Therefore
$n=ky_{1}+x_{1}$.

If $k=1$, $\|n\|\leq\|y_{1}\|+\|x_{1}\|$. Since $x_{1}\geq 0$ and $k\geq 1$ we
have $n\geq y_{1}$ so that $\log\frac{n}{y_{1}}\geq 0$, and the result
follows.

If $k>1$, since $y_{1}\geq 2$, we have $n>k$ and we have

$\|n\|\leq\|y_{1}\|+\|x_{1}\|+\|k\|\leq\|y_{1}\|+\|x_{1}\|+\alpha\log k.$

We have also $n\geq ky_{1}$ so that $k\leq n/y_{1}$ and the result follows.

We proceed by induction. Let $m=[x_{1},y_{1}]n$, by the hypothesis of
induction

$\|m\|\leq\alpha\log\frac{m}{y_{2}\cdots
y_{\ell}}+\sum_{j=2}^{\ell}(\|y_{k}\|+\|x_{k}\|).$

We have $n=my_{1}+x_{1}$, therefore

$\|n\|\leq\|y_{1}\|+\|x_{1}\|+\|m\|.$

Since $n\geq my_{1}$ we obtain

$\log\frac{m}{y_{2}\cdots y_{\ell}}\leq\log\frac{n}{y_{1}y_{2}\cdots
y_{\ell}}.$

Combining our inequalities we get

$\|n\|\leq\|y_{1}\|+\|x_{1}\|+\alpha\log\frac{n}{y_{1}y_{2}\cdots
y_{\ell}}+\sum_{j=2}^{\ell}(\|y_{k}\|+\|x_{k}\|),$

which is what we wanted to prove. ∎

Lemma 7 essentially amounts to a general process of writing $n$ in terms of
smaller values of the $[p,q]$ operator. Note that the straightforward method
of calculating $\|n\|$ is not the same as running through all possible valid
options in applying the above lemma and then taking the smallest value. Our
lemma above essentially does not take into account the small amount of
subtraction we are doing actually does give us a smaller number to work with.
Equivalently, the above lemma ignores that when building up a number,
additions increase the size of the number slightly.

Lemma 7 does not include the case $[x_{\ell},y_{\ell}]\cdots[x_{1},y_{1}]n=0$.
In this case the conclusion is not necessarily true with the difficulty
connected to the fact that $\log 0$ is not defined.

Note that this problem happens only for a unique particular value of $n$ if we
fix the chain of operators because

$x_{\ell}=k=[x_{\ell-1},y_{\ell-1}]\cdots[x_{1},y_{1}]n$

implies

$n=y_{1}(\cdots(y_{\ell-2}(y_{\ell-1}k+x_{\ell-1})+x_{\ell-2})\cdots)+x_{1}.$

We will often need to check values of this sort separately.

There are two broad categories of results required for the main theorem. The
first set, “definite” results, are statements of the form $S(\alpha,n)$ for
some range of $\alpha$ and for $n$ satisfying some finite set of conditions of
the form $n\equiv k$ (mod $m$) or within some fixed finite range and always
using valid fixed paths. These will most of the time, be a statement of the
form $v_{p}\geq c$ for some specific prime $p$ and value $c$. These cannot be
used by themselves to improve upon the $\|n\|\leq 3\log_{2}n$ bound since they
will always have exceptional moduli. Generally, the definite results will have
a modulo condition that will be of the form $n\not\equiv-1$ (mod $m$) for some
$m$.

The second type of results we need, “indefinite”, are results that look at
$v_{p}(n+1)$ for various fixed primes $p$ and use variable paths. These
results can be thought of as being equivalent to various statements about the
p-adic representations of certain specific fractions. Each indefinite result
represents one possible reducing path which will give rise to one of our
inequalities. Essentially, what we show is that given that the $v_{p}$ are
large enough, at least one of the reductions corresponding to a indefinite
result will be efficient enough for our purposes. The definite results will
then handle the set of $n$ where the $v_{p}$ are too small to allow the
reductions in the indefinite results.

In general, the definite results are not very interesting but are a necessary
foundation. They require many individual cases but demonstrate little in the
way of actual structure. For convenience, we will label definite results as
lemmata. We will label indefinite results as propositions when stated in terms
of general $\alpha$ in a large interval. When we restrict these propositions
to $\alpha>K$ will be labeled as corollaries. Some of the definite results are
very similar, and in those cases we will restrict some of them to an appendix.
We will reserve the word Theorem for results of the form “For all $n\geq 1$,
$\|n\|\leq\alpha\log n$ or of the form “For sufficiently large $n$,
$\|n\|\leq\alpha\log n$.”

There is one subtlety that is a problem for both definite and indefinite
results: there may be a small finite set of cases that one needs to check
where the path in question is not valid due to hitting 0, as discussed above.
For example, if one wants to use the path $[1,3]n$ on all positive integers
$n\equiv 1$ (mod $3$), then one will run into problems at $n=1$. Thus one will
frequently need to check that the relevant small values of $n$ satisfy one’s
desired bound when the path fails to be valid. Unfortunately, for indefinite
results, the same problem arises but one does not, in general, have a finite
list to test. The solution here is to insist on additional congruence
restrictions on $n$ which ensure that at no time has one reduced too far. The
details of this should be made clear in the first few results of where they
come up, but we will not include these details in all the proofs.

##  2 The weak version of the theorem

In this section we will prove Theorem 4.

Note that $\frac{5}{\log 2+\frac{1}{2}\log 3}=4.204\cdots$ whereas simply
using base 2 yielded a constant of $\frac{3}{\log 2}=4.328\cdots$. Thus, this
weaker version of our main theorem is already stronger than the previously
known bound.

We will now derive the inequalities needed to prove this result:

######  Lemma 8.

For $n>1$, $\alpha\geq\frac{6}{\log 6}=3.34886\cdots$ and $S(\alpha,n)$ fails,
then we have $v_{2}\geq 1$ and $v_{3}\geq 1$.

###### Proof.

Direct computation establishes this for $n=2$ or $n=3$. We may thus assume
that $n\geq 4$. If $v_{2}=0$ then we have $2|n$ and so our earlier lemma about
composites apply. Thus, we may assume that $v_{2}\geq 1$. Assume then that
$v_{3}=0$. If $n\equiv 0$ (mod 3), then we may again use our composite lemma.
Thus, we may assume that $n\equiv 1$ (mod 3). Thus we can use the path
$[1,6]n$ and since

$\frac{\|6\|+\|1\|}{\log 6}=\frac{6}{\log 6}$

we have $n=1+6\frac{n-1}{6}$ and so

$\|n\|\leq\|1\|+\|6\|+\|\frac{n-1}{6}\|\leq
1+5+\alpha\log\frac{n}{6}=6-\alpha\log 6+\alpha\log n\leq\alpha\log n.$

∎

We will not go through this level of detail in later lemmata but will instead
simply note the relevant paths and generally leave the raw calculation out.

######  Lemma 9.

For $n>1$, if $\alpha\geq\frac{5}{\log 4}=3.60\cdots$ and $S(\alpha,n)$ fails,
then $v_{2}\geq 2$.

###### Proof.

Assume that $v_{2}=1$. The hypothesis $v_{2}=1$ allows us to assume that
$n\equiv 1$ (mod 4) and $n>1$. Thus we use the path $[1,4]n$. ∎

######  Lemma 10.

For $n>1$ if $\alpha\geq\frac{5}{\log 4}$ and $S(\alpha,n)$ fails then either
$v_{2}\geq 3$ or $v_{3}\geq 2$.

###### Proof.

Assume as given, and assume that $v_{2}=2$ and $v_{3}=1$. We thus have
$n\equiv 2$ (mod 3). and $n\equiv 3$ (mod 8). We then we have $n\equiv 3$ or
$11$ (mod 16). In the first case, we may take the reduction path
$[1,8][1,2]n$. We can check that $\|8\|+\|2\|+\|1\|+\|1\|\leq\frac{5}{\log
4}\log(16)$. Similarly, in the second case, we have either $n\equiv 2$ (mod 9)
or $n\equiv 5$ (mod 9). If $n\equiv 2$ (mod 9), we have either $n=11$ which
works or we have the path $[1,18][1,4]1,2]n$ which can be easily seen to be
valid and works for this value of $\alpha$. If $n\equiv$ (5 mod 9), we need to
break it down into two further cases: $n\equiv$ 11 (mod 32) or $n\equiv 27$
(mod 32). If $n\equiv 11$ (mod 32) we may use $[1,12][1,4][1,2]n$ which is
sufficient. If $n\equiv 27$ (mod 32) we either have $n=59$ or we may use
$[1,6][1,6][1,4][1,2]n.$ ∎

We also have the following slightly stronger lemma that we don’t need but is
worth noting:

######  Lemma 11.

For $n>1$, $\alpha\geq\frac{11}{\log 24}=3.46124\cdots$ and $S(\alpha,n)$
fails, then $v_{2}\geq 2$.

###### Proof.

We may assume that $n\equiv 2$ mod 3 since otherwise $v_{3}=0$, which would
trigger Lemma 8. Since $v_{2}=1$ we must have $n\equiv 1$ (mod 4) and so we
have $n\equiv 1$ (mod 8). or $n\equiv 5$ (mod 8). If $n\equiv$ (1 mod 8), we
may use $[1,8]n$. If $n\equiv 5$ (mod 8), either $n=5$ or we may use
$[1,6][1,4]n$ . ∎

######  Lemma 12.

For $n>1$ if $\alpha\geq\frac{15}{\log 60}=3.66359\cdots$ and $S(\alpha,n)$
fails, then $v_{5}\geq 1$.

###### Proof.

We may assume $n\equiv 1,2,$ or $3$ (mod 5). We may also assume that
$v_{2}\geq 2$ and $v_{3}\geq 1$.

Case I: $n\equiv 1$ (mod 5). Then we use the path $[1,3][1,10]n$.

Case II: $n\equiv 2$ (mod 5). We have two subcases, the case of $b=1$ and
$b>1$.

Case IIa: $v_{3}=1$. We may then assume $v_{2}\geq 3$ (or the previous lemma
triggers). So we have $n\equiv 7$ (mod 8) and $n\equiv 2$ or $5$ (mod 9). If
$n\equiv 2$ (mod 9) we may use $[2,45]n$. If $n\equiv 5$ (mod 9), and $n\equiv
7$ (mod 16) we then use $[1,6][1,4][1,2][2,15]n$ If $n\equiv 5$ (mod 9) and
$n\equiv 15$ (mod 16) we may then use $[1,8][1,2][2,15]n$

Case IIb: $v_{3}\geq 2$. So we have $n\equiv 8$ (mod 9).
We may then use $[1,6][2,15]n$.

Case III: $n\equiv 3$ (mod 5). We may then use $[1,3][1,10][1,2]n$.
∎

One might want to improve the above lemma to allow $\alpha\geq\frac{5}{\log
4}$ but there does not seem to be any obvious path to do so. IIa and III
prevent this improvement. Improving this lemma might allow us to get
correspondingly tighter bounds on the next few lemmata.

We now begin our indefinite results:

######  Proposition 13.

If $S(\alpha,n)$ fails, $v_{2}\geq 1$, $v_{3}\geq 1$ and $v_{5}\geq 1$, then

$(3-\alpha\log 2)v_{2}>(\alpha\log 3-4)v_{3}+(\alpha\log 2-2).$

###### Proof.

We may assume that $v_{2}\geq 1$, $v_{3}\geq 1$, $v_{5}\geq 1$ and assume that
$S(\alpha,n)$ fails for some $\alpha$. We note that $[0,2][1,2]^{v_{2}}n$ will
have $v_{3}$ 1s at the end of its base-3 expansion. Thus, we may use the
reduction

$\|n\|\leq\|[1,3]^{v_{3}}[0,2][1,2]^{v_{2}}n\|+3v_{2}+4v_{3}+2.$

So we have

$\alpha\log
n<\|n\|\leq\alpha\log(\frac{n}{3^{v_{3}}2^{v_{2}+1}})+3v_{2}+4v_{3}+2,$

and so we have

$\alpha\log n<\alpha\log n-(\alpha\log 3)v_{3}-(\alpha\log
2)(v_{2}+1)+3v_{2}+4v_{3}+2$

which forces $(\alpha\log 3-4)v_{3}+\alpha-2<(3-\alpha\log 2)v_{2}$.

∎

The above proof essentially amounts to using the fact that $\frac{-1}{2}$ in
the $3$-adics is $\cdots 111$ (equivalently, that $1/2$ has expansion
$0.111\cdots$ in base 3), along with the facts that $n\equiv-1$ (mod)
$3^{v_{3}}$, and $[1,2](-1)=-1$. Thus, repeatedly applying $[1,2]$ doesn’t
alter how the number is behaving mod $3^{v_{3}}$, but $3$-adically $-1=\cdots
2222$ to the resulting number must have at least $v_{3}$ 2s in its base 3
expansion, which when we do a $[1,4]$ then turns into $v_{3}$ 1s at the start
of the base 3 expansion.

We can improve the above proposition since at the end of the reduction we can
use either $[0,3]$ or $[2,15]$ since we know that the number at that stage is
not $1$ (mod 3) since we have exhausted all the $v_{3}$, and $-1/2\equiv 2$
(mod 5). We note that, that the worse case is scenario here is that we use the
$[2,15]$ (which is always a weaker reduction than $[0,3]$ We then obtain:

######  Proposition 14.

If $S(\alpha,n)$ fails, $v_{2}\geq 1$, $v_{3}\geq 1$ and $v_{5}\geq 1$, then

$(3-\alpha\log 2)v_{2}>(\alpha\log 3-4)v_{3}+\alpha\log 6-5.$

Here the $\alpha\log 6-5$ term comes from adding $\alpha\log 2-2$ and
$\alpha\log 3-3$ This result is slightly stronger than the earlier result, and
will be necessary in the proof of the weak version of the theorem since we
want a linear inequality in $\alpha$ which has a positive constant term for
the range of $\alpha$ we care about.

Similarly, we obtain:

######  Proposition 15.

Assume that $v_{2}\geq 3$, $v_{3}\geq 1$, $v_{5}\geq 1$, and $S(n,\alpha)$
fails for some $\alpha\in I_{0}$. Then:

$\left(5-\alpha\log 3\right)v_{3}>\left(2\alpha\log
2-5\right)\lfloor\frac{v_{2}-1}{2}\rfloor+\alpha\log 6-6$

###### Proof.

We have $\|n\|\leq\|[2,3]^{v_{3}}n\|+5v_{3}$. Note that $k=[2,3]^{v_{3}}n$ is
either $1$ (mod $3$) or $0$ (mod $3$). If $k$ is $0$ (mod 3), then we have

$\|k\|\leq\|[1,4]^{\lfloor v_{2}/2\rfloor}[0,3]k\|+5\lfloor v_{2}/2\rfloor+3.$

This gives rise to the inequality

$\left(2\alpha\log 2-5\right)\lfloor\frac{v_{2}}{2}\rfloor+\alpha\log
3-3<\left(5-\alpha\log 3\right)v_{3}.$

If $k$ is $1$ (mod 3) we instead have

$\|k\|\leq\|[1,4]^{\lfloor(v_{2}-1)/2\rfloor}[1,6]k\|+5\lfloor(v_{2}-1)/2\rfloor+6.$

This gives rise to the inequality

$\left(2\alpha\log 2-5\right)\lfloor\frac{v_{2}-1}{2}\rfloor+\alpha\log
6-6<\left(5-\alpha\log 3\right)v_{3}.$

We note that the first inequality is always stricter than the second as long
as we have $\alpha<\frac{3}{\log 2}$ which we can assume since otherwise we
cannot have $S(n,\alpha)$ fail at all.

Thus, in either case we have the desired inequality. Note that $v_{5}\geq 1$
ensures that the paths in question are always valid. ∎

The above result can be thought of as essentially arising from $-1/3$ having
$2$-adic representation $01$ repeating; note that $[1,4]$ is the same as
$[0,2][1,2]$ which corresponds to our $01$ repeating part in the 2-adic
expansion and is equivalent to saying that if a number $k$ divisible by 3 ends
in $m$ 1s in base 2 then $k/3$ will have look like $(\cdots)\cdots
0101010101$.

One can easily see from the above propositions that one has a contradiction if
$S(\alpha,n)$ fails and $\alpha\geq\frac{5}{\log 2+\frac{1}{2}\log 3}$. Thus
one can conclude simply from the above using base 2 and base 3 that for all
$n>1$ we have

$\|n\|\leq\frac{5}{\log 2+\frac{1}{2}\log 3}\log n.$

A few remarks: We have three types of “gadgets” that we will use in our
indefinite reductions. The above proof shows examples of two of those types.
The first type is an “initial gadget” which allows us to go from doing an
inefficient reduction at the beginning of the form $[p-1,p]^{v_{p}}$ to an
actually helpful reduction, generally but not always, of the form
$[1,p+1]^{x}$ for some x dependent on some set of primes and exactly what form
of gadget we used. In our above example of the reductions in Proposition 15,
our initial gadget is the pair of reductions of either $[0,3]$ or $[1,6]$
depending. We will write initial gadgets as [I].

Our next gadget is a “final gadget” which use a small but finite set of
remaining primes at the end after a series of reductions. In Proposition 14
our final gadget $[F]$ takes on the values either $[0,3]$ or $[2,15]$.

Final gadgets are necessary because for many of our reductions, the initial
gadget used will be somewhat inefficient, and so without the final gadget, the
constant in the resulting linear inequality will be weak. Squeezing out a
small amount of efficiency from the final gadgets allows us to mitigate and
sometimes remove this issue. Unfortunately, the final gadgets are sometimes
ugly and make our resulting inequalities harder to follow. Readers are
encouraged to read through the final gadgets, but to be aware that they are
not really structural in any deep sense.

In this context, we can rewrite the essence of the proof of Proposition 15 by
saying that we have the reduction

$[1,4]^{e}[I][2,3]^{v_{3}}n$

where $[I]$ is the initial gadget that is either $[0,3]$ or $[1,6]$ and then
we choose $e$ to do as much $[1,4]$ reduction as we can. Using the our earlier
terminology, we could say that the essence of Proposition 15 is to repeatedly
burn $3$ followed by an initial gadget allowing us to do repeated $[1,4]$
reduction.

There is a third type of gadget, a “transition gadget” which will be used
later and does not show up in this simple proof. Essentially, sometimes we
will exhaust doing one sort of efficient reduction, and then want to switch to
doing a more efficient reduction. An example of this below occurs in
Proposition 30 where after exhausting repeated $[1,3]$ reduction we go to
$[1,5]$ reduction. We shall call these gadgets “transition gadgets” and denote
them with $[T]$. The most common transition gadget will be ones which allow us
to use an extra $[0,2]$ reduction, allowing us to switch from doing $[1,q]$
reductions to $[1,2q-1]$ reduction. We will discuss this gadget more when it
occurs in Proposition 30 below.

For both the initial and transition gadget, maximizing their efficiency will
be critical to having small enough constants. The next section of this paper
will address a related question: what happens when $v_{2}$ is assumed to be
sufficiently large? This will allow us to address what happens if we can both
ignore the need for definite results and ignore the efficiency of our gadgets
and merely care about their existence (and thus ignore final gadgets
completely).

The above illustrates the essential method. We will use the same method to
prove the main theorem, but will do so by relying on a larger number of bases
and and frequently will also require checking special cases as well.

The basic method of many lemmata is similar enough to that above that we will
not include all the details; in some cases, we will include the proofs in the
Appendix.

##  3 The proof of the main theorem

In this section we will prove Theorem 1.

######  Lemma 16.

If $\alpha\geq\frac{18}{\log 135}=3.669\cdots$, and $S(\alpha,n)$ fails, then
$v_{3}\geq 2$.

###### Proof.

Given the earlier lemmata, we may assume that $v_{2}\geq 3$. So $n\equiv 7$
(mod 8). Similarly, we may assume that $n\equiv 4$ (mod 5). We may assume that
$v_{3}1$ and thus must have either $n\equiv 2$ (mod 9) or $n\equiv 5$ (mod 9).

Case I: $n\equiv 2$ (mod 9) In this case, we have either $n\equiv 2,11$ or
$20$ (mod 27). If $n\equiv 2$ (mod 27) then we use $[2,27]$. If $n\equiv 11$
(mod 27) then we use $[1,12][2,9]$. If $n\equiv 20$ (mod 28) then we depending
on whether $[1,6][1,4][2,9]n$ is even or odd we either use $[1,12][1,4][2,9]n$
or $[1,10][1,6][1,4][2,9]n$.

Case II: $n\equiv 5$ (mod 9). So $n\equiv 5,14$ or $23$ (mod 27) If
$\|n\|\equiv 5$ (mod 27), then we may use $[1,18][2,3]n$. If $n\equiv 14$ (mod
27) then we may use $[1,15][1,3][2,3]n$. If $n\equiv 23$ (mod 27) then
depending on the parity of $[1,12][1,6][2,3]n$ we use either
$[1,24][1,6][2,3]n$ or $[1,10][1,12][1,6][2,3]n$. ∎

######  Lemma 17.

If $\alpha\geq\frac{29}{\log 2304}=3.7456\cdots$ and $S(\alpha,n)$ fails, then
$v_{2}\geq 6$,.

###### Proof.

We may assume that $v_{5}\geq 1$, and $v_{3}\geq 2$.

We may write $n$ in terms of one of the following reductions depending on
$k=[1,4][1,2]^{v_{2}-1}(n)$ (mod 4):

Case I: If $k\equiv 1$ (mod 4), we may use the reduction

$[1,3][1,12][1,4][1,2]^{v_{2}-1}(n).$

Case II: If $k\equiv 2$ (mod 4), we may use the reduction

$[1,10][1,6][1,3][1,4][1,2]^{v_{2}-1}(n).$

Case III: If $k\equiv 3$ (mod 4), we may use the reduction

$[1,3][1,10][1,6][1,4][1,2]^{v_{2}-1}(n).$

Case IV: If $k\equiv 0$ (mod 4), we may use the reduction

$[1,12][1,3][1,4][1,2]^{v_{2}-1}(n).$

∎

The next two lemmata have very similar proofs and have the proofs included in
the appendix.

######  Lemma 18.

If $\alpha\geq\frac{29}{\log 2304}=3.7456\cdots$ and $S(\alpha,n)$ fails, then
$v_{7}\geq 1$.

Through similar logic we obtain:

######  Lemma 19.

If $\alpha\geq\frac{29}{\log 2304}=3.7456\cdots$ and $S(\alpha,n)$ fails then
$v_{13}\geq 1$.

The proof is again the Appendix

######  Lemma 20.

Assume $\alpha\geq\frac{29}{\log 2304}=3.7456\cdots$ and that $S(\alpha,n)$
fails. Then $v_{3}\geq 3$.

###### Proof.

Given the above, we may assume that $v_{2}\geq 6$, $v_{5}\geq 1$, $v_{7}\geq
1$, and $v_{13}\geq 1$, We may assume that $v_{3}=2$. Thus, we have either
$[2,3][2,3]n\equiv 0$ or $1$ (mod 3). First, assume that $[2,3][2,3]n\equiv 0$
(mod 3) consider $k=[1,4]^{3}[2,9][2,3]n$. If $k$ is even we may use
$[0,4][1,4]^{3}[2,9][2,3]n$. If $k$ is odd we may use one of
$[1,4]^{4}[2,9][2,3]n$ and $[1,10][1,2][1,4]^{3}[2,9][2,3]n$.

Now assume that $[2,3][2,3]n\equiv 1$ (mod 3). Look at
$k=[1,4]^{i}[1,6][2,3][2,3]n$, where $i$ is as large as possible (and thus is
at least 3). Note that $k\not\equiv 1$ (mod 4). Consider then the
possibilities for $k$ (mod 4).

Case I: $k\equiv 2$ (mod 4) Then we may use
$[1,14][0,2][1,4]^{3}[1,6][2,3][2,3]n$.

Case II: $k\equiv 3$ (mod 4). Then we may use
$[1,7][1,10][1,2][1,4]^{3}[1,6][2,3][2,3]n$.

Case III: $k\equiv 0$ mod 4. Then we may use
$[1,13][0,4][1,4]^{3}[1,6][2,3][2,3]n$.

∎

######  Lemma 21.

If $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$ and $S(\alpha,n)$ then
$v_{2}\geq 8$.

###### Proof.

We may assume that $v_{3}\geq 3$, $v_{5}\geq 1$, and that $v_{7}\geq 1$.

Set $k=[1,4][1,2]^{v_{2}-1}n$. Consider $k$ (mod 4). We have four cases:

Case I: $k\equiv 0$ (mod 4) we may use $[1,3][1,9][1,16][1,2]^{v_{2}-1}n$

Case II: $k\equiv 1$ (mod 4) we may use $[1,9][1,12][1,4][1,2]^{v_{2}-1}n$

Case III $k\equiv 2$ (mod 4) we may use
$[1,3][1,9][1,10][1,8][1,2]^{v_{2}-1}n$.

Case IV: $k\equiv 3$ (mod 4) we may use
$[1,9][1,10][1,6][1,4][1,2]^{v_{2}-1}n$.

Note that the first two cases above are the current worst case scenarios. ∎

We can now use the above lemmata and a similar sort of logic to obtain:

######  Lemma 22.

If $\alpha\geq\frac{41}{\log 55296}=3.7544$, $S(\alpha,n)$ fails, then
$v_{11}\geq 1$.

######  Lemma 23.

Assume $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$ and that $S(\alpha,n)$
fails. Then $v_{3}\geq 4$.

###### Proof.

Given the above, we may assume that $v_{2}\geq 7$, $v_{5}\geq 1$, $v_{7}\geq
1$, and $v_{13}\geq 1$ $[2,3]^{3}n\equiv 0$ or $1$ (mod 3).

Assume that $[2,3]^{3}n\equiv 1$ (mod 3) (the situation where it is 0 (mod 3)
is nearly identical and a little easier). Look at
$k=[1,4]^{i}[1,6][2,3][2,3]n$, where $i$ is as large as possible (and thus is
at least 3). Note that $k\not\equiv 1$ (mod 4). Consider then the
possibilities for $k$ (mod 4).

Case I: $k\equiv 2$ (mod 4) Then we may use
$[1,13][1,14][0,2][1,4]^{3}[1,6][2,3]^{3}n$ where $[A]$ is one of $[1,26]$,
$[0,4]$ or $[1,10][0,2]$.

Case II: $k\equiv 3$ (mod 4). Then we may use
$[B][1,10][1,2][1,4]^{3}[1,6][2,3]^{3}n$ where $[B]$ is one of $[1,26][0,2]$,
$[0,4]$ or $[1,13][1,14]$.

Case III: $k\equiv 0$ mod 4. Then we may use
$[1,13][0,4][1,4]^{3}[1,6][2,3]^{3}n$.

∎

We may now prove:

######  Lemma 24.

If $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$ and $S(\alpha,n)$ then
$v_{2}\geq 10$.

###### Proof.

We may assume that $v_{3}\geq 4$ and $v_{5}\geq 1$.

Set $k=[1,4][1,2]^{v_{2}-1}n$. Consider $k$ (mod 4). We will write $[A]$ to be
one of $[0,2]$ or $[1,22]$ We have four cases:

Case I: $k\equiv 0$ (mod 4) we may use $[1,9][1,9][1,16][1,2]^{v_{2}-1}n$.

Case II: $k\equiv 1$ (mod 4) we may use
$[A][1,3][1,9][1,12][1,4][1,2]^{v_{2}-1}n$.

Case III $k\equiv 2$ (mod 4) we may use
$[A][1,3][1,9][1,10][1,8][1,2]^{v_{2}-1}n$.

Case IV: $k\equiv 3$ (mod 4) we may use
$[A][1,3][1,9][1,10][1,6][1,4][1,2]^{v_{2}-1}n$.
∎

######  Lemma 25.

If $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$ and $S(\alpha,n)$ fails,
then $v_{19}\geq 1$.

The proof is in the appendix.

######  Lemma 26.

Assume that $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$. Assume that
$S(\alpha,n)$ fails. Then $v_{5}\geq 2$.

###### Proof.

We may assume that $v_{3}\geq 3$ and that $v_{p}\geq 1$ for $p=7$, $11$, $13$,
$19$. We may assume that $v_{2}\geq 8$ (In fact may use that $v_{2}\geq 9$ but
we will not need it here.)

We now assume that $v_{5}=1$, and consider cases:

Case I: $n\equiv 4$ (mod 25). We may then take $[1,6]^{3}[4,25]n$.

Case II: $n\equiv 9$ (mod 25). We may then take $[1,6]^{3}[4,25][1,2]n$.

Case III: $n\equiv 14$ (mod 25). We have two scenarios depending on whether
$v_{3}-1\geq v_{2}$ or not. If $v_{3}-1\geq v_{2}$, then we have $v_{3}\geq 8$
and so we may take $[1,6]^{8}[4,25][2,3]n$.

If $v_{3}-1\leq v_{2}$ we may instead use $[1,16][A][1,6]^{i}[4,25][2,3]n$.
Here $i=v_{3}-1$ and then $[A]$ is either $[0,3]$ or $[2,33]$. We are using
here that $[1,6]^{i}[4,25][2,3]n$ cannot be $1$ mod 3.

Case IV: $n\equiv 19$ (mod 25). The argument for Case IV is nearly identical
to that of Case III.

∎

This next lemma is not strictly speaking needed, but it is useful when
checking the larger base reductions, and was used to make some of the
computations more efficient.

######  Lemma 27.

If $p$ is an odd prime and $p\leq 10^{6}$, and $p|n-1$ then $S(\alpha,n)$ for
all $\alpha\geq\frac{9}{\log 12}=3.62\cdots$ .

###### Proof.

Assume as given. Note that by direct computation we have
$n<\frac{5}{2}\log_{2}n$ for all $1<n\leq 2\cdot 10^{6}+1$. So we may assume
that $n$ is prime and $n>2\cdot 10^{6}+1$. Earlier results prove the desired
claim for $p=2,3,5,7$ and we may assume that $n\equiv 2$ (mod 3) and $n\equiv
3$ (mod 4). If $p=11$ then we may use the reduction $[1,6][1,22]n$. So we may
assume that $p\geq 13$.

First consider the case when $p\equiv 2$ (mod 3). Then $p\geq 17$ and we have

$n=2p\left(6[1,6]\left(\frac{n-1}{2p}\right)+1\right)+1.$

Thus, we have $\|n\|\leq F\left(\frac{n}{12p}\right)+\|p\|+7$. Thus, we have
$\|n\|\leq\alpha\log_{2}\frac{n}{12p}+\frac{5}{2}\log_{2}p+7\leq\alpha\log_{2}n-\alpha\log_{2}p+\frac{5}{2}\log_{2}p+7-\alpha\log_{2}12$.
So
$\|n\|\leq\alpha\log_{2}(n)+(\frac{5}{2}-\alpha)\log_{2}p+7-\alpha\log_{2}12$.
The right hand side of this last inequality is bounded by $\alpha\log_{2}n$
when $\alpha\geq\frac{\frac{5}{2}\log_{2}17+7}{\log_{2}17+\log_{2}12}$ which
is less than $\frac{9}{\log_{2}12}$.

Now, consider the case when $p\equiv 1$ (mod 3). Then we have

$n=2p\left(\frac{n-1}{2p}\right)+1$

and can use a $[1,6]$ reduction on $p$. Then we have
$\|n\|\leq\|[1,2p]n\|+\|[1,6]p\|+9\leq\alpha\log_{2}\frac{n}{2p}+\alpha\log_{2}\frac{p}{6}+9=\alpha\log_{2}n+9-\alpha\log_{2}12\leq\alpha\log_{2}n$
with this last inequality valid when $\alpha\geq\frac{9}{\log_{2}12}$ ∎

We can with a little work present a version of Proposition 14 which is tighter
for the range of $\alpha$ we care about:

######  Proposition 28.

Assume that $S(\alpha,n)$ fails for some $\alpha\in I_{0}$. Assume further
$v_{2}\geq 1$, $v_{3}\geq 1$, $v_{5}\geq 1$, $v_{7}\geq 1$, $v_{11}\geq 1$,
and $v_{13}\geq 1$. Then

$(3-\alpha\log 2)v_{2}>(\alpha\log 3-4)v_{3}+\alpha\log 2-2+C_{1}(\alpha).$

Here $C_{1}(\alpha)$ = $\alpha\log 2730-28$ when $x\in[\frac{26}{\log
1439},\frac{7}{\log 7})$, and $C_{1}(\alpha)=\alpha\log 390-21$ when
$\alpha\in[\frac{7}{\log 7},\frac{3}{\log 2}).$

###### Proof.

Assume that $S(\alpha,n)$ fails for some $\alpha$. We have

$\|n\|\leq\|[1,3]^{v_{3}}[1,4][1,2]^{v_{2}-1}n\|+3v_{2}+4v_{3}+2.$

Set $k=[1,3]^{v_{3}}[1,4][1,2]^{v_{2}-1}n$ and note that $k$ is not $1$ (mod
3) since we have exhausted all the digits which were $1$ in base 3, since
there were exactly $v_{3}$ of them. We have then the following congruence
restrictions on $k$:

  * •

$k\equiv 0$ or $2$ (mod 3).

  * •

$k\equiv 2$ (mod 5). This is because $[1,4][1,2]^{v_{2}-1}n\equiv 2$ (mod
$5$), and the operator $[1,3]$ sends $2$ (mod 5) to $2$ (mod 5). Equivalently,
this is because $-1/2\equiv 2$ (mod 5). By similar logic we have:

  * •

$k\equiv 3$ (mod 7).

  * •

$k\equiv 5$ (mod 11).

  * •

$k\equiv 6$ (mod 13).

Note that this is sufficient to get that $k\geq 2502$. Now,if $k$ is $0$ (mod
3) then we can write $k$ itself in terms of either $[1,13][1,14][0,3]k$ or
$[1,13][0,6]k$ depending on whether $k$ is even or odd. If $k$ is $2$ mod 3,
then we can instead write $k$ in terms of $\ell=[2,15]k$, and then as before
do either $[1,13][1,14]\ell$ or $[1,13][0,2]\ell$ to the end. Writing the
complete reduction out we have the reduction

$[F][1,3]^{v_{3}}[I][1,2]^{v_{2}}n$

where our initial gadget $[I]=[0,2]$ and our final gadget $[F]$ is one of
$[1,13][1,14][0,3]$, $[1,13][0,6]k$, $[1,13][1,14][2,15]$, or
$[1,13][0,2][2,15]$. We then have under the assumption that $S(\alpha,n)$
fails that

$\alpha\log 3^{v_{3}}2^{v_{2}+1}+f(\alpha)\leq 4v_{3}+3(v_{2}-1)+5$ (1)

where $f(\alpha)$ is the contribution of the final gadget. Counting the
contributions of each possible option for our final gadget and labeling them
$f_{i}(\alpha)$ for $i=1,2,3,4$. We have then:

$\begin{split}f_{1}(\alpha)&=\alpha\log 78-14+(\alpha\log 7-7)\\\
f_{2}(\alpha)&=\alpha\log 78-14\\\ f_{3}(\alpha)&=\alpha\log
78-14++(\alpha\log 5-7)\\\ f_{4}(\alpha)&=\alpha\log 78-14++(\alpha\log
35-14).\end{split}$ (2)

We note that we do not need to include a given final gadget piece when
reducing with a given $\alpha$ if the corresponding $f_{j}(\alpha)$ is
negative. Thus we may take

$C_{1}(\alpha)=\min(\max(f_{1}(\alpha),0),\max\left(f_{2}(\alpha),0),\max(f_{3}(\alpha,0)),\max(f_{4}(\alpha),0)\right).$

A straightforward calculation then determines that $C_{1}(\alpha)$ takes on
the values claimed.

∎

The level of detail we have gone in the proof above is higher than we will
generally go into in similar results below.

From Proposition 28 we have

######  Corollary 29.

Assume that $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$, and that
$S(\alpha,n)$. Then

$v_{2}>0.31349v_{3}+5.03429.$ (3)

###### Proof.

Simply plug in $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$ into Proposition
28. ∎

######  Proposition 30.

Assume that $S(\alpha,n)$ fails for some $\alpha$ and $v_{2}\geq 2$,
$v_{3}\geq 1$, $v_{5}\geq 1$, and $v_{7}\geq 1$.

$(3-\alpha\log 2)v_{2}>(\alpha\log 3-4)v_{3}+(\alpha\log
5-6)v_{5}+C_{2}(\alpha).$

Here $C_{2}(\alpha)=2\alpha\log 2-4$ when $\alpha\in[\frac{26}{\log
1439},\frac{4}{\log 3}]$, and $C_{2}(\alpha)=\alpha\log\frac{4}{3}$ when
$\alpha\in[\frac{4}{\log 3},\frac{3}{\log 2})$.

###### Proof.

We may assume that $v_{2}\geq 2$, $v_{3}\geq 1$ and $v_{5}\geq 1$, $v_{7}\geq
1$ and we then can use the following reductions:

$[1,5]^{v_{5}}[T][1,3]^{v_{3}-1}[0,2][1,2]^{v_{2}}n$

where $[T]$ is the transition gadget which is either $[0,2][1,3]$ or $[0,2]$.
Note that in this case we are corresponding $p$-adic expansions are that
$-1/2$ is 1-repeating in the $3$-adics and that $-1/4$ is 1-repeating in the
$5$-adics. We wish to see that this reduction is valid. Set
$m=[1,2]^{v_{2}}(n)$. One has that $v_{p}(m)=v_{p}$ for any odd prime $p$, and
particularly for $p=3$ and $p=5.$ We note that $m$ is even, and so the
$k=[0,2]m$ is valid. This will now be a number which ends in $v_{3}$ 1s in
base 3, and $v_{5}$ 2s in base 5. We then have $\ell=[1,3]^{v_{3}-1}k$ is
valid and will still end in $v_{5}$ 2s in base 5. We want to be able to divide
by 2 again, so we use our transition gadget of either $[0,2][1,3]$ or $[0,2]$
depending on whether $\ell$ is even or odd. The resulting number then ends in
$v_{5}$ $1$s in base 5, and so the final $[1,5]^{v_{5}}$ is valid. We use that
$v_{7}\geq 1$ to insure that the number we eventually reduce to is at least 1.

One may then verify that the constant for $C_{2}(\alpha)$ gives each worst
case scenario corresponding to the given range of $\alpha$.

∎

We will not in general, go through the same level of detail in later results
of stating explicitly how all the base aspects are preserved except in some
non-obvious cases.

As before we gain an explicit version for our a given range of $\alpha$:

######  Corollary 31.

If $S(\alpha,n)$ fails for some $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$
then we have

$v_{2}>0.31349v_{3}+0.1069v_{5}+2.71627.$ (4)

We also have:

######  Proposition 32.

Assume that $S(\alpha,n)$ fails. Assume further that $v_{2}\geq 1$, $v_{3}\geq
3$, $v_{5}\geq 2$, and $v_{7}\geq 1$. Then

$(3-\alpha\log 2)v_{2}>(2\alpha\log
3-7)\lfloor\frac{v_{3}-3}{2}\rfloor+(\alpha\log 5-6)v_{5}+C_{3}(\alpha).$

Here $C_{3}(\alpha)$ is as follows: $C_{3}(\alpha)=\alpha\log 24-10$, when
$\alpha\in[\frac{26}{\log 1439},\frac{4}{\log 3}]$, $C_{3}(\alpha)=3\alpha\log
2-6$ when $\alpha\in(\frac{4}{\log 3},\frac{6}{\log 5}],$ and
$C_{3}(\alpha)=\alpha\log(8/5)$ when $\alpha\in(\frac{6}{\log 5},\frac{3}{\log
2})$.

###### Proof.

The proof uses the reduction scheme
$[1,9]^{e}[T][1,5]^{v_{5}-1}[I][1,2]^{v}_{2}n$. Here we have $[I]$ is the
initial gadget either $[0,4]$ or $[1,6][0,2]$. We have for the transition
gadget $[T]$ either $[0,2]$ or $[0,2][1,5]$. Here we have
$e=\lfloor(v_{3}-1)/2\rfloor$ (we need the -1 in $e$ since we may have used a
3 in the in our initial gadget). Following that the reductions are valid uses
logic similar to that in the previous proposition. We use that $v_{7}\geq 1$
to insure that the number we eventually reduce to is at least 1.

∎

From Proposition 32 and Proposition 15 as well as our lower bounds on $v_{2}$,
$v_{3}$, $v_{5}$, $v_{7}$ we obtain:

######  Theorem 33.

Assume $\alpha\geq\frac{25}{6\log 2+2\log 3}$. Then for all $n>1$, we have
$\|n\|\leq\alpha\log n$.

###### Proof.

This proof is the same method as with Theorem 4, but with our strengthened
Proposition 32 being used also. ∎

We may then using Theorem 33 always assume in all subsequent results that we
have $\alpha\in I_{2}$.

From Proposition 32, we obtain:

######  Corollary 34.

Assume that $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$ Assume further that
$S(\alpha,n)$ fails. Then

$v_{2}>1.57093v_{3}+0.1069v_{5}+1.29586.$ (5)

######  Lemma 35.

Assume that $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$, and that
$S(\alpha,n)$ fails. Then $v_{17}>1$.

The proof is in the Appendix.

We can now give a slightly tighter version of Proposition 32 by instead making
our final gadget $[F]$ one of the following: $[1,34][0,2]$,
$[2,33][1,17][0,2]$, $[1,51][0,2]$, $[1,6][1,17][0,2]$, $[1,19][1,6]$,
$[0,3]$, $[2,51]$. To see that all cases are covered, let $k$ be our number
right before the final gadget. Note that at least one of the first four
reductions will work for any given even k depending on (k mod 8), so we may in
the last three options for our final gadget assume that $k$ is odd. Then we do
each of the three others based on $k$ (mod 3). (We will use similar logic for
later final gadgets but will not in general explicitly list every modulus used
in a case by case breakdown.) We then obtain:

######  Proposition 36.

Assume that $S(\alpha,n)$ fails for some $\alpha\in I_{2}$. Assume also that
$v_{2}\geq 1$, $v_{3}\geq 3$, $v_{5}\geq 2$, $v_{7}\geq 1$, $v_{11}\geq 1$,
$v_{13}\geq 1$, $v_{17}\geq 1$, $v_{19}\geq 1$. Then

$(3-\alpha\log 2)v_{2}>\frac{2\alpha\log 3-7}{2}v_{3}+(\alpha\log
5-6)v_{5}+C_{4}+C_{5}.$

Here $C_{4}=\alpha\log(8/15)+3$ when $\alpha\in(\frac{26}{\log
1439},\frac{6}{\log 5}]$, and $C_{4}=\alpha\log(8/3)-3$ when
$\alpha\in(\frac{6}{\log 5},\frac{25}{6\log 2+2\log 3})$.

Here $C_{5}=\alpha\log 51-14$ when $\alpha\in(\frac{26}{\log
1439},\frac{11}{\log 17}]$, and $C_{5}=\alpha\log 3-3$ when
$\alpha\in(\frac{11}{\log 17},\frac{25}{6\log 2+2\log 3})$.

(Here for readability we have split $C_{4}$ which arises from our initial and
transition gadgets and $C_{5}$ which arises from our final gadget.)

As usual, we get a corollary from this:

######  Corollary 37.

Assume that $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots\cdots$ and that
$S(\alpha,n)$ fails. Then

$v_{2}>1.57093v_{3}+0.1069v_{5}+4.04879.$ (6)

We can use the above Proposition, together with the fact that $S(\alpha,n)$
fails in our range then $v_{3}\geq 4$ and $v_{5}\geq 2$ to conclude that:

######  Lemma 38.

If $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$, and $S(\alpha,n)$ fails,
then $v_{2}\geq 11$.

We would like to be able to use the construction from Proposition 36 to get
that $v_{2}\geq 12$, but that construction by itself is insufficient to reach
that conclusion. We will present a similar version which has a slightly
modified final gadget which is optimized near our choice of $\alpha$:

######  Proposition 39.

Assume that $S(\alpha,n)$ fails for some $\alpha\in I_{2}$. Assume further
that $v_{2}\geq 1$, $v_{3}\geq 3$, $v_{5}\geq 2$, $v_{7}\geq 1$, $v_{11}\geq
1$, $v_{13}\geq 1$, $v_{17}\geq 1$, and $v_{19}\geq 1$. Then

$(3-\alpha\log 2)v_{2}>\frac{2\alpha\log 3-7}{2}v_{3}+(\alpha\log
5-6)v_{5}+C_{4}+C_{5}.$

Here $C_{4}=\alpha\log(8/15)+3$ when $\alpha\in(\frac{26}{\log
1439},\frac{6}{\log 5}]$, and $C_{4}=\alpha\log(8/3)-3$ when
$\alpha\in(\frac{6}{\log 5},\frac{25}{6\log 2+2\log 3})$. $C_{6}=\alpha\log
1071-25$ when $\alpha\in[\frac{26}{\log 1439},\frac{11}{\log 17}]$, and
$C_{6}=\alpha\log 63-14$ when $\alpha\in[\frac{11}{\log 17},\frac{26}{6\log
2+2\log 3}]$.

###### Proof.

The construction is identical to that of the proof for Proposition 36 but with
the following changes. We extend the final gadget $[0,3]$ to one of
$[1,6][0,3]$, $[0,9]$ or $[2,21][0,3]$. Similarly, we extend $[2,51]$ to one
of $[0,3][2,51]$, $[2,21][2,51]$ or $[1,6][2,51]$. We extend
$[2,33][1,17][0,2]$ with either to do either $[1,4][2,33][1,17][0,2]$ or
$[1,14][1,2][2,33][1,17][0,2]$. Our entire tail list then is:

$[1,34][0,2]$, $[1,4][2,33][1,17][0,2]$, $[1,14][1,2][2,33][1,17][0,2]$,
$[1,51][0,2]$, $[1,6][1,17][0,2]$, $[1,19][1,6]$, $[1,6][0,3]$, $[0,9]$,
$[2,21][0,3]$, $[0,3][2,51]$, $[2,21][2,51]$ or $[1,6][2,51]$. The worst case
situations for this new final gadget then are $[2,21][0,3]$, and
$[2,21][2,51]$

∎

We then have

######  Corollary 40.

Assume that $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots\cdots$ and that
$S(\alpha,n)$ fails. Then

$v_{2}>1.57093v_{3}+0.1069v_{5}+5.6271.$ (7)

From which we immediately get:

######  Lemma 41.

If $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots\cdots$ and that
$S(\alpha,n)$, then $v_{2}\geq 13$.

This now allows us to prove:

######  Lemma 42.

If $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$, and $S(\alpha,n)$ fails,
then $v_{7}\geq 2$.

###### Proof.

We may assume that $v_{2}\geq 12$, $v_{3}\geq 4$, $v_{5}\geq 2$, $v_{7}\geq
1$, $v_{11}\geq 1$, $v_{13}\geq 1$, $v_{17}\geq 1$, and $v_{19}\geq 1$.

Case I: $n\equiv 6$ (mod 49). We may use the reduction $[1,8]^{3}[6,49]n$.

Case II: $n\equiv 13$ (mod 49). We may use the reduction
$[1,4][1,8]^{3}[6,49][1,2]n$

Case III: $n\equiv 20$ (mod 49). We may use the reduction

$[1,8]^{4}[6,49][2,3]n$.

Case IV: $n\equiv 27$ (mod 49). We may use the reduction
$[F][2,15]^{2}[1,8]^{3}[6,49][1,2]^{2}n.$
Here $[F]$ is one of $[0,2]$, $[1,4]$ or $[1,22][1,2]$

Case V: $n\equiv 34$ (mod 49). We may use different reductions based on
$k=[1,8]^{i}[6,49][5,4]n$. Here $i$ is the maximum number of times we may
apply $[1,8]$, noting that $i$ is at least 4, and that $k$ is not $1$ (mod 8).
If $k\equiv 0$ (mod 2) then we may use the reduction
$[1,19][1,3][1,15][0,2][1,8]^{i}[6,49][5,4]n$,

So we may assume that $k$ is odd. If $k\equiv 1$ (mod 4), then since $k$
cannot be $1$ (mod 8), we may use

or $[1,15][1,18][1,4][1,8]^{i}[6,49][5,4]n$

We may then assume that $k\equiv 3$ (mod 4).

If $k\equiv 3$ (mod 4), we may use one of

$[2,57][1,176][1,2][1,8]^{i}[6,49][5,4]n$,

$[1,114][1,88][1,2][1,8]^{i}[6,49][5,4]n$,

$[2,57][1,44][1,2][1,8]^{i}[6,49][5,4]n$,

or $[1,30][1,22][1,2][1,8]^{i}[6,49][5,4]n$.

Case VI: $n\equiv 41$ (mod 49).

We may then take $[1,9][1,4][1,8]^{3}[6,49][2,3][1,2]n$.

∎

We now turn to bounding $v_{3}$ from below.

######  Proposition 43.

Assume that $\alpha\in I_{2}$ and $S(\alpha,n)$ fails. Assume further that
$v_{3}\geq 1$, $v_{5}\geq 2$, $v_{7}\geq 1$, $v_{11}\geq 1$, $v_{17}\geq 0$,
$v_{19}\geq$. Assume there are integers $i_{5}$ and $i_{7}$ such that $2\leq
i_{5}\leq v_{5}$ and $0\leq i_{7}\leq v_{7}$, and that $v_{2}\geq
2i_{7}+i_{5}+7$. Then we have:

$v_{3}>(\alpha\log 28-11)i_{7}+(\alpha\log 10-8)i_{5}+(\frac{\alpha\log
4-5}{2})(v_{2}-2i_{7}-i_{5}-4)+C_{11}+C_{12}.$ (8)

Here $C_{11}=\alpha\log 19-11$ if $\alpha\in[\frac{26}{\log
1439},\frac{11}{\log 19}]$ or $C_{11}=0$ when $\alpha\in(\frac{11}{\log
19},\frac{25}{6\log 2+2\log 3}]$. Here $C_{12}=\alpha\log 459-\frac{39}{2}$.

###### Proof.

Assume as given. We will use the reduction

$[F][1,28]^{i_{7}}[T_{2}][1,10]^{i_{5}-1}[T_{1}][1,4]^{e_{i}}[I][2,3]^{v_{3}}n.$

We have $[I]$ is either $[0,3]$ or $[1,6]$. We have
$e_{i}=\lfloor\frac{v_{2}-i_{5}-2i_{7}-j-4}{2}\rfloor$ where $j=1$ if we used
in $[I]$ and $j=0$ if we used $[0,3]$. We have $[T_{2}]$ is either $[0,3]$
$[0,3][1,4]$, or $[0,3][1,4]^{2}$. $[T_{2}]$ then is one of
$[0,3][1,10][2,19]$, $[0,3][2,19]$, or $[0,3][1,10]$. Our final gadget $[F]$
has multiple parts. We will write $[F]=[F_{2}][F_{1}]$. $[F_{1}]$ is either
empty or if we had $[T_{2}]=[0,3][1,10][2,19]$ or $[T_{2}]=[0,3][1,10]$ and is
$[2,55]$ otherwise. $[F_{2}]$ is either $[1,17][1,4]$, or is $[1,34][1,4]$; we
can do the second whenever $v_{2}-i_{5}-2i_{7}-j-4$ is odd. Changing which of
$[T_{2}]$ options is our worst case scenario contributes the constant term of
$C_{11}$, while the rest of our gadgets contribute the $C_{12}$ term.

∎

######  Corollary 44.

Assume that $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$, and that
$S(\alpha,n)$ fails. Assume there are positive integers $i_{5}$ and $i_{7}$
such that $1\leq i_{5}\leq v_{5}$ and $1\leq i_{7}\leq v_{7}$, and that
$v_{2}\geq 2i_{7}+i_{5}+7$ Then

$1.49171i_{7}+0.61976i_{5}+0.11694v_{2}+3.54325.$ (9)

######  Lemma 45.

If $S(\alpha)$ fails for some $\frac{41}{\log 55296}=3.7544\cdots$, then
$v_{3}\geq 9$, and $v_{2}\geq 22$. Under the same assumption we also have
$v_{2}\geq v_{3}+11$.

###### Proof.

We repeatedly apply Corollary 44 with $i_{5}=2$, $i_{7}=2$ along with 7 using
that we must have integer values for $v_{2}$ and $v_{3}$. We first use to
conclude that $v_{3}\geq 9$. We then conclude that $v_{2}\geq 20$, and so
conclude that $v_{3}\geq 10$, and thus $v_{2}\geq 22$. We apply again
Corollary 44 to gain the last inequality. ∎

We are now in a position where we can bound $v_{5}$ from below.

######  Proposition 46.

Assume that $\alpha\in I_{2}$. Assume that $v_{3}\geq 1$, $v_{5}\geq 1$,
$v_{7}\geq 1$, $v_{11}\geq 2$, $v_{2}\geq v_{3}+11$, and that $S(\alpha,n)$
fails. Then we have

$(9-\alpha\log 5)v_{5}\geq C_{13}+C_{14}+C_{15}+\frac{\alpha\log
16-9}{4}(v_{2}-v_{3})+(\alpha\log 6-6)v_{3}.$

Here, $C_{13}=\frac{11}{4}-\alpha\log\frac{16}{5}$, $C_{14}=\alpha\log 33-13$,
and $C_{15}=\alpha\log 114-17$.

###### Proof.

We perform the following reduction:

$[F][1,16]^{e_{2}}[T][1,6]^{e_{3}}[I][4,5]^{v_{5}-1}.$

Here,

$[I]$ is the initial gadget given by one of $[4,25]$, $[4,25][1,2]$,
$[4,25][2,3]$ or $[4,5][1,2][1,2]$.

We then have $e_{3}$ is ten as large as possible; we’ll have $e_{3}=v_{3}$,
except when in the initial gadget we used the reduction $[4,25][2,3]$, in
which case we have $e_{3}=v_{3}-1$.

We note that $m=[1,6]^{e_{3}}[I][4,5]^{v_{3}-1}$ cannot be $1$ (mod 3). We
then use the transition gadget $[T]$ as either $[0,3]$ or $[2,33]$. The number
after $[T]$ either way will allow repeated $[1,16]$ reduction as $-1/15$ has
in the $2$-adics the repeating digits $0000100001\cdots$. We have then that
$e_{3}=\lfloor\frac{v_{2}-v_{3}}{4}\rfloor$ when we are in the the first and
third of our cases for our initial gadget. In our second case where use used
$[I]=[4,25][1,2]$ we have $e_{3}=\lfloor\frac{v_{2}-1-v_{3}}{4}\rfloor$, and
in our fourth case where we have $[I]=[4,25][1,2][1,2]$ we have
$e_{3}=\lfloor\frac{v_{2}-1-v_{3}}{4}\rfloor$.

We then consider our final gadget $[F]$, by considering

$k=[1,16]^{e_{2}}[T][1,6]^{e_{3}}[I][4,5]^{v_{5}-1}$

If $k\equiv 5$ (mod 6), we make $[F]=[2,57][1,2]$. If $k\equiv 0$ (mod 3), we
make $[F]=[2,91][0,3]$. If $k\equiv 1$ (mod 6), we do $[2,49][1,6]$. If
$k\equiv 1$ (mod 6) we do $[2,49][1,6]$. If $k\equiv 0$ (mod 3), we do
$[2,91][0,3]$. We may thus assume that $k$ is even and that $k=1$ (mod 3) or
$k\equiv 2$ (mod 3). If $k\equiv 0$ mod 16, we do $[0,16]$. If $k\equiv 8$
(mod 16) we do $[1,242][0,8]$. If $k\equiv 4$ (mod 8), we do $[2,121][0,4]$.
If $k\equiv 2$ (mod 4), we do $[1,91][1,2][0,2]$

Let us now discuss $C_{10}$, $C_{11}$, and $C_{12}.$ $C_{10}$ arises from the
contribution of $[I]$, and that $e_{2}$ may not use every power of 2. We have
a slight advantage here in that one might think one needs to take the worst
case scenario of both $e_{2}$ and $[T]$, but we cannot both loses powers of 2
to $[I]$ and lose a power of 3 to $[I]$. Our worst case turns out to always be
our third case, where we have a $[2,3]$ instead of a $[1,6]$. Our worst case
for $e_{3}$, then becomes not getting to use all three 2s. We thus have

$C_{10}=(\alpha\log 5)-5-\left(\frac{3}{4}\left(\alpha\log
16-9\right)+\left(1+(\alpha\log
2-2)\right)\right)=\frac{11}{4}-\alpha\log\frac{16}{5}.$

$C_{11}$ arises from our transition gadget $[T]$, which given our range of
$\alpha$ always has $[2,33]$ as the worst case, hence $C_{11}=\alpha\log
33-13$.

$C_{12}$ contains the contribution from our final gadget $[F]$. The worst case
scenario here is always $[2,57][1,2]$, which gives $C_{12}$.

∎

As usual, the above proposition has an associated corollary:

######  Corollary 47.

Assume that $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$, and $S(\alpha,n)$
fails. Then

$v_{5}>0.11914v_{2}+0.12668v_{3}-0.23936.$ (10)

######  Lemma 48.

If $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$, and $S(\alpha,n)$ fails,
then $v_{2}\geq 27$, $v_{3}\geq 13$ and $v_{2}\geq 27$.

###### Proof.

We use the same tactic as with Lemma 45, but now iterate also the inequality
from Equation10. We first conclude that $v_{5}\geq 4$, and so we may take
$i_{5}=4$, and $i_{7}=2$ (justified by our increase in $v_{2}$). We then get
that $v_{3}\geq 12$, and so $v_{2}\geq 25$, and continue this way process,
obtaining that $v_{5}\geq 5$, $v_{2}\geq 26$, $v_{3}\geq 13$. and then that
$v_{2}\geq 27$.

∎

We now present another lower bound for $v_{2}$. This one essentially extends
our earlier bounds of Propositions 36 and Proposition 36 where instead of a
complicated final gadget, we have another transition gadget and then repeated
reduction of $[1,17]$. After that, we a new, somewhat simple, final gadget,
which depends on how much 5 reduction we used earlier.

######  Proposition 49.

Assume that $\alpha\in I_{2}$ and $S(\alpha,n)$ fails. Assume further that
$v_{2}\geq 1$, $v_{3}\geq 4$, $v_{5}\geq 2$, $v_{11}\geq 1$, $v_{13}\geq 1$,
and $v_{17}\geq 1$. Then

$(3-\alpha\log 2)v_{2}>\frac{\alpha\log 9-7}{2}v_{3}+(\alpha\log
5-6)v_{5}+(\alpha\log 17-10)v_{17}+C_{10}.$

Here $C_{10}=\alpha\log\frac{40678}{243}-18.5$ when $\alpha\in(\frac{26}{\log
1439},\frac{14}{\log 49}]$, $C_{10}=\alpha\log\frac{4160}{243}-10.5$ when
$\alpha\in[\frac{14}{\log 49},\frac{6}{\log 5}]$, and
$C_{10}=\alpha\log\frac{832}{243}-4.5$ when $\alpha\in(\frac{6}{\log
5},\frac{25}{6\log 2+2\log 3}]$.

###### Proof.

We use the following reduction

$[F][1,17]^{v_{17}}[T_{2}][1,9]^{e}[T_{1}][1,5]^{v_{5}-1}[I][1,2]^{v_{2}}n$

Where the indicated gadgets are defined as follows. Our initial gadget, $I$,
occurs after burning as many $[1,2]$ possible. We then have an initial gadget
of either $[0,4]$ or $[1,6]$. We then reduce by $[1,5]^{v_{5}-1}$. $T_{1}$
then is either $[1,10]$ or $[0,2]$ so we have effectively divided by another
2. We then repeatedly reduce by $[1,9]$ as many times as we can except for the
last one which we then do either $[0,2]$ or $[1,18]$ for $[T_{2}]$, and then
repeatedly reduce by $[1,17]$, using all of them. For $F$ our final gadget we
either apply $[0,2]$ or $[1,49][1,2]$ (depending on whether we have an even or
odd number). We then apply either $[0,4]$ or $[1,66][0,2]$ and then use either
a $[1,65]$ if we did not use our final 5 in $T_{1}$ earlier and using just
$[1,13]$ if we used our final 5. Note that in terms of our $p$-adic expansions
this result amounts to $-1/4$ being $1$ repeating in the $5$-adics, $-1/8$ is
$01$ repeating in the $3$-adics, and $-1/16$ is $1$ repeating in the
$17$-adics. ∎

As before we plug in our desired value of $\alpha$ into the above proposition
to obtain our corollary:

######  Corollary 50.

If $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$ , and $S(\alpha,n)$ fails
then:

$v_{2}>1.57093v_{3}+0.1069v_{5}+1.60217v_{17}+0.30388.$ (11)

We now turn to establishing that we may always take $i_{5}=v_{5}$ and
$i_{7}=v_{7}$ for our given range of $\alpha$. This is the same as showing
that $v_{2}\geq 2v_{7}+v_{5}+7$.

Our next proposition will help us do that.

######  Proposition 51.

Assume that $\alpha\in I_{2}$ and that $S(\alpha,n)$ fails. Assume further
that If $v_{2}\geq 1$, $v_{3}\geq 1$, $v_{5}\geq 3$, $v_{7}\geq 3$,
$v_{11}\geq 1$, and $v_{13}\geq 1$. Then have

$(3-\alpha\log 2)v_{2}>C_{15}+\beta v_{7}+(\alpha\log
25-11)\frac{v_{5}-1}{2}+\gamma v_{13}+(\alpha\log 3-4)v_{3}.$

Here we have $\beta=\frac{\alpha\log 49-13}{2}$, $\gamma=\alpha\log 13-9$.
$C_{15}$ is given by the following: If $\alpha\leq\frac{7}{\log 7}$,
$C_{15}=\alpha\log\frac{1824}{25}-15$. If $\alpha\in(\frac{7}{\log
7},\frac{25}{6\log 2+2\log 3}]$, then $C_{15}=\alpha\log\frac{48}{25}-4$.

###### Proof.

The reduction path here is to use

$[F][1,49]^{e_{7}}[T_{3}][1,25]^{e_{5}}[T_{2}][1,13]^{v_{13}}[T_{1}][1,3]^{v_{3}}[1,4][1,2]^{v_{2}-1}n.$

Here, $[T_{1}]$ is the transition gadget $[0,3]$ or $[2,15]$ (Here we are
using that $[1,3]^{v_{3}}[1,4][1,2]^{v_{2}-1}n$ cannot be $1$ (mod 3)),
followed by either $[1,14]$ or $[0,2]$ .We now have a number that behaves like
$-1/12$ $p$-adically for $p=5$, $7$ and $13$. After our reductions of
$[1,13]$, we use $[T_{2}]$ which is $[0,2]$ if we have reduced to an even
number and $[1,19][1,2]$ if have reduced to an odd number. We set
$e_{5}=\lfloor{\frac{v_{5}}{2}-1}\rfloor$. And then for $[T_{3}]$ use either
$[0,2]$ or $[1,50]$ depending on whether our number up to this point is even
or odd. We then reduce repeatedly by as many $[1,49]$, so
$e_{7}=\lfloor\frac{v_{7}}{2}\rfloor$. Then $[F]$ is then $[1,7]$ if $v_{7}$
was odd, since we have one more $7$ we can use it to reduce further.

∎

######  Corollary 52.

If $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$ and $S(\alpha,n)$ fails then

$v_{2}>0.31349v_{3}+1.36434v_{5}+1.5841v_{13}+2.02641v_{7}-5.2647.$ (12)

The constant in the above corollary is unfortunately too negative; in order to
do our general reduction to lower bound $v_{3}$, we will need to know that
$v_{2}\geq v_{5}+2v_{7}+7$. There are two obvious approaches to improving this
bound. The first is to throw in a final gadget. Unfortunately, the obvious
final gadget would involve reductions using $p=97$. If we had that $v_{97}\geq
1$, we could use the final gadget $[2,97]$, which would help somewhat. Proving
that sort of Lemma would be difficult without at least having much higher
$v_{p}$ for many smaller $p$. The other method is to bump up $v_{3}$, $v_{5}$,
$v_{7}$, and $v_{13}$ high enough that they give us the inequality we need.
The inequality in Corollary 52 above is not strong enough by itself due to the
large negative constant on the right-hand side.Note that Corollary 52 is
strong enough to get that $v_{2}\geq v_{7}+9$ which we will use below.

######  Proposition 53.

Assume that $\alpha\in I_{2}$ and $S(\alpha,n)$ fails. Assume further that
$v_{2}\geq v_{7}+8$. Assume that $v_{3}\geq 4$, $v_{5}\geq 1$, $v_{11}\geq 1$.
$v_{13}\geq 1$, $v_{17}\geq 1$. Then

$\frac{(\alpha\log 27-11)}{3}v_{3}+(\alpha\log 14-9)v_{7}+(\alpha\log
80-15)m_{1}+C_{21}C_{22}\leq(15-\alpha\log 13)v_{13}.$

Here $C_{21}=\alpha\log\frac{832}{3}-20$, and
$m_{1}=\min(\lfloor\frac{v_{2}-v_{7}-6}{3}\rfloor,v_{5})$.

###### Proof.

We use the reduction

$([1,20][1,4])^{(}m_{1})[2,27]^{e_{3}}[1,14]^{v_{7}}[I][12,13]^{v_{13}}n.$

Here $[I]$ is given by one of $[0,13]$, $[1,26]$, $[2,39]$, $[1,26][1,2]$,
$[2,39][1,2]^{4}$, $[2,39][1,2]$, $[2,39][1,2]^{6}$, $[1,26][1,2]^{2}$,
$[2,39][2,3]$, $[2,39][1,2]^{5}$, $[2,39][1,2]^{3}$, $[2,3][1,2]^{2}$.
$e_{3}=\lfloor\frac{v_{3}-j}{3}\rfloor$ where $j$ is the number of 3s burned
in $[I]$. Our worst case scenarios occur either when $[12,13]^{v_{13}}n\equiv
5$ (mod 13), and we have to use $[2,39][1,2]^{6}$, or when $[2,39][2,3]$, and
where we then lose two 3s in $v_{3}$ which we cannot use; this rise to
$C_{21}$. ∎

######  Corollary 54.

If $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$ and $S(\alpha,n)$ fails then

$v_{13}>0.08528v_{3}+0.1691v_{7}+0.27038m_{1}+0.20845.$ (13)

As before, $m_{1}=\min(\lfloor\frac{v_{2}-v_{7}-6}{3}\rfloor,v_{5})$.

We obtain from this:

######  Lemma 55.

If $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$ and $S(\alpha,n)$ fails then
$v_{13}\geq 3$, and $m_{1}\geq 2$. We also have $v_{2}\geq 2v_{5}+v_{7}+8$.

###### Proof.

We may have that $m_{1}\geq 1$ by earlier remarks. We then conclude that
$v_{13}\geq 2$. This allows us to get that $m_{1}\geq 2$ This allows us to use
Corollary 52 get that $v_{2}\geq 2v_{5}+v_{7}+8$. ∎

######  Proposition 56.

Assume that $\alpha\in I_{2}$, and that $S(\alpha,n)$ fails. Assume that
$v_{2}\geq v_{3}+7$. Assume also that $v_{3}\geq 5$, $v_{5}\geq 1$, $v_{7}\geq
1$, $v_{11}\geq 1$, $v_{13}\geq 1$, $v_{17}\geq 1$, and $v_{19}\geq 1$. Then

$(17-\alpha\log 17))v_{17}>(\alpha\log 18-9)\frac{v_{3}}{2}+(\alpha\log
35-13))m_{3}+C_{24}.$

Here $C_{24}=\alpha\log(\frac{17(32)}{3\sqrt{2}}))-\frac{47}{2}$. Here
$m_{3}=\min(v_{5},v_{7})$.

###### Proof.

We use the reduction $[2,35]^{m_{3}}[1,18]^{e_{3}}[I][16,17]^{v_{17}}$ Here
$[I]$ is the initial gadget given by one of $[0,17]$, $[1,34]$, $[2,51]$,
$[1,34][1,2]$, $[2,51][1,2]^{6}$, $[2,51][1,2]$, $[2,51][1,2]^{3}$,
$[1,34][1,2]^{2}$ $[2,51][2,3]$, $[2,51][1,2]^{7}$, $[2,3][1,2]^{2}$,
$[2,51][2,3]^{3}$ $[2,51][1,2]^{4}$ $[2,51][2,3][1,2]^{6}$, $[1,34][1,2]^{3}$.
We have then $e_{3}=\lfloor{v_{3}-j}\rfloor$ where $j$ is the number of 3s
used in [I]. The worst case is when we use $[2,51][2,3][1,2]^{6}$, and then
lose a 3 in to the floor in the definition of $e$. ∎

######  Corollary 57.

Assume $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$ and $S(\alpha,n)$ fails.
Then

$v_{17}>0.1455v_{3}+0.054735m_{3}-0.82932.$ (14)

Here $m_{3}=\min(v_{5},v_{7}).$

We note that since $m_{3}\geq 2$, we immediately get from the above that we
may assume that $v_{17}\geq 2.$

######  Proposition 58.

Assume that $\alpha\in I_{2}$ and $S(\alpha,n)$ fails. Assume further
$v_{2}\geq 11$, $v_{3}\geq 2$, $v_{5}\geq 2$, $v_{7}\geq 1$, and $v_{11}\geq
1$. Then

$(11-\alpha\log 7)v_{7}>\frac{3\alpha\log 2-7}{3}v_{2}+\frac{(\alpha\log
15-9)}{2}m_{2}+C_{18}+C_{19}.$

Here $C_{18}=\alpha\log 21-\frac{40}{3}$, and $C_{19}=\alpha\log 44-14$, when
$\alpha\in[\frac{26}{\log 1439},\frac{12}{\log 22}]$, and $C_{20}=\alpha\log
2-2$, when $\alpha\in(\frac{12}{\log 22},\frac{26}{6\log 2+2\log 3})$. Here
$m_{2}=\min(v_{3}-1,v_{5})$

###### Proof.

Here we use the path $[F][1,15]^{m_{2}}[T][1,8]^{e_{2}}[I][6,7]^{v_{7}}n$.
Here, $[I]$ is the gadget doing one of the following depending on
$[1,8]^{e_{2}}[I][6,7]^{v_{7}}n$ (mod 7): $[0,7]$ $[1,14]$, $[2,21]$,
$[1,14][1,2]$, $[2,21][1,2][1,2]]$ or $[2,21][1,2]$. We then set
$e_{2}=\lfloor\frac{v_{2}-j}{3}\rfloor$ where $j=1$ when our transition gadget
used $[1,14]$, or $[2,21][1,2]$, $j=2$ when our transition gadget used
$[1,14][1,2]$, and $j=0$ otherwise. Essentially, $j$ counts how many 2s we had
to burn in our initial gadget. Our $C_{18}$ comes from all aspects but our
transition gadget $[T]$, We then use a transition gadget $[T]$ of one of
$[0,2]$, $[1,22][1,2]$ or $[1,18][1,4]$, which has either worst case $[0,2]$,
$[1,22][1,2]$ which contributes our $C_{19}$ term.

∎

######  Corollary 59.

If $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$ and $S(\alpha,n)$ fails
then:

$v_{7}>0.054619v_{2}+0.315942m_{4}-0.45895.$ (15)

We then proceed iterating our inequalities as before and we obtain:

######  Lemma 60.

If $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$ and $S(\alpha,n)$ fails
then: $v_{2}\geq 35$, $v_{3}\geq 18$, $v_{5}\geq 7$, $v_{7}\geq 4$,
$v_{13}\geq 5$, $v_{17}\geq 3$.

###### Proof.

We iterate as before to obtain all the inequalities above but with $v_{13}\geq
3$. We then may use our inequalities to conclude that $v_{2}-v_{7}\geq 27$,
and so we have that $m_{1}\geq 7$. This allows us to now conclude that
$v_{13}\geq 5$. ∎

######  Proposition 61.

Assume that $\alpha\in I_{2}$ and $S(\alpha,n)$ fails. Assume further that
$v_{2}\geq 1$, $v_{3}\geq 5$, $v_{5}\geq 3$, $v_{11}\geq 1$, $v_{13}\geq 1$,
and $v_{17}\geq 1$. Then

$\begin{split}(3-\alpha\log 2)v_{2}&>\frac{\alpha\log
9-7}{2}(v_{3}-m_{6})+(\alpha\log 5-6)(v_{5}-m_{5})+(\alpha\log 17-10)v_{17}\\\
&+(\alpha\log 33-12)m_{6}+(\alpha\log 65-14)m_{5}+C_{20}.\end{split}$ (16)

Here $C_{20}=\log\frac{16}{\log 1485}+17$. We have
$m_{5}=\min(v_{5}-1,v_{13})$, and $m_{6}=\min(v_{11},v_{3}-4)$.

###### Proof.

We use a reduction similar to that in Proposition 49. We We use the following
reduction

$[1,65]^{m_{5}}[T_{4}][1,33]^{m_{6}}[T_{3}][1,17]^{v_{17-1}}[T_{2}][1,9]^{e}[T_{1}][1,5]^{v_{5}-1}[I][1,2]^{v_{2}}n$

Where the indicated gadgets are defined as follows. Our initial gadget, $I$,
occurs after burning as many $[1,2]$ possible. We then have an initial gadget
of either $[0,4]$ or $[1,6]$. We then reduce by $[1,5]^{v_{5}-m_{5}-1}$.
$T_{1}$ then is either $[1,10]$ or $[0,2]$ so we have effectively divided by
another 2. We then repeatedly reduce by $[1,9]$ as many times as we can except
for the last one which we then do either $[0,2]$ or $[1,18]$ for $[T_{2}]$,
and then repeatedly reduce by $[1,17]$. $[T_{3}]$ then is either $[0,2]$ or
$[1,49][1,2]$. We have then $[T_{4}]$ is either $[0,2]$ or $[1,66]$. Our worst
case scenario then is when we use $[I]=[1,6]$ and every other gadget is just
$[0,2]$. This gives rise to our constant term. ∎

######  Corollary 62.

If $\alpha\geq\frac{41}{\log 55296}=3.7544\cdots$ , and $S(\alpha,n)$ fails
then:

$\begin{split}v_{2}&>1.57093v_{3}+0.1069v_{5}+1.60217v_{17}\\\
&+4.09891m_{5}+1.26426m_{6}-0.02443.\end{split}$ (17)

We note that we have from earlier that $m_{5}\geq 5$ and that $m_{6}\geq 1$.

We are now ready to prove our main theorem:

###### Proof.

We iterate as before using that none of our $v_{p}$ may be an integer. From
repeated iteration we get that $v_{2}\geq 65$, $v_{3}\geq 28$, $v_{5}\geq 11$,
$v_{7}\geq 6$. We now improve our bounds on $m_{5}$. Our current set of
inequalities implies that $v_{5}\geq 0.25v_{13}+3$, so we may take $m_{5}\geq
0.25v_{13}+2$, we may repeat this process to conclude that $v_{13}\geq
0.1v_{5}+3$, $v_{5}\geq 0.3v_{13}+8$, $v_{5}\geq 0.4v_{13}+13$, $v_{5}\geq
0.5v_{13}+20$, $v_{13}\geq 0.11v_{5}+5$. We continue iterating this way, to
get that $v_{5}\geq v_{13}$ and conclude that therefore $m_{5}=v_{13}$. We may
then obtain that $v_{3}\geq v_{5}+4$, and thus may take $m_{2}=v_{5}$. But the
resulting system has no solutions. ∎

There are multiple possible avenues for tightening this result. At present,
the primary obstacle is to have stronger definite results. It may be possible
to improve on those results using an automated approach. Unfortunately, even
if one has better definite results, it is likely that one will need to adjust
some of the Propositions in addition to including more similar reducing paths
using other primes. This adjusting would be necessary for two reasons. First,
our final gadgets as written are optimized for our choice of $\frac{41}{\log
55296}$ and so one would wish to modify the gadgets. Second, one would likely
need additional reduction path inequalities to obtain a contradiction.

##  4 The limits of the method

Improving the main result beyond $\frac{41}{\log 55296}$ may be possible. The
primary obstacle appears to be obtaining tighter definite results. We can
easily construct additional similar inequalities or strengthen our current
inequalities as long the $v_{p}$ are large. For example, for the reduction in
Proposition 46, we can extend it so that we then do repeated $[1,31]$
reduction at the end. It may be possible to engage in an automated method of
proving definite results. If one ignores definite results, one can get the
following result using the same methods:

######  Theorem 63.

There exists a finite set of primes $P$, such that for all $p$ in $P$, $v_{p}$
is sufficiently large then $S(\alpha,n)$ holds for $\alpha\geq\frac{5}{2\log
2}$.

Note that $\frac{5}{2\log 2}=3.606\cdots$ so the above result is substantially
stronger as an induction step in the cases where it is valid. Unfortunately,
making the set of primes small enough for this result to be useful appears
difficult. There appears to be some tradeoff between having this set small and
having the $v_{p}$ themselves not be too large. In this section, we will not
attempt to explicitly construct such a set $P$ nor determine what sufficiently
large is, but prove the non-explicit form above.

Let $p_{1},p_{2}\cdots p_{k}$ and $q_{1},q_{2},\cdots q_{\ell}$ be primes (not
necessarily distinct). We will write

$f(v_{p_{1}},v_{p_{2}},\cdots
v_{p_{k}})\lhd_{\alpha}g(v_{q_{1}},v_{q_{2}},\cdots v_{q_{\ell}})$

to mean that there is a constant $C$ and a finite list of primes
$r_{1},r_{2},r_{3}\cdots r_{m}$ such that if $S(\alpha,n)$ fails and
$v_{r_{1}},v_{r_{2}},v_{r_{3}}\cdots v_{r_{m}}$ are sufficiently large then we
have

$f(v_{p_{1}},v_{p_{2}},\cdots v_{p_{k}})\leq g(v_{q_{1}},v_{q_{2}},\cdots
v_{q_{\ell}})+C.$

In general, the $r_{i}$ may include the $p_{i}$ and $q_{i}$ and most of the
time well. Since in this section we will be interested only in proving results
involving $\lhd_{\alpha}$ rather than $\leq$, we will not need to pay careful
attention to the specifics of the initial gadgets and transition gadgets. We
will also be able to completely ignore final gadgets since all they do is
improve the constant term in our linear inequalities. Note that if a system of
linear inequalities with $\lhd_{\alpha}$ is inconsistent when we replace the
diamonds with less than signs, then the system will be inconsistent for
sufficiently large values of the relevant variables.

We will define $\rhd_{\alpha}$ as the same but with $\geq$ replacing the
$\leq$ in the definition.

We also need to discuss briefly what sorts of reductions are possible in
general. This discussion was unnecessary in the previous section because we
only needed to focus on making our reductions as efficient as possible. In
general, if we have a prime $p$ we can burn $p$ by using the inefficient
reduction $[p-1,p]$ repeatedly and then use an initial gadget to get a number
that behaves like $-1/p$ with respect to other primes. This allows us to
reductions of the form

$[1,p+1]^{m}[I][p-1,p]^{v_{p}-1}n$

where $m$ is a function of the $v_{q}$ over the $q$ which divide $p+1$, $[I]$
is an initial gadget. In general, when we have a reduction behaving $-1/t$ we
can then transition to $-1/(qt)$ where $q$ is either a prime which divides $t$
or is a prime which divides $t+1$ if we have exhausted as much $[1,t+1]$ until
we have no more $q$s remaining, although this may require coordination with
the initial gadget. Almost all our general indefinite reductions fit the above
pattern. Proposition 51 is a good example of these techniques. We do however
need to note that if we have something behaving like $-1/t$, then we may have
a other options as well. For example, when we have something acting as $-1/t$,
we can instead of doing direct $[1,t+1]$ reduction we can also reduce using a
base reduction that is more complicated, such as using the base 2 reduction
corresponding to $-1/t$. In general, we can guarantee the existence of
transition gadgets as appropriate by using Dirichlet’s theorem on primes in
arithmetic progressions. However, gadgets directly constructed this way are
generally inefficient and contribute many primes in $S$.

######  Proposition 64.

For $\alpha\geq\frac{5}{2\log 2}$ if $S(\alpha,n)$ fails then we have:

$Jv_{2}\rhd_{\alpha}A\min(v_{11},v_{419})+Bv_{1153}+Cv_{193}++Dv_{577}+Ev_{17}+Fv_{97}$
$+Gv_{7}+Hv_{5}+Iv_{3}.$

Here $A=\alpha\log 4609-26$, $B=\alpha\log 1153-22$, $C=\alpha\log 193-18$,
$D=\alpha\log 577-20$, $E={\alpha\log 17-9}$, $F=\alpha\log 97-15$,
$G=\frac{\alpha\log 49-13}{2}$, $H=\frac{\alpha\log 25-11}{2}$,
$I=\frac{\alpha\log 9-7}{2}$ and $J=3-\alpha\log 2$.

###### Proof.

We will use the reduction

$k_{1}=[T_{1}][1,9]^{v_{3}-3}[I_{1}][[1,2]^{v_{2}-2}[n]$

where $[I_{1}]$ is an initial gadget and $T_{1}$ is a transition gadget which
correspond to first having $-1/8$ mod $3^{v_{3}}$, and then having $-1/24$ in
the later moduli for our other primes (because we get an extra division by 3).
We then further reduce $k_{1}$ using the reduction

$k_{2}=[T_{4}][1,97]^{v_{97}-2}[T_{3}][1,49]^{v_{7}-1}[T_{2}][1,25]^{\frac{v_{5}}{2}-2}k_{1}.$

Here $T_{2}$ is a transition gadget which allows us to divide by an extra
power of 2; this gadget is simple: just either $[0,2][1,25]$ or $[0,2]$
depending on the parity of $[1,25]^{\frac{v_{5}}{2}-2}k_{1}.$ The transition
gadget $[T_{3}]$ similar to $T_{2}$, but instead is either $[0,2][1,49]$ or
$[0,2]$. The transition gadget $[T_{4}]$ instead allows us to do one of
$[0,3]$, $[0,3][1,97]$, or $[0,3][1,97]^{2}$ depending on

$[1,97]^{v_{97}-2}[T_{3}][1,49]^{v_{7}-1}[T_{2}][1,25]^{\frac{v_{5}}{2}-2}k_{1}{\mathrm{mod}}3.$

We then reduce $k_{2}$ using

$k_{3}=[T_{5}][1,289]^{{\frac{v_{17}}{2}}-2}[2,193]^{v_{193}}k_{2}.$

Here $[T_{5}]$ is either $[0,2][1,289]$ or $[0,2]$. Note that we use at this
stage that $\|289\|=17$ which comes from writing $289=1+288$ rather than the
$289=17^{2}$. We then reduce $k_{3}$ further using the reduction

$[1,4609]^{\min(v_{11},v_{419})}[T_{7}][1,1153]^{v_{1153}-1}[T_{6}][1,577]^{v_{577}-1}k_{3}.$

Here $[T_{6}],$ and $[T_{7}]$ are similar reductions. ∎

We have an immediate corollary:

######  Corollary 65.

For $\alpha\geq\frac{5}{2\log 2}$ if $S(\alpha,n)$ fails then we have:

$v_{2}\rhd_{\alpha}8.85119\min(v_{11},v_{419})+6.855883988v_{1153}$
$+4.5112v_{577}+2.7622513v_{17}+1.96228518v_{193}$
$+2.99956421v_{97}+1.22821404v_{7}+0.75563395v_{5}+0.9248125036v_{3}.$

Similarly we have:

######  Proposition 66.

For $\alpha\geq\frac{5}{2\log 2}$ if $S(\alpha,n)$ fails then we have:

$Jv_{3}\rhd_{\alpha}A\min(v_{11},v_{419})+Bv_{1153}+Cv_{193}++Dv_{577}+Ev_{17}+Fv_{97}$
$+Gv_{7}+Hv_{5}+Iv_{13}=.$

Here $A=\alpha\log 4609-26$, $B=\alpha\log 1153-22$, $C=\alpha\log 193-18$,
$D=\alpha\log 577-20$, $E={\alpha\log 17-9}$, $F=\alpha\log 97-15$,
$G=\frac{\alpha\log 49-13}{2}$, $H=\frac{\alpha\log 25-11}{2}$, $I=\alpha\log
13-9$ and $J=5-\alpha\log 3$.

###### Proof.

The essential reduction is very similar to the that in the previous
proposition but we instead change $k_{1}$ slightly so that we have
$k_{1}=[T_{1b}][1,13]^{v_{13}}[T_{1a}][1,4]^{\frac{v_{2}}{2}-2}[I_{2}][2,3]^{v_{3}}$
and then continue from there. The new transition gadgets needed are
straightforward. Note that the repeated $[1,4]$ reductions do not form a term
on the right-hand side when $\alpha$ hits our lowest desired value, but if one
had a slightly larger value of $\alpha$ one would get a $v_{2}$ term on the
right-hand side of our inequality. ∎

We obtain then the next corollary:

######  Corollary 67.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{3}\rhd_{\alpha}4.2652484\min(v_{11},v_{419})+3.3037419v_{1153}+2.824871272v_{577}$
$+1.174503128v_{17}+0.9455941v_{193}+1.4454425v_{97}+0.49960527v_{7}+0.293776v_{5}+0.242v_{13}.$

######  Proposition 68.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(11-\alpha\log 7)v_{7}\rhd_{\alpha}\frac{\alpha\log
225-17}{2}\min(v_{3},v_{5})+(\alpha\log 29-12)v_{29}+\frac{\alpha\log
8-7}{3}v_{2}.$

###### Proof.

We use the reduction

$k_{1}=[1,29]^{v_{29}-1}[T_{1}][1,8]^{\frac{v_{2}}{3}-1}[I][6,7]^{v_{7}-2}.$

Here the required transition and initial gadgets are straightforward. We then
further reduce $k_{1}$ using the reduction

$[1,225]^{\min(v_{3},v_{5})/2-C}[T_{2}]k_{1}.$

Again, the transition gadgets are straightforward. ∎

We have then the following corollary:

######  Corollary 69.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{7}\rhd_{\alpha}0.31826965\min(v_{3},v_{5})+0.0364054v_{29}+0.041859v_{2}.$

This system is now sufficient to conclude that if $\alpha\geq\frac{5}{2\log
2}$ and $S(\alpha,n)$ fails then $v_{2}\rhd_{\alpha}.9651v_{3}$. We therefore
have:

######  Proposition 70.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(9-\alpha\log 5)v_{5}\rhd_{\alpha}0.965(\alpha\log 6-6)v_{3}.$

###### Proof.

This follows from the reduction

$[1,6]^{0.965v_{3}}[I][4,5]^{v_{5}-1}n.$

We need the $0.965$ above because we do not yet have a guarantee that $v_{2}$
is at least as large as $v_{3}$ and so must use the observation from earlier.
We use $0.965$ here rather than $0.9651$ because the most straightforward
versions of $[I]$ will expend some $[1,2]$ reductions (although they can
strictly speaking be replaced by other reductions).

∎

We have then as a corollary:

######  Corollary 71.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{5}\rhd_{\alpha}0.139654v_{3}.$

This system is now sufficient to conclude that if $\alpha\geq\frac{5}{2\log
2}$ and $S(\alpha,n)$ fails then $v_{2}\rhd_{\alpha}1.05v_{3}$ which allows us
to obtain a more substantial lower bound for $v_{5}$:

######  Proposition 72.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(9-\alpha\log 5)v_{5}\rhd_{\alpha}(\alpha\log 31-11)v_{31}+(\alpha\log
11-8)v_{11}+\frac{\alpha\log 16-9}{4}(v_{2}-v_{3})+(\alpha\log 6-6)v_{3}.$

###### Proof.

We use the reduction

$k_{1}=[1,16]^{v_{2}/4-2}[T_{1}][1,6]^{v_{3}-C}][I][4,5]^{v_{5}-1}n$

and then reduce $k_{1}$ further by

$[1,961]^{v_{31}/2-1}[T_{4}][1,121]^{v_{11}/2-1}[T_{2}]k_{1}.$

∎

######  Corollary 73.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{5}\rhd_{\alpha}0.433619038v_{31}+0.2029867158v_{11}+.0782428591v_{2}+0.066477v_{3}.$

We have a similar other path for $v_{5}$ with a slightly different reduction:

######  Proposition 74.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(9-\alpha\log 5)v_{5}\rhd_{\alpha}\frac{\alpha\log
961-22}{2}v_{31}+\frac{\alpha\log 81-13}{4}v_{3}.$

###### Proof.

We again first burn $[4,5]^{v_{5}-1}n$, and then exhaust all powers of 2 which
does not cost us anything for our desired range of $\alpha$ since $-1/5$ has
just as many 1s as it has 0s in its 2-adic repeating part. We then use a
transition gadget to allow us to reduce using $[1,81]$ repeatedly before using
another transition gadget to move us onto the same track as above.

∎

######  Corollary 75.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{5}\rhd_{\alpha}0.433619038v_{31}+0.22296285v_{3}.$

######  Proposition 76.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(21-\alpha\log 31)v_{31}\rhd_{\alpha}\frac{\alpha\log
125-16}{3}v_{5}+\frac{\alpha\log
3969-25}{2}\min(v_{7},v_{3}/2)+\frac{\alpha\log 32-11}{5}v_{2}.$

###### Proof.

We burn $31$ with the straightforward initial gadget allowing us to then do
repeated $[1,32]$ reduction, and then use a transition gadget to get to allow
repeated $[1,125]$ reduction, which we can do since $124=4(31)$ followed by an
additional transition gadget allowing for repeated $[1,3969]$ reduction. Here
we are using that $3968=(3^{7})(31)$. Note that $3969=(3^{4})(7^{2})$. ∎

######  Corollary 77.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{31}\rhd_{\alpha}0.0547317v_{5}+0.2836145\min(v_{7},v_{3}/2)+0.034824967v_{2}.$

######  Proposition 78.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(31-\alpha\log 193)v_{193}\rhd_{\alpha}(\alpha\log 194-17)v_{97}.$

###### Proof.

We use the following reduction: We repeatedly burn $193$ followed by an
initial gadget and then do repeated $[1,194]$ reduction. Note that how much
$[1,194]$ reduction we can do is controlled only by the size of $v_{97}$ since
$v_{2}\rhd v_{97}$ by Corollary 65.

∎

######  Corollary 79.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{193}\rhd_{\alpha}0.1663870397v_{97}.$

Note that our current system is enough to conclude that
$v_{2}\rhd_{\alpha}v_{5}$ for $\alpha\geq\frac{5}{2\log 2}$. However, this is
not obvious simply from looking at these inequalities. We would like to be
able to do so directly by treating our current system of inequalities as a
simple linear programming problem. However, we run into the problem that we
have variables that are of the form $\min(v_{q},v_{r})$ in addition to the
various $v_{p}$ directly. Sometimes we will also want to understand terms of
the form $\min(av_{q},v_{r})$ for some constant $a$.

Our solution is to bootstrap our system by adding in additional inequalities.
For example, in Corollary 77, we have a term that is $\min(v_{7},v_{3}/2)$.
Using our current system of inequalities above, we can get that
$v_{3}\rhd_{\alpha}.55v_{7}$, and so
$\min(v_{3}/2,v_{7})\rhd_{\alpha}0.275v_{7}$. Including this as another
inequality in our system then us to conclude that
$\min(v_{3}/2,v_{7})\rhd_{\alpha}0.279v_{7}$. We iterate this process as
improving our inequalities involving minima of $v_{3}$,$v_{5}$ and $v_{7}$ to
obtain that $v_{7}\rhd_{\alpha}.124v_{3}$, $v_{5}\rhd_{\alpha}0.258v_{3}$, and
$v_{3}\rhd_{\alpha}0.375v_{3}$ and apply them to the relevant minimum terms.
This is then enough to conclude that $v_{2}\rhd_{\alpha}v_{5}$. We are now
ready to prove:

######  Proposition 80.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(21-\alpha\log 29)v_{29}\rhd_{\alpha}(\alpha\log 233-18)v_{233}+(\alpha\log
30-11)\min(v_{3},v_{5}).$

###### Proof.

We burn $[28,29]$, and then reduce by $[1,30]$ as many times as we can which
is dependent on $\min(v_{3},v_{5})$ since we already had
$v_{2}\rhd_{\alpha}v_{3}$ and by our above remark we have
$v_{2}\rhd_{\alpha}v_{5}$. We then reduce all our 2s, using that $-1/29$ in
the 2-adics has many 2s as it has 1s, allowing us to then use a transition
gadget which lets us repeatedly reduce by $[1,233]$.

∎

######  Corollary 81.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{29}\rhd_{\alpha}0.187516256v_{233}+0.143107\min(v_{3},v_{5}).$

Note that this system is now enough to conclude that
$v_{3}\rhd_{\alpha}.381v_{5}$, $v_{5}\rhd_{\alpha}.263v_{3}$, and
$v_{7}\rhd_{\alpha}.137v_{3}$.

The next two pairs of propositions and corollaries are straightforward enough
that we will omit their proofs:

######  Proposition 82.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(33-\alpha\log 233)v_{233}\rhd_{\alpha}(\alpha\log 467-21)v_{467}+(\alpha\log
234-17)\min(v_{3}/2,v_{13}).$

######  Corollary 83.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{233}\rhd_{\alpha}0.08757403v_{467}+0.2006\min(v_{3}/2,v_{13}).$

######  Proposition 84.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(41-\alpha\log 467)v_{467}\rhd_{\alpha}(\alpha\log
935-23)\min(v_{5},v_{11},v_{17})+(\alpha\log
468-19)\min(v_{3}/2,v_{13})\lhd_{\alpha}v_{233}.$

######  Corollary 85.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{467}\rhd_{\alpha}0.08878896\min(v_{5},v_{11},v_{17})+0.168646187\min(v_{3}/2,v_{13}).$

Our next set of reductions yield additional lower bounds for $v_{2}$ and
$v_{3}$:

######  Proposition 86.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(3-\alpha\log 2)v_{2}\rhd_{\alpha}(\alpha\log 769-21)v_{769}+(\alpha\log
193-17)v_{193}+(\alpha\log 97-15)v_{97}$ $+\frac{\alpha\log
49-13}{2}v_{7}+\frac{\alpha\log 25-11}{2}v_{5}+\frac{\alpha\log 9-7}{2}v_{3}.$

###### Proof.

This is identical to the start of the reduction of Proposition 64 but instead
when we are done reducing by $[1,97]$ we use a transition gadget to do
repeated $[1,193]$ reduction, and then use a transition gadget to do repeated
$[1,769]$ reduction. ∎

######  Corollary 87.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{2}\rhd_{\alpha}5.9341989398v_{769}+3.962285186v_{193}+2.99956421093v_{97}$
$+1.22821404v_{7}+0.75563395v_{5}+0.9248125036v_{3}.$

Just as Proposition 86 gave a modified version of Proposition 64, we can give
a modified version of Proposition 66:

######  Proposition 88.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(5-\alpha\log 3)v_{3}\rhd_{\alpha}(\alpha\log 769-21)v_{769}+(\alpha\log
193-17)v_{193}+(\alpha\log 97-15)v_{97}$

$+\frac{\alpha\log 49-13}{2}v_{7}+\frac{\alpha\log
25-11}{2}v_{5}+\frac{\alpha\log 4-5}{2}v_{2}.$

######  Corollary 89.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{3}\rhd_{\alpha}2.8595965v_{769}+1.9093625v_{193}+1.4454425039v_{97}+0.49960527v_{7}+0.293776v_{5}.$

Note that this allows us to conclude that $v_{3}\rhd_{\alpha}v_{769}$ which we
will need when we prove Proposition 96 later.

We have the straightforward lower bound on $v_{769}$:

######  Proposition 90.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(39-\alpha\log 769)v_{769}\rhd_{\alpha}(\alpha\log
770-22)\min(v_{5},v_{7},v_{11}).$

###### Proof.

This is essentially just the obvious reduction where one first repeatedly
burns $v_{769}$ and then does repeated $[1,770]$. The only thing to note here
is that to make this depend on just $\min(v_{5},v_{7},v_{11})$ we need to use
that $v_{2}\rhd_{\alpha}v_{5}$.

∎

######  Corollary 91.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{769}\rhd_{\alpha}0.1311647\min(v_{5},v_{7},v_{11}).$

Our next proposition is also a straightforward reduction, along with the notes
that $-1/577$ has as many 0s as 1s in the repeating its 2-adic expansion, and
that $v_{2}\rhd_{\alpha}v_{17}$:

######  Proposition 92.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(37-\alpha\log 577)v_{577}\rhd_{\alpha}(\alpha\log
1155-23)\min(v_{3},v_{5},v_{7},v_{11})+\frac{\alpha\log 578-21}{2}v_{17}.$

######  Corollary 93.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{577}\rhd_{\alpha}0.173019\min(v_{3},v_{5},v_{7},v_{11})+0.0688507v_{17}.$

Our next proposition gives us a lower bound for $v_{17}$:

######  Proposition 94.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(17-\alpha\log 17)v_{17}\rhd_{\alpha}(\alpha\log 137-17)v_{137}+(\alpha\log
35-12)\min(v_{5},v_{7})+\frac{\alpha\log 18-9}{2}v_{3}.$

###### Proof.

Again, the reduction needed is straightforward, requiring only the note that
$-1/17$ has many 0s as 1s in its repeating part of its 2-adic expansion.

∎

######  Corollary 95.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{17}\rhd_{\alpha}0.109872v_{137}+0.12139299\min(v_{5},v_{7})+0.1050538v_{3}.$

We have then:

######  Proposition 96.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(41-\alpha\log 1153)v_{1153}\rhd_{\alpha}(\alpha\log
2307-25)\min(v_{769})+(\alpha\log 1154-22)v_{577}.$

###### Proof.

This is a straightforward reduction with two minor notes. The reduction is to
first repeatedly burn $1153$, then do repeated $[1,1154]$ repeatedly, and then
do $[2,2307]$ repeatedly noting that $2307=(767)(3)$ and that
$v_{3}\rhd_{\alpha}v_{769}$ as noted earlier. We need to do $[2,2307]$ rather
than our usual method of using powers of $2$ and then slipping in an extra
division by 2 because the 2-adic repeating part of $-1/1153$ is too long for
us to verify that the number of $0$s is at least the number of $1$s.

∎

######  Corollary 97.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{1153}\rhd_{\alpha}0.18812579v_{769}+0.22033497v_{577}.$

We have the following straightforward reduction:

######  Proposition 98.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(15-\alpha\log 11)v_{11}\rhd_{\alpha}(\alpha\log 12-8)\min(v_{2}/2,v_{3}).$

######  Corollary 99.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{11}\rhd_{\alpha}0.15152613\min(v_{2}/2,v_{3}).$

The next proposition is again a simple reduction:

######  Proposition 100.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(15-\alpha\log 13)v_{13}\rhd_{\alpha}\frac{\alpha\log
27-10}{3}v_{3}+(\alpha\log 14-9)v_{7}.$

###### Proof.

The reduction here is straightforward, burning $[12,13]$ repeatedly, then
using $[1,14]$ reduction before switching to $[1,27]$ reduction. The only
thing to note is that how many times we can do $[1,14]$ reduction depends only
on $v_{7}$ because $v_{2}\rhd_{\alpha}v_{7}$. ∎

######  Corollary 101.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{13}\rhd_{\alpha}0.1094249v_{3}+.090171v_{7}.$

Using our bootstrapping to handle the minima again, we can now conclude that
$v_{2}\rhd_{\alpha}1.01(v_{5}+v_{7})$ (In fact can easily get
$v_{2}\rhd_{\alpha}1.9(v_{5}+v_{7})$ which allows us to have enough 2s to do
the next proposition:

######  Proposition 102.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(15-\alpha\log 13)v_{13}\rhd_{\alpha}(\alpha\log
170-17)\min(v_{5},v_{17})+\frac{\alpha\log 27-11}{3}v_{3}+(\alpha\log
14-9)v_{7}.$

###### Proof.

This reduction is similar to the previous reduction except that instead of
exhausting the 2s after doing all the $[1,14]$ reduction we do repeated
$[2,27]$ until we slip in an extra division by $13$ followed by $[1,170]$
reduction.

∎

######  Corollary 103.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{13}\rhd_{\alpha}0.265\min(v_{5},v_{17})+0.0514428v_{3}+0.090171v_{7}.$

######  Proposition 104.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(17-\alpha\log 17)v_{17}\rhd_{\alpha}(\alpha\log
290-19)\min(v_{5},v_{29})+\frac{\alpha\log 18-9}{2}v_{3}.$

###### Proof.

This is a straightforward reduction where we burn $[16,17]$ repeatedly to then
do $[1,18]$ repeatedly, slip in an extra division by $17$, and then do
$[1,290]$ repeatedly. The only quirk we need to note is that we have to use
further bootstrapping to verify that we have sufficient $v_{2}$, in particular
that $v_{2}\rhd 0.5v_{3}+v_{5}$. ∎

######  Corollary 105.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{17}\rhd_{\alpha}0.21378844\min(v_{5},v_{29})+0.1050538v_{3}.$

We also have the following lower bound for $v_{97}$:

######  Proposition 106.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(27-\alpha\log 97)v_{97}\rhd_{\alpha}(\alpha\log 389-20)v_{389}+(\alpha\log
195-17)\min(v_{3},v_{5},v_{13})+\frac{\alpha\log 98-15}{2}v_{7}.$

###### Proof.

We burn $97$ repeatedly followed by repeating $[1,98]$, then slip in an
additional division by 2, and then repeat $[1,195]$ followed by repeating
$[1,389]$.

∎

######  Corollary 107.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{97}\rhd_{\alpha}0.1437175759v_{389}+0.19221751\min(v_{3},v_{5},v_{13})+0.0731782v_{7}.$

######  Proposition 108.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(37-\alpha\log 389)v_{389}\rhd_{\alpha}(\alpha\log
390-19)\min(v_{3},v_{5},v_{13}).$

###### Proof.

Proof omitted. ∎

######  Corollary 109.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{389}\rhd_{\alpha}0.16256771\min(v_{3},v_{5},v_{13}).$

######  Proposition 110.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(37-\alpha\log 419)v_{419}\rhd_{\alpha}(\alpha\log 839-23)v_{839}+(\alpha\log
420-19)\min(v_{5},v_{7}).$

###### Proof.

The reduction here is to first burn $419$ repeatedly and then do repeated
$[1,420]$ reduction before slipping in a 2 to allow repeated $[1,839]$
reduction. We note that $v_{2}\rhd_{\alpha}2v_{7}$ and so $[1,420]$ reduction
only depends on $v_{5}$ and $v_{7}$. ∎

######  Corollary 111.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{419}\rhd_{\alpha}0.084169v_{839}+0.182987\min(v_{5},v_{7}).$

We can bootstrap to get that $v_{2}\rhd_{\alpha}3v_{7}$ and so we are able to
prove:

######  Proposition 112.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(45-\alpha\log 839)v_{839}\rhd_{\alpha}(\alpha\log 840-21)\min(v_{5},v_{7}).$

######  Corollary 113.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{839}\rhd_{\alpha}0.158582\min(v_{5},v_{7}).$

Note that we easily have from our above inequalities that
$v_{5}\rhd_{\alpha}v_{97}$.

######  Proposition 114.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$(15-\alpha\log 11)v_{11}\rhd_{\alpha}(\alpha\log 485-20)v_{97}+(\alpha\log
12-8)\min(v_{2}/2,v_{3}).$

###### Proof.

We burn $[10,11]$ repeatedly, and then do $[1,12]$ reduction repeatedly before
slipping in an extra division by $2$. We then slip in an extra division by 11
and another $2$ allowing us to do $[1,485]$ reduction. We note that how many
times we can reduce by $[1,485]$ is a function just of $v_{97}$ since by our
earlier remark we have $v_{5}\rhd_{\alpha}v_{97}$.

∎

######  Corollary 115.

If $\alpha\geq\frac{5}{2\log 2}$ and $S(\alpha,n)$ fails then we have:

$v_{11}\rhd_{\alpha}0.362848v_{97}+0.15152613v_{3}.$

A careful reader may wonder why we prefer $[1,12]$ reduction in 114, rather
than using our 3s by doing $[1,243]$. In fact, $[1,243]$ yields a smaller
coefficient for $v_{3}$ in the inequality for the range of $\alpha$ we care
about, and one would have only $0.12v_{3}$. As $\alpha$ gets smaller,
$[1,243]$ gets more efficient and there is a point where it will surpass
$[1,12]$.

We are now in a position to prove Theorem 63.

###### Proof.

Assume that $S(\alpha,n)$ fails for $\alpha\geq\frac{5}{2\log 2}$ and that
$v_{p}$ is sufficiently large for some set of primes $p$. Then all the linear
inequalities in this section are true. However, with repeated bootstrapping
this system is now sufficient to get a contradiction.

∎

Note that in theory the method given here is constructive since one can use
Dirichlet’s theorem to guarantee the existence of the necessary transition
gadgets. The inequalities involved use the primes 2, 3, 5, 7, 11, 13, 17, 29,
31, 97, 193, 233, 389, 419, 467, 577, 769, 839 and 1153. Their product is
slightly under $10^{36}$. Recall Linnik’s theorem: Let $P(a,d)$ be the the
least prime in the arithmetic progression $a,a+d,a+2d\cdots$. Then Linnik’s
theorem says there are effective constants $c$ and $\ell$ with $p(a,d)\leq
cd^{\ell}$ as long as $a<d$. Thus, if one has effective constants in Linnik’s
theorem, one can then take $S$ to be the set of primes that are at most
$c(10^{36})^{\ell}$ but where one only needs $v_{p}\geq 1$ for all the primes
except the 19 primes used in our linear inequalities who will require larger
values. It is plausible that a careful and extensive computation could use a
smaller set. We suspect that our set of 19 primes above can be taken as a
valid set for $S$ with no other primes.

##  5 P-adic expansions and efficient reductions

In the previous section, we had to take substantial advantage of primes $p$
where $-1/p$ had many 0s in the repeating parts of their 2-adic expansion. In
the section prior, we also took advantage of such primes albeit in a more
limited fashion In particular in the previous section, in order to start a
reduction which required slipping in an extra division by 2, we had to start
with a prime $p$ such that the number of zeros in the repeating parts is at
least as high as the number of 1s. When these two quantities are exactly
equal, one does not end up with any $v_{2}$ term on the right-hand side of our
resulting inequality when $\alpha=\frac{2.5}{\log 2}$, and we get inequalities
with a $v_{2}$ term with positive coefficient when there are more $0$s than
$1$s. If one were to attempt to make the same reduction with a prime $p$ that
has more 1s than 0s, one would have a coefficient with a negative reduction
which would substantially complicate matters. Luckily, such primes are very
rare.

Motivated by these observations we will say an odd number $n>1$ is
_2-balanced_ (or just _balanced_) if $\frac{-1}{n}$ has in its purely periodic
2-adic piece exactly as many 1s as 0s. Similarly, we say $n$ is _2-efficient_
(or just _efficient_) if it has more 0s than 1s, and 2-inefficient (or just
inefficient) if it has more 1s than 0s. The first thing to note is that
2-inefficient numbers do exist but they seem to be very rare. The smallest
example is $187$ which has 21 1s and only 19 0s. 2-inefficient primes also do
exist but are very rare; an example is $p=937$ where there are 59 1s and 58
0s.

There are good heuristic reasons for expecting that inefficient numbers and
inefficient primes should be uncommon. Let $n$ be a positive odd number
greater than $1$. Note that we can obtain the 2-adic expansion of $-1/n$
explicitly by taking

$\frac{2^{k\phi(n)}-1}{n}$

in base $2$ and letting $k$ go to infinity. (Here $\phi$ is the Euler $\phi$
function.) Moreover, in the case of $k=1$ we will just have the quantity

$M=\frac{2^{\phi(n)}-1}{n}.$

Note that $M$’s base $2$ expansion must contain a complete copy of the
repeating part of $-1/n$, and in fact must agree with the first $\phi(n)$
digits of $-1/n$, but the last set of digits of $M$ must be all 0s, because
$M$ has about $\log_{2}n$ fewer digits than $2^{\phi(n)}$ does, so there’s a
bias towards having extra zeros.

We have the following questions about efficient, balanced and inefficient
numbers.

Let $B(x$) be the number of balanced n less than or equal to x, and similarly
define $E(x)$ and $I(x)$.

######  Conjecture 116.

For all $x$ we have $B(x)+E(x)\geq I(x)$.

It is also likely that for all $x$ we have that $B(x)\geq I(x)$ and that
$E(x)\geq I(x)$, but we are substantially less confident in those claims and
so will not label them as conjectures. Asymptotics for all three of these
quantities would be nice. Unfortunately, at this point we do not even have
conjectural orders of magnitude of growth for any of these three quantities,
although we are confident that the set of all odd numbers which are either
balanced or efficient has density 1 in the set of odd numbers, and thus
strongly suspect that $I(x)=o(x)$.

Unfortunately, at present, we do not even see any way to prove that there are
infinitely many inefficient numbers. We have easily that there are infinitely
many efficient numbers; if we set $n=2^{k}-1$ then $-1/n$ has repeating part
with exactly one 1 and $k-1$ zeros. Thus, $2^{k}-1$ is efficient for $k\geq
2$. Similarly, $n=2^{k}+1$ is easily seen to be balanced.

Of course, for our earlier situation, what we really care about are not just
efficient numbers, balanced numbers, and inefficient numbers, but rather
efficient primes, balanced primes, and inefficient primes. One obvious
question is are there are infinitely many primes which are balanced, efficient
or inefficient? We strongly expect that there are infinitely many efficient
primes. Note that if there are infinitely many Mersenne primes then this is
trivially true by the remark in the last paragraph. Since the set of efficient
primes appears to be much larger than the set of Mersenne primes, one would
hope that an unconditional proof is possible. A subsequent paper by this
author and Christian Roettger will show that there are infinitely many
balanced primes. [13]

Another natural question is whether powers of primes are efficient, balanced
or inefficient. In the context of the original problem, the most natural
question is whether all powers of $3$ are balanced. A power of 3 that is
efficient would be very helpful for improving Theorem 63/ An efficient power
of $3$ would also allow one to possibly give a shorter proof of Theorem 63 by
allowing $v_{3}$ to be directly bounded below by a function of $v_{2}$ rather
than having to go through other $v_{p}$ as intermediaries. Such a power of $3$
if it is not too big and is reasonably efficient might also allow for a
shorter proof of Theorem 1 or result in tightening of that Theorem.
Unfortunately, no such power of 3 exists. The aforementioned paper by [13]
will prove that all powers of 3 are balanced.

Our questions about balanced, efficient, and inefficient numbers can also be
generalized to the $p$-adics for other primes $p$. However, there are multiple
potential generalizations. We discuss three of the more natural ones here.

First, one can compare the number of non-zero and zero digits in which case
one has an expected ratio based on a naive random model where the chance that
any given digit is zero is $1/(p-1)$. One then correspondingly defines numbers
a as balanced, efficient and inefficient with respect to the expected number
of 0s. However, this seems tricky and unlikely to be the correct
generalization. At a practical level, this generalization seems to be
unhelpful for understanding integer complexity.

Second, one can take the average value of the digits in the purely periodic
part, and defines a number to be $p$-balanced if the average is exactly
$(p-1)/2$, $p$-efficient if the average is strictly less than $(p-1)/2$ and
$p$-inefficient if the average is great $(p-1)/2$. This generalization seems
to be the most natural generalization.

The third possible generalization is a variant of the second generalization
where instead of averaging the values of the digits, one instead averages the
integer complexity of the values of the digits. This average is a useful
metric for understanding whether a given reduction is likely to give rise to a
productive inequality using our methods above. Unfortunately, it isn’t obvious
how to use this average to define corresponding notions of balanced,
efficient, and inefficient.

It is most likely that that second generalization is the most natural to
anyone interested in questions about $p$-adic behavior independent of their
applications to integer complexity issues. The second generalization also has
the advantage that as long as $p$ is small in practice this will also give
useful information from an integer complexity standpoint.

Define $S(m,n,\alpha)$ to be to denote the statement “If for all $m<k<n$,
$\|k\|\leq\alpha\log k$ then $\|n\|\leq\alpha\log n$.” We suspect then that a
careful study of efficient primes will allow one to prove the following:

######  Conjecture 117.

For any $\alpha>\frac{2}{\log 2}$ there is a finite set of primes $S_{\alpha}$
such that for any $m$ if $v_{p}$ is sufficiently large for all $p\in
S_{\alpha}$, then $S(m,n,\alpha)$.

Note that with a small amount of additional work the proof of Theorem 63 can
be adjusted to give a stronger result in terms of $S(m,n,\alpha)$ and can then
be thought of as the special case of Conjecture 117 where
$\alpha=\frac{5}{2\log 2}$.

One question closely related to the above conjecture is whether these methods
can be used to establish results of the form For all $n$ except an explicit,
finite exceptional set B, we have $\|n\|\leq\beta\log n$ where $\beta$ is some
number strictly less than $\frac{26}{\log 1439}$. While our results have been
phrased in terms of the interval $I_{0}$, they can mostly be adjusted with
little work to become sensible reductions for smaller choices of $\alpha$, and
it may be possible to make such an extension. Note that in this case the
definite results may be easier to handle than the indefinite results. Suppose
for example one is interested in the case $n\equiv 1$ (mod $6$). Then the
reduction $[1,6]n$ involves a the number $\frac{n-1}{6}$ and so one can have
that reduction be used to get an efficient representation of $n$ as long as
$n$ is larger than some exceptional set. For example, if one had as the
exceptional set just $\\{1,1439\\}$ it would be possibly useful as long as one
had $n>6(1439)+1$. The difficulty then would arise from the indefinite
results, and one would need to have additional auxiliary primes to ensure that
the reduction did not lead to too small a number.

##  6 Appendix

Proof of Lemma18:

###### Proof.

This proof is very similar to the earlier lemmata.

We may assume that $n\equiv 1,2,3,4$ or $5$ (mod 7). And by the above work, we
may also assume assume that $n\equiv 8$ (mod 9), $n\equiv 4$ (mod 5) and
$n\equiv 15$ (mod 16). In fact, we can do better than that for $v_{2}$, but
will not need it in this lemma. As before we have cases, this time based on
$n$ (mod 7):

Case I: If $n\equiv 1$ (mod 7) then we may use $[1,14]n$.

Case II: If $n\equiv 2$ (mod 7) then we may use $[2,21]n$.

Case III: If $n\equiv 3$ (mod 7). then we may use
$[1,4][1,10][1,3][1,7][1,2]n$.

Case IV: If $n\equiv 4$ (mod 7) then we may use
$[1,4][1,10][1,3][1,7][1,2][2,3]n$.

Case V: If $n\equiv 5$ (mod 7) then we may use $[1,8][1,14][2,3]n$. ∎

Proof of Lemma 19:

###### Proof.

We may assume that $v_{2}\geq 6$, $v_{3}\geq 2$, $v_{5}\geq 1$, $v_{7}\geq 1$.

Case I. $n\equiv 1$ (mod 13). We may use $[1,26]n$.

Case II, $n\equiv 2$ (mod 13). We may use $[2,39]n$.

Case III. $n\equiv 3$ (mod 13). We may use $[1,26][1,2]n$.

Case IV. $n\equiv 4$ (mod 13). We may use $[1,8][2,9][1,14][4,65]n$.

Case V. $n\equiv 5$ (mod 13). We may use $[1,14][2,39][1,2]n$.

Case VI. $n\equiv 6$ (mod 13). We may use one of $[1,48][2,9][6,91]n$,

$[1,6][1,16][2,9][6,91]n$ or $[1,6][1,10][1,2][1,16][2,9][6,91]n$ or
$[1,20][1,2][1,16][2,9][6,91]n$, depending on $[1,16][2,9][6,91]n$ (mod 6).

Case VII. $n\equiv 7$ (mod 13). We may use $[1,26][1,2]^{2}n$.

Case VIII. $n\equiv 8$ (mod 13). We may use $[1,14][2,39][2,3]n$.

Case IX. $n\equiv 9$ (mod 13). We may use $[1,8][2,9][1,14][4,65][1,2]n$.

Case X. $n\equiv 10$ (mod 13). We may use $[1,14][2,39][1,2]^{3}n$.

Case XI. $n\equiv 11$ (mod 13). May use $[1,14][1,26][1,2][2,3]n$.
∎

Proof of Lemma 22:

###### Proof.

We may assume that $v_{2}\geq 8$, $v_{3}\geq 3$, $v_{5}\geq 1$, $v_{7}\geq 1$
and $v_{13}\geq 1$.

Case I $n\equiv 1$ (mod 11). We may use $[1,12]^{3}[1,22]n$.

Case II: $n\equiv 2$ (mod 11). We may use $[1,4][1,12]^{2}[2,33]n$.

Case III: $n\equiv 3$ (mod 11). We may use $[1,12]^{3}[1,22][1,2]n$.

Case IV: $n\equiv 4$ (mod 11). We may use $[1,14][1,4][1,12]^{2}[4,55]n$.

Case V: $n\equiv 5$ (mod 11). We may use $[1,4][1,12]^{2}[2,33][1,2]n$.

Case VI: $n\equiv 6$ (mod 11). We may use $[1,12]^{3}[6,77]n$.

Case VII: $n\equiv 7$ (mod 11). We may use $[1,12]^{2}[1,22][1,2]^{2}n$.

Case VIII: $n\equiv 8$ (mod 11). We may use $[1,14][1,4][1,12][2,33][2,3]n$.

Case IX: $n\equiv 9$ (mod 11). We may use $[1,14][1,4][1,12]^{2}[4,55][1,2]n$.

Note that in Cases IV and IX we did not need to use that $\|55\|=12$ from
$55=2(27)+1)$ rather than the weaker representation from the factorization of
$55$, so if the earlier lemmata can be tightened, this one is easier to
tighten than it might naively appear.

∎

Proof of Lemma 25

###### Proof.

We may assume that $v_{2}\geq 8$, $v_{3}\geq 3$, $v_{5}\geq 1$, $v_{7}\geq 1$,
$v_{11}\geq 1$, and $v_{13}\geq 1$.

Case I: $n\equiv 1$ (mod 19). We may use $[1,20][1,38](n)$.

Case II $n\equiv 2$ (mod 19). We may use $[1,20][2,57](n)$.

Case III $n\equiv 3$ (mod 19). We may use $[1,10][1,38][1,2](n)$.

Case IV: $n\equiv 4$ (mod 19). We may use $[1,3][1,12][1,4][4,95](n)$.

Case V: $n\equiv 5$ (mod 19). We may use $[2,57][1,2](n)$.

Case VI: $n\equiv 6$ (mod 19). We may use $[1,24][1,4][6,133](n)$.

Case VII: $n\equiv 7$ (mod 19). We may use $[1,20][1,38][1,2]^{3}n$.

Case VIII: $n\equiv 8$ (mod 19). We may use $[1,20][2,57][2,3]n$.

Case IX: $n\equiv 9$ (mod 19). We may use $[1,21][1,12][1,4][4,95][1,2]n$.

Case X: $n\equiv 10$ (mod 19). We may use
$[1,22][1,8][1,4][2,39][2,57][1,2][4,5]n$.

Case XI:$n\equiv 11$ (mod 19). We may use $[2,57][1,2]^{2}n$.

Case XII: $n\equiv 12$ (mod 19). We may use
$[A][1,4][1,27][1,4][1,4][1,20][12,247]n$.
Here $[A]$ is either $[1,13][0,2]$ or $[1,6]$.

Case XIII: $n\equiv 13$ (mod 19). We may use $[1,24][1,4][6,133][1,2]n$.

Case XIV: $n\equiv 14$ (mod 19). We may use $[1,3][1,24][1,4][4,95][2,3]n$.

Case XV: $n\equiv 15$ (mod 19). We may use $[1,10][1,38][1,2]^{4}n$.

Case XVI: $n\equiv 16$ (mod 19) We may use either
$[1,8][1,4][2,57][2,3][1,2][1,2]n$
or $[1,10][1,4][1,4][2,57][2,3][1,2][1,2]n.$

Case XVII: $n\equiv 17$ (mod 19). We may use $[1,8][1,4][2,57][2,3][1,2]n$.
∎

Proof of Lemma 35

###### Proof.

We may assume that $v_{2}\geq 10$, $v_{3}\geq 4$, $v_{5}\geq 2$, $v_{7}\geq 1$
$v_{11}\geq 1$ $v_{13}\geq 1$ $v_{19}\geq 1$.

Case I: $n\equiv 1$ (mod 17). We may use $[1,34]n$.

Case II: $n\equiv 2$ (mod 17). We may use $[2,51]n$.

Case III: $n\equiv 3$ (mod 17). We may use $[1,18][1,34][1,2]n$.

Case IV: $n\equiv 4$ (mod 17). We may use $[1,18][4,85]n$.

Case V: $n\equiv 5$ (mod 17). We may use $[1,18][1,34][2,3]n$.

Case VI: $n\equiv 6$ (mod 17). We may use $[1,18]^{2}[6,119]n$.

Case VII: $n\equiv 7$ (mod 17). We may use $[1,18][1,34][1,2]^{3}n$.

Case VIII: $n\equiv 8$ (mod 17). We may use $[1,18][2,51][2,3]^{2}n$.

Case IX: $n\equiv 9$ (mod 17). We may use $[1,18][4,85][1,2]n$.

Case X: $n\equiv 10$ (mod 17). We may use $[1,18]^{2}[6,119][1,2]^{2}n$.

Case XI: $n\equiv 11$ (mod 17). We may use $[1,18][1,34][2,3][1,2]n$.

Case XII: $n\equiv 12$ (mod 17). We may use
$[1,10][1,6][1,18][4,85][1,2][2,3]n$.

Case XIII: $n\equiv 13$ (mod 17). We may use $[1,18]^{2}[6,119][1,2]n$.

Case XIV: $n\equiv 14$ (mod 17). We may use $[1,6][1,18][4,85][2,3]n$.

Case XV: $n\equiv 15$ (mod 17). We may use $[1,18]^{2}[1,34][1,2]^{4}n$.
∎

Acknowledgements: Harry Altman and Juan Arias de Reyna provided extensive
feedback. Juan Arias de Reyna provided substantial and detailed suggestions,
including making explicit Lemma 7, checking and supplying correct versions of
some the final gadgets, strengthening and simplifying the final gadgets, along
with many other suggestions both large and small which greatly improved the
presentation of the results.

## References

  * [1] H. Altman, Integer Complexity: The Integer Defect, Mosc. J. Comb. Number Theory 8 (2019), 3, 193–217
  * [2] H. Altman, Integer Complexity and Well-Ordering, Michigan Math. J. 64 3 (2015), 509-538.
  * [3] H. Altman, J. Zelinsky, Numbers With Integer Complexity Close to the Lower Bound Integers, 12A, (2012).
  * [4] J. Arias de Reyna, “Complejidad de los números naturales,” Gaceta R. Soc. Mat. Esp., 3 (2000), 230–250. (See also the English version at https://arxiv.org/abs/2111.03345 ).
  * [5] J. Čerņenoks, J. ;J. Iraids, J., M. Opmanis, R. Opmaniss, K. Podnieks, Integer complexity: experimental and analytical results II, Descriptional complexity of formal systems, 58–69, Lecture Notes in Comput. Sci., 9118, Springer, Cham, 2015.
  * [6] K. Cordwell, A. Epstein, A. Hemmady, S. J. Miller, E. Palsson, A. Sharma, S. Steinerberger, Y. N. T. Vu, Yen “On algorithms to calculate integer complexity.” Integers 19 (2019), A12
  * [7] Richard K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly, 93 (1986), 186–190; and see 94 (1987), 965 & 96 (1989), 905.
  * [8] Richard K. Guy, Unsolved Problems in Number Theory, Third Edition, Springer-Verlag, New York, 2004, pp. 399–400.
  * [9] Jānis Iraids, Kaspars Balodis, Juris Čerņenoks, Mārtiņš Opmanis, Rihards Opmanis, Kārlis Podnieks. Integer Complexity: Experimental and Analytical results, arXiv:1203.6462, 2012
  * [10] K. Mahler & J. Popken, On a maximum problem in arithmetic (Dutch), Nieuw Arch. Wiskunde, (3) 1 (1953), 1–15; MR 14, 852e.
  * [11] J. Arias de Reyna, J. van de Lune, Algorithms for determining integer complexity http://arxiv.org/abs/1404.2183
  * [12] Daniel A. Rawsthorne, How many 1’s are needed?, Fibonacci Quart., 27 (1989), 14–17; MR 90b:11008.
  * [13] Christian Roettger, Joshua Zelinsky, “On balanced numbers”, in preparation.