# Three Cousins of Recamán's Sequence

Max Alekseyev, Joseph Samuel Myers, Richard Schroeppel, Scott R Shannon, Neil James Alexander Sloane, Paul Zimmermann

► To cite this version:

Max Alekseyev, Joseph Samuel Myers, Richard Schroeppel, Scott R Shannon, Neil James Alexander Sloane, et al.. Three Cousins of Recamán's Sequence. The Fibonacci Quarterly, 2022, 60 (3), pp.201-219. 10.48550/arXiv.2004.14000. hal-02951011v2

HAL Id: hal-02951011

https://inria.hal.science/hal-02951011v2

Submitted on 2 Jun 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
THREE COUSINS OF RECAMÁN'S SEQUENCE

MAX A. ALEKSEYEV, JOSEPH SAMUEL MYERS, RICHARD SCHROEPPEL, S. R. SHANNON, N. J. A. SLOANE, AND PAUL ZIMMERMANN

ABSTRACT. Although $10^{230}$ terms of Recamán's sequence have been computed, it remains a mystery. Here three distant cousins of that sequence are described, one of which is also mysterious. (i) $\{A(n), n \ge 3\}$ is defined as follows. Start with $n$, and add $n+1, n+2, n+3, \dots$, stopping after adding $n+k$ if the sum $n+(n+1)+\dots+(n+k)$ is divisible by $n+k+1$. Then $A(n)=k$. We determine $A(n)$ and show that $A(n) \le n^2 - 2n - 1$. (ii) $\{B(n), n \ge 1\}$ is a multiplicative analog of $\{A(n)\}$. Start with $n$, and successively multiply by $n+1, n+2, \dots$, stopping after multiplying by $n+k$ if the product $n(n+1)\cdots(n+k)$ is divisible by $n+k+1$. Then $B(n)=k$. We conjecture that $\log^2 B(n) = (\frac{1}{2} + o(1)) \log n \log \log n$. (iii) The third sequence, $\{C(n), n \ge 1\}$, is the most interesting, because the most mysterious. Concatenate the decimal digits of $n, n+1, n+2, \dots$ until the concatenation $n \| n+1 \| \dots \| n+k \|$ is divisible by $n+k+1$. Then $C(n)=k$. If no such $k$ exists we set $C(n) = -1$. We have found $k$ for all $n \le 1000$ except for two cases. Some of the numbers involved are quite large. For example, $C(92) = 218128159460$, and the concatenation $92\|93\|\dots\|(92+C(92))$ is a number with about $2 \cdot 10^{12}$ digits. We have only a probabilistic argument that such a $k$ exists for all $n$.

# 1. INTRODUCTION

Recamán's sequence $\{R(n), n \ge 0\}$ is defined by $R(0) = 0$ and, for $n \ge 1$, $R(n) = R(n-1) - n$ if that number is positive and not already in the sequence, and otherwise $R(n) = R(n-1) + n$ (in the latter case repeated terms are permitted). Terms $R(0)$ through $R(11)$ are 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22. The sequence was contributed by Bernardo Recamán Santos in 1991 to what is now the *On-line Encyclopedia of Integer Sequences* (or OEIS) [10]. The most basic question about this sequence is still unanswered: does every nonnegative integer appear? The fifth author (NJAS) and several Bell Labs colleagues developed a method for speeding up the computation of the sequence, and in 2001 Allan Wilks used it to compute the first $10^{15}$ terms. At that point every number below 852655 had appeared, but 852655 = $5 \cdot 31 \cdot 5501$ itself was missing. Benjamin Chaffin has continued this work, and in 2018 reached $10^{230}$ terms [2]. However, 852655 is still missing.

Thirty years ago it seemed like a very plausible conjecture that every number would eventually appear in Recamán's sequence. Today, it is not so clear. For much more about this sequence, see entry A005132¹ in [10].

A somewhat similar situation arose in connection with the third of our new sequences, $\{C(n)\}$, discussed in Sect. 4. We have no proof that the search for $C(n)$ will always terminate, and after reaching $10^{11}$ in our search for $C(44)$, we were beginning to have doubts. However, after considerably more computation using a different algorithm (described in §4.1-§4.3) we were able to show that $C(44) = 2783191412912$. Similar results for other hard-to-find values of $C(n)$ have convinced us that the search for $C(n)$ should always terminate.

In Recamán's sequence we start by trying to subtract $n$ from the previous term. In the three sequences discussed here, to compute $A(n)$, $B(n)$, or $C(n)$ we define an intermediate sequence which starts with $n$ and is extended by either *adding* ($A(n)$, Section 2), *multiplying*

<footnote n="1">¹Six-digit numbers prefixed by A refer to entries in [10].</footnote>
by $(B(n)$, Section 3), or concatenating $(C(n)$, Section 4) $n + i$ to the $i$th term to get the next term.

*Notation.* A centered dot $(\cdot)$ indicates multiplication. In Section 2, $T_n$ denotes the triangular number $n(n+1)/2$; in Sections 3 and 4 a vertical bar ($|$) means “divides” and $\nu_p(n)$ denotes the exponent of the highest power of $p$ that divides $n$ (the *p-adic valuation* of $n$); and in Section 4, $\parallel$ denotes concatenation of the decimal (or more generally, base $b$) representations of numbers. Also in Section 4 we distinguish between the *number* $\alpha \bmod \gamma$ and the *congruence* $\alpha \equiv \beta \pmod \gamma$.

## 2. THE ADDITIVE VERSION, {$A(n)$}.

To find $A(n)$, $n \ge 3$, we define an intermediate sequence {$a_n(i), i \ge 0$} by starting with $a_n(0) = n$, and, for $i \ge 1$, letting $a_n(i) = a_n(i-1) + n + i$. We stop when we reach a term $a_n(k)$ which is divisible by $d = n + k + 1$, and set $A(n) = k$. In other words, if the number $d$ that we are about to add to $a_n(k)$ actually divides $a_n(k)$, then instead of adding it we stop.

An equivalent definition is that $A(n)$ is the smallest positive integer $k = k(n)$ such that $d(n) = n + k + 1$ divides

$$a_n(k) = (k+1)n + \frac{k(k+1)}{2}. \qquad (2.1)$$

If $n = 3$, for example, the sequence {$a_3(i)$} is $a_3(0) = 3$, $a_3(1) = 7$, $a_3(2) = 12$, and we stop with $k = 2 = A(3)$ since 12 is divisible by $d = 3 + 2 + 1 = 6$. For $n = 4$ the sequence {$a_4(i)$} is 4, 9, 15, 22, 30, 39, 49, 60, where we stop with $k = 7 = A(4)$ since $a_4(7) = 60$ is divisible by $d = 4 + 7 + 1 = 12$.

Table 1 gives the values of $A(n) = k(n)$, $d(n) = n+k(n)+1$, $p(n) = a_n(k)$, and $q_n = p(n)/d(n)$ for $n = 3, 4, \dots, 17$. The last column gives the values of a parameter $m$ that will arise when we relate this problem to triples of triangular numbers $T_j$. We start the table at $n = 3$, because although we can certainly define the sequence {$a_2(i)$}, it turns out that $a_2(i) = T_{i+2} - 1$, and it is easy to show that $T_{i+2} - 1$ is never divisible by $i + 3$. So $A(2)$ does not exist.

On the other hand, $A(n)$ exists for all $n \ge 3$. The record high values of $A(n)$ in the table at $n = 3, 4, 5, 8, 17$ suggest that $(n-1)^2 - 2$ is an upper bound. If we take $k = (n-1)^2 - 2$ for $n \ge 3$ we find from (2.1) that $a_n(k) = (n+1)n(n-1)(n-2)/2$, which is indeed divisible by $n + k + 1 = n(n-1)$, and so $A(n) \le (n-1)^2 - 2$.

The sequences {$A(n)$}, {$d(n)$}, and {$p(n)$} have now been added to [10]: {$A(n)$} is A332542. However, to our surprise, the {$q_n$} sequence appeared to match an existing sequence, although with a shift in subscripts. For $n \ge 2$, let $\Xi(n)$ denote the smallest $k > 0$ such that

$$T_n + T_k = T_m \qquad (2.2)$$

for some integer $m$. The initial values are $\Xi(2) = 2$, $\Xi(3) = 5$, $\Xi(4) = 9, \dots$ (A082183) and apparently agree with $q_{n+1}$. We will show in Theorem 2.4 that this is true.

The representation of numbers as sums or differences of triangular numbers is a classical subject, going back to Fermat and Gauss, and has been studied in many recent papers [1, 5, 7, 9, 12, 13, 14, 15]. However, we were unable to find Theorems 2.3 and 2.4 in the literature.

Following [7] we define a *triangular triple* to be an ordered triple of nonnegative integers $[n, k, m]$ satisfying (2.2). We say that a triple is *trivial* if any of $n, k, m$ are zero.

It is easy to see that $\Xi(n)$ exists, since it is straightforward to check that $[n, T_n - 1, T_n]$ is a triangular triple for $n \ge 1$. So $\Xi(n) \le T_n - 1$.

