Find the smallest positive integer that cannot be made from four 8s, or show it doesn't exist

Question

This puzzle was inspired by one recently posted by @Max.

What is the smallest positive integer that cannot be made from four 8s, where bracketing is allowed and the only permitted operations are addition, subtraction, multiplication, division, rooting (so the square root is allowed, because the symbol does not require the writing of a number to specify which root, and for example the eighth and 88th roots are also allowed, using up one and two 8s respectively: the rule is that you can use the radical symbol, $\surd \,$), exponentiation, taking the absolute value, and the floor and ceiling functions? All other operations, such as taking logarithms, are not allowed.

If the number exists, it is greater than 100. (See @Marius's answer to @Max's question.)

But it is not clear that it does exist, because there is no largest integer that can be made from four 8s. Although

$$\Huge 8^{ \raise.1ex{\Big(} 8^{(8^{\huge 8})} \raise.1ex{\Big)} }$$

is a very large number, it can be exceeded by inserting a sufficiently large number of $\surd$ symbols into the expression

$$\left\lceil \frac{\huge 8}{\sqrt{\sqrt{\sqrt{\large 8 \raise1.8ex\,}}} ~ \raise.2ex- ~ \Large\frac{8}{8}} \right\rceil ~ \raise-4ex.$$

If the required number does not exist, prove its non-existence, for example by showing how to construct a four-8s expression for any given positive integer.

Answer 1

Bear with me for any poor formatting. I think I have a way to generate any number using equations of this form:

$X=\Large\left\lfloor\frac{8}{\sqrt{\sqrt{\sqrt{\sqrt{8}}-\frac{8}{8}}}}\Large\right\rfloor$

Equations of this form can be written as:

$X=\Large\left\lfloor\frac{8}{{\left(8^{0.5^a}-1\right)}^{0.5^b}}\Large\right\rfloor$

And then for large a (not even very large):

$8^{0.5^a}-1 \approx \ln{8}*0.5^a$

Which is its own separate proof. The rate that the above equation converges won't matter since we'll be dealing with arbitrarily large a. But it seems to converge quickly.

Now we make the substitution:

$X=\Large\left\lfloor\frac{8}{{(\ln{8}*0.5^a)}^{0.5^b}}\Large\right\rfloor$

Which is equivalent to:

$X=\Large\left\lfloor\frac{8}{0.5^{\left(a+\frac{\ln{\ln{8}}}{\ln{0.5}}\right)(0.5^b)}}\Large\right\rfloor$

You'll notice that if we can get:

$\left(a+\frac{\ln{\ln{8}}}{\ln{0.5}}\right)(0.5^b)$

to be any number we like, we can get X to be any number we like. And we can!

Let's suppose I want to make the number 2017. Then:

$\left(a+\frac{\ln{\ln{8}}}{\ln{0.5}}\right)(0.5^b)=\frac{\ln{\frac{8}{2017.5}}}{\ln{0.5}}\approx 7.97835295...$

We can match this with arbitrary precision! For instance a=8365910, and b=20

So we plug our values back in:

$X=\Large\left\lfloor\frac{8}{{\left(8^{0.5^{8365910}}-1\right)}^{0.5^{20}}}\Large\right\rfloor=2017$

I tried looking for a calculator that can do this, and this site seems to handle it. But you have to specify precision, such as with

8/(8^(n(0.5,1000)^8365910)-1)^(n(0.5,1000)^20)

Which will return 2017.4993496403731... which of course rounds down to 2017. You'll notice I set 2017.5 as my original target so that the floor function had plenty of room to round down.

EDIT: Quick proof of that approximate substitution thing I used above:

$\lim_{a\to \infty}{\frac{8^{0.5^a}-1}{\ln{8}*0.5^a}}$
Derive top and bottom since both equal zero (L'Hospital's Rule)
$\lim_{a\to \infty}{\frac{\ln{8}\ln{0.5}*0.5^a8^{0.5^a}}{\ln{8}\ln{0.5}*0.5^a}}$
Cancel out terms
$\lim_{a\to \infty}{8^{0.5^a}}=1$
So they're equal

Some actual values so you can see how quickly it converges.

f(1)=1.7585751636...

f(10)=1.001016039957...

f(100)=1.0000000000000000000000000000008201950684...

f(1000)=1+9.703335688...e-302

EDIT EDIT: Fixed a mistake in my meaning.

Answer 2

Having thought about this some more, I now think that perhaps all positive integers can be made and therefore the required number does not exist. I'm putting this as a separate answer from my first effort, because this lot of handwaving points in the other direction from the first lot.

Consider the number

$X=\Large\lceil\sqrt[\sqrt{\sqrt{\sqrt{8}}}-\frac{8}{8}]{\sqrt{\sqrt{8}}}\Large\rceil$,

in which

$\sqrt{\sqrt{\sqrt{8}}}-\frac{8}{8}$

is the index of the root shown using the expression's largest radical symbol, namely the first of the sequence of three in its right hand part. (All other instances of the symbol denote square roots.)

Now

adding $\sqrt{}$s on the left makes the index of the root smaller and smaller, getting closer to 0, which makes the value of the whole expression ever larger,

whereas

adding them on the right makes the value of the whole expression ever smaller.

We can make positive integers of the form $X(a,b)$, where

$a$ and $b$ are the numbers of instances of $\sqrt{}$ on the left and right respectively, so that

and where

increasing $a$ increases X, whereas increasing $b$ decreases it.

I conjecture that by choosing the right values of $a$ and $b$ we can probably get X to be any positive integer we like.

Answer 3

This is a bit of handwaving that suggests that the required number does exist.

Call an expression "basic" if it does not contain any instances of $\sqrt{}$.

* Basic expressions are finitely many.

* In each basic expression, the places in which the $\sqrt{}$ symbol may be permissibly inserted are also finitely many.

* In each of these places there is no upper bound on the number of $\sqrt{}$ symbols that may be inserted, and the constructibility of infinitely many numbers is equivalent to the insertability of however many $\sqrt{}$ symbols you like at each of these places.

Now $\sqrt{}$ is not a finely tunable tool. If you have only one number, say 100, and you are allowed to use $\sqrt{}$ as many times as you like, you can make 10, and using floor and ceiling functions you can make 1, 2, 3 and 4, but you can't make every positive integer. Given any positive integer, can you make it by choosing one of the finitely many basic expressions containing four 8s and then distributing sufficiently many instances of $\sqrt{}$ into each of the finitely many places where you can insert them? I doubt it.

Answer 4

If you're allowed an increasing monadic operator (e.g. !) by which you can make arbitrarily large integers, a decreasing monadic operator (e.g. sqrt) by which you can turn an arbitrarily large number into a number arbitrarily close to 1, and the floor and/or ceiling operator to turn a real into an integer, you can get any positive integer.