# What numbers are in the set $S$?

Here is a problem that I came up with that has been bothering me for a while, and I haven't been able to solve it.

Let $S$ be the set defined by the following rules:

• $2\in S$.
• Define the functions $\alpha$ and $\beta$ as $$\alpha(n)=n^2$$ $$\beta(n)=\lfloor n/3\rfloor$$ If $n\in S$, then $\alpha(n)\in S$ and $\beta(n)\in S$.
• If the previous two rules do not imply that a number $n$ is in $S$, then $n\notin S$.

QUESTION: What numbers are in $S$?

So far, I've verified that every positive integer from $1$ to $14$ is in $S$, since I've found "composition sequences" of $\alpha$ and $\beta$ that, when applied to $2$, yield each of those numbers. For example, $$3=(\beta^{\circ 4}\circ\alpha^{\circ 3})(2)$$ Things get a little crazy when I get to $n=6$: $$6=(\beta^{\circ 10}\circ\alpha^{\circ 2}\circ \beta\circ\alpha^{\circ 2})(2)$$ ...and even crazier at $n=14$: $$14=(\beta^{\circ 3}\circ \alpha\circ \beta^{\circ 10}\circ \alpha^{\circ 2}\circ \beta\circ \alpha\circ \beta^{\circ 10}\circ \alpha^{\circ 2}\circ\beta^{\circ 2}\circ \alpha^{\circ 3})(2)$$ Any ideas how to prove (or disprove) that any positive integer can be reached?

NOTE: It is true that all positive integers are in $S$ if (not iff) the following is true:

Blockquote For any positive integer $N$, there exist positive integers $a,b$ such that $$N=\bigg\lfloor \frac{2^{2^a}}{3^b}\bigg\rfloor$$

If someone figures out how to prove this, then we're done... if it's false, then there remains some work to be done.

• Your final question is closely related to the binary expansion of $\log_2 3$ (it is equivalent to every finite sequence of binary digits appearing somewhere in it). – Eric Wofsey Apr 21 '18 at 23:24
• @EricWofsey ...which is equivalent to $\log_2(3)$ being a normal number, right? – Franklin Pezzuti Dyer Apr 21 '18 at 23:24
• No, that is weaker than normality, but it is related. – Eric Wofsey Apr 21 '18 at 23:26
• Er, sorry, it's the binary expansion of $1/\log_2 3$, not the binary expansion of $\log_2 3$. – Eric Wofsey Apr 21 '18 at 23:30
• Anyways, my understanding is that this is the sort of question whose answer is almost certainly yes, but also no one has any idea how to answer it. (But I might be wrong about the latter.) – Eric Wofsey Apr 21 '18 at 23:36

I don't know how to answer this, but let me elaborate on my comments about your proposed proof strategy. The punchline is that it is very likely that $S$ does contain all positive integers via your strategy, but it is an open problem to prove this.

As you say, a sufficient condition for $S$ to contain a positive integer $N$ is that $N$ can be written in the form $$N=\bigg\lfloor \frac{2^{2^a}}{3^b}\bigg\rfloor.$$ More generally, if you modify your definition of $S$ to start with $x\in S$ and modify your functions to $\alpha(n)=n^y$ and $\beta(n)=\lfloor n/z\rfloor$ for some positive integers $x,y,$ and $z$, then a sufficient condition for $S$ to contain $N$ is that $N$ can be written in the form $$N=\bigg\lfloor \frac{x^{y^a}}{z^b}\bigg\rfloor.$$

I now claim that this is possible for all positive integers $N$ iff every finite sequence of digits appears in the base $y$ expansion of $\log_z x$. So, in your case, that would be the binary expansion of $\log_3 2$. The proof is basically "take $\log_z$ of everything"; I've written up the details below.

