Prime signatures are a way of describing the prime factorization of a number. For example, the number 28’s prime factorization is 2^{2} × 7, which can be abstracted to *p*^{2}*q* (where *p* and *q* are distinct primes) or *p _{1}*

^{2}

*p*(where

_{2}*p*and

_{1}*p*are distinct primes.)

_{2}### 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 _{1}*,

*p*

_{1}^{2},

*p*, etc.).

_{2}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 _{1}*, where

*p*represents a unique prime, and the second (from the right) binary column to

_{1}*p*

_{1}^{2}, which represents the square of the prime. Let’s take a look:

### Table 1

Number | Prime factorization | Prime signature | p_{1}^{2} | p_{1} | |
---|---|---|---|---|---|

1 | 1 | p_{1}^{0} | {} | 0 | 0 |

2 | 2 | p_{1} | {1} | 0 | 1 |

3 | 3 | p_{1} | {1} | 0 | 1 |

4 | 2 × 2 | p_{1}^{2} | {2} | 1 | 0 |

5 | 5 | p_{1} | {1} | 0 | 1 |

The next new prime signature we encounter is {1,1} for 6. 6’s prime factorization is of the form *p _{1}*

*p*, so we need a column for

_{2}*p*as well:

_{2}### Table 2

Number | Prime factorization | Prime signature | p_{2} | p_{1}^{2} | p_{1} | |
---|---|---|---|---|---|---|

6 | 2 × 3 | p_{1}p_{2} | {1,1} | 1 | 0 | 1 |

