W

 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 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 p1, p12, p2, 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

NumberPrime factorizationPrime signaturep12p1
11p10{}00
22p1{1}01
33p1{1}01
42 × 2p12{2}10
55p1{1}01

 

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

NumberPrime factorizationPrime signaturep2 p12p1
62 × 3p1p2{1,1}101
77p1{1}001

 

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

NumberPrime factorizationPrime signaturep2 p12p1
82 × 2 × 2p13{3}011

 

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

Num-
ber
Prime factorizationPrime signature p22p3 p14p2 p12p1
162 × 2 × 2 × 2p14{4}001000
302 × 3 × 5p3p2p1{1,1,1}010101
362 × 2 × 3 × 3p22p12{2,2}100010

 

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

ColumnSmallest pxnSmallest number requiring the columnNumber’s prime signature
1p122{1}
2p12224{2}
3p236{1,1}
4p142416{4}
5p3530{1,1,1}
6p223236{2,2}
7p47210{1,1,1,1}
8p1828256{8}
9p3252900{2,2,2}
10p24341,296{4,4}
11p5112,310{1,1,1,1,1}
12p61330,0306{1}
13p427244,100{2,2,2,2}
14p11621665,536{16}
15p717510,5107{1}
16p3454810,000{4,4,4}
17p28381,679,616{8,8}
18p521125,336,100{2,2,2,2,2}
19p8199,699,6908{1}
20p923223,092,8709{1}
21p62132901,800,9006{2}
22p44741,944,810,000{4,4,4,4}
23p1322324,294,967,296{32}
24p10296,469,693,23010{1}
25p1131200,560,490,13011{1}
26p72172260,620,460,1007{2}
27p3858656,100,000,000{8,8,8}
28p2163162,821,109,907,456{16,16}
29p12377,420,738,134,81012{1}
30p5411428,473,963,210,000{4,4,4,4,4}
31p8219294,083,986,096,1008{2}
32p1341~3.04250264 × 101413{1}
33p1443~1.30827613 × 101614{1}
34p92232~4.97704286 × 10169{2}
35p1547~6.14889783 × 101715{1}
36p64134~8.13244863 × 10176{4}
37p4878~3.78228594 × 1018{8,8,8,8}
38p164264~1.84467441 × 1019{64}
39p1653~3.25891585 × 101916{1}
40p102292~4.18569305 × 101910{2}
41p1759~1.92276035 × 102117{1}
42p112312~4.02245102 × 102211{2}
43p74174~6.79230242 × 10227{4}
44p1861~1.17288381 × 102318{1}
45p316516~4.30467210 × 1023{16,16,16}
46p1967~7.85832155 × 102419{1}
47p232332~7.95866111 × 1024{32,32}
48p2071~5.50673545 × 102520{1}

 

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

NumberPrime factorizationPrime signatureBinary Decimal
2p1{1}000000000011
4p12{2}000000000102
6p1p2{1,1}000000001015
8p13{3}000000000113
12p12p2{1,2}000000001106
16p14{4}000000010008
24p13p2{1,3}000000001117
30p1p2p3{1,1,1}0000001010121
32p15{5}000000010019
36p12p22{2,2}0000010001034
48p14p2{1,4}0000000110012
60p12p2p3{1,1,2}0000001011022
64p16{6}0000000101010
72p13p22{2,3}0000010001135
96p15p2{1,5}0000000110113
120p13p2p3{1,1,3}0000001011123
128p17{7}0000000101111
144p14p22{2,4}0000010100040
180p12p22p3{1,2,2}0000011001050
192p16p2{1,6}0000000111014
210p1p2p3p4{1,1,1,1}0000101010185
216p13p23{3,3}0000010011139
240p14p2p3{1,1,4}0000001110028
256p18{8}00010000000128
288p15p22{2,5}0000010100141
360p13p22p3{1,2,3}0000011001151
384p17p2{1,7}0000000111115
420p12p2p3p4{1,1,1,2}0000101011086
432p14p23{3,4}0000010110044
480p15p2p3{1,1,5}0000001110129
512p19{9}00010000001129
576p16p22{2,6}0000010101042
720p14p22p3{1,2,4}0000011100056
768p18p2{1,8}00010000100132
840p13p2p3p4{1,1,1,3}0000101011187
864p15p23{3,5}0000010110145
900p12p22p32{2,2,2}00100100010290
960p16p2p3{1,1,6}0000001111030
1024p110{10}00010000010130
1080p13p23p3{1,3,3}0000011011155
1152p17p22{2,7}0000010101143
1260p12p22p3p4{1,1,2,2}00001110010114
1296p14p24{4,4}01000001000520
1440p15p22p3{1,2,5}0000011100157
1536p19p2{1,9}00010000101133
1680p14p2p3p4{1,1,1,4}0000101110092
1728p16p23{3,6}0000010111046
1800p13p22p32{2,2,3}00100100011291
1920p17p2p3{1,1,7}0000001111131
2048p111{11}00010000011131
2160p14p23p3{1,3,4}0000011110060
2304p18p22{2,8}00010100000160
2310p1p2p3p4p5{1,1,1,1,1}100010101011109

 

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

