.

# Binary-encoded prime signatures

Written in

by

Prime signatures are a way of describing the prime factorization of a number. For example, the number 28’s prime factorization is 22 × 7, which can be abstracted to p2q (where p and q are distinct primes) or p12p2 (where p1 and p2 are distinct primes.)

### Encoding in binary

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 p1p12p2, etc.).

Let’s start with the number 1. For our purposes, the prime signature of 1 is {}, since it contains no prime factors. The prime signatures of 2 and 3 are {1}, indicating the presence of exactly one prime factor. 4 has a prime signature of {2}, since it’s a square of a prime.

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

### Table 1

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

### Table 2

Continuing on, we see 7 (prime signature of {1}) then 8 (prime signature of {3}). We don’t need a new column for p13, though: since we already have p12 and p1, we can just put a “1” in each of those columns to indicate a p13.

### Table 3

In fact, the only new columns we’ll ever need to add are of the form px2n, where px is a unique prime 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 p14 for 16, then p3 for 30, then p22 for 36.

### Table 4

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.

### Table 5

All of the numbers in the above table happen to take the form m2n, 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.

### Table 6

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:

### Table 7

Although we can convert any positive 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 p2. Since there is a p2 but no p1 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.

### Table 8

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”:

### Table 9

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.

### Table 10

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.

### An alternate approach

To resolve the problem with denormalized prime signatures, a different approach is needed. Rather than using p1p12 and p2 as the first three columns, we can use p1p12 and p1p2.

Similarly, instead of p3 as the fifth column, we can use p1p2p3. This will ensure that there are no columns that contain pn as an element that do not also contain pn-1 (where n is greater than 1).

The following table uses this scheme, producing a different binary and decimal output from the similar table above (Table 6):

### Table 11

As above in Table 7 we can convert each integer into another which represents its prime signature:

### Table 12

Using this scheme we can convert any integer greater than 1 into a unique integer which represents its binary-encoded prime signature. We can also perform the operation in reverse for any integer greater than zero. To ensure the reverse operation returns a unique integer, we use the smallest such integer matching the specified prime signature. For example, 4 (decimal) is equal to 100 (binary), which represents the prime signature of {1,1}. The lowest integer that matches that prime signature is 2 × 3, i.e. 6.

Below is a table of the first few integers using the new scheme, and the numbers whose prime signatures they represent. The bolded number represents the smallest number represented by the encoded prime signature.

### Table 13

As before, we can repeatedly “encode” a number by first determining its prime signature, then determining the integer that uniquely refers to that prime signature. For example, we can encode the number 18 by first determining that its prime signature is {1,2} and then determining that the unique integer that maps to the prime signature {1,2} is 5 (see Table 13.) We can then repeat the process for the number 5, whose prime signature is {1}, which is encoded as the number 1. Repeating once more, the number 1 becomes the prime signature {}, which becomes 0, the unique integer that maps to the “empty” prime signature of {}.

Thus, starting with 18 we get the sequence 18, 5, 1, 0. Once we reach zero, no further encoding can be done. The following table shows some examples of the “encode” sequences that can be found with certain starting integers:

### Table 14

Note that all sequences that begin with a prime number have three elements: the starting number, 1, then 0. Longer sequences are possible with starting numbers with prime signatures other than {1}. It appears that all sequences (except the one-element series starting with 0) will end with a 1 followed by a 0.

Similarly, it is possible to generate a sequences by repeatedly “decoding” a number. Here, we start with an integer, for example 4. From Table 13 we can determine that that integer maps to prime signature {1,1}, and the smallest number that matches that prime signature is 6 (2 × 3). We can then repeat the process: 6 maps to prime signature {1,3} (again, referring to Table 13), and the smallest number which maps to that signature is 24. Repeating the process we can see that the sequences starting with 4 begins 4, 6, 24, 480…

Unlike the “encode” sequences, which all end with 0, the “decode” sequences appears to climb ever higher. The following table includes some examples of “decode” sequences:

### Table 15

For more sequences related to prime signatures, see the iterative mapping of prime signatures page.

Tags