We will say exactly what all the triangular triples $[n, k, m]$ are for a given $n \ge 1$ (this is a consequence of Theorem 2.1), and then use this to determine $\Xi(n)$ (Theorem 2.3).
THREE COUSINS OF RECAMÁN'S SEQUENCE

<table><caption>TABLE 1</caption><thead><tr><th>n</th><th>A(n) = k(n)</th><th>d(n)</th><th>p(n) = a<sub>n</sub>(k)</th><th>q<sub>n</sub> = p(n)/d(n)</th><th>m</th></tr></thead><tbody><tr><td>3</td><td>2</td><td>6</td><td>12</td><td>2</td><td>3</td></tr><tr><td>4</td><td>7</td><td>12</td><td>60</td><td>5</td><td>6</td></tr><tr><td>5</td><td>14</td><td>20</td><td>180</td><td>9</td><td>10</td></tr><tr><td>6</td><td>3</td><td>10</td><td>30</td><td>3</td><td>6</td></tr><tr><td>7</td><td>6</td><td>14</td><td>70</td><td>5</td><td>8</td></tr><tr><td>8</td><td>47</td><td>56</td><td>1512</td><td>27</td><td>28</td></tr><tr><td>9</td><td>14</td><td>24</td><td>240</td><td>10</td><td>13</td></tr><tr><td>10</td><td>4</td><td>15</td><td>60</td><td>4</td><td>10</td></tr><tr><td>11</td><td>10</td><td>22</td><td>176</td><td>8</td><td>13</td></tr><tr><td>12</td><td>20</td><td>33</td><td>462</td><td>14</td><td>18</td></tr><tr><td>13</td><td>25</td><td>39</td><td>663</td><td>17</td><td>21</td></tr><tr><td>14</td><td>11</td><td>26</td><td>234</td><td>9</td><td>16</td></tr><tr><td>15</td><td>5</td><td>21</td><td>105</td><td>5</td><td>15</td></tr><tr><td>16</td><td>31</td><td>48</td><td>1008</td><td>21</td><td>26</td></tr><tr><td>17</td><td>254</td><td>272</td><td>36720</td><td>135</td><td>136</td></tr></tbody></table>

The next theorem is essentially due to Nyblom [9]. We give a proof since we will use the argument in the proof of Theorem 2.3.

**Theorem 2.1.** For a given integer $S \ge 1$, all pairs of nonnegative integers $m, k$ such that

$$S = T_m - T_k \qquad (2.3)$$

are obtained in a unique way by factorizing $2S$ as a product $d \cdot e$ where $d$ is odd and $e$ is even, and taking

$$k = \frac{\max(d, e) - \min(d, e) - 1}{2}, \qquad (2.4)$$

$$m = \frac{\max(d, e) + \min(d, e) - 1}{2}. \qquad (2.5)$$

*Proof.* From (2.3) we have

$$2S = m(m+1) - k(k+1) = (m-k)(m+k+1).$$

Since their sum is odd, $m-k$ and $m+k+1$ are of opposite parity, and also $m-k < m+k+1$. Let $d$ be whichever of $m-k$ and $m+k+1$ is odd, and let $e$ be the other. Then $m-k = \min(d, e)$, $m+k+1 = \max(d, e)$, and solving for $k$ and $m$ we get (2.4), (2.5). The uniqueness follows since conversely $k$ and $m$ determine $d$ and $e$. $\square$

In particular, as Nyblom [9] shows, the number of pairs $(m, k)$ such that (2.3) holds is equal to the number of odd divisors of $2S$.

We now take $S = T_n$. Theorem 2.1 gives all triangular triples $[n, k, m]$ containing $n$. There are always two obvious factorizations, $2T_n = 1 \cdot n(n+1)$ with $d = 1$ and $e = n(n+1)$, and $2T_n = n \cdot (n+1)$, with $\{d, e\} = \{n, n+1\}$. The first case leads to the triple $[n, T_n-1, T_n]$ already mentioned, and the second leads to the trivial solution $[n, 0, n]$. It follows that the number of nontrivial triangular triples for a given $n$ (see A309507) is equal to the number of odd divisors $d > 1$ of $2T_n$.
This result is reminiscent of the fact that the number of primitive Pythagorean triples with an even leg $2uv$ is equal to the number of odd divisors of $2uv$ (cf. [13], A024361). The nontrivial triangular triples $[n, k, m]$ sorted into lexicographic order are given by

$$[n, A333530(n), A333531(n)],$$

or by $[n, A198455(n), A198456(n)]$ if we impose the restriction that $k \ge n$. (Lee and Zafrulah [7] also give some tables of triangular triples.) The numbers $n$ such that there is a triple $[n, n, m]$ are listed in A053141.

The following property and its elegant proof are due to Bradley Klee (personal communication).

**Theorem 2.2.** If $[n, k, m]$ is a triangular triple, then

$$n + k \ge m. \qquad (2.6)$$

Equality holds if and only if $n = 0$ or $k = 0$.

*Proof.* If we set $x = 2n + 1$, $y = 2k + 1$, $z = 2m + 1$ then (2.2) becomes

$$x^2 + y^2 = z^2 + 1.$$

Certainly $[x, y, z]$ is not (quite) a Pythagorean triple, but this equation does suggest using the triangle inequality, which yields

$$x + y \ge \sqrt{z^2 + 1} > z,$$

and so

$$n + k > m - \frac{1}{2},$$

and (2.6) follows since all the quantities are integers. If equality holds in (2.6) then $n^2+k^2 = m^2$ (from (2.2)) and so $kn = 0$. □

We can now apply Theorem 2.1 to determine $\Xi(n)$.

**Theorem 2.3.** For $n \ge 2$, $\Xi(n)$ is obtained by choosing that odd divisor $d$ of $n(n + 1)$ which is different from $n$ and $n + 1$, and minimizes

$$\left| d - \frac{n(n+1)}{d} \right|. \qquad (2.7)$$

Then $\Xi(n)$ is the value of $k$ given by (2.4) with this value of $d$ and $e = n(n + 1)/d$.

*Proof.* From (2.4) we see that the minimal $k$ is obtained by choosing $d$ and $e$ so as to minimize $\max(d, e) - \min(d, e)$. But $d$ and $e$ are constrained by $d \cdot e = n(n + 1)$. So we must minimize (2.7). Since we require $k > 0$, we must avoid $d = n$ and $d = n + 1$. □

*Remark.* In a few cases there is no need to do any minimization. For if $n$ is a Mersenne prime, or if $n + 1$ is a Fermat prime, then the only odd divisor of $n(n + 1)$ apart from $n$ or $n + 1$ is $d = 1$, and we get $\Xi(n) = T_n - 1$.

We now return to our study of $\{A(n)\}$, and explain the connection with triangular triples. The agreement of $q_n$ and $\Xi(n - 1)$ is no coincidence.

**Theorem 2.4.** For $n \ge 3$, $q_n = \Xi(n - 1)$.
*Proof.* Note that $R$ is a triangular number if and only if $8R+1$ is the square of an odd integer. Indeed, $8T_n + 1 = 4n^2 + 4n + 1 = (2n+1)^2$. The proof of the theorem is in two parts.

(i) Given $n \ge 3$, let $k$ denote the smallest nonnegative integer such that $d = n + k + 1$ divides

$$p = (k+1)n + \frac{k(k+1)}{2}.$$

Then

$$q = \frac{(k+1)n + \frac{k(k+1)}{2}}{n+k+1} \qquad (2.8)$$

is such that $R = T_{n-1} + T_q$ is a triangular number. Indeed, $8R+1 = (\alpha/d)^2$, where

$$\alpha = 2n^2 + 2kn + k^2 + n + 2k + 1 = (2n + 2k + 1)d - 2p,$$

which is certainly divisible by $d$. (These calculations were performed in Maple, but they can easily be verified by hand.) This proves that $\Xi(n-1) \le q_n$.

(ii) Conversely, suppose $n \ge 3$ and $q = \Xi(n-1)$ is such that

$$T_{n-1} + T_q = T_m \qquad (2.9)$$

for some integer $m$. For given values of $n$ and $q$, (2.8) is a quadratic equation for $k$, and the unique solution with $k \ge 0$ is

$$k = -n + q - \frac{1}{2} + \frac{1}{2}\sqrt{4n^2 + 4q^2 - 4n + 4q + 1}.$$

Using (2.9) we can rewrite this as

$$k = q + m - n,$$

from which we get

$$p = (k+1)n + \frac{k(k+1)}{2} = \frac{(q+m+n)(q+m-n+1)}{2} = q(n+k+1).$$

This proves that $q_n \le \Xi(n-1)$. $\square$

In row $n$ of Table 1, $A(n)$ corresponds to the triangular triple $[n-1, q_n, m]$, where $m$ is given in the final column.