Now, the bad news is that questions like this are typically very hard to answer: if you pick some specific nicely defined irrational number, it is usually very difficult to say much about its base expansions. In particular, I'm pretty sure that for all positive integers $x,y,$ and $z$ for which $\log_z x$ is irrational, it is an open problem whether the base $y$ expansion of $\log_z x$ contains all finite sequences.

On the other hand, if you pick a random number (uniformly from some interval), then with probability $1$ it will contain every finite sequence in every base. So it is considered extremely likely that $\log_z x$ contains every finite sequence in base $y$; it would be an amazing discovery if it didn't. In particular, this means it is extremely likely that your set $S$ contains all positive integers.

Of course, since this condition is only sufficient and not necessary for $S$ to contain all positive integers, it is possible that there is an easier proof which does not require solving this open problem. I haven't been able to find any promising approach that doesn't end up reducing to a question of this sort, though.

OK, now here's the proof of the claimed equivalence. Let's write $C=\log_z x$.

First, suppose every finite sequence of digits appears in the base $y$ expansion of $C$, and let $N$ be any positive integer. Choose integers $m$ and $k$ such that $$\log_z N<\frac{m}{y^k}<\frac{m+1}{y^k}<\log_z(N+1).$$ Let the string $s$ be the base $y$ expansion of $m$, with enough initial zeroes added (if necessary) so that $s$ has length at least $k$. This string $s$ appears infinitely many times in the base $y$ expansion of $C$ (since every finite string containing it appears somewhere), and in particular it appears somewhere starting after the decimal point. This means that there exist positive integers $a$ and $b$ such that the base $y$ expansion of $y^aC-b$ is identical to that of $\frac{m}{y^k}$ up to the $k$th digit after the decimal point. That is, $$\frac{m}{y^k}\leq y^aC-b<\frac{m+1}{y^k}.$$ By our choice of $m$ and $k$, this implies that $\lfloor z^{y^aC-b}\rfloor=N$. But $$z^{y^aC-b}=\frac{z^{y^a\log_z x}}{z^b}=\frac{x^{y^a}}{z^b},$$ so this is exactly what we wanted.

Conversely, suppose every $N$ can be written in this form, and let $s$ be a finite string of base $y$ digits. Note that there exists a positive integer $N$ such that the base $y$ expansions of $\log_z N$ and $\log_z(N+1)$ after the decimal point both start with $s$. (This is true because the difference between $\log_z N$ and $\log_z(N+1)$ goes to $0$ as $N$ gets large.) By hypothesis, there exist positive integers $a$ and $b$ such that $$N=\bigg\lfloor \frac{x^{y^a}}{z^b}\bigg\rfloor.$$ This means that $$\log_z \frac{x^{y^a}}{z^b}=y^aC-b$$ is between $\log_z N$ and $\log_z(N+1)$, and thus its base $y$ expansion starts with $s$ after the decimal point. This implies that the string $s$ appears in the base $y$ expansion of $C$ (starting $a$ digits after the decimal point), as desired.

I will use $[x]$ for the floor of $x\ge 0$.

For a real $x\ge0$ and an integer $b$ we have $[[x/3^b]/3] = [x/3^{b+1}]$.

So it is enough to show that each integer number $N\ge 2$ can be written in the form $$N = \left[\frac {2^{2^a}}{3^b}\right] \ ,$$ for suitable natural numbers $a,b$. This relation above is equivalent to the double inequality: $$N \le \frac {2^{2^a}}{3^b}< N+1\ ,$$ that we successively restate equivalently: $$\log N \le 2^a\log 2- b \log 3 < \log(N+1)\ ,$$ $$\underbrace{\frac {\log N}{\log 3}}_{=:U} \ \le \ 2^a \underbrace{\frac {\log 2}{\log 3}}_{=:s}- b \ < \ \underbrace{\frac{\log(N+1)}{\log 3}}_{=:V}\ .$$ Let $T$ be the "torus" (or the "circle") $\mathbb R/\mathbb Z$. The multiplication by $2$ map from $\mathbb R$ induces a map, also called "multiplication by $2$" in the following, $T=\mathbb R/\mathbb Z\overset {\cong}{\to} \mathbb R/2\mathbb Z\to \mathbb R/\mathbb Z=T$.