NumberEncoded
10
21
31
42
51
65
71
83
92
105
111
126
131
145
155
   
NumberEncoded
168
171
186
191
206
215
225
231
247
252
265
273
286
291
3021

 

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

NumberDecoded
011
12, 3, 5, 7...2
24, 9, 25, 49...4
38, 27, 125...8
4Invalid: p2, but no p10
56, 10, 14, 15...6
612, 18, 20, 28...12
724, 40, 54, 56...24
816, 81...16
932, 243...32
1064, 729...64
11128, 2187...128
1248, 80, 112...48
1396, 486...96
14192, 1458...192
15384, 4374...384
16-20Invalid: p3, but no p20
2130, 42, 70...30
2260, 84, 90...60
23120, 270...120
24-27Invalid: p3, but no p20
28240, 810...240
29480, 2430...480
30960, 7290...960
311920, 21870...1920
32-33Invalid: p22, but no p120
3436, 100...36
3572, 108...72
36-38Invalid: p23, but no p130
39216, 1000...216
40144, 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 numberResulting “encode” sequence
11, 0
22, 1, 0
33, 1, 0
44, 2, 1, 0
66, 5, 1, 0
77, 1, 0
88, 3, 1, 0
99, 2, 1, 0
1010, 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 numberResulting “decode” sequence
00, 1, 2, 4, 0...
33, 8, 16, 0...
55, 6, 12, 48, 0...
77, 24, 0...
99, 32, 0...
1010, 64, 0...
1111, 128, 256, 0...
1313, 96, 0...
1414, 192, 0...
1515, 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 p1, p12 and p2 as the first three columns, we can use p1, p12 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

NumberPrime factorizationPrime signatureBinary Decimal
2p1{1}000000000011
4p12{2}000000000102
6p1p2{1,1}000000001004
8p13{3}000000000113
12p12p2{1,2}000000001015
16p14{4}000000010008
24p13p2{1,3}000000001106
30p1p2p3{1,1,1}0000001000016
32p15{5}000000010019
36p12p22{2,2}0000010000032
48p14p2{1,4}000000001117
60p12p2p3{1,1,2}0000001000117
64p16{6}0000000101010
72p13p22{2,3}0000010000133
96p15p2{1,5}0000000110012
120p13p2p3{1,1,3}0000001001018
128p17{7}0000000101111
144p14p22{2,4}0000010001034
180p12p22p3{1,2,2}0000001010020
192p16p2{1,6}0000000110113
210p1p2p3p4{1,1,1,1}0000100000064
216p13p23{3,3}0000010010036
240p14p2p3{1,1,4}0000001001119
256p18{8}00010000000128
288p15p22{2,5}0000010001135
360p13p22p3{1,2,3}0000001010121
384p17p2{1,7}0000000111014
420p12p2p3p4{1,1,1,2}0000100000165
432p14p23{3,4}0000010010137
480p15p2p3{1,1,5}0000001100024
512p19{9}00010000001129
576p16p22{2,6}0000010100040
720p14p22p3{1,2,4}0000001011022
768p18p2{1,8}0000000111115
840p13p2p3p4{1,1,1,3}0000100001066
864p15p23{3,5}0000010011038
900p12p22p32{2,2,2}00100000000256
960p16p2p3{1,1,6}0000001100125
1024p110{10}00010000010130
1080p13p23p3{1,3,3}0000011000048
1152p17p22{2,7}0000010100141
1260p12p22p3p4{1,1,2,2}0000100010068
1296p14p24{4,4}01000000000512
1440p15p22p3{1,2,5}0000001011123
1536p19p2{1,9}00010000100132
1680p14p2p3p4{1,1,1,4}0000100001167
1728p16p23{3,6}0000010011139
1800p13p22p32{2,2,3}00100000001257
1920p17p2p3{1,1,7}0000001101026
2048p111{11}00010000011131
2160p14p23p3{1,3,4}0000011000149
2304p18p22{2,8}0000010101042
2310p1p2p3p4p5{1,1,1,1,1}100000000001024
2520p13p22p3p4{1,1,2,3}0000100010169
2592p15p24{4,5}01000000001513
2880p16p22p3{1,2,6}0000001110028

 

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

Table 12

NumberEncoded
10
21
31
42
51
64
71
83
92
104
111
125
131
144
154
   
NumberEncoded
168
171
185
191
205
214
224
231
246
252
264
273
285
291
3016

 

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

EncodedPrime SignatureDecoded
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 numberResulting “encode” sequence
11, 0
22, 1, 0
33, 1, 0
44, 2, 1, 0
55, 1, 0
66, 4, 2, 1, 0
77, 1, 0
88, 3, 1, 0
99, 2, 1, 0
1010, 4, 2, 1, 0
1111, 1, 0
1212, 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 numberResulting “decode” sequence
00, 1, 2, 4, 6, 24, 480, 17418240001, ...
33, 8, 16, 30, 11520, ...
55, 12, 96, 7560, ...
77, 48, 1080, 39916800, ...
99, 32, 36, 216, 25804800, ...
1010, 64, 210, 6451200, ...
1111, 128, 256, 900, 1791590400, ...
1313, 192, 53760, ...

 

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

 

Validate this page