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.)

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 p₁, p₁², p₂, 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 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:

Table 1

Number	Prime factorization		Prime signature	p12	p1
1	1	p10	{}	0	0
2	2	p1	{1}	0	1
3	3	p1	{1}	0	1
4	2 × 2	p12	{2}	1	0
5	5	p1	{1}	0	1

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

Table 2

Number	Prime factorization		Prime signature	p2	p12	p1
6	2 × 3	p1p2	{1,1}	1	0	1
7	7	p1	{1}	0	0	1

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₁³.

Table 3

Number	Prime factorization		Prime signature	p2	p12	p1
8	2 × 2 × 2	p13	{3}	0	1	1

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 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 p₃ for 30, then p₂² for 36.

Table 4

Num- ber	Prime factorization		Prime signature	p22	p3	p14	p2	p12	p1
16	2 × 2 × 2 × 2	p14	{4}	0	0	1	0	0	0
30	2 × 3 × 5	p3p2p1	{1,1,1}	0	1	0	1	0	1
36	2 × 2 × 3 × 3	p22p12	{2,2}	1	0	0	0	1	0

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

Column		Smallest pxn	Smallest number requiring the column	Number’s prime signature
1	p1	2	2	{1}
2	p12	22	4	{2}
3	p2	3	6	{1,1}
4	p14	24	16	{4}
5	p3	5	30	{1,1,1}
6	p22	32	36	{2,2}
7	p4	7	210	{1,1,1,1}
8	p18	28	256	{8}
9	p32	52	900	{2,2,2}
10	p24	34	1,296	{4,4}
11	p5	11	2,310	{1,1,1,1,1}
12	p6	13	30,030	6{1}
13	p42	72	44,100	{2,2,2,2}
14	p116	216	65,536	{16}
15	p7	17	510,510	7{1}
16	p34	54	810,000	{4,4,4}
17	p28	38	1,679,616	{8,8}
18	p52	112	5,336,100	{2,2,2,2,2}
19	p8	19	9,699,690	8{1}
20	p9	23	223,092,870	9{1}
21	p62	132	901,800,900	6{2}
22	p44	74	1,944,810,000	{4,4,4,4}
23	p132	232	4,294,967,296	{32}
24	p10	29	6,469,693,230	10{1}
25	p11	31	200,560,490,130	11{1}
26	p72	172	260,620,460,100	7{2}
27	p38	58	656,100,000,000	{8,8,8}
28	p216	316	2,821,109,907,456	{16,16}
29	p12	37	7,420,738,134,810	12{1}
30	p54	114	28,473,963,210,000	{4,4,4,4,4}
31	p82	192	94,083,986,096,100	8{2}
32	p13	41	~3.04250264 × 1014	13{1}
33	p14	43	~1.30827613 × 1016	14{1}
34	p92	232	~4.97704286 × 1016	9{2}
35	p15	47	~6.14889783 × 1017	15{1}
36	p64	134	~8.13244863 × 1017	6{4}
37	p48	78	~3.78228594 × 1018	{8,8,8,8}
38	p164	264	~1.84467441 × 1019	{64}
39	p16	53	~3.25891585 × 1019	16{1}
40	p102	292	~4.18569305 × 1019	10{2}
41	p17	59	~1.92276035 × 1021	17{1}
42	p112	312	~4.02245102 × 1022	11{2}
43	p74	174	~6.79230242 × 1022	7{4}
44	p18	61	~1.17288381 × 1023	18{1}
45	p316	516	~4.30467210 × 1023	{16,16,16}
46	p19	67	~7.85832155 × 1024	19{1}
47	p232	332	~7.95866111 × 1024	{32,32}
48	p20	71	~5.50673545 × 1025	20{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.

Table 6

Number	Prime factorization	Prime signature	Binary	Decimal
2	p1	{1}	00000000001	1
4	p12	{2}	00000000010	2
6	p1p2	{1,1}	00000000101	5
8	p13	{3}	00000000011	3
12	p12p2	{1,2}	00000000110	6
16	p14	{4}	00000001000	8
24	p13p2	{1,3}	00000000111	7
30	p1p2p3	{1,1,1}	00000010101	21
32	p15	{5}	00000001001	9
36	p12p22	{2,2}	00000100010	34
48	p14p2	{1,4}	00000001100	12
60	p12p2p3	{1,1,2}	00000010110	22
64	p16	{6}	00000001010	10
72	p13p22	{2,3}	00000100011	35
96	p15p2	{1,5}	00000001101	13
120	p13p2p3	{1,1,3}	00000010111	23
128	p17	{7}	00000001011	11
144	p14p22	{2,4}	00000101000	40
180	p12p22p3	{1,2,2}	00000110010	50
192	p16p2	{1,6}	00000001110	14
210	p1p2p3p4	{1,1,1,1}	00001010101	85
216	p13p23	{3,3}	00000100111	39
240	p14p2p3	{1,1,4}	00000011100	28
256	p18	{8}	00010000000	128
288	p15p22	{2,5}	00000101001	41
360	p13p22p3	{1,2,3}	00000110011	51
384	p17p2	{1,7}	00000001111	15
420	p12p2p3p4	{1,1,1,2}	00001010110	86
432	p14p23	{3,4}	00000101100	44
480	p15p2p3	{1,1,5}	00000011101	29
512	p19	{9}	00010000001	129
576	p16p22	{2,6}	00000101010	42
720	p14p22p3	{1,2,4}	00000111000	56
768	p18p2	{1,8}	00010000100	132
840	p13p2p3p4	{1,1,1,3}	00001010111	87
864	p15p23	{3,5}	00000101101	45
900	p12p22p32	{2,2,2}	00100100010	290
960	p16p2p3	{1,1,6}	00000011110	30
1024	p110	{10}	00010000010	130
1080	p13p23p3	{1,3,3}	00000110111	55
1152	p17p22	{2,7}	00000101011	43
1260	p12p22p3p4	{1,1,2,2}	00001110010	114
1296	p14p24	{4,4}	01000001000	520
1440	p15p22p3	{1,2,5}	00000111001	57
1536	p19p2	{1,9}	00010000101	133
1680	p14p2p3p4	{1,1,1,4}	00001011100	92
1728	p16p23	{3,6}	00000101110	46
1800	p13p22p32	{2,2,3}	00100100011	291
1920	p17p2p3	{1,1,7}	00000011111	31
2048	p111	{11}	00010000011	131
2160	p14p23p3	{1,3,4}	00000111100	60
2304	p18p22	{2,8}	00010100000	160
2310	p1p2p3p4p5	{1,1,1,1,1}	10001010101	1109

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

Number	Encoded
1	0
2	1
3	1
4	2
5	1
6	5
7	1
8	3
9	2
10	5
11	1
12	6
13	1
14	5
15	5
16	8
17	1
18	6
19	1
20	6
21	5
22	5
23	1
24	7
25	2
26	5
27	3
28	6
29	1
30	21

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 p₂. Since there is a p₂ 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.

Table 8

Number	Decoded
0	1	1
1	2, 3, 5, 7…	2
2	4, 9, 25, 49…	4
3	8, 27, 125…	8
4	Invalid: p2, but no p1	0
5	6, 10, 14, 15…	6
6	12, 18, 20, 28…	12
7	24, 40, 54, 56…	24
8	16, 81…	16
9	32, 243…	32
10	64, 729…	64
11	128, 2187…	128
12	48, 80, 112…	48
13	96, 486…	96
14	192, 1458…	192
15	384, 4374…	384
16-20	Invalid: p3, but no p2	0
21	30, 42, 70…	30
22	60, 84, 90…	60
23	120, 270…	120
24-27	Invalid: p3, but no p2	0
28	240, 810…	240
29	480, 2430…	480
30	960, 7290…	960
31	1920, 21870…	1920
32-33	Invalid: p22, but no p12	0
34	36, 100…	36
35	72, 108…	72
36-38	Invalid: p23, but no p13	0
39	216, 1000…	216
40	144, 324…	144

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

Starting number	Resulting “encode” sequence
1	1, 0
2	2, 1, 0
3	3, 1, 0
4	4, 2, 1, 0
6	6, 5, 1, 0
7	7, 1, 0
8	8, 3, 1, 0
9	9, 2, 1, 0
10	10, 5, 1, 0

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

Starting number	Resulting “decode” sequence
0	0, 1, 2, 4, 0…
3	3, 8, 16, 0…
5	5, 6, 12, 48, 0…
7	7, 24, 0…
9	9, 32, 0…
10	10, 64, 0…
11	11, 128, 256, 0…
13	13, 96, 0…
14	14, 192, 0…
15	15, 384, 0…

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 p₁, p₁² and p₂ as the first three columns, we can use p₁, p₁² and p₁p₂.

Similarly, instead of p₃ as the fifth column, we can use p₁p₂p₃. This will ensure that there are no columns that contain p_n as an element that do not also contain p_n-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

Number	Prime factorization	Prime signature	Binary	Decimal
2	p1	{1}	00000000001	1
4	p12	{2}	00000000010	2
6	p1p2	{1,1}	00000000100	4
8	p13	{3}	00000000011	3
12	p12p2	{1,2}	00000000101	5
16	p14	{4}	00000001000	8
24	p13p2	{1,3}	00000000110	6
30	p1p2p3	{1,1,1}	00000010000	16
32	p15	{5}	00000001001	9
36	p12p22	{2,2}	00000100000	32
48	p14p2	{1,4}	00000000111	7
60	p12p2p3	{1,1,2}	00000010001	17
64	p16	{6}	00000001010	10
72	p13p22	{2,3}	00000100001	33
96	p15p2	{1,5}	00000001100	12
120	p13p2p3	{1,1,3}	00000010010	18
128	p17	{7}	00000001011	11
144	p14p22	{2,4}	00000100010	34
180	p12p22p3	{1,2,2}	00000010100	20
192	p16p2	{1,6}	00000001101	13
210	p1p2p3p4	{1,1,1,1}	00001000000	64
216	p13p23	{3,3}	00000100100	36
240	p14p2p3	{1,1,4}	00000010011	19
256	p18	{8}	00010000000	128
288	p15p22	{2,5}	00000100011	35
360	p13p22p3	{1,2,3}	00000010101	21
384	p17p2	{1,7}	00000001110	14
420	p12p2p3p4	{1,1,1,2}	00001000001	65
432	p14p23	{3,4}	00000100101	37
480	p15p2p3	{1,1,5}	00000011000	24
512	p19	{9}	00010000001	129
576	p16p22	{2,6}	00000101000	40
720	p14p22p3	{1,2,4}	00000010110	22
768	p18p2	{1,8}	00000001111	15
840	p13p2p3p4	{1,1,1,3}	00001000010	66
864	p15p23	{3,5}	00000100110	38
900	p12p22p32	{2,2,2}	00100000000	256
960	p16p2p3	{1,1,6}	00000011001	25
1024	p110	{10}	00010000010	130
1080	p13p23p3	{1,3,3}	00000110000	48
1152	p17p22	{2,7}	00000101001	41
1260	p12p22p3p4	{1,1,2,2}	00001000100	68
1296	p14p24	{4,4}	01000000000	512
1440	p15p22p3	{1,2,5}	00000010111	23
1536	p19p2	{1,9}	00010000100	132
1680	p14p2p3p4	{1,1,1,4}	00001000011	67
1728	p16p23	{3,6}	00000100111	39
1800	p13p22p32	{2,2,3}	00100000001	257
1920	p17p2p3	{1,1,7}	00000011010	26
2048	p111	{11}	00010000011	131
2160	p14p23p3	{1,3,4}	00000110001	49
2304	p18p22	{2,8}	00000101010	42
2310	p1p2p3p4p5	{1,1,1,1,1}	10000000000	1024
2520	p13p22p3p4	{1,1,2,3}	00001000101	69
2592	p15p24	{4,5}	01000000001	513
2880	p16p22p3	{1,2,6}	00000011100	28

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

Table 12

Number	Encoded
1	0
2	1
3	1
4	2
5	1
6	4
7	1
8	3
9	2
10	4
11	1
12	5
13	1
14	4
15	4
16	8
17	1
18	5
19	1
20	5
21	4
22	4
23	1
24	6
25	2
26	4
27	3
28	5
29	1
30	16

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

Encoded	Prime Signature	Decoded
0	{}	1
1	{1}	2, 3, 5, 7, 11…
2	{2}	4, 9, 25, 49, 121…
3	{3}	8, 27, 125, 343…
4	{1,1}	6, 10, 14, 15…
5	{1,2}	12, 18, 20, 28…
6	{1,3}	24, 40, 54, 56…
7	{1,4}	48, 80, 112, 162…
8	{4}	16, 81, 625…
9	{5}	32, 243…
10	{6}	64, 729…
11	{7}	128, 2187…
12	{1,5}	96, 160, 224…
13	{1,6}	192, 320, 448…
14	{1,7}	384, 640, 896…
15	{1,8}	768, 1280, 1792…
16	{1,1,1}	30, 42, 70…
17	{1,1,2}	60, 84, 90…
18	{1,1,3}	120, 168, 264…
19	{1,1,4}	240, 336, 528…
20	{1,2,2}	180, 252, 300…
21	{1,2,3}	360, 504, 792…
22	{1,2,4}	720, 1008…
23	{1,2,5}	1440, 2016…
24	{1,1,5}	480, 672…
25	{1,1,6}	960, 1344…
26	{1,1,7}	1920, 2688…
27	{1,1,8}	3840, 5376…
28	{1,2,6}	2880, 4032…
29	{1,2,7}	5760, 8064…
30	{1,2,8}	11520, 16128…
31	{1,2,9}	23040, 32256…
32	{2,2}	36, 100, 196, 225…
33	{2,3}	72, 200, 392…
34	{2,4}	144, 400, 784…
35	{2,5}	288, 800, 1568…
36	{3,3}	216, 1000…
37	{3,4}	432, 2000…
38	{3,5}	864, 4000…
39	{3,6}	1728, 8000…
40	{2,6}	576, 1600…

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

Starting number	Resulting “encode” sequence
1	1, 0
2	2, 1, 0
3	3, 1, 0
4	4, 2, 1, 0
5	5, 1, 0
6	6, 4, 2, 1, 0
7	7, 1, 0
8	8, 3, 1, 0
9	9, 2, 1, 0
10	10, 4, 2, 1, 0
11	11, 1, 0
12	12, 5, 1, 0

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

Starting number	Resulting “decode” sequence
0	0, 1, 2, 4, 6, 24, 480, 17418240001, …
3	3, 8, 16, 30, 11520, …
5	5, 12, 96, 7560, …
7	7, 48, 1080, 39916800, …
9	9, 32, 36, 216, 25804800, …
10	10, 64, 210, 6451200, …
11	11, 128, 256, 900, 1791590400, …
13	13, 192, 53760, …

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