Will Nicholes

Binary-encoded Prime Signatures

Prime signatures are a way of describing the prime factorization of a number. For example, the number 28's prime factorization is 2² × 7, which can be abstracted to p²q (where p and q are distinct primes) or p₀²p₁ (where p₀ and p₁ are distinct primes.)

The prime signature lists the exponents of the prime factors, sorted from smallest exponent to greatest. Using 28 as an example, its prime prime signature is {1,2}. All prime numbers have a prime signature of {1}, squares of primes have prime signatures of {2}, a number composed of two primes has a prime signature of {1,1}, etc.

Another way of expressing the prime factorization would be in to encode it as binary, where each binary digit represents an element of the prime factorization. In order to do this, we need to assign each binary "column" to an element (such as p, p², q, etc.).

Let's start with the number 1: it might seem as though its prime signature would be {0} or {}, meaning no primes at all; however, by definition, the prime signature of 1 is {1}. The prime signatures of 2 and 3 are also {1} since each is a prime; 4 has a prime signature of {2}, since it's a square of a prime.

We can therefore assign the rightmost binary column to p, where p represents a unique prime, and the second (from the right) binary column to p², which represents the square of the prime. Let's take a look:

The next new prime signature we encounter is {1,1} for 6. 6's prime factorization is of the form pq, so we need a column for q as well:

Continuing on, we see 7 (prime signature of {1}) then 8 (prime signature of {3}). We don't need a new column for p³, though: since we already have p² and p, we can just put a "1" in each of those columns to indicate a p³.

In fact, the only new columns we'll ever need to add are of the form p_x²ⁿ, where p_x is a unique prime (p, q, etc.) and n is a non-negative integer. So now that we know all the columns we'll ever need to add, the question becomes: in what order shall we add them?

Skipping through the numbers whose prime signatures we've already seen, we find that the next columns we'll need are p⁴ for 16, then r for 30, then q² for 36.

The following table lists the first 48 binary columns needed, the number whose prime signature required the column be added, and its prime signature. For brevity, long prime signatures such as {1,1,1,1,1,1} are shown as 6{1}, meaning the prime signature consists of 6 ones.

With the exception of 1, all of the numbers in the above table happen to take the form m²ⁿ, where m is a primorial number (Wikipedia has an overview of primorials here), and n is a non-negative integer.

In the table below are the smallest integers that represent the first 53 unique prime signatures. Their prime signature is converted into a binary encoding, then the binary is converted to decimal. Thus each unique prime signature can be represented as a single integer.

From this we can see that each integer can be converted into another integer which represents its prime signature: 2 gives us 1, 6 gives us 5, etc. Here is a table of the first 30 integers converted in this manner:

*The number 1 is a special case; if we consider its prime signature to be {0} or {} (which would be consistent with the fact that it has no true prime factors), its binary-encoded prime signature would be 0; if we go by the definition of its prime signature as {1}, then its binary-encoded prime signature would be 1. To be consistent with the fact that all the other binary "columns" are created from numbers of the form m²ⁿ (where m is a primorial and n is a non-negative integer), for the purposes of binary encoding and decoding we will consider the prime signature of 1 to be {} and its binary-encoded prime signature representation to be 0.

Although we can convert any integer into another integer which represents its binary-encoded prime signature, we can't always perform the reverse operation. Some codes are invalid because they represent a "denormalized" prime signature. For example, decimal 4 (binary 100) corresponds to a prime signature of q. Since there is a q but no p in this representation, it would never be the result of a "forward" conversion. One could represent the result of an invalid reverse operation as a zero, however, since no valid prime signature would convert to 0 upon decoding.

Below is a table of the first few integers, and the numbers whose prime signatures they represent. The rightmost column shows the smallest number represented by the encoded prime signature, or 0 if the prime signature encoded is not valid.

Repeatedly "encoding" or "decoding" a number gives us some interesting results. Since zero does not have a valid prime signature, further "encode"s cannot be performed once a zero appears. Since a 0 is the result when a 1 is encoded, and a 1 is a result when a prime number is encoded, most small integers quickly hit a "dead-end":

More investigation is needed to see if any numbers don't hit this dead-end (for example, if they enter a repeating loop.)

The following table shows what happens when we repeatedly "decode" a number. Here we assume that decoding a number gives us the smallest number whose prime signature matches what's encoded, or zero if the encoding is invalid as explained above.

Here, upon repeated "decoding", an invalid prime signature is quickly found, and the sequence enters a loop: 0, 1, 2, 4, 0, 1, 2, 4, 0... More investigation is needed here also to determine whether there are other loops that might appear, or perhaps even an endless, non-looping sequence. The latter seems unlikely, since the likelihood that a number will be an invalid prime signature representative increases the larger it is.