home / posts

Parasitic Numbers

When I wrote my last post on double trouble numbers, I wasn't aware of parasitic numbers, of which double trouble numbers are a special case (although our definition of double trouble numbers permitted leading zeros, something we will not permit here). In fact, there is a lot out there on these numbers including a good wikipedia article. However, I will take the same approach here as I took in my post on double trouble numbers, generalize it to $n$-parasitic numbers and explore some further properties. I recommend that you read my post on double trouble numbers first because I will make use of the ideas it presents.

An $n$-parasitic number $x$ gives the number $nx$ when its digits in base $b$ are right rotated one position. Unlike our treatment of double trouble numbers, we do not permit leading zeros. To preclude leading zeros, the least significant digit must be greater or equal to $n$. Generalizing from double trouble numbers, a state is now a pair in $\mathbb{Z}_b \times \mathbb{Z}_n$ and the state transition function $\delta : \mathbb{Z}_b \times \mathbb{Z}_n \to \mathbb{Z}_b \times \mathbb{Z}_n$ is defined as $$\delta : (d, c) \mapsto (nd + c, \lfloor (nd + c) / b \rfloor)$$ In fact, state transition corresponds to multiplication by $n$ modulo $nb - 1$, a fact we will use later. As such, a state $(d, c)$ can be viewed as an integer $cb + d \in \mathbb{Z}_{nb - 1}$. The code to generate an $n$-parasitic number given $n$, base $b$ and least significant digit $d$ in Python is therefore simple and terse.

def parasitic(n, b, d):
    """Returns a list of the digits of the elementary n-parasitic number in base b 
       with least significant digit d (ordered from least significant to most significant) given n, b and d
    """

    assert n >= 2 and n < b and d >= n and d < b

    digits = [d]
    s = n * d
    while s != d:
        digits.append(s % b)
        s = (n * s) % (n*b - 1)
    return digits

We will now prove the following lemma.

Lemma The length of an elementary $n$-parasitic number in base $b$ divides the multiplicative order of $b$ modulo $nb - 1$

Proof $\;$Let $x$ be an elementary $n$-parasitic number of length $\ell$ with least significant digit $d$. Let $m$ be the multiplicative order of $b$ modulo $nb - 1$. We need to show that $\ell \mid m$. The following equality follows immediately from the definition of an $n$-parasitic number: $$b^{\ell - 1} + \frac{x - d}{b} = nx$$ With simple algebra, we can rearrange the above to yield $$x = \frac{d \cdot (b^\ell - 1)}{nb - 1}$$ Now for $x$ to be an integer as required, then $nb - 1$ must divide $d \cdot (b^\ell - 1)$. A sufficient condition for this is that $b^\ell \equiv 1 \pmod{nb - 1}$, in which case $\ell = m$, the multiplicative order of $b$ modulo $nb - 1$. Suppose $\ell < m$. In this case, it holds that $nb - 1 \mid d \cdot (t - 1)$ where $t = b^\ell \pmod{nb - 1}$. Now from the equality above, there is a larger $n$-parasitic number $x'$ with the same least significant digit $d$ whose length is $m$ and which is equal to $\frac{d \cdot (b^m - 1)}{nb - 1}$. From the generalization of our result in the double trouble numbers post, we know that all $n$-parasitic numbers with the same least significant digit are unique up to concatenation. Since $x$ is elementary and $x'$ is formed by concatenating copies of $x$, it follows that $\ell \mid m$. $$\tag*{$\blacksquare$}$$

As a corollary, it holds that $\ell \mid \phi(nb - 1)$ where $\phi$ is Euler's totient function. Furthermore, we note that the multiplicative order of $b$ modulo $nb - 1$ is equal to the multiplicative order of $n$ modulo $nb - 1$.

Let us define an equivalence relation on $n$-parasitic numbers. We write $x \sim_{n, b} y$ if the $n$-parasitic numbers $x$ and $y$ are circular permutations of each other in base $b$. Let $P_{n, b}$ be the set of $n$-parasitic numbers in base $b$. The number of equivalence classes $|P_{n, b}/\sim_{n, b}|$ under the relation $\sim_{n, b}$ is related to the number of cyclotomic cosets of $n$ modulo $nb - 1$. More formally, we have the following equality $$|P_{n, b}/\sim_{n, b}| = |\{C_d : d \in \{k, \ldots, b - 1\}\}|$$ where $C_d := \{d \cdot n^k : k \in \{0, \ldots, nb - 1\}\}$. For shorthand, let us define $a_{n}(b) = |P_{n, b}/\sim_{n, b}|$.

The sequence generated by $a_2(3), a_2(4), \ldots$ is the sequence A006694 in the OEIS. More precisely, $a_2(b) = \text{A006694}(b - 1)$.

We will now take a look at the length of $n$-parasitic numbers, in particular, the bases that give minimal and maximal lengths. Recall that the minimal length of an $n$-parasitic number is 2. The sequence of bases that give minimal length $n$-parasitic numbers is generated by $s_n(k) = (n + 1)k + n$ for $k \geq 1$. To see this, observe that for any $k \geq 1$, setting the least significant digit to $nk + 1$ yields an $n$-parasitic number of length 2 in base $(n + 1)k + n$. For $n = 2$, we have that $s_2$ generates the sequence A016789 in the OEIS.

Now in regard to maximal length $n$-parasitic numbers, recall that the maximal length in base $b$ is $nb - 2$. If a base has a maximal length $n$-parasitic number, then it follows immediately from our corollary above that $nb - 1$ is prime. The converse does not necessarily hold. For certain choices of $n$, there are no maximal length $n$-parasitic numbers. An example is $n = 4$ because any base $b$ is a quadratic residue modulo $4b - 1$ whose square roots are $2b$ and $2b - 1$ and therefore its multiplicative order modulo $4b - 1$ cannot be $4b - 2$. We do not have a general form for the bases that give maximal lengths. An interesting special case is $n = 2$ where the sequence of bases giving maximal lengths is the sequence A051733 in the OEIS.

We will make one final remark. For base 10, which is quite a commonly-used base, we discovered that 142857, the best-known cyclic number (in base 10) and which has some other remarkable properties, is the only $n$-parasitic number in base 10 whose length is not equal to 18, the multiplicative order of 10 modulo $2 \cdot 10 - 1$. This number is 5-parasitic.