Jane’s infinite rosary

This mathematical treat was inspired by Jane Street‘s puzzle: Traversing the Infinite Sidewalk. I shared the puzzle with my mathematical friend Éric, and we had quite some fun discovering its properties.¹

It is also a testimony to the richness derived from the irrationality of ${\log }_2(3)$ and reminiscent of (Caruso, 2012) about the mathematics underlying the 12-tone Pythagorean temperament and the 53-commas musical scale.

Here goes Jane’s story: Jane owns an infinite rosary. It has a single end and is comprised of an infinite number of black and white beads. Starting from the end, the bead positions are numbered $n=0,1,2,\dots$ and each bead has a label $L(n)=1,1,2,2,3,3,\dots$ Every third bead including the zeroth one is black; the other beads are white.

Jane tells the beads of her rosary in a special way: each time she is done with a bead (say bead $n$), she moves on, either up to bead $n+L(n)$ or down to bead $n–L(n)$.

Starting at bead $0$, can Jane tell every bead in her rosary? (That is the question.)

Prelude: names

To weave the magic of a thing, you see, one must find its true name out.

Ursula K. Le Guin, A Wizard of Earthsea

• Bead: a natural number $n\in \mathbb{N}$ (the number represents the position of the bead in Jane’s rosary).
• Black bead: a bead $n$ divisible by $3$ (denoted $3\mid n$).
  When we know for sure that a bead is black, we may indicate it with: $\text{●}3n$.
• White bead: a bead $n$ not divisible by $3$ (denoted $3\nmid n$).
  When we know for sure that a bead is white, we may indicate it with: $\text{○}3n+1$.
• Even bead: a bead $n$ divisible by 2 (denoted $2\mid n$).
• Odd bead: a bead $n$ not divisible by 2 (denoted $2\nmid n$).
• Label: the label of bead $n$ is: $L(n)=1+\lfloor \frac{n}{2}\rfloor$, where $\lfloor \rfloor$ denotes the floor function.
  $L$ is an increasing function.
• Up: going up from bead $n$, Jane reaches bead $U(n)$ also denoted $nU$ (postfix notation for unary operator $U$).
  $$\begin{array}{}\text{(1)}& U:\mathbb{N}\to \mathbb{N},n\mapsto \lfloor \frac{3n}{2}\rfloor +1\end{array}$$
  $L$ is a strictly increasing function.
• Down: going down from bead $n>0$, Jane reaches bead $D(n)$ also denoted $nD$ (postfix notation for unary operator $D$).
  $$\begin{array}{}\text{(2)}& D:\mathbb{N}\to \mathbb{N},n\mapsto \lceil \frac{n}{2}\rceil –1\end{array}$$
  $D$ is an increasing function.
• Lambda: Jane can reach white bead $n$ by performing one up move from bead $\lambda (n)$ also denoted $n\lambda$ (postfix notation for unary operator $\lambda$).
  $$\begin{array}{}\text{(3)}& \lambda :\mathbb{N}\setminus 3\mathbb{N}\to \mathbb{N},n\mapsto \lfloor \frac{2n}{3}\rfloor \end{array}$$
  $\lambda$ is a strictly increasing function. Also, it holds that:
  $$\begin{array}{}\text{(4)}& \mathrm{\forall }n\in \mathbb{N}\setminus 3\mathbb{N},n=n\lambda U\end{array}$$
• Mu: given any $n$, there is a unique way for Jane to reach bead $n$ while moving down from an odd bead, which we denote $\mu (n)$ or $n\mu$ (postfix notation for unary operator $\mu$).
  $$\begin{array}{}\text{(5)}& \mu :\mathbb{N}\to \mathbb{N},n\mapsto 2n+1\end{array}$$
  $\mu$ is a strictly increasing function. Also, it holds that:
  $$\begin{array}{}\text{(6)}& \mathrm{\forall }n\in \mathbb{N},n=n\mu D\end{array}$$