The real interval $I=(U, V)$ projects to an interval $\bar I$ in the torus $T$. (If there is no integer in $I$, then we can use without abuse and/or danger of confusion the "same notation" $(U,V)$... But we use $(U,V)_T:=\bar I$ to have a small pedant distinction.)

Because $s\not\in \mathbb Q$, (by unique factorization in $\mathbb Z$, a power of two is not a power of three,) the ergodic doubling map $T\overset{2}{\to} T$, applied recursively from the starting point $s$, gives rise to a sequence $(T^as)_{a\in\mathbb N}$.

If we can show this sequence is dense in $T$, then there exists an $a$, so that $T^a s \in (U,V)_T$. This determines the corresponding $b$, and the solution.

The doubling map can be better understood if we write $s$ in binary representation, $$s = 0, s_0s_1s_2s_3\dots\ .$$ The first digits are as in the following code snippet:

sage: floor( log(2)/log(3) * 2^20).digits(base=2)[::-1]
[1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1]
sage: print "%.11f" % s
0.63092975357
sage: print "%.11f" % (2^-1 + 2^-3 + 2^-8 + 2^-9 + 2^-14 + 2^-17 + 2^-20 )
0.63092899323


The doubling map corresponds to the shift $$(s_0, s_1, s_2, s_3,\dots) \to (s_1, s_2, s_3,\dots)\ .$$ The question remains now: If we give a finite sequence of digits (zeros and/or ones, e.g. the first digits of $U$, taken with the approximation $(V-U)/2$), does this sequence appear "somewhere" in the binary representation of our $s$ (on consecutive places)?

This is too much ergodicity for me, have to put a break here, time.

(The doubling map on $\mathbb R\mod 1$ is one of the first examples in each exposition of dynamical systems, the favorite search engine will exhibit many hits.)

Some experiment:

Using sage we can implement the above for the first few integers $>2$. The code is:

R = RealField(100000)

def T(x):
return (2*x).frac()

for N in [3..64]:

U = ( R(log(N  )) / R(log(3)) ).frac()
V = ( R(log(N+1)) / R(log(3)) ).frac()

s = R(log(2)) / R(log(3))

if V < U:
if 1-U > V:    U, V = U, R(1)
else      :    U, V = R(0), V

a = 0
while not( a > N and U <= s and s < V ) and a < 500:
a += 1
s = T(s)

b = floor( ( R(2)^a * log(R(2)) - log(N) ) / log(R(3)) )
print ( "%s = [ 2^(2^%s) / 3^%s ]"
% ( floor( exp( R(2)^a * log(R(2)) - b * log(R(3)) ) ), a, b ) )


Results:

3 = [ 2^(2^4) / 3^9 ]
4 = [ 2^(2^6) / 3^39 ]
5 = [ 2^(2^8) / 3^160 ]
6 = [ 2^(2^7) / 3^79 ]
7 = [ 2^(2^20) / 3^661576 ]
8 = [ 2^(2^19) / 3^330787 ]
9 = [ 2^(2^10) / 3^644 ]
10 = [ 2^(2^11) / 3^1290 ]
11 = [ 2^(2^17) / 3^82695 ]
12 = [ 2^(2^15) / 3^20672 ]
13 = [ 2^(2^23) / 3^5292620 ]
14 = [ 2^(2^18) / 3^165392 ]
15 = [ 2^(2^25) / 3^21170487 ]
16 = [ 2^(2^69) / 3^372435190163881929150 ]
17 = [ 2^(2^21) / 3^1323153 ]
18 = [ 2^(2^32) / 3^2709822655 ]
19 = [ 2^(2^80) / 3^762747269455630190904380 ]
20 = [ 2^(2^24) / 3^10585242 ]
21 = [ 2^(2^95) / 3^24993702525522090095554811833 ]
22 = [ 2^(2^31) / 3^1354911326 ]
23 = [ 2^(2^60) / 3^727412480788831890 ]
24 = [ 2^(2^48) / 3^177590937692583 ]
25 = [ 2^(2^47) / 3^88795468846290 ]
26 = [ 2^(2^74) / 3^11917926085244221732878 ]
27 = [ 2^(2^63) / 3^5819299846310655140 ]
28 = [ 2^(2^65) / 3^23277199385242620569 ]
29 = [ 2^(2^66) / 3^46554398770485241141 ]
30 = [ 2^(2^71) / 3^1489740760655527716607 ]
31 = [ 2^(2^67) / 3^93108797540970482285 ]
32 = [ 2^(2^53) / 3^5682910006162746 ]
33 = [ 2^(2^37) / 3^86714325042 ]
34 = [ 2^(2^58) / 3^181853120197207970 ]
35 = [ 2^(2^45) / 3^22198867211570 ]
36 = [ 2^(2^68) / 3^186217595081940964573 ]
37 = [ 2^(2^43) / 3^5549716802890 ]
38 = [ 2^(2^41) / 3^1387429200720 ]
39 = [ 2^(2^79) / 3^381373634727815095452188 ]
40 = [ 2^(2^81) / 3^1525494538911260381808762 ]
41 = [ 2^(2^161) / 3^1844209735770936274870220836597588246728413581752 ]
42 = [ 2^(2^158) / 3^230526216971367034358777604574698530841051697716 ]
43 = [ 2^(2^59) / 3^363706240394415943 ]
44 = [ 2^(2^154) / 3^14407888560710439647423600285918658177565731104 ]
45 = [ 2^(2^46) / 3^44397734423143 ]
46 = [ 2^(2^62) / 3^2909649923155327568 ]
47 = [ 2^(2^114) / 3^13103898309700925572018241187760081 ]
48 = [ 2^(2^69) / 3^372435190163881929149 ]
49 = [ 2^(2^148) / 3^225123258761100619490993754467479034024464545 ]
50 = [ 2^(2^96) / 3^49987405051044180191109623668 ]
51 = [ 2^(2^52) / 3^2841455003081371 ]
52 = [ 2^(2^57) / 3^90926560098603983 ]
53 = [ 2^(2^119) / 3^419324745910429618304583718008322701 ]
54 = [ 2^(2^109) / 3^409496822178153924125570037117499 ]
55 = [ 2^(2^107) / 3^102374205544538481031392509279372 ]
56 = [ 2^(2^78) / 3^190686817363907547726092 ]
57 = [ 2^(2^80) / 3^762747269455630190904379 ]
58 = [ 2^(2^157) / 3^115263108485683517179388802287349265420525848856 ]
59 = [ 2^(2^191) / 3^1980205125525243161966916284371100358043128831900396755423 ]
60 = [ 2^(2^82) / 3^3050989077822520763617527 ]
61 = [ 2^(2^350) / 3^1447036516603094510357950642070627639392595028537243195306937714466705813009580996918246268676282514900260 ]
62 = [ 2^(2^162) / 3^3688419471541872549740441673195176493456827163507 ]
63 = [ 2^(2^95) / 3^24993702525522090095554811832 ]
64 = [ 2^(2^231) / 3^2177258560896638515992457337687990263124256995974882712059461472653787 ]


(Of course, for $4, 16, 64$ we have better solutions. All the above computations are not exact, since sage does not accept too big exponents. So the equal sign should be replaced by $\approx$. (But the best ASCII approximation for this sign is the equal sign, sorry.))

• Also, $3$ can be written simpler as $$\bigg\lfloor\frac{2^{2^3}}{3^4}\bigg\rfloor$$ – TheSimpliFire Apr 27 '18 at 12:38