To summarize: initially we found $A(n)$ by seeing when a certain series of trial divisions finally succeeded. Our analysis shows that an explicit answer is given by first finding $q_n$ from Theorems 2.3 and 2.4, finding $m$ by solving the quadratic equation $T_{n-1} + T_{q_n} = T_m$, and then $A(n) = q_n + m - n$. For example, if $n=5$, we find that $q_5 = \Xi(4) = 9$, and $T_4 + T_9 = 10 + 45 = 55 = T_m$ tells us that $m=10$ and $A(5) = 9 + 10 - 5 = 14$.

### 3. THE MULTIPLICATIVE VERSION, {$B(n)$}.

For the multiplicative version we replace the addition of $n+i$ in the definition of $a_n(i)$ by multiplication, keeping the stopping rule. So we define $B(n)$ for $n \ge 1$ by introducing an intermediate sequence $\{b_n(i), i \ge 0\}$ which starts with $b_n(0) = n$, and, for $i \ge 1$, satisfies $b_n(i) = b_n(i-1) \cdot (n+i)$. We stop when we reach a term $b_n(k)$ which is divisible by $d = n+k+1$, and set $B(n) = k$. In other words, if the number $d$ that we are about to multiply $b_n(k)$ by actually divides $b_n(k)$, then instead of multiplying by it we stop.

An equivalent definition is that $B(n)$ is the smallest positive integer $k = k(n)$ such that $d(n) = n + k + 1$ divides

$$b_n(k) = \frac{(n+k)!}{(n-1)!} \qquad (3.1)$$
When $n = 1$, for example, the sequence $\{b_1(i)\}$ is 1, 2, 6, 24, 120, and we stop with $k = 4 = B(1)$ since 120 is divisible by $d = 1 + 4 + 1 = 6$. For $n = 4$, the sequence $\{b_4(i)\}$ is 4, 20, 120, 840, and we stop with $k = 3 = B(4)$ since 840 is divisible by $d = 4 + 3 + 1 = 8$.

Table 2 gives the values of $B(n) = k(n)$, $d(n) = n+k(n)+1$, $p(n) = b_n(k)$, and $q_n = p(n)/d(n)$ for $n = 1, 2, \dots, 12$.

<table><caption>TABLE 2</caption><thead><tr><th>n</th><th>B(n) = k(n)</th><th>d(n)</th><th>p(n) = b<sub>n</sub>(k)</th><th>q<sub>n</sub> = p(n)/d(n)</th></tr></thead><tbody><tr><td>1</td><td>4</td><td>6</td><td>120</td><td>20</td></tr><tr><td>2</td><td>3</td><td>6</td><td>120</td><td>20</td></tr><tr><td>3</td><td>2</td><td>6</td><td>60</td><td>10</td></tr><tr><td>4</td><td>3</td><td>8</td><td>840</td><td>105</td></tr><tr><td>5</td><td>4</td><td>10</td><td>15120</td><td>1512</td></tr><tr><td>6</td><td>5</td><td>12</td><td>332640</td><td>27720</td></tr><tr><td>7</td><td>4</td><td>12</td><td>55440</td><td>4620</td></tr><tr><td>8</td><td>3</td><td>12</td><td>7920</td><td>660</td></tr><tr><td>9</td><td>5</td><td>15</td><td>2162160</td><td>144144</td></tr><tr><td>10</td><td>4</td><td>15</td><td>240240</td><td>16016</td></tr><tr><td>11</td><td>6</td><td>18</td><td>98017920</td><td>5445440</td></tr><tr><td>12</td><td>5</td><td>18</td><td>8910720</td><td>495040</td></tr></tbody></table>

The sequences $\{B(n)\}$, $\{d(n)\}$, $\{p(n)\}$, $\{q_n\}$ have now been added to [10]: $\{B(n)\}$ is A332558. Just as in the additive version, there is a close match with an existing sequence in [10]. If we add 1 to the values of $k(n)$ we get 5, 4, 3, 4, 5, 6, ..., which appears to match the entry for A061836, although the definitions are different. The older sequence, which we will denote by $\{\beta(n)\}$, has a more natural definition: $\beta(n)$ for $n \ge 0$ is defined to be the smallest integer $\kappa > 0$ such that $n + \kappa$ divides $\kappa!$.

**Theorem 3.1.** For $n \ge 1$, $\beta(n) = B(n) + 1$.

*Proof.* By definition, $B(n)$ is the smallest $k > 0$ such that

$$n + k + 1 \mid n(n+1)(n+2)\cdots(n+k), \qquad (3.2)$$

whereas $\beta(n)$ is the smallest $\kappa > 0$ such that

$$n + \kappa \mid 1 \cdot 2 \cdot 3 \cdots \kappa,$$

or, replacing $\kappa$ by $k + 1$, the smallest $k$ such that

$$n + k + 1 \mid 1 \cdot 2 \cdot 3 \cdots (k + 1). \qquad (3.3)$$

The ratio of the right-hand sides of (3.2) and (3.3) equals $\binom{n+k}{k+1}$ which is an integer, so the right-hand side of (3.3) divides the right-hand side of (3.2). So the value of $k$ defined by (3.2) is less than or equal to the value defined by (3.3). To complete the proof, it is enough to show that if $n + k + 1$ divides $n(n+1)(n+2)\cdots(n+k)$ then it divides $(k+1)!$. But $n + k + 1$ also divides $(\sigma+n)(\sigma+n+1)(\sigma+n+2)\cdots(\sigma+n+k)$ for any $\sigma$ that is a multiple of $n+k+1$. Taking $\sigma = -(n+k+1)$, that expression becomes $(-1)^{k+1}(k+1)!$. $\square$

We do not know of any simple formula for $B(n)$ in terms of $n$. The following is a weak upper bound, which at least shows that $B(n)$ always exists.
**Theorem 3.2.** For $n \ge 3$, $B(n) \le n - 1$.

*Proof.* Substituting $k = n - 1$ in (3.1), we get $b_n(n - 1) = (2n - 1)!(n - 1)!$, which is divisible by $n + k + 1 = 2n$ for $n \ge 3$. □

**3.1. Asymptotic growth of $B(n)$**. We conjecture that as $n$ goes to infinity,

$$B(n) = \exp\left( (c + o(1)) (\log n)^{1/2} (\log \log n)^{1/2} \right), \quad (3.4)$$

with $c = 1/\sqrt{2} = 0.7071...$. In the rest of this section we sketch some arguments that support the conjecture.<fnref n="2" />

Since $B(n) = \beta(n) - 1$ from Theorem 3.1, we study the asymptotic growth of $\beta(n)$ instead. Let $\beta'(n)$ be the smallest integer $k \ge 1$ such that $n + k$ is $k$-smooth (i.e., it has only factors less than or equal to $k$). Since $k!$ is $k$-smooth, clearly $\beta'(n) \le \beta(n)$. The converse is not always true: $\beta(2) = 4$ but $\beta'(2) = 2$ since $2 + 2 = 2 \cdot 2 \cdot 10^8$, only 5.7% of the values of $n$ are such that $\beta'(n) < \beta(n)$, and for $10^9 \le n < 2 \cdot 10^9$ the proportion decreases to 4.2%. Our first unproved assumption is that $\beta(n)$ and $\beta'(n)$ have the same asymptotic behavior, so that it suffices to study the asymptotic behavior of $\beta'(n)$.

The number $\Psi(n, k)$ of $k$-smooth numbers $\le n$ is given by Dickman's $\rho$ function:

$$\frac{\Psi(n, k)}{n} \approx \rho(u),$$

where $u = \log n / \log k$ [3, 4]. As $u$ goes to infinity, we have [4, Eq. (1.6)]:

$$\rho(u) = u^{-u+o(u)}. \quad (3.5)$$

However, what we want is the local density $\Psi'(n, k)$ around $n$. This is studied in Kruppa's Ph. D. thesis [6, formula (5.6)], where it is shown that