7 | 7 | p_{1} | {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 _{1}*

^{3}, though: since we already have

*p*

_{1}^{2}and

*p*, we can just put a “1” in each of those columns to indicate a

_{1}*p*

_{1}^{3}.

### Table 3

Number | Prime factorization | Prime signature | p_{2} | p_{1}^{2} | p_{1} | |
---|---|---|---|---|---|---|

8 | 2 × 2 × 2 | p_{1}^{3} | {3} | 0 | 1 | 1 |

In fact, the only new columns we’ll ever need to add are of the form *p _{x}*

^{2n}, where

*p*is a unique prime and

_{x}*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 _{1}*

^{4}for 16, then

*p*for 30, then

_{3}*p*

_{2}^{2}for 36.

### Table 4

Num- ber | Prime factorization | Prime signature | p_{2}^{2} | p_{3} | p_{1}^{4} | p_{2} | p_{1}^{2} | p_{1} | |
---|---|---|---|---|---|---|---|---|---|

16 | 2 × 2 × 2 × 2 | p_{1}^{4} | {4} | 0 | 0 | 1 | 0 | 0 | 0 |

30 | 2 × 3 × 5 | p_{3}p_{2}p_{1} | {1,1,1} | 0 | 1 | 0 | 1 | 0 | 1 |

36 | 2 × 2 × 3 × 3 | p_{2}^{2}p_{1}^{2} | {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 p_{x}^{n} | Smallest number requiring the column | Number’s prime signature | |
---|---|---|---|---|

1 | p_{1} | 2 | 2 | {1} |

2 | p_{1}^{2} | 2^{2} | 4 | {2} |

3 | p_{2} | 3 | 6 | {1,1} |

4 | p_{1}^{4} | 2^{4} | 16 | {4} |

5 | p_{3} | 5 | 30 | {1,1,1} |

6 | p_{2}^{2} | 3^{2} | 36 | {2,2} |

7 | p_{4} | 7 | 210 | {1,1,1,1} |

8 | p_{1}^{8} | 2^{8} | 256 | {8} |

9 | p_{3}^{2} | 5^{2} | 900 | {2,2,2} |

10 | p_{2}^{4} | 3^{4} | 1,296 | {4,4} |

11 | p_{5} | 11 | 2,310 | {1,1,1,1,1} |

12 | p_{6} | 13 | 30,030 | 6{1} |

13 | p_{4}^{2} | 7^{2} | 44,100 | {2,2,2,2} |

14 | p_{1}^{16} | 2^{16} | 65,536 | {16} |

15 | p_{7} | 17 | 510,510 | 7{1} |

16 | p_{3}^{4} | 5^{4} | 810,000 | {4,4,4} |

17 | p_{2}^{8} | 3^{8} | 1,679,616 | {8,8} |

18 | p_{5}^{2} | 11^{2} | 5,336,100 | {2,2,2,2,2} |

19 | p_{8} | 19 | 9,699,690 | 8{1} |

20 | p_{9} | 23 | 223,092,870 | 9{1} |

21 | p_{6}^{2} | 13^{2} | 901,800,900 | 6{2} |

22 | p_{4}^{4} | 7^{4} | 1,944,810,000 | {4,4,4,4} |

23 | p_{1}^{32} | 2^{32} | 4,294,967,296 | {32} |

24 | p_{10} | 29 | 6,469,693,230 | 10{1} |

25 | p_{11} | 31 | 200,560,490,130 | 11{1} |

26 | p_{7}^{2} | 17^{2} | 260,620,460,100 | 7{2} |

27 | p_{3}^{8} | 5^{8} | 656,100,000,000 | {8,8,8} |

28 | p_{2}^{16} | 3^{16} | 2,821,109,907,456 | {16,16} |

29 | p_{12} | 37 | 7,420,738,134,810 | 12{1} |

30 | p_{5}^{4} | 11^{4} | 28,473,963,210,000 | {4,4,4,4,4} |

31 | p_{8}^{2} | 19^{2} | 94,083,986,096,100 | 8{2} |

32 | p_{13} | 41 | ~3.04250264 × 10^{14} | 13{1} |

33 | p_{14} | 43 | ~1.30827613 × 10^{16} | 14{1} |

34 | p_{9}^{2} | 23^{2} | ~4.97704286 × 10^{16} | 9{2} |

35 | p_{15} | 47 | ~6.14889783 × 10^{17} | 15{1} |

36 | p_{6}^{4} | 13^{4} | ~8.13244863 × 10^{17} | 6{4} |

37 | p_{4}^{8} | 7^{8} | ~3.78228594 × 10^{18} | {8,8,8,8} |

38 | p_{1}^{64} | 2^{64} | ~1.84467441 × 10^{19} | {64} |

39 | p_{16} | 53 | ~3.25891585 × 10^{19} | 16{1} |

40 | p_{10}^{2} | 29^{2} | ~4.18569305 × 10^{19} | 10{2} |

41 | p_{17} | 59 | ~1.92276035 × 10^{21} | 17{1} |

42 | p_{11}^{2} | 31^{2} | ~4.02245102 × 10^{22} | 11{2} |

43 | p_{7}^{4} | 17^{4} | ~6.79230242 × 10^{22} | 7{4} |

44 | p_{18} | 61 | ~1.17288381 × 10^{23} | 18{1} |

45 | p_{3}^{16} | 5^{16} | ~4.30467210 × 10^{23} | {16,16,16} |

46 | p_{19} | 67 | ~7.85832155 × 10^{24} | 19{1} |

47 | p_{2}^{32} | 3^{32} | ~7.95866111 × 10^{24} | {32,32} |

48 | p_{20} | 71 | ~5.50673545 × 10^{25} | 20{1} |

All of the numbers in the above table happen to take the form *m*^{2n}, 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 | p_{1} | {1} | 00000000001 | 1 |

4 | p_{1}^{2} | {2} | 00000000010 | 2 |

6 | p_{1}p_{2} | {1,1} | 00000000101 | 5 |

8 | p_{1}^{3} | {3} | 00000000011 | 3 |

12 | p_{1}^{2}p_{2} | {1,2} | 00000000110 | 6 |

16 | p_{1}^{4} | {4} | 00000001000 | 8 |

24 | p_{1}^{3}p_{2} | {1,3} | 00000000111 | 7 |

30 | p_{1}p_{2}p_{3} | {1,1,1} | 00000010101 | 21 |

32 | p_{1}^{5} | {5} | 00000001001 | 9 |

36 | p_{1}^{2}p_{2}^{2} | {2,2} | 00000100010 | 34 |

48 | p_{1}^{4}p_{2} | {1,4} | 00000001100 | 12 |

60 | p_{1}^{2}p_{2}p_{3} | {1,1,2} | 00000010110 | 22 |

64 | p_{1}^{6} | {6} | 00000001010 | 10 |

72 | p_{1}^{3}p_{2}^{2} | {2,3} | 00000100011 | 35 |

96 | p_{1}^{5}p_{2} | {1,5} | 00000001101 | 13 |

120 | p_{1}^{3}p_{2}p_{3} | {1,1,3} | 00000010111 | 23 |

128 | p_{1}^{7} | {7} | 00000001011 | 11 |

144 | p_{1}^{4}p_{2}^{2} | {2,4} | 00000101000 | 40 |

180 | p_{1}^{2}p_{2}^{2}p_{3} | {1,2,2} | 00000110010 | 50 |

192 | p_{1}^{6}p_{2} | {1,6} | 00000001110 | 14 |

210 | p_{1}p_{2}p_{3}p_{4} | {1,1,1,1} | 00001010101 | 85 |

216 | p_{1}^{3}p_{2}^{3} | {3,3} | 00000100111 | 39 |

240 | p_{1}^{4}p_{2}p_{3} | {1,1,4} | 00000011100 | 28 |

256 | p_{1}^{8} | {8} | 00010000000 | 128 |

288 | p_{1}^{5}p_{2}^{2} | {2,5} | 00000101001 | 41 |

360 | p_{1}^{3}p_{2}^{2}p_{3} | {1,2,3} | 00000110011 | 51 |

384 | p_{1}^{7}p_{2} | {1,7} | 00000001111 | 15 |

420 | p_{1}^{2}p_{2}p_{3}p_{4} | {1,1,1,2} | 00001010110 | 86 |

432 | p_{1}^{4}p_{2}^{3} | {3,4} | 00000101100 | 44 |

480 | p_{1}^{5}p_{2}p_{3} | {1,1,5} | 00000011101 | 29 |

512 | p_{1}^{9} | {9} | 00010000001 | 129 |

576 | p_{1}^{6}p_{2}^{2} | {2,6} | 00000101010 | 42 |

720 | p_{1}^{4}p_{2}^{2}p_{3} | {1,2,4} | 00000111000 | 56 |

768 | p_{1}^{8}p_{2} | {1,8} | 00010000100 | 132 |

840 | p_{1}^{3}p_{2}p_{3}p_{4} | {1,1,1,3} | 00001010111 | 87 |

864 | p_{1}^{5}p_{2}^{3} | {3,5} | 00000101101 | 45 |

900 | p_{1}^{2}p_{2}^{2}p_{3}^{2} | {2,2,2} | 00100100010 | 290 |

960 | p_{1}^{6}p_{2}p_{3} | {1,1,6} | 00000011110 | 30 |

1024 | p_{1}^{10} | {10} | 00010000010 | 130 |

1080 | p_{1}^{3}p_{2}^{3}p_{3} | {1,3,3} | 00000110111 | 55 |

1152 | p_{1}^{7}p_{2}^{2} | {2,7} | 00000101011 | 43 |

1260 | p_{1}^{2}p_{2}^{2}p_{3}p_{4} | {1,1,2,2} | 00001110010 | 114 |

1296 | p_{1}^{4}p_{2}^{4} | {4,4} | 01000001000 | 520 |

1440 | p_{1}^{5}p_{2}^{2}p_{3} | {1,2,5} | 00000111001 | 57 |

1536 | p_{1}^{9}p_{2} | {1,9} | 00010000101 | 133 |

1680 | p_{1}^{4}p_{2}p_{3}p_{4} | {1,1,1,4} | 00001011100 | 92 |

1728 | p_{1}^{6}p_{2}^{3} | {3,6} | 00000101110 | 46 |

1800 | p_{1}^{3}p_{2}^{2}p_{3}^{2} | {2,2,3} | 00100100011 | 291 |

1920 | p_{1}^{7}p_{2}p_{3} | {1,1,7} | 00000011111 | 31 |

2048 | p_{1}^{11} | {11} | 00010000011 | 131 |

2160 | p_{1}^{4}p_{2}^{3}p_{3} | {1,3,4} | 00000111100 | 60 |

2304 | p_{1}^{8}p_{2}^{2} | {2,8} | 00010100000 | 160 |

2310 | p_{1}p_{2}p_{3}p_{4}p_{5} | {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 _{2}*. Since there is a

*p*but no

_{2}*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.

_{1}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: p, but no _{2}p_{1} | 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: p, but no _{3}p_{2} | 0 |

21 | 30, 42, 70… | 30 |

22 | 60, 84, 90… | 60 |

23 | 120, 270… | 120 |

24-27 | Invalid: p, but no _{3}p_{2} | 0 |

28 | 240, 810… | 240 |

29 | 480, 2430… | 480 |

30 | 960, 7290… | 960 |

31 | 1920, 21870… | 1920 |

32-33 | Invalid: p_{2}^{2}, but no p_{1}^{2} | 0 |

34 | 36, 100… | 36 |

35 | 72, 108… | 72 |

36-38 | Invalid: p_{2}^{3}, but no p_{1}^{3} | 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 _{1}*,

*p*

_{1}^{2}and

*p*as the first three columns, we can use

_{2}*p*,

_{1}*p*

_{1}^{2}and

*p*_{1}*p*.

_{2}Similarly, instead of *p _{3}* as the fifth column, we can use

*p*

_{1}*p*

_{2}*p*. This will ensure that there are no columns that contain

_{3}*p*as an element that do not also contain

_{n}*p*(where n is greater than 1).

_{n-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 | p_{1} | {1} | 00000000001 | 1 |

4 | p_{1}^{2} | {2} | 00000000010 | 2 |

6 | p_{1}p_{2} | {1,1} | 00000000100 | 4 |

8 | p_{1}^{3} | {3} | 00000000011 | 3 |

12 | p_{1}^{2}p_{2} | {1,2} | 00000000101 | 5 |

16 | p_{1}^{4} | {4} | 00000001000 | 8 |

24 | p_{1}^{3}p_{2} | {1,3} | 00000000110 | 6 |

30 | p_{1}p_{2}p_{3} | {1,1,1} | 00000010000 | 16 |

32 | p_{1}^{5} | {5} | 00000001001 | 9 |

36 | p_{1}^{2}p_{2}^{2} | {2,2} | 00000100000 | 32 |

48 | p_{1}^{4}p_{2} | {1,4} | 00000000111 | 7 |

60 | p_{1}^{2}p_{2}p_{3} | {1,1,2} | 00000010001 | 17 |

64 | p_{1}^{6} | {6} | 00000001010 | 10 |

72 | p_{1}^{3}p_{2}^{2} | {2,3} | 00000100001 | 33 |

96 | p_{1}^{5}p_{2} | {1,5} | 00000001100 | 12 |

120 | p_{1}^{3}p_{2}p_{3} | {1,1,3} | 00000010010 | 18 |

128 | p_{1}^{7} | {7} | 00000001011 | 11 |

144 | p_{1}^{4}p_{2}^{2} | {2,4} | 00000100010 | 34 |

180 | p_{1}^{2}p_{2}^{2}p_{3} | {1,2,2} | 00000010100 | 20 |

192 | p_{1}^{6}p_{2} | {1,6} | 00000001101 | 13 |

210 | p_{1}p_{2}p_{3}p_{4} | {1,1,1,1} | 00001000000 | 64 |

216 | p_{1}^{3}p_{2}^{3} | {3,3} | 00000100100 | 36 |

240 | p_{1}^{4}p_{2}p_{3} | {1,1,4} | 00000010011 | 19 |

256 | p_{1}^{8} | {8} | 00010000000 | 128 |

288 | p_{1}^{5}p_{2}^{2} | {2,5} | 00000100011 | 35 |

360 | p_{1}^{3}p_{2}^{2}p_{3} | {1,2,3} | 00000010101 | 21 |

384 | p_{1}^{7}p_{2} | {1,7} | 00000001110 | 14 |

420 | p_{1}^{2}p_{2}p_{3}p_{4} | {1,1,1,2} | 00001000001 | 65 |

432 | p_{1}^{4}p_{2}^{3} | {3,4} | 00000100101 | 37 |

480 | p_{1}^{5}p_{2}p_{3} | {1,1,5} | 00000011000 | 24 |

512 | p_{1}^{9} | {9} | 00010000001 | 129 |

576 | p_{1}^{6}p_{2}^{2} | {2,6} | 00000101000 | 40 |

720 | p_{1}^{4}p_{2}^{2}p_{3} | {1,2,4} | 00000010110 | 22 |

768 | p_{1}^{8}p_{2} | {1,8} | 00000001111 | 15 |

840 | p_{1}^{3}p_{2}p_{3}p_{4} | {1,1,1,3} | 00001000010 | 66 |

864 | p_{1}^{5}p_{2}^{3} | {3,5} | 00000100110 | 38 |

900 | p_{1}^{2}p_{2}^{2}p_{3}^{2} | {2,2,2} | 00100000000 | 256 |

960 | p_{1}^{6}p_{2}p_{3} | {1,1,6} | 00000011001 | 25 |

1024 | p_{1}^{10} | {10} | 00010000010 | 130 |

1080 | p_{1}^{3}p_{2}^{3}p_{3} | {1,3,3} | 00000110000 | 48 |

1152 | p_{1}^{7}p_{2}^{2} | {2,7} | 00000101001 | 41 |

1260 | p_{1}^{2}p_{2}^{2}p_{3}p_{4} | {1,1,2,2} | 00001000100 | 68 |

1296 | p_{1}^{4}p_{2}^{4} | {4,4} | 01000000000 | 512 |

1440 | p_{1}^{5}p_{2}^{2}p_{3} | {1,2,5} | 00000010111 | 23 |

1536 | p_{1}^{9}p_{2} | {1,9} | 00010000100 | 132 |

1680 | p_{1}^{4}p_{2}p_{3}p_{4} | {1,1,1,4} | 00001000011 | 67 |

1728 | p_{1}^{6}p_{2}^{3} | {3,6} | 00000100111 | 39 |

1800 | p_{1}^{3}p_{2}^{2}p_{3}^{2} | {2,2,3} | 00100000001 | 257 |

1920 | p_{1}^{7}p_{2}p_{3} | {1,1,7} | 00000011010 | 26 |

2048 | p_{1}^{11} | {11} | 00010000011 | 131 |

2160 | p_{1}^{4}p_{2}^{3}p_{3} | {1,3,4} | 00000110001 | 49 |

2304 | p_{1}^{8}p_{2}^{2} | {2,8} | 00000101010 | 42 |

2310 | p_{1}p_{2}p_{3}p_{4}p_{5} | {1,1,1,1,1} | 10000000000 | 1024 |

2520 | p_{1}^{3}p_{2}^{2}p_{3}p_{4} | {1,1,2,3} | 00001000101 | 69 |

2592 | p_{1}^{5}p_{2}^{4} | {4,5} | 01000000001 | 513 |

2880 | p_{1}^{6}p_{2}^{2}p_{3} | {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.

## Leave a Reply