• Nu: given any $n$, there is a unique way for Jane to reach bead $n$ while moving down from an even bead, which we denote $\nu (n)$ or $n\nu$ (postfix notation for unary operator $\nu$).
  $$\begin{array}{}\text{(7)}& \nu :\mathbb{N}\to \mathbb{N},n\mapsto 2n+2\end{array}$$
  $\nu$ is a strictly increasing function. Also, it holds that:
  $$\begin{array}{}\text{(8)}& \mathrm{\forall }n\in \mathbb{N},n=n\nu D\end{array}$$
• Recitation: starting at bead $n$ and randomly moving up or down finitely or infinitely many times, Janes performs a recitation. In other words a recitation is a sequence of natural numbers $(a_n)$ such that $a_0=n$ and $\mathrm{\forall }i,a_{i+1}\in \{a_{i}U,a_{i}D\}$.
• Length: the length of a recitation is the number of moves it comprises, finite or infinite. For a finite recitation of length $l$, we can write: $$\mathrm{\exists }(M_i{)}_1^l\in \{U,D{\}}^l,n_0{M}_1{M}_2\dots M_l=n_l$$
  $n_0$ is the start of the recitation. $n_l$ is the end of the recitation.
• Minimal recitation: a recitation from bead $n$ to bead $m$, with minimal length. By convention, a minimal recitation to bead $m$ means a minimal recitation from bead $0$ to bead $m$.
• Height: the height of bead $n$ (denoted $h(n)$) is the length of a minimal recitation to bead $n$. As we are about to see, every bead has a finite height.

The height of a bead

By definition $h(0)=0$.

What about the height of bean $n$ in general?

Given $n>0$, observe that:

• $3\nmid n⟹n=mU,$ where $m=n\lambda =\lfloor \frac{2n}{3}\rfloor <n$,
• $3\mid n\wedge 9\nmid n⟹n=m{U}^{2}D,$ where $m=n\mu {\lambda }^2=\lfloor \frac{8n}{9}\rfloor <n$,
• $9\mid n⟹n=m{U}^{2}D,$ where $m=n\nu {\lambda }^2=\lfloor \frac{8n+6}{9}\rfloor <n$.