$$\frac{\Psi'(n, k)}{n} \approx \rho(u) - \gamma \frac{\rho(u-1)}{\log n}, \quad (3.6)$$

$\gamma$ being the Euler-Mascheroni constant. In our case the local density is close to the global density. For example for $n = 10^{25} + 2554$ we have $\beta'(n) = 29972$, thus $u \approx 5.584$, which yields $\rho(u) \approx 6.7 \cdot 10^{-5}$, and $\gamma\rho(u-1)/\log n \approx 1.1 \cdot 10^{-5}$. Our second unproved assumption is that the local density is $\approx \rho(u)$ asymptotically. The expected distance between two $k$-smooth numbers around $n$ being $\approx 1/\rho(u)$, the expected distance between a random $n$ and the next $k$-smooth number is thus $\approx 1/(2\rho(u))$.

The above arguments, together with (3.5), combine to suggest that $B(n)$ is approximately equal to the solution $k$ of the equations

$$k \approx \frac{u^u}{2}, \quad u = \frac{\log n}{\log k}. \quad (3.7)$$

We have

$$\begin{align*} \log k &\approx u \log u \approx \frac{\log n}{\log k} (\log \log n - \log \log k), \\ (\log k)^2 &\approx \log n (\log \log n - \log \log k), \\ 2 \log \log k &\approx \log \log n, \end{align*}$$

<footnote n="2">²A proof of Equation (3.4) might be possible using the techniques of [8].</footnote>
and so

$$ (\log k)^2 \approx \frac{1}{2} \log n \log \log n, $$

which gives (3.4).

<figure><img src="image_2.png" /><figcaption>FIGURE 1. The first 1000 terms of $B(n)$ and (the curved line) $\overline{B(n)}$.</figcaption></figure>

Let

$$ \overline{B(n)} := \exp\left(\frac{1}{\sqrt{2}} (\log n)^{1/2} (\log \log n)^{1/2}\right) \qquad (3.8) $$

denote the main term on the right-hand side of (3.4). $\overline{B(n)}$ is a reasonably good fit to $B(n)$, even for small $n$. The graph in Fig. 1 shows the first 1000 terms of $B(n)$ and (the curved line) $\overline{B(n)}$. We find that $\overline{B(n)}$ is still a reasonably good fit to $B(n)$, even out to $n = 10^{30}$. Furthermore, it appears that $\lim_{n \to \infty} \overline{B(n)}$ is also given by the right-hand side of (3.4). It would be nice to know more about the asymptotic behavior of $B(n)$.

4. THE CONCATENATION VERSION, {$C(n)$}.

For the third version we replace addition and multiplication by concatenation, but again keep the same stopping rule. We define $C(n)$ for $n \ge 1$ by introducing an intermediate sequence $\{c_n(i), i \ge 0\}$ which starts with $c_n(0) = n$, and, for $i \ge 1$, satisfies $c_n(i) = c_n(i-1)\|(n+i)$, where $r \| s$ denotes the number whose decimal expansion is the concatenation of the decimal expansions of $r$ and $s$. We stop if and when we reach a term $c_n(k)$ which is divisible by $d = n+k+1$, and set $C(n) = k$. In other words, if the number $d$ that we are about to concatenate to $c_n(k)$ actually divides $c_n(k)$, then instead of concatenating $d$ we stop. In contrast to the first two versions, here we do not have a proof that such a $k$ always exists. It is theoretically possible that the sequence $c_n(i)$ never stops, in which case we define $C(n)$ to be $-1$.

When $n = 1$, for example, the sequence $\{c_1(i)\}$ is $c_1(0) = 1$, $c_1(1) = 1 \| 2 = 12$, and we stop with $k = 1 = C(1)$ since 12 is divisible by $d = 1+1+1 = 3$. Note that we cannot have $C(n) = 0$ since it would imply that $n+1$ divides $n$.

For $n = 7$, the sequence $\{c_7(i)\}$ is

7, 78, 789, 78910, 7891011, ..., 7891011121314151617181920,
THREE COUSINS OF RECAMÁN'S SEQUENCE

<table><caption>TABLE 3</caption><thead><tr><th>n</th><th>C(n)</th><th>n</th><th>C(n)</th><th>n</th><th>C(n)</th><th>n</th><th>C(n)</th></tr></thead><tbody><tr><td>1</td><td>1</td><td>26</td><td>33172</td><td>51</td><td>2249</td><td>76</td><td>320</td></tr><tr><td>2</td><td>80</td><td>27</td><td>9</td><td>52</td><td>21326</td><td>77</td><td>59</td></tr><tr><td>3</td><td>1885</td><td>28</td><td>14</td><td>53</td><td>53</td><td>78</td><td>248</td></tr><tr><td>4</td><td>6838</td><td>29</td><td>317</td><td>54</td><td>98</td><td>79</td><td>31511</td></tr><tr><td>5</td><td>1</td><td>30</td><td>708</td><td>55</td><td>43</td><td>80</td><td>20</td></tr><tr><td>6</td><td>44</td><td>31</td><td>1501</td><td>56</td><td>20</td><td>81</td><td>5</td></tr><tr><td>7</td><td>13</td><td>32</td><td>214</td><td>57</td><td>71</td><td>82</td><td>220</td></tr><tr><td>8</td><td>2</td><td>33</td><td>37</td><td>58</td><td>218</td><td>83</td><td>49</td></tr><tr><td>9</td><td>1311</td><td>34</td><td>34</td><td>59</td><td>91</td><td>84</td><td>12</td></tr><tr><td>10</td><td>18</td><td>35</td><td>67</td><td>60</td><td>1282</td><td>85</td><td>25</td></tr><tr><td>11</td><td>197</td><td>36</td><td>270</td><td>61</td><td>277</td><td>86</td><td>22</td></tr><tr><td>12</td><td>20</td><td>37</td><td>19</td><td>62</td><td>56</td><td>87</td><td>105</td></tr><tr><td>13</td><td>53</td><td>38</td><td>20188</td><td>63</td><td>47</td><td>88</td><td>34</td></tr><tr><td>14</td><td>134</td><td>39</td><td>78277</td><td>64</td><td>106</td><td>89</td><td>4151</td></tr><tr><td>15</td><td>993</td><td>40</td><td>10738</td><td>65</td><td>1</td><td>90</td><td>1648</td></tr><tr><td>16</td><td>44</td><td>41</td><td>287</td><td>66</td><td>890</td><td>91</td><td>2221</td></tr><tr><td>17</td><td>175</td><td>42</td><td>2390</td><td>67</td><td>75</td><td>92</td><td>218128159460</td></tr><tr><td>18</td><td>124518</td><td>43</td><td>695</td><td>68</td><td>280</td><td>93</td><td>13</td></tr><tr><td>19</td><td>263</td><td>44</td><td>2783191412912</td><td>69</td><td>19619</td><td>94</td><td>376</td></tr><tr><td>20</td><td>26</td><td>45</td><td>3</td><td>70</td><td>148</td><td>95</td><td>23965</td></tr><tr><td>21</td><td>107</td><td>46</td><td>700</td><td>71</td><td>15077</td><td>96</td><td>234</td></tr><tr><td>22</td><td>10</td><td>47</td><td>8303</td><td>72</td><td>64</td><td>97</td><td>321</td></tr><tr><td>23</td><td>5</td><td>48</td><td>350</td><td>73</td><td>313</td><td>98</td><td>259110640</td></tr><tr><td>24</td><td>62</td><td>49</td><td>21</td><td>74</td><td>34</td><td>99</td><td>109</td></tr><tr><td>25</td><td>15</td><td>50</td><td>100</td><td>75</td><td>557</td><td>100</td><td>346</td></tr></tbody></table>

and after concatenating 20 we stop with $k = 13 = C(7)$, since the last number there, which is $c_7(13)$, is a multiple of 21.

For $n = 2$ the sequence $\{c_2(i)\}$ is 2, 23, 234, ... and stops with $k = 80 = C(2)$ at the 154-digit number

$$c_2(80) = 234567891011121314151617181920\dots6970717273747576777879808182,$$

which is divisible by 83.

Although a purist may be unhappy because its definition involves base 10 arithmetic,<fnref n="3" /> we find $\{C(n)\}$ more interesting than $\{A(n)\}$ and $\{B(n)\}$ because its behavior is so erratic for such a simple rule, and we have no theoretical explanation for this mixture of very small and very large numbers.

Table 3 gives the values of $C(n)$ for $n \le 100$. The values up to about $2 \cdot 10^5$ were found by straightforward direct search, but for the larger values we used the sieving algorithm described in the rest of this section. At the present time we have found the exact value of $C(n)$ for all $n \le 1000$ except for two cases: $n = 539$, where we only have upper and lower bounds, and $n = 158$, where we have searched up to $10^{14}$ without success, and it is possible that $c_{158}(i)$

<footnote n="3">³There is also a base-2 version, with similar properties, although we will not discuss it here: see A332563.</footnote>
does not terminate. The entry for $C(n)$ in [10], A332580, includes a table for $n \le 1000$. Although we do not have a proof that the sequence $\{c_n(i)\}$ always terminates, the following heuristic argument suggests that it should. After $k$ steps, we test $c_n(k)$ for divisibility by $d = n + k + 1$. There are three obvious cases when the division is impossible: (i) when $n + k + 1$ is even, since $c_n(k) \equiv n + k \pmod{10}$ is odd and cannot be divisible by an even number; (ii) when $n + k + 1$ is a multiple of 5, since then $c_n(k) \equiv 4 \pmod{9}$ (mod 10) cannot be divisible by 5; (iii) when $n + k + 1$ is a multiple of 3 in the case when $n \equiv 2 \pmod{3}$, since then $n + k \equiv 2 \pmod{3}$ and so

$$c_n(k) \equiv 2 + 0 + 1 + 2 + \cdots + 0 + 1 + 2 \equiv 2 \pmod{3}.$$

Apart from this, $c_n(k)$ is essentially a very large random number.<fnref n="4" /> The chance that $c_n(k)$ is divisible by $d$ is roughly $1/d$, and since for a fixed $n$ the sum $\sum_{k=1}^{\infty} 1/(n+k+1)$ diverges, we expect one of the divisions to succeed. However, we must admit that even when we try to make this argument more precise by taking into account conditions (i), (ii), (iii), the results do not fully explain the extreme irregularities in the values of $C(n)$ that can be seen in Table 3. This sequence is still very mysterious.

### 4.1. The concatenated words $_nW_m$.
We now present the sieving algorithm for $C(n)$ which we used to obtain

$$ \begin{aligned} C(44) &= 2783191412912, C(92) = 218128159460, C(494) = 2314160375788, \\ 10^{14} < C(539) \le 887969738466613, C(761) = 615431116799, \\ C(854) = 440578095296, \text{ and } C(944) = 1032422879252. \end{aligned} \quad (4.1) $$

The numbers involved in this search are quite large<fnref n="5" />. To find $C(539)$, for example, we must test numbers with about $10^{16}$ digits, that is, numbers on the order of $10^{10^{16}}$, so see if they are divisible by numbers like 887969738466613. Our algorithm (see §4.3) is therefore fairly complicated, and requires some considerable technical machinery, which is developed in this section.

Although we only use it here for base 10 calculations, we present the algorithm in terms of an arbitrary base $b \ge 2$. For an integer $m \ge 0$, let $[m]_b$ denote its $b$ representation (formed by digits from $\{0, 1, \dots, b-1\}$) starting with the most significant digit.

For any positive integer $m$, let $W_m$ be the integer whose base-$b$ representation is the concatenation of the base-$b$ representations of integers 1, 2, ..., $m$, that is

$$[W_m]_b = [1]_b \parallel [2]_b \parallel \cdots \parallel [m]_b.$$

We set $W_0 := 0$.

Similarly, for integers $m \ge n \ge 1$, we define an integer $_nW_m$ by

$$[_nW_m]_b = [n]_b \parallel [n+1]_b \parallel \cdots \parallel [m]_b,$$

so that $W_m = {}_1W_m$.

It can be seen that (extending the definition of $c_n(i)$ to base $b$), we have $c_n(i) = {}_nW_{n+i}$. Correspondingly, the value of $C(n)$ (in base $b$) is given by $m-n-1$, where $m$ is the smallest positive integer such that $m > n$ and

$$_nW_{m-1} \equiv 0 \pmod{m} \quad (4.2)$$

<footnote n="4">⁴If $k$ has $j$ digits, $c_n(k)$ has about $jk$ digits, and we routinely search for $k$ up to $10^{11}$.</footnote>

<footnote n="5">⁵We are tempted to say mind-boggling.</footnote>
For a positive integer $w$ we denote by $|w|$ the length of $[w]_b$. Clearly

$$ {}_nW_m = W_m - W_{n-1} \cdot b^{|_n W_m|}. $$

In the following, we assume that $m$ is an $\ell$-digit integer, with $\ell \ge 1$.

**Lemma 4.1.** Suppose $m$ is an $\ell$-digit integer in base $b$ (i.e., $b^{\ell-1} \le m < b^\ell$) and $1 \le n < m$. Then

$$ |W_m| = \ell \cdot (m+1) - \frac{b^\ell - 1}{b-1} $$

and

$$ |_n W_m| = |W_m| - |W_{n-1}|. $$

In particular,

$$ |W_{b^{\ell-1}}| = \ell \cdot b^\ell - \frac{b^\ell - 1}{b-1} $$

and for any nonnegative integer $k < \ell$,

$$ |_b^k W_m| = \ell \cdot (m+1) - \left( \frac{b^{\ell-k} - 1}{b-1} + k \right) \cdot b^k. \quad (4.3) $$

*Proof.* It is easy to see that $[W_m]_b$ is formed by the concatenation of $b^k - b^{k-1}$ $k$-digit numbers for each $k = 1, 2, \dots, \ell-1$, and $m - b^{\ell-1} + 1$ $\ell$-digits numbers. Hence,

$$ |W_m| = \sum_{k=1}^{\ell-1} k \cdot (b^k - b^{k-1}) + \ell \cdot (m - b^{\ell-1} + 1) = \ell \cdot (m+1) - \frac{b^\ell - 1}{b-1}. $$

Since $[{_nW}_m]_b$ is obtained from $[W_m]_b$ by removing the prefix $[{_nW}_{n-1}]_b$, we have

$$ |_n W_m| = |W_m| - |W_{n-1}|. $$

□

**Lemma 4.2.** Suppose that $b^{\ell-1} \le m < b^\ell$. Then

$$ {}_b^{\ell-1} W_m = \frac{m - (m+1)b^\ell + (b^{2\ell-1} - b^{\ell-1} + 1)b^\ell(m+1-b^{\ell-1})}{(b^\ell - 1)^2}. $$

In particular, for $m = b^\ell - 1$ we have

$$ {}_b^{\ell-1} W_{b^{\ell-1}} = \frac{b^\ell - 1 - b^{2\ell} + (b^{2\ell-1} - b^{\ell-1} + 1)b^\ell(b^\ell - b^{\ell-1})}{(b^\ell - 1)^2}. $$

*Proof.* Notice that

$$ [{_b^{\ell-1} W_m}]_b = [{b^{\ell-1}]_b} \| [{b^{\ell-1} + 1}]_b \| \dots \| [m]_b, $$

where each term in the right hand side is composed of $\ell$ digits. It follows that

$$ {}_b^{\ell-1} W_m = \sum_{i=0}^{m-b^{\ell-1}} (m-i) \cdot b^{\ell-i} = \frac{m - (m+1)b^\ell + (b^{2\ell-1} - b^{\ell-1} + 1)b^\ell(m+1-b^{\ell-1})}{(b^\ell - 1)^2}. $$

□
**Lemma 4.3.** Suppose that $b^{\ell-1} \le m < b^\ell$ and $1 \le n \le m$. Then

$$W_m = b^{\ell-1} W_m + \sum_{k=1}^{\ell-1} b^{k-1} W_{b^{k-1}} \cdot b^{|b^k W_m|}$$

and

$$_nW_m = b^{\ell-1} W_m - W_{n-1} \cdot b^{|nW_m|} + \sum_{k=1}^{\ell-1} b^{k-1} W_{b^{k-1}} \cdot b^{|b^k W_m|}.$$

*Proof.* We notice that

$$[W_m]_b = [b^0 W_{b-1}]_b \| [b W_{b^2-1}]_b \| \cdots \| [b^{\ell-2} W_{b^{\ell-1}-1}] \| \| [b^{\ell-1} W_m]_b,$$

implying that

$$W_m = b^{\ell-1} W_m + \sum_{k=1}^{\ell-1} b^{k-1} W_{b^{k-1}} \cdot b^{|b^k W_m|}.$$

By substituting this expression into $_nW_m = W_m - W_{n-1} \cdot b^{|nW_m|}$ we obtain the formula for $_nW_m$. $\square$

**4.2. Prime powers dividing solutions to the congruence** $_nW_{m-1} \equiv 0 \pmod m$. To find $C(n)$ we must find the smallest positive integer $m > n$ satisfying the congruence (4.2). As we will see in Section 4.3, we build $m$ from the set of prime powers dividing $m$. In this section we will show how to identify these prime powers.

Suppose that a solution $m$ to the congruence (4.2) is divisible by a prime power $p^d$ for some integer $d \ge 1$. Then $m$ is a solution to the pair of congruences:

$$\begin{cases} _nW_{m-1} \equiv 0 \pmod{p^d}, \\ m \equiv 0 \pmod{p^d}. \end{cases} \qquad (4.4)$$

Our algorithm relies on the ability to identify the $\ell$-digit solutions $m$ to this system for any given $\ell$ and prime power $p^d$. We will use the following expression for $_nW_{m-1}$.

**Theorem 4.4.** Suppose that $b^{\ell-1} \le m - 1 < b^\ell$ and $1 \le n < m$. Then

$$_nW_{m-1} = \frac{a_{n,\ell} \cdot b^{\ell(m-b^{\ell})} - (b^{\ell} - 1)m - 1}{(b^{\ell} - 1)^2}, \qquad (4.5)$$

where

$$\begin{aligned} a_{n,\ell} &:= (b^{2\ell-1} - b^{\ell-1} + 1) \cdot b^{\ell(b^{\ell}-b^{\ell-1})} \\ &\quad - (b^{\ell}-1)^2 W_{n-1} \cdot b^{\ell b^{\ell} - \frac{b^{\ell-1}}{b-1} - |W_{n-1}|} \\ &\quad + (b^{\ell}-1)^2 \sum_{k=1}^{\ell-1} b^{k-1} W_{b^{k-1}} \cdot b^{\ell b^{\ell} - \left(\frac{b^{\ell-k-1}}{b-1} + k\right) b^k} \end{aligned}$$

is an integer that depends only on $n$ and $\ell$ but not on $m$.

*Proof.* The formulas for $_nW_{m-1}$ and $a_{n,\ell}$ follow from Lemmas 4.1-4.3. Noticing that $\ell b^\ell - \frac{b^{\ell-1}}{b-1} - |W_{n-1}| = |_nW_{b^{\ell-1}}|$ and $\ell b^\ell - \left(\frac{b^{\ell-k-1}}{b-1} + k\right) \cdot b^k = |_b W_{b^{\ell-1}}|$ by Lemma 4.1, it is easy to verify that all exponents of $b$ in the formula for $a_{n,\ell}$ are nonnegative, and thus $a_{n,\ell}$ is an integer. $\square$
*Remark.* Since $a_{n,l}$ grows doubly exponentially in $l$, we may not be able to compute it explicitly even for relatively small values of $l$. However, we can efficiently compute $a_{n,l}$ modulo $q$ for a given positive integer $q$ as explained in Section 4.3.

It is important to note that the system (4.4) has no solution when $p | b$. Indeed, if we assume that $m$ is a solution to the system (4.4) for prime $p | b$ and $d = 1$, then the number $nW_{m-1} - (m-1) = nW_{m-2} \cdot b^l$ is divisible by $b$ but not by $p$, a contradiction.

Since $p \nmid b$, Theorem 4.4 allows us to rewrite the system (4.4) in the following equivalent form:

$$ \begin{cases} a_{n,l} \cdot b^{l(m-b^l)} - (b^l - 1)m - 1 \equiv 0 \pmod{p^{d+2s}}, \\ m \equiv 0 \pmod{p^d}, \end{cases} \quad (4.6) $$

where $s := \nu_p(b^l - 1)$. From now on, we assume that the integers $n, l$, and a prime $p$ are fixed, and we are solving the system (4.6) with respect to $m$ for varying values of the integer $d \ge 1$.

Let $r$ be the multiplicative order of $b$ modulo $p$, and $r_1 := \frac{r}{\gcd(r, l)}$ the multiplicative order of $b^l$ modulo $p$. More generally, let $r_d$ be the multiplicative order of $b^l$ modulo $p^d$. It is clear that $r_d$ divides $r_1 \cdot p^{d-1}$. In fact, $r_d = r_1 \cdot p^{d-1-\delta}$ with $\delta \ge 0$, where $\delta = 0$ unless $b^{l}r_1 \equiv 1 \pmod{p^2}$. In the latter case $p$ is a generalized Wieferich prime in base $b^l$ (and such primes are expected to be very rare).

We will consider two cases depending on whether $r_1 = 1$ (i.e., $r \nmid l$) or $r_1 > 1$.

4.2.1. Case $p \nmid b^l - 1$. In this case, $r_1 > 1$, i.e., $s = 0$ in the system (4.6). It follows that the system (4.6) has no solution when $\nu_p(a_{n,l}) > 0$. So we assume that $\nu_p(a_{n,l}) = 0$ and rewrite the system (4.6) in the form:

$$ \begin{cases} b^{lm} \equiv \frac{b^l b^l}{a_{n,l}} \pmod{p^d}, \\ m \equiv 0 \pmod{p^d}. \end{cases} \quad (4.7) $$

The following lemma enables us to lift the solutions to the system (4.7) from $d = 1$ to solutions for $d > 1$.

**Lemma 4.5.** Let $k \ge 1$ be an integer. If there is a solution $m$ to the system (4.7) for $d = k$, it has the form $m \equiv p^k t \pmod{p^k r_1}$ for some $t \in \mathbb{Z}_{r_1} = \{0, \dots, r_1 - 1\}$. Moreover, when $k > 1$, $m \equiv p^{k-1} t \pmod{p^{k-1} r_1}$ is a solution to the system (4.7) for $d = k - 1$.

*Proof.* If a solution $m$ to the first congruence of the system (4.7) for $d = k$ exists, it is given by a discrete logarithm to base $b^l$ modulo $p^k$, and thus it represents a residue modulo $r_k$. At the same time, a solution to the second congruence of (4.7) represents the zero residue modulo $p^k$. Since $r_k = p^{k-1-\delta}r_1$ for some integer $\delta \ge 0$ and $\gcd(r_1, p) = 1$, we have $\text{lcm}(r_k, p^k) = p^k r_1$ and thus by the Chinese Remainder Theorem, the solutions to (4.7) are given by $m \equiv p^k t \pmod{p^k r_1}$ for some $t \in \mathbb{Z}_{r_1}$.

Now, if $m \equiv p^k t \pmod{p^k r_1}$ is a solution to (4.7) for $d = k$, then this $m$ also satisfies the system (4.7) for $d = k - 1$. Since $p^k t \equiv p^{k-1} t \pmod{p^{k-1} r_1}$, we conclude that $m \equiv p^{k-1} t \pmod{p^{k-1} r_1}$ is a solution to the system (4.7) for $d = k - 1$. $\square$

The following theorem gives bounds on $d$ for the system (4.7) to be solvable, and describes the form of the solutions.

**Theorem 4.6.** Suppose that the prime $p$ does not divide $b$ or $a_{n,l}$. Let $m \equiv pt \pmod{pr_1}$ be a solution to the system (4.7) for $d = 1$. Then the system (4.7) is solvable for a general $d$ if and
only if $1 \le d \le D$, and the solutions are given by $m \equiv p^d t \pmod{p^d r_1}$, where

$$D := \nu_p\left(\left(\frac{b^{\ell b^\ell}}{a_{n,\ell}}\right)^{r_1} - 1\right) = \nu_p\left(a_{n,\ell}^{r_1} - b^{\ell b^\ell r_1}\right).$$

*Proof.* Suppose that $m = m_0$ is a solution to the system (4.7). Then $p^d \mid m_0$, implying that $b^{\ell m_0 r_1} \equiv 1 \pmod{p^d}$ since $r_d \mid p^{d-1}r_1 \mid m_0 r_1$. Taking the first congruence of (4.7) to the power $r_1$, we get

$$a_{n,\ell}^{r_1} \equiv b^{\ell b^\ell r_1} \pmod{p^d},$$

implying that $d \le D$.

Let $g$ be a primitive root modulo $p^D$, and thus $g$ modulo $p^D$ has the order $(p-1)p^{D-1}$. Since $(\frac{b^{\ell b^\ell}}{a_{n,\ell}})^{r_1} \equiv 1 \pmod{p^D}$, it follows that $\frac{b^{\ell b^\ell}}{a_{n,\ell}} \equiv g^{s(p-1)p^{D-1}/r_1} \pmod{p^D}$ for some integer $s$, $0 \le s < r_1$. Furthermore, since $sp^D \equiv sp^{D-1} \pmod{r_1 p^{D-1}}$, we have

$$\left(\frac{b^{\ell b^\ell}}{a_{n,\ell}}\right)^p \equiv g^{ps(p-1)p^{D-1}/r_1} \equiv g^{s(p-1)p^{D-1}/r_1} \equiv \frac{b^{\ell b^\ell}}{a_{n,\ell}} \pmod{p^D}. \quad (4.8)$$

We will show by induction on $d$ that $m \equiv p^d t \pmod{p^d r_1}$ is a solution to the system (4.7) for $d = 1, 2, \dots, D$. For $d = 1$, this is given. If $m \equiv p^k t \pmod{p^k r_1}$ is a solution to the system (4.7) for $d = k < D$, then by taking the first congruence of (4.7) to the power $p$ and using the congruence (4.8), we get

$$b^{\ell p^{k+1} t} \equiv \left(\frac{b^{\ell b^\ell}}{a_{n,\ell}}\right)^p \equiv \frac{b^{\ell b^\ell}}{a_{n,\ell}} \pmod{p^{k+1}},$$

which implies that $m \equiv p^{k+1} t \pmod{p^{k+1} r_1}$ is a solution to the system (4.7) for $d = k+1$ (since $k+1 \le D$).

By Lemma 4.5, there exist no other solutions to the system (4.7) besides those constructed from $d = 1$. $\square$

Theorem 4.6 allows us to concentrate on the case $d = 1$. In this case, Theorem 4.6 implies that $D \ge 1$ is necessary for the solubility of the system (4.7), which is equivalent to

$$a_{n,\ell}^{r_1} \equiv 1 \pmod{p}.$$

This condition holds trivially when $r_1 = p-1$. However, it is nontrivial when $r_1 < p-1$ and can be used as a quick test for solubility of the system (4.7). If this condition holds, we proceed with computing the discrete logarithm of $a_{n,\ell}$ to base $b^\ell$ modulo $p$. If the logarithm exists and equals $e$, i.e., $a_{n,\ell} \equiv b^{\ell e} \pmod{p}$, then from the first congruence of (4.7) it follows that $m \equiv b^\ell - e \pmod{r_1}$. Combining this with the second congruence of (4.7), i.e., $m \equiv 0 \pmod{p}$, we get a solution to the system (4.7) as $m \equiv p(b^\ell - e) \pmod{pr_1}$, which we can lift using Lemma 4.5.

4.2.2. Case $p \mid b^\ell - 1$. In this case, we have $r_1 = 1$, i.e., $s > 0$ in the system (4.6). We will need the following lemma.

**Lemma 4.7.** Let $m, u, d, s$ be positive integers and let $p$ be a prime such that $p^d \mid m$ and $p^s \mid u$. Then

$$(1+u)^m \equiv 1+mu+\frac{m(m-1)}{2}u^2 \pmod{p^{d+2s}},$$
which in the case $p \ge 3$ can be shortened to

$$ (1+u)^m \equiv 1+mu \pmod{p^{d+2s}}. $$

*Proof.* Since

$$ (1+u)^m = 1+mu + \frac{m(m-1)}{2}u^2 + \sum_{k=3}^{m} \binom{m}{k} u^k, $$

it is enough to prove that $p^{d+2s} \mid \binom{m}{k}u^k$ for all $k$ in the range $3 \le k \le m$. Consider two cases depending on whether or not $p$ divides $k$.

If $p \nmid k$, then

$$ p^{d+2s} \mid p^d u^2 \mid \frac{m}{k} \binom{m-1}{k-1} u^k = \binom{m}{k} u^k. $$

If $p \mid k$, then letting $t := \nu_p(k) > 0$, we get

$$ p^{d-t+ks} \mid \frac{m}{k} \binom{m-1}{k-1} u^k. $$

It remains to show that $d-t+ks \ge d+2s$, i.e., $(k-2)s-t \ge 0$. Except for the case when $p=2$ and $t=1$, $k \ge p^t$ implies

$$ (k-2)s-t \ge p^t-2-t \ge 0. $$

On the other hand, if $p=2$ and $t=1$, from $k \ge 3$ it follows that

$$ (k-2)s-t \ge s-1 \ge 0. $$

□

**Theorem 4.8.** Let $p \ge 3$ be a prime such that $s := \nu_p(b^\ell - 1) > 0$. Then the system (4.6) has a solution if and only if $d \le D$, where

$$ D := \nu_p(a_{n,\ell} - b^{\ell b^\ell}) - 2s, $$

in which case the solutions are given by $m \equiv 0 \pmod{p^d}$.

*Proof.* If $m$ is a solution to the system (4.6), then $m \equiv 0 \pmod{p^d}$, which by Lemma 4.7 with $u := b^\ell - 1$ implies that

$$ b^{\ell m} \equiv (1+b^\ell-1)^m \equiv 1+m(b^\ell-1) \pmod{p^{d+2s}}, $$

and thus we can rewrite the first congruence of system (4.6) as

$$ \left( \frac{a_{n,\ell}}{b^{\ell b^\ell}} - 1 \right) (1 + m(b^\ell - 1)) \equiv 0 \pmod{p^{d+2s}}. $$

Since the second factor is coprime to $p$ and $p \nmid b$, we conclude that $m \equiv 0 \pmod{p^d}$ gives a solution to the system (4.6) if and only if

$$ a_{n,\ell} - b^{\ell b^\ell} \equiv 0 \pmod{p^{d+2s}}, $$

which concludes the proof. □

**Theorem 4.9.** Let $s := \nu_2(b^\ell - 1) > 0$. Then the system (4.6) for $p=2$ has a solution if and only if $d \le D$, where

$$ D := \nu_2(a_{n,\ell} - b^{\ell b^\ell}) - 2s + 1, $$

in which case the solutions are given by $m \equiv 0 \pmod{2^{d+1}}$ if $d < D$, and by $m \equiv 2^d \pmod{2^{d+1}}$ if $d = D$.
*Proof.* First we notice that $s > 0$ implies that $b$ is odd.

Let $m$ be a solution to the system (4.6) for $p = 2$. In particular, we have $\nu_2(m) \ge d$. Since by Lemma 4.7

$$b^{lm} \equiv (1 + b^l - 1)^m \equiv 1 + m(b^l - 1) + \frac{m(m-1)(b^l - 1)^2}{2} \pmod{2^{d+2s}},$$

the first congruence of system (4.6) for $p = 2$ is equivalent to

$$\left( \frac{a_{n,l}}{b^{l}b^{l}} - 1 \right) (1 + m(b^{l} - 1)) + \frac{a_{n,l} m(m-1)(b^{l} - 1)^{2}}{2} \equiv 0 \pmod{2^{d+2s}}. \quad (4.9)$$

It remains to consider two cases depending on whether $\nu_2(m) = d$ or $\nu_2(m) > d$:

* If $\nu_2(m) = d$ (i.e., $m \equiv 2^d \pmod{2^{d+1}}$), then $m$ is a solution to the congruence (4.9) if and only if $\nu_2(a_{n,l} - b^{l}b^{l}) = d + 2s - 1$.

* If $\nu_2(m) > d$ (i.e., $m \equiv 0 \pmod{2^{d+1}}$), then $m$ is a solution to the congruence (4.9) if and only if $\nu_2(a_{n,l} - b^{l}b^{l}) \ge d + 2s$.

□

4.3. **The C(n) sieve.** As we saw in §4.1, to find $C(n)$ we must solve the congruence (4.2). We construct solutions to this congruence using an analog of wheel factorization [11] for integers in the interval $[b^{l-1}, b^l)$. That is, we consider $p^d$ to be a factor of an integer $m$ only if $m$ is a solution to the system (4.6). The integers $m$ that are factored completely in this way (i.e., the product of the identified factors equals $m$) give the solutions to the congruence (4.2). The following is THE C(n) SIEVE:

**Input:** an integer base $b \ge 2$, an integer $n$, and an upper bound $L := b^l$ for some $l \ge 1$

**Output:** either $C(n) = m - n - 1$ with $L/b < m \le L$, or NONE if no such $m$ exists

1: initialize an array $T[m] = 1$ for $m$ in the interval $(L/b, L]$

2: **for** each prime $p \le L$ **do**

3: $A \leftarrow \text{COMPUTEA}(n, l, b, p) \qquad \triangleright \text{i.e., } A \leftarrow a_{n,l} \pmod p$

4: **if** $p \mid b$ **or** $A = 0$ **then**

5: proceed to the next value of $p$

6: $r_1 \leftarrow \text{ord}_p(L) \qquad \triangleright \text{i.e., multiplicative order of } L \text{ modulo } p$

7: **if** $r_1 > 1$ **then**

8: **if** $A^{r_1} \not\equiv 1 \pmod p$ **then**

9: proceed to the next value of $p$

10: $q \leftarrow$ discrete logarithm of $A$ base $L$ modulo $p$; if it does not exist, continue to the next value of $p$

11: $M \leftarrow r_1 \cdot p$

12: $m_0 \leftarrow (L - q)p \pmod M$

13: **else** \qquad $\triangleright$ case $r_1 = 1$

14: $m_0 \leftarrow 0$

15: **if** $p = 2$ **then**

16: $M \leftarrow 4$

17: **else**

18: $M \leftarrow p$

19: **if** $m_0 = 0$ **then** \qquad $\triangleright$ we consider only positive solutions

20: $m_0 \leftarrow M$

21: $d \leftarrow 1$
22: **while** $m_0 \le L$ **and** $(p, m_0, d)$ is a solution to the system (4.6) **do**

23: $m \leftarrow m_0 + \left\lfloor \frac{L/b-m_0}{M} \right\rfloor \cdot M$

24: **while** $m \le L$ **do**

25: $T[m] \leftarrow p \cdot T[m]$

26: $m \leftarrow m + M$

27: $m_0 \leftarrow m_0 \cdot p$

28: $M \leftarrow M \cdot p$

29: $d \leftarrow d + 1$

30: **if** $p = 2$ **and** $m_0/2 \le L$ **and** $(p, m_0/2, d)$ is a solution to the system (4.6) **then**
$\triangleright$ case $p = 2$ and $d = D$

31: $m_0 \leftarrow m_0/2$

32: $m \leftarrow m_0 + \left\lfloor \frac{L/b-m_0}{M} \right\rfloor \cdot M$

33: **while** $m \le L$ **do**

34: $T[m] \leftarrow p \cdot T[m]$

35: $m \leftarrow m + M$

36: **for** $m$ from $\max\{L/b+1, n+2\}$ to $L$ **do**

37: **if** $T[m] = m$ **then**

38: return $C(n) = m - n - 1$

39: return NONE

*Remarks.* Lines 3-20 find $m_0$ and $M$ such that the residues $m \equiv m_0 \pmod M$ satisfy the system (4.4) for $d=1$. In lines 21-29 we multiply $T[m]$ by the prime $p$ for solutions $m$ in the interval $(L/b, L]$, and incrementally lift the solutions to larger $d$. The exceptional case of $p=2$ and $d=D$ is addressed in lines 30-35. In lines 36-38, we check if any integer $m$ in the interval $(L/b, L]$ was factored completely, and derive $C(n)$ from the smallest such $m$.

Since the performance of our algorithm depends on our ability to compute $a_{n,l} \pmod p$, we
explain how to do this efficiently using Lemmas 4.1-4.3.

We start with a function based on Lemma 4.1 that computes $|W_m|$.

1: **function** LENW$(m, b)$

2: if $m=0$ then

3: **return** 0

4: $\ell \leftarrow [\log_b(m+1)]$

5: **return** $\ell \cdot (m+1) - (b^\ell - 1)/(b-1)$

$\triangleright$ computes $|W_m|$ in base $b$

$\triangleright$ number of base-$b$ digits in $m$

Next, we use Lemma 4.2 to design a function that for given integers $m, b, q$ with $b^{\ell-1} \le m < b^\ell$
computes $b^{\ell-1} W_m \pmod q$ in base $b$.

1: **function** BWMQ$(m, b, q)$

2: $\ell \leftarrow [\log_b(m+1)]$

3: $d_1 \leftarrow (b^\ell - 1)^2$

4: $d_2 \leftarrow 1$

5: $g \leftarrow \gcd(d_1, q)$

6: **while** $g > 1$ **do**

7: $d_1 \leftarrow d_1/g$

$\triangleright$ computes $b^{\ell-1} W_m \pmod q$ in base $b$

$\triangleright$ number of base-$b$ digits in $m$
8: $d_2 \leftarrow d_2 \cdot g$

9: $g \leftarrow \gcd(d_1, g)$

10: $B \leftarrow b \pmod{q \cdot d_2}$ ▷ a residue modulo $q \cdot d_2$

11: **return LIFT** $((m - (m+1) \cdot B^\ell + (B^{2\ell-1} - B^{\ell-1} + 1) \cdot B^{\ell(m+1-b^{\ell-1})}) / d_1) / d_2$

The function BWMQ first represents the denominator of the expression for $b^{\ell-1}W_m$ from Lemma 4.2 as $(b^\ell - 1)^2 = d_1 \cdot d_2$, where $d_1$ and $d_2$ are the largest divisors of $(b^\ell - 1)^2$ such that $d_1$ is co-prime to $q$ while $d_2$ is composed of prime factors dividing $q$. Then the function defines $B$ to be a residue modulo $qd_2$ such that all computations involving $B$ are performed modulo the same number. Namely, this function computes the numerator of the expression for $b^{\ell-1}W_m$ divided by $d_1$ as a residue modulo $qd_2$, which is then lifted (with the function LIFT) to an integer and divided by $d_2$. This approach produces the correct value for $b^{\ell-1}W_m \bmod q$ even if $q$ is not co-prime to $b^\ell - 1$ (i.e., when $d_2 > 1$).

Similarly, we use Lemma 4.3 and the expression (4.3) to design a recursive function that computes $nW_m \bmod q$ for given integers $n, m, b, q$.

1: **function NWMQ(n, m, b, q)** ▷ computes $nW_m \bmod q$ in base $b$

2: $\ell \leftarrow [\log_b(m+1)]$ ▷ number of base-$b$ digits in $m$

3: $B \leftarrow b \pmod q$ ▷ a residue modulo $q$

4: $r \leftarrow BWMQ(m, b, q) + \sum_{k=1}^{\ell-1} BWMQ(b^k - 1, b, q) \cdot B^{\ell(m+1)} - ((b^{\ell-k-1})/(b-1)+k) \cdot b^k$

5: **if** $n > 1$ **then**

6: $r \leftarrow r - NWMQ(1, n-1, b, q) \cdot B^{\text{LENW}(m,b)} - \text{LENW}(n-1,b)$

7: **return** LIFT($r$)

Finally, we are ready to design a function that computes $a_{n,\ell} \bmod q$ for given integers $n, \ell, b, q$. This function implements the formula:

$$a_{n,\ell} = (nW_{b^{\ell}-1} + 1)(b^{\ell}-1)^2 + b^{\ell},$$

which follows from Theorem 4.5 for $m = b^\ell$.

1: **function** COMPUTEA(n, ℓ, b, q) ▷ computes $a_{n,\ell} \bmod q$ in base $b$

2: $C \leftarrow b^\ell \pmod q$ ▷ a residue modulo $q$

3: **return** LIFT $((NWMQ(n, b^\ell - 1, b, q) + 1) \cdot (C - 1)^2 + C)$

*Remark.* Although we use COMPUTEA (and thus NWMQ and BWMQ) in our algorithm for computing $C(n)$ only for prime $q = p$, it works equally well for non-prime $q$.

**4.4. Discussion.** When the value $C(n)$ is small, less than $10^7$ (say), it can be computed directly by explicitly constructing $c_n(i)$ and testing its divisibility by $n+i+1$ for each $i = 1, 2, \dots$. In base 10, this naive search is faster than the $C(n)$ sieve when $C(n)$ is below $10^7$ or so. However, for larger values of $C(n)$ the sieve gives a significant speed-up. It therefore makes sense to combine the two algorithms, by first running the naive search up to a certain threshold, and then, if it was unsuccessful, switching to the sieve. The choice for the threshold will depend on how the algorithms are implemented.<fnref n="6" />

<footnote n="6">⁶Our implementations are currently available from https://github.com/maxale/Recaman_cousin_C</footnote>
THREE COUSINS OF RECAMÁN'S SEQUENCE

ACKNOWLEDGMENTS

We thank Michael J. Collins, Bradley Klee, Victor S. Miller, Kerry Mitchell, and Al-
lan C. Wechsler for helpful comments during our work on $A(n)$, David A. Corneth, Rémy
Sigrist, and Jinyuan Wang for computing further terms in certain sequences arising in our
study of $B(n)$, and Pierrick Gaudry for his help with the asymptotics of $B(n)$ and for inde-
pendently checking some of the calculations for $C(n)$.

REFERENCES

[1] D. W. Ballew and R. C. Weber, *Pythagorean triples and triangular numbers*, The Fibonacci Quarterly, **17.2** (1979), 168-172.

[2] B. Chaffin, E. M. Rains, N. J. A. Sloane, and A. R. Wilks, Numerical investigations of Recamán's sequence, in preparation, 2021.

[3] K. Dickman, *On the frequency of numbers containing prime factors of a certain relative magnitude*, Ark. Mat. Astr. Fys., **22.10** (1930), 1-14.

[4] A. Granville, *Smooth numbers: computational number theory and beyond*, in *Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography*, Math. Sci. Res. Inst. Publ., **44**, Cambridge Univ. Press, Cambridge, 2008, 267-323.

[5] P. W. Haggard, *Pythagorean triples and sums of triangular numbers*, Internat. J. Mathematical Education in Science and Technology, **28.1** (1997), 109-116.

[6] A. Kruppa, *Speeding up integer multiplication and factorization*, PhD Dissertation, Univ. Henri Poincaré Nancy 1, 2010; http://docnum.univ-lorraine.fr/public/SCD_T_2010_0054_KRUPPA.pdf.

[7] H. Lee and M. Zafrullah, *A note on triangular number*, Punjab Univ. J. Math., **26** (1993), 75-83.

[8] H. W. Lenstra Jr, J. Pila, and C. Pomerance, *A hyperelliptic smoothness test. I*, Phil. Trans. Roy. Soc. London, Series A, **345.1676** (1993), 397-408.

[9] M. A. Nyblom, *On the representation of the integers as a difference of nonconsecutive triangular numbers*, The Fibonacci Quarterly, **39.3** (2001), 256-263.

[10] OEIS Foundation Inc. (2021), *The On-Line Encyclopedia of Integer Sequences*, https://oeis.org.

[11] P. Pritchard, *Explaining the wheel sieve*, Acta Informatica, **17** (1982), 477-485.

[12] W. Sierpiński, *On triangular numbers which are sums of two smaller triangular numbers* [Polish], Wiadom. Mat., **(2) 7** (1963): 27-28; MR0182602.

[13] A. Tripathi, *On Pythagorean triples containing a fixed integer*, The Fibonacci Quarterly, **46/47.4** (2008/09), 331-340.

[14] M. Ulas, *A note on Sierpiński's problem related to triangular numbers*, Colloq. Math., **117.2** (2009): 165-173.

[15] A. M. Vaidya, *On representing an integer as a sum of two triangular numbers*, Vidya, **B 15.2** (1972), 104-105.
THE FIBONACCI QUARTERLY

MSC2010: 11B83 (11D72, 11D85)

DEPARTMENT OF MATHEMATICS & COMPUTATIONAL BIOLOGY INSTITUTE, GEORGE WASHINGTON UNIVERSITY, ASHBURN, VA 20147, USA

*E-mail address: maxal@gwu.edu*

C/O TRINITY COLLEGE, CAMBRIDGE, CB2 1TQ, UK

*E-mail address: jsm@polyomino.org.uk*

500 SOUTH MAPLE DR., WOODLAND HILLS, UT 84653, USA

*E-mail address: rcs@xmission.com*

P.O. Box 2260, ROWVILLE, VICTORIA 3178, AUSTRALIA

*E-mail address: scott_r_shannon@hotmail.com*

THE OEIS FOUNDATION INC., 11 SOUTH ADELAIDE AVE., HIGHLAND PARK, NJ 08904, USA

*E-mail address: njasloane@gmail.com*

INRIA NANCY – GRAND EST, LORIA, F-54600 VILLERS-LÈS-NANCY, FRANCE

*E-mail address: Paul.Zimmermann@inria.fr*