Based on some new analysis I’ve done of Nanyan numerals (as described here), I’ve discovered a new algorithm for generating Nanyan numerals. Previously, the only way I new to generate them was to factor the number and recursively figure out the Nanyan numeral for each prime factor and then combine them from lowest to highest. Or you can just find the lowest factor of a number and then combine that with the numeral for the number divided by that lowest factor. Either way, there was no avoiding a recursive algorithm.

But now, there’s a new way to generate Nanyan numerals. It’s not technically recursive (in one sense, at least), though it does use a stack. Here’s now it works:

1. First off, we’ll need three things:
   1. factor_stack – a stack to keep track of factors in descending order
   2. first_two – a boolean to keep track of whether or not this is the first two added for the latest sequence (starts off with value true)
   3. buffer – the buffer for the final constructed numeral
2. Now, find the lowest factor of the given number. Divide that number by that factor and hold onto that value. We’ll subtract it later.
3. Now, based on that factor, we’ll do one of two things:
   1. If the lowest factor is a 2:
      1. If first_two is true, add “O” to buffer and set first_two to false.
      2. Otherwise, add “X” to buffer
   2. Otherwise (lowest factor is not a 2):
      1. Set first_two to true
      2. If there is a factor on factor_stack and the factor on top is less than or equal to the lowest factor found in step 2, pop that factor off factor_stack and add “|” to buffer
      3. Lastly, push the lowest factor found in step 2 onto the factor_stack
4. Subtract the value held onto in step 2 (number / lowest factor) from the number. That result becomes the new number. If that value is greater than 1, loop back to 2.
5. After you’ve looped through until the number is 1, there may still be factors on the factor_stack. For each factor still on the stack, add “|” to the buffer.
6. The buffer should now contain the Nanyan numeral.

That’s all there is too it: just one loop to create the numeral, and you’re done.

Code

What follows is a description of a python script that can generate Nanyan numerals.

To start, we’ll need an algorithm for finding the lowest factor of a given number. There are many ways to do this, but I think I’ll do this simply:

First, well need to import math for later:

import math

Next, let’s define some starting primes in a list. These will be the primes we use for the lowest factor. We’ll exclude two because we’ll do a bitwise-and to determine if a number is divisible by 2.

primes = [3,5,7,11]

Now let’s define a function that will add to this list up to a certain number. It will use the smallestFactor function we’ll write in a minute to determine whether a given number is prime.

def primes_up_to(n):
    c = primes[-1]
    while c < n:
        c += 2
        f = smallestFactor(c)
        if c == f: primes.append(c)

Now for the important part: we’re going to use this prime generator in our smallestFactor function, which will in turn use primes_up_to to generate primes. But we’ll write it in such a way that we’ll never create an infinite recursion:

def smallestFactor(n):
    if n & 1 == 0: return 2
    sqrt_n = math.sqrt(n)
    if primes[-1] < sqrt_n:
        primes_up_to(sqrt_n)
    for p in primes:
        if p > sqrt_n: break
        if n % p == 0: return p
    return n

See? Since we only check for primes up the the square root of a number, when we generate new primes, we should already have all the necessary parts. Or if not, it will recursively call the functions until we get to the point where we have the primes we need, which we’ve already seeded with 3, 5, 7, and 11.

Now to take the algorithm above and turn it into code. It should look something like this:

def makeNumeral(n):
    if n == 1: return "|"
    current = n
    s = []
    factors = []
    firstTwo = True
    while current > 1:
        f = smallestFactor(current)
        current = current - (current // f)
        if f == 2:
            s.append('O' if firstTwo else 'X')
            firstTwo = False
        else:
            firstTwo = True
            while len(factors) > 0 and factors[-1] <= f:
                factors.pop()
                s.append('|')
            factors.append(f)

    s.extend(['|'] * len(factors))

    return "".join(s)

That should do it. If you examine it with the algorithm explained above, you’ll see it’s practically a one-for-one implementation.

• factors is the factor_stack
• firstTwo is first_two
• s is the buffer

Now all you need is a number to convert:

print(makeNumeral(5040))

That’s a good anti-prime number to test with. Run your code, and you should get

OXXXO|O|OX|OO||

There you have it! A simple way to generate Nanyan numerals. There are other methods, but this one is pretty succinct. Happy coding!

Here’s the whole thing, just for simplicity:

import math

primes = [3,5,7,11]

def primes_up_to(n):
    c = primes[-1]
    while c < n:
        c += 2
        f = smallestFactor(c)
        if c == f: primes.append(c)

def smallestFactor(n):
    if n & 1 == 0: return 2
    sqrt_n = math.sqrt(n)
    if primes[-1] < sqrt_n:
        primes_up_to(sqrt_n)
    for p in primes:
        if p > sqrt_n: break
        if n % p == 0: return p
    return n

def makeNumeral(n):
    if n == 1: return "|"
    current = n
    s = []
    factors = []
    firstTwo = True
    while current > 1:
        f = smallestFactor(current)
        current = current - (current // f)
        if f == 2:
            s.append('O' if firstTwo else 'X')
            firstTwo = False
        else:
            firstTwo = True
            while len(factors) > 0 and factors[-1] <= f:
                factors.pop()
                s.append('|')
            factors.append(f)

    s.extend(['|'] * len(factors))

    return "".join(s)

print(makeNumeral(5040))