My First OEIS Entry: A267263

I submitted the sequence A267263 to the Online Encyclopedia of Integer Sequences (OEIS).

It’s defined as the ‘number of nonzero digits in representation of n in primorial base’.

But… what does that mean? Let’s break it down:

Primorial

The product of the first $k$ prime numbers: $2 \times 3 \times 5 \times \cdots \times p_k$.

Defined in the OEIS as sequence A002110.

Primorial number system

A mixed radix representation using the primes as the place values, instead of the usual base-10.

For example, thirteen is: $13_{10} = 201_\# = 2 \times (3\#) + 0 \times (2\#) + 1 = \brack{\mat{2&0&1}} \cdot \brack{\mat{6&2&1}}$.

So, this is basically another way of writing numbers down, or representing them and assigning them to ‘strings’ of digits. The way we usually do is with base-10, also called decimal. Since successive place values in base-10 is multiplied by $10$, thus the value of $1\underbrace{0 \cdots 0}_\text{k zeros}$ is $10^k$ in decimal.

However, in the primorial number system, the place values are the products of the first $k$ prime numbers. So, the value of $1\underbrace{0 \cdots 0}_\text{k zeros}$ is $2 \times 3 \times 5 \times \cdots \times p_k$ in primorial.

In effect, this sequence describes how many ‘imperfect matches’ a number has when reducing modulo subsequent primes. It is analogous to the Hamming weight of a binary number, but in a different base.

No, Really, What Does It Mean?

Well, it’s sort of a curiosity. It came up when I was studying algorithms for searching for prime generating polynomials. In the same way that the computational complexity of modular exponentiation is determined by the Hamming weight of the exponent, the A267263 sequence appears in the computational complexity of algorithms based on recursive wheel factorization.

I realize that this just introduced more questions than it answered. I plan on writing more about these topics, but for now, I just wanted to share this interesting sequence. For now, I’ll leave you with a table of the first few values of the sequence, and a way to generate these values in Python.

Calculating the Sequence

Here’s a table of the first few values of the sequence, along with their primorial string representation:

Hence, the sequence A267263 is defined as the number of bolded digits in the primorial string representation of $n$.

To generate the information in this blog, I use the following Python code:

11 collapsed lines
1
# A267263.py - exploration of an integer sequence: https://oeis.org/A267263
2
# NOTE: read a full post at: https://cade.io/a267263
3

4
# we use a lazy prime generator from SymPy
5
from sympy import sieve
6

7
# pandas is just used for conversion to a markdown table
8
import pandas
9

10
# digits used for string conversion
11
DIGITS = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
12

13
def A267263(n: int) -> int:
14
    ''' Number of nonzero digits in representation of n in primorial base. '''
15
    return sum(1 for n in primorial_residues(n) if n != 0)
16

17
def primorial_residues(num: int) -> list:
18
    ''' Calculates successive residues in the primorial radix system. '''
19
    res = []
20

21
    # at each step, maintain the current 'digit' and what's left
22
    div, mod = num, 0
23
    for prime in sieve:
24

25
        # quit once we have enough residues to represent the number
26
        if div == 0: break
27

28
        # otherwise, continue to extract the next residue
29
        div, mod = divmod(div, prime)
30
        res.append(mod)
31

32
    # and so, we will have place values for: [2#, 3#, 5#, ...]
33
    return res
34

8 collapsed lines
35
def primorial_string(num: int) -> str:
36
    ''' Converts a number to its primorial representation '''
37
    # NOTE: this won't work for very large numbers that exceed (37#)
38
    return ''.join(DIGITS[n] for n in primorial_residues(num)[::-1]) or '0'
39

40
def bold_nonzeros(s: str) -> str:
41
    ''' Bolds all non-zero digits in a string '''
42
    return '0'.join(f'**{ss}**' if ss else '' for ss in s.split('0'))
43

44
# generate a table of values and useful information to display
45
rows = [(n, A267263(n), bold_nonzeros(primorial_string(n))) for n in range(16)]
46
df = pandas.DataFrame(rows, columns=['$n$', '$A267263(n)$', 'Primorial String'])
47

5 collapsed lines
48
# transpose the dataframe, to change orientation
49
df = df.transpose()
50
df.columns = df.iloc[0]
51
df = df[1:]
52
df.index.name = '$n$'
53

54
# print the transposed table as markdown
55
print(df.to_markdown(index=True, stralign='right'))

This requires a few dependencies, which you can install with:

1
pip install sympy pandas tabulate