mixedmath

I've previously described machine learning experiments concerning learning the Möbius function. (See general report and technical report, as well as slides from a talk and ctypes). This work went into my preprint on the arxiv DLD. Studying number theory with deep learning: a case study with the Möbius and squarefree indicator functions. arXiv 2025.

The goal is to learn the function $\mu(n)$, which is $0$ if a nontrivial square divides $n$ and otherwise is $(-1)^{\omega(n)}$, where $\omega(n)$ is the number of prime divisors of $n$. For example, $\mu(1) = \mu(6) = \mu(10) = \mu(15) = 1$, $\mu(2) = \mu(3) = \mu(7) = -1$, and $\mu(4) = \mu(8) = \mu(9) = \mu(12) = 0$.

Given enough time, the "obvious strategies" become arbitrarily good at learning whether $\mu(n) = 0$ or not. This is not a deep statement and instead describes statistical distribution of square divisibility. One of my strategies in training models to study $\mu$ before was to choose representations of integers that obfuscate divisibility by squares — deliberately trying to force the models to learn something different.

Many people who have read or heard about my experiments have offered different inconvenient integer representations and asked how they compare. In this note, I describe two representative representations and how they fare.

Every model I've trained seems to pick up either

• divisibility by squares: these become arbitrarily good at learning when $\mu(n) = 0$ and don't learn anything about how to distinguish $\mu(n) = \pm 1$).
• divisibility by small primes: these use the correlative fact that if a small prime divides a number, then it's more likely to be squarefull. These also don't learn how to distinguish between $\mu(n) = \pm 1$.

(Or alternately the representations are too inconvenient and the models don't learn either of these).

Zeckendorf Representation

Every positive integer has a unique representation as a sum of distinct Fibonacci numbers such that the sum does not include any two consecutive Fibonacci numbers. This is straightforward to prove and leads to two closely related ways of representing an integer $n$: as a sequence of Fibonacci numbers that sum to $n$, or as a binary sequence with $1$s corresponding to the included Fibonacci numbers.

A straightforward greedy algorithm computes these very quickly.

fibs = [0, 1]

def extend_fib(n):
    """Extends `fibs` to have at least one number larger than n."""
    while n > fibs[-1]:
        nextfib = fibs[-1] + fibs[-2]
        fibs.append(nextfib)

def zeckendorf(n):
    """
    Computes the Zeckendorf representation of a non-negative integer n.

    Returns:
        A list of Fibonacci numbers that sum to n, with no two consecutive
        Fibonacci numbers. Returns an empty list if n is 0.
    """
    if n < 0: raise ValueError("Input must be a non-negative integer.")
    if n == 0: return []
    extend_fib(n)
    representation = []
    for fib in reversed(fibs):
        if n >= fib:
            representation.append(fib)
            n -= fib
    return representation

def zeckendorf_indices(n):
    """
    Computes the Zeckendorf representation of a non-negative integer n.

    Returns:
        The indices of the Fibonacci numbers that sum to n with no consecutive
        indices being 1. Returns an empty list if n is 0.
    """
    if n < 0: raise ValueError("Input must be a non-negative integer.")
    if n == 0: return []
    extend_fib(n)
    representation = []
    for fib in reversed(fibs):
        if n >= fib:
            representation.append(1)
            n -= fib
        else:
            representation.append(0)
    representation.reverse()
    return remove_trailing_zeros(representation)

def remove_trailing_zeros(inlist):
    """Remove trailing zeros from input array."""
    end = -1
    for i in range(len(inlist) - 1, -1, -1):
        if inlist[i] != 0: break
        end = i
    return inlist[:end]

Similar systems include

• Square-Fibonacci base (writing $n = \sum a_i F_i^2$ with $a_i \in \{ 0, 1, 2 \}$), or
• Chung-Graham (writing $n = \sum a_i F_{i + 2}$ with $a_i \in \{0, 1, 2\}$ and $a_i = 0$ if $i$ is odd).

I didn't know these representations of integers before Joshua Zelinsky asked me about them. A couple others have given similar ideas.

With each of these, the models learn nothing. These representations are simply too far removed.^{1 1}According to Littlewood's Mathematicians Miscellany, Charles Darwin believed that every once in a while one should perform a fool's experiment. These almost always fail, but any success will be terrific. Darwin purportedly played the trombone to his tulips. The result of that experiment was negative. (The result of this experiment was also negative).

Mixed base, negaternary, and other systems

In standard base $b$, we can write \begin{equation} n = \pm \sum_{i = 0}^K a_i b^i \qquad (0 \leq a_i \lt b) \end{equation} for some $K$ depending on $n$. Closely related are negative bases, where we can write \begin{equation} n = \sum_{i = 0}^K a_i (-b)^i \qquad (0 \leq a_i \lt b). \end{equation} One can also treat mixed base, writing \begin{equation} n = \sum_{i = 0}^K a_i (b_i)^i \qquad (0 \leq a_i \lt b_i). \end{equation}

In each of these, it's straightforward to determine divisibility by primes dividing the base (or primes dividing the "one's base"). The models picked up on this but nothing more.

Factoradic Representation

This came from my coauthor Tom Oliver and performed surprisingly well (given that it feels like an inconvenient representation).

We call a permutation $\sigma$ of $\mathbb{N}$ to be tame if $\sigma(i) = i$ for almost every $i$. We can write a tame permutation by writing the sequence \begin{equation} \sigma(0), \sigma(1), \sigma(2), \ldots \end{equation} As $\sigma(i) = i$ for almost every $i$, we can truncate the purmutation at $J$ where all $j$ for which $\sigma(j) \neq j$ satisfy $j \leq J$. The set of tame permutations can then be ordered lexicographically. We use the reversed right-to-left lexicographic order.

We define the factoradic form of $n \in \mathbb{N}$ to be the $n$th tame permutation in the reversed, right-to-left lexicographic order.

In practice, this is made much clearer by a couple of examples.

• The factoradic form of $0$ is $(0, 1, 2, 3, \ldots)$.
• The factoradic form of $1$ is $(1, 0, 2, 3, \ldots)$.
• The factoradic form of $2$ is $(0, 2, 1, 3, 4, \ldots)$.

There are $k!$ permutations of the first $k$ integers, and thus any integer $n < k!$ has a factoradic form that can be specified by giving $\sigma(j)$ for $j \leq k$.

An alternate way of giving the factoradic form of $n$ is to give the $n$th (ordered) permutation of the integers up to $k$ (for some $k$ with $n < k!$). This is how I compute them in practice.

ALGORITHM: return factoradic form of n
  1. If n = 0 return (0).
  2. If n = 1 return (1, 0).  // 0! = 1! is confusing
  3. Set k to the the minimal integer with n < k!
  4. Compute L, the (k! - n)th lexicographically ordered
     permutation of (0, 1, ... , k-1).
  5. Return REVERSE(L).

Another simple algorithm gives the $n$th ordered permutation of $(0, \ldots, k - 1)$.

ALGORITHM: return the nth permutation of (0, 1, ..., k-1).
  1. Set L = (0, 1, ..., k-1).
  2. Set n' = n - 1.  // 0-indexing lists is confusing.
  3. Initialize RET = [].
  4. For each m in [k-1 .. 0]:
  5.   Set q = FLOOR(n' / m!).
  6.   Set r = n MODULO n!
  7.   Append qth element of L to RET.
  8.   Remote qth element of L.
  9.   Set n' := n' - q * m!
 10. Return RET.

Python code for this practically matches the pseudocode.

import math

def nth_permutation(n, k):
    current_list = list(range(k))
    nprime = n - 1
    ret = []
    for m in range(k-1, -1, -1):
        mfact = math.factorial(m)
        q = nprime // mfact
        r = nprime % mfact
        nprime -= q * mfact
        ret.append(current_list[q])
        del current_list[q]
    return ret

def factoradic(n):
    if n == 0: return (0, )
    if n == 1: return (1, 0)
    k = 0
    while True:
        if n < math.factorial(k):
            break
        k += 1
    np = nth_permutation(math.factorial(k) - n, k)
    return list(reversed(np))

assert factoradic(9) == [3, 0, 1, 2]
assert factoradic(1234) == [2, 6, 0, 3, 4, 1, 5]
assert factoradic(123456789) == [9, 3, 6, 1, 4, 2, 5, 0, 7, 11, 10, 8]

I trained models using the factoradic representations. It turns out that these models successfully learned divisibility-by-small-primes rules.

Oliver and Vernitski's preprint Oliver and Vernitski. Divisibility rules for integers presented as permutations. arXiv 2025) shows that factoradic representations "obviously" encode divisibility rules — but I think it' not at all obvious that a ML model would pick up on this. But they do!

Leave a comment

Comment via email