This shows (by induction on $n$) that every bead has a finite height.$\text{<img draggable="false" role="img" class="emoji" alt="◻" src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

This also gives two upper bounds:

$$\begin{array}{}\text{(9)}& \text{for all }n,h(n)\le 1+\frac{4n}{3}\text{(10)}& \text{for all }n>0,h(n)\le 6\frac{\log (n)}{\log (9/8)}\end{array}$$

The logarithmic bound was suggested by Jianing Song.

Computing the height of a bead

The following simple exploration-based algorithm will do:

def height(n: int) -> int:
    if n < 0: raise Exception("n must be a nonnegative integer")
    if n == 0: return 0
    if n == 1: return 1
    visited = {0, 1}  # the beads we have visited so far
    rings = [{0}, {1}]  # the beads ordered by height (min length of path from 0)
    for height in itertools.count(2):
        new_ring = set()
        for bead in rings[height - 1]:
            label = (bead >> 1) + 1
            for next_bead in {bead - label, bead + label}:
                if not next_bead in visited:
                    if next_bead == n: return height
                    visited.add(next_bead)
                    new_ring.add(next_bead)
        rings.append(new_ring)

def height(n: int) -> int:

    if n < 0: raise Exception("n must be a nonnegative integer")

    if n == 0: return 0

    if n == 1: return 1

    visited = {0, 1}  # the beads we have visited so far

    rings = [{0}, {1}]  # the beads ordered by height (min length of path from 0)

    for height in itertools.count(2):

        new_ring = set()

        for bead in rings[height - 1]:

            label = (bead >> 1) + 1

            for next_bead in {bead - label, bead + label}:

                if not next_bead in visited:

                    if next_bead == n: return height

                    visited.add(next_bead)

                    new_ring.add(next_bead)

        rings.append(new_ring)

​

Below is a plot of the height function.

Minimal recitations

In this section, we study some properties of minimal recitations.

Minimal recitations ending in a white bead

The following property holds for any white bead $n$ ($3\nmid n$): there exists a minimal recitation to $n$ that ends in an up move. In other words:

The proof is by induction on the height of $n$. Assume $h\in \mathbb{N}$ given, and assume that for each white bead $n$ of height $<h$, property ($\text{11}$) holds.

Further assume (by contradiction) the existence of a white bead $n$ of height $h$ such that no minimal recitation to $n$ ends in up. Finally, consider a minimal recitation $\mathit{R}$ to $n$ (thus necessarily ending in a down move).

Being a white bead, $n$ is either of the form $3k+1$ or $3k+2$ for some $k\ge 0$.

Let’s first deal with the case where $n=3k+1$. Observe the following three commutative diagrams:

The ending of recitation $\mathit{R}$ must correspond to one of the above diagrams. There are three possibilities:

• Case 1: $\mathit{R}$ ends in $n=(n\mu \mu )D^2$. Since $12k+7$ is a white bead of height $h-2$, it must have a minimal recitation ending in up. Which produces a minimal recitation ending in $n=(n\mu \mu \lambda )D^{2}U$ – i.e., down–down–up.
• Case 2: $\mathit{R}$ ends in $n=(n\mu \nu )D^2$. Since $12k+8$ is a white bead of height $h-2$, it must have a minimal recitation ending in up. Which produces another minimal recitation ending in $n=(n\mu \nu \lambda )D^{2}U$ – i.e., down–down–up.
• Case 3: $\mathit{R}$ ends in $n=(n\nu )D$. Since $6k+4$ is a white bead of height $h-1,$ it must have a minimal recitation ending in up. Which produces another minimal recitation ending in $n=(n\nu \lambda )DU$ – i.e., down–up.

Each time there is a contradiction because a minimal recitation is produced, which is ending in an up move.

Next let’s deal with the case where $n=3k+2$. The corresponding commutative diagrams are as follows:

Again, we have a contradiction since in all cases we can construct a minimal recitation ending in an up move. This shows that property ($\text{11}$) holds for all white beads. $\text{<img draggable="false" role="img" class="emoji" alt="◻" src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

Minimal recitations ending in a black bead

An consequence of property ($\text{11}$) is that for any black bead $n>0,3\mid n$: there exists a minimal recitation to $n$ that ends in an up–down sequence. In other words:, for all $n\in \mathbb{N},n>0$:

The proof is similar as for the white beads, with the following two commutative diagrams.

Interlude: more names

Hey, Louie. The man is dry. Give him one on the house, okay?

Ridley Scott, Blade Runner (1982)

• Eager recitation: a recitation that only moves up.
• Seed: the seed of bead $n$ (denoted $\sigma (n)$) is the black bead from which $n$ can be reached via an eager recitation (only up moves).
• Lambex: the lambex of bead $n$ (denoted $\mathrm{\Lambda }(n)$) is the number of up moves required to reach $n$ from its seed $\sigma (n)$. In other words: $n=\sigma (n)U^{\mathrm{\Lambda }(n)}$ or equivalently $\sigma (n)=n{\lambda }^{\mathrm{\Lambda }(n)}.$
• Up-chains: we call up-chain starting at bead $n$ (denoted $\uparrow (n)$) the set of beads reachable by an eager recitation (only up moves) from bead $n$:
  $$\begin{array}{}\text{(13)}& & \uparrow (n)\stackrel{\text{def}}{=}\{n{U}^i\mid i\in \mathbb{N}\}\end{array}$$
  Note that:
  $$\begin{array}{}\text{(14)}& \mathbb{N}=\underset{n\in \mathbb{N}}{⨄}\uparrow (3n)\end{array}$$
• Down-chains: we call down-chain starting at bead $n$ (denoted $\downarrow (n)$) the set of beads reachable by downwards recitation (only down moves) from bead $n$:
  $$\begin{array}{}\text{(15)}& & \downarrow (n)\stackrel{\text{def}}{=}\{n{D}^i\mid i\in \mathbb{N}\}\end{array}$$
  Note that every down-chain is finite and ends in $0$.
• Jane’s reluctant recitation: Jane starts the reluctant recitation at bead $0$ and always moves down rather than up, unless moving down would lead to a bead that Jane has already visited, in which case Jane reluctantly moves up. See figure 9 for an illustration.
• Rho: $\rho (i)$ is the $i$^th bead in Jane’s reluctant recitation. For instance, $\rho (0)=0$, $\rho (5)=3$, $\rho (13)=12$. See figure 10 for an illustration.
  By construction, $\rho$ is an injective function. And $\rho (i)$ is actually well defined for all $i\ge 0$, as we will see later.

The structure of Jane’s rosary

The partitioning of Jane’s rosary in up-chains produces an interesting one-to-one mapping $\gamma$ between $\mathbb{N}$ and $\mathbb{N}\times \mathbb{N}$:

$$\gamma (n)\stackrel{def}{=}(\frac{\sigma (n)}{3},\mathrm{\Lambda }(n))$$

This is illustrated by Figure 6.

With this mapping, the beads’ heights have a clean representation:

Theorem 1: minimal recitations ending in a black bead

Theorem 1 further studies the properties of minimal recitations ending in a black bead. Let $3n>0$ be a black bead.

The following properties hold:

In particular, this shows that which of $\mu (3n)$ or $\nu (3n)$ belongs to a minimal recitation to $3n$ is determined by which has the larger lambex (and the smaller seed).

This is illustrated in figure 7: the solid arrows point to predecessors with lower lambex, the dashed arrows point to predecessors with larger lambex.

Theorem 1 guarantees the correctness of the following improved algorithm for computing $h(n)$ with complexity $\log (n)$ in time and contant complexity in space:

def height(n: int) -> int:
    if n < 0: raise 'param must be nonnegative'
    h = 0
    while True:
        if n == 0: return h
        h += 1
        match n%3:
            case 0:
                h += 1
                n=(4*n+2)//3
                while True:
                    h += 1
                    match n%3:
                        case 0:
                            n = (2*n)//3
                            break
                        case 1:
                            n = (2*n)//3
                        case 2:
                            n = (2*n)//3 + 1
                            break
            case _:
                n = (2*n)//3

def height(n: int) -> int:

    if n < 0: raise 'param must be nonnegative'

    h = 0

    while True:

        if n == 0: return h

        h += 1

        match n%3:

            case 0:

                h += 1

                n=(4*n+2)//3

                while True:

                    h += 1

                    match n%3:

                        case 0:

                            n = (2*n)//3

                            break

                        case 1:

                            n = (2*n)//3

                        case 2:

                            n = (2*n)//3 + 1

                            break

            case _:

                n = (2*n)//3

($\text{16}$), ($\text{17}$) and ($\text{18}$) are easy.

The remainder of the proof is by induction on the height of $3n$.

We can easily check that ($\text{19}$), ($\text{20}$), ($\text{21}$) and ($\text{22}$), are true for all $n$ such that $h(3n)\le 5$.

Now assume $h>0$ given, such that ($\text{19}$), ($\text{20}$), ($\text{21}$) and ($\text{22}$), are true for for all $n$ such that $h(3n)<h$. Further consider a black bead $3n$ of height $h$.

The following diagram (where $s$ is the successor function: $s(k)=k+1$) is well defined and commutes:

Observe that $c_1=D(a_1)$, $d_1=D(b_1)$, $b_1=s(a_1)$, $d_1=s(c_1)$. Also, depending on $nmod3$, the possibilities for $a_1$, $b_1$, $c_1$, $d_1$ are: $$\begin{array}{ccccc}nmod3& a_{1}mod3& b_{1}mod3& c_{1}mod3& d_{1}mod3\\ 0& \text{●}0& \text{○}1& \text{○}2& \text{●}0\\ 1& \text{○}1& \text{○}2& \text{○}1& \text{○}2\\ 2& \text{○}2& \text{●}0& \text{●}0& \text{○}1\end{array}$$

So depending on $nmod3$, the « $\lambda$-step » either creates two black beads ($b_1$ and $c_1$ or $a_1$ and $d_1$), or it creates no black beads at all. When no black beads are created, the « $\lambda$ steps » can be applied again. Let’s see how it goes.

Assuming four white beads $a_i$, $b_i$, $c_i$, $d_i$ where $c_i=D(a_i)$, $d_i=D(b_i)$, $b_i=s(a_i)$ and $d_i=s(c_i)$, the only possible configuration is described by the following two diagrams:

Where $c_{i+1}=D(a_{i+1})$, $d_{i+1}=D(b_{i+1})$, $b_{i+1}=s(a_{i+1})$, $d_{i+1}=s(c_{i+1})$, and depending on $kmod3$, the possibilities for $a_{i+1}$, $b_{i+1}$, $c_{i+1}$, $d_{i+1}$ are: $$\begin{array}{ccccc}kmod3& a_{i+1}mod3& b_{i+1}mod3& c_{i+1}mod3& d_{1}i+1mod3\\ 0& \text{○}2& \text{●}0& \text{●}0& \text{○}1\\ 1& \text{●}0& \text{○}1& \text{○}2& \text{●}0\\ 2& \text{○}1& \text{○}2& \text{○}1& \text{○}2\end{array}$$

This shows that the « $\lambda$-step » can be repeatedly applied $i>0$ times until two black beads are created, either $b_i$ and $c_i$ or $a_i$ and $d_i$. Note that the « $\lambda$-steps » cannot be indefinitely applied, since this would result in an infinitely descending sequence $(c_i)$.

On the one hand, if $b_i$ and $c_i$ are the black beads, the configuration is summarized by the following commutative diagram:

and the following deductions can be made:

• $\mathrm{\Lambda }(\mu (3n))>\mathrm{\Lambda }(\nu (3n))$,
• $a_i$ belongs to a minimal recitation to $3n$. If it did not, $b_i$ would belong to a minimal recitation to $3n$, we would have $h(b_i)=h(3n)-i-1<h$, and by induction hypothesis ($\text{19}$) we could write the following contradiction:
  $$h(a_i)+i+1>h(3n)=h(b_i)+i+1\ge h(a_i)+i+1,$$
• there is a minimal recitation to $3n$ ending in $a_i{U}^{i}D$,
• there is a minimal recitation to $3n$ ending in $\sigma (\mu (3n))U^{\mathrm{\Lambda }(\mu (3n))}D$,
• $h(3n-1)\le h(a_i)+1+i=h(3n)$,
• $h(c_i)\le h(a_i)+1<h(3n)=h$, and by induction hypothesis ($\text{20}$) we can write: $h(3n+1)\le h(d_i)+i\le h(c_i)+i\le (h(a_i)+1)+i=h(3n)$.

On the other hand, if $a_i$ and $d_i$ are the black beads, the configuration is summarized by the following commutative diagram:

and similarly, the following deductions can be made:

• $\mathrm{\Lambda }(\nu (3n))>\mathrm{\Lambda }(\mu (3n))$,
• $b_i$ belongs to a minimal recitation to $3n$,
• there is a minimal recitation to $3n$ ending in $\sigma (\nu (3n))U^{\mathrm{\Lambda }(\nu (3n))}D$,
• $h(3n-1)\le h(3n)$,
• $h(3n+1)\le h(3n)$.

Overall, properties ($\text{19}$), ($\text{20}$), ($\text{21}$) and ($\text{22}$) hold for all $n$ such that $h(3n)=h.\text{<img draggable="false" role="img" class="emoji" alt="◻" src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

Jane’s reluctant recitation

The reluctant recitation was suggested by Neal Gersh Tolunsky. The recitation starts at bead $0$ and Jane tells the beads, always preferring to move down rather than up, unless moving down would lead to a bead that Jane has already visited, in which case Jane reluctantly moves up.

The following figure illustrate the moves of the reluctant recitation.

The following algorithm computes $\rho (i)$:

def rho(i: int) -> int:
    if i < 0: raise Exception("argument must be nonnegative")
    if i == 0: return 0
    visited = {0: 0}
    bead = 1
    for age in range(1, i):
        visited[bead] = age
        label = 1 + bead//2
        if not bead - label in visited:
            bead -= label  # moving down
        else:
            bead += label  # moving up
    return bead

def rho(i: int) -> int:

    if i < 0: raise Exception("argument must be nonnegative")

    if i == 0: return 0

    visited = {0: 0}

    bead = 1

    for age in range(1, i):

        visited[bead] = age

        label = 1 + bead//2

        if not bead - label in visited:

            bead -= label  # moving down

        else:

            bead += label  # moving up

    return bead

Theorem 2: Jane’s reluctant recitation never halts

While performing the reluctant recitation, Jane moving on to bead $n$ never causes a gap to appear in the rosary’s up-chains – i.e., a gap in the sequence $\sigma (n),\sigma (n)U,\cdots ,\sigma (n)U^{\mathrm{\Lambda }(n)}=n$.

This ensures that the reluctant-recitation never halts.

The proof is by contradiction and by induction on the index $i$ or the first move that would create a gap.

Looking at Figure 10, we see that moves up to the $20$^th do not create a gap.

Now assume (by contradiction) the existence of $i\ge 0$ such that none of Jane’s reluctant moves prior to $i$ has created a gap but Jane’s $i$^th move creates a gap by reaching bead $n=\rho (i).$

Since an up move cannot create a gap in an up-chain, it holds that $n=\rho (i-1)D$.

Since a gap is created, $\rho (i)$ must be a white bead (non divisible by $3$) and there must be a gap $g$ just « to the left » of $n$ in the up-chain, at the moment $n$ is reached:

$$g=\lambda (n).$$

We must consider two cases: $n=3k+1$ and $n=3k+2$.

Gap « to the left » of $3k+1$

Consider the case $\rho (i)=3k+1$.

If $\rho (i-1)=\rho (i)\nu$, then one of the two following commutative diagrams holds, where ${◯✓}_a$ indicates $\rho (i-a)$:

The left hand side diagram brings a contradiction, since from ${◯✓}_2$ Jane should have moved down to $g=◯$, rather than up to ${◯✓}_1$.

The right hand side diagram also brings a contradiction: since ${◯✓}_1$ has not created a gap (induction hypothesis), $4k+2$ must have been visited at some earlier step ${◯✓}_j$, and from ${◯✓}_j$ Jane should have moved down to $◯$.

Consequently $\rho (i-1)=\rho (i)\nu =6k+3$ is a black bead, and we must consider two subcases: $\rho (i-2)=\rho (i-1)\mu$ and $\rho (i-2)=\rho (i-1)nu$

Subcase: $\rho (i-2)=\rho (i-1)\mu$

If $\rho (i-2)=\rho (i-1)\mu$, then one of the two following commutative diagrams holds:

On the left hand side diagram, since after ${◯✓}_3$ Jane chose to move up to ${◯✓}_2$, $4k+2$ must have been visited at some earlier step ${◯✓}_j$. But there is a contradiction since from ${◯✓}_j$ Jane should have moved down to $g=◯$.

On the right hand side diagram, since ${◯✓}_2$ has not created a gap (induction hypothesis), $8k+5$ must have been visited at some earlier step ${◯✓}_j$. After ${◯✓}_j$ Jane must have moved down to ${◯✓}_{j-1}$ and from ${◯✓}_{j-1}$ she should have moved down to $◯$, again a contradiction.

Subcase: $\rho (i-2)=\rho (i-1)\nu$

If $\rho (n-2)=\rho (n-1)\nu$, then one of the two following commutative diagrams holds:

On the left hand side diagram, since after ${◯✓}_3$ Jane chose to move up to ${◯✓}_2$, $4k+2$ must have been visited at some earlier step ${◯✓}_j$. But there is a contradiction since from ${◯✓}_j$ Jane should have moved down to $g=◯$.

On the right hand side diagram, since ${◯✓}_2$ has not created a gap (induction hypothesis), $8k+5$ must have been visited at some earlier step ${◯✓}_j$. After ${◯✓}_j$ Jane must have moved down to ${◯✓}_{j-1}$ and from ${◯✓}_{j-1}$ she should have moved down to $◯$, again a contradiction.

At this point, we conclude that it is not possible that $\rho (n)=3k+1$.

Gap « to the left » of $3k+2$

Consider now the case $\rho (i)=3k+1$.

The same reasoning as previously brings contradictions.

If $\rho (i-1)=\rho (i)\mu$, the commutative diagrams to consider are:

If $\rho (i-1)=\rho (i)\nu$ and $\rho (i-2)=\rho (n-1)\mu$, the commutative diagrams to consider are:

If $\rho (i-1)=\rho (i)\nu$ and $\rho (i-2)=\rho (i-1)\nu$, the commutative diagrams to consider are: