Iterative mapping of prime signatures

Perhaps the most elegant way of arranging all of the positive integers in a two-dimensional grid is the pairing function. The grid is populated by placing a 1 in its starting corner, then filling the grid with diagonal stripes: 2 and 3 in the first stripe, 4 through 6 in the second, and so on.

Below is such a table with the first few diagonals filled in:

Table 1

	1	2	3	4	5	6	7	8	9
1	1	3	6	10	15	21	28	36	45
2	2	5	9	14	20	27	35	44
3	4	8	13	19	26	34	43
4	7	12	18	25	33	42
5	11	17	24	32	41
6	16	23	31	40
7	22	30	39
8	29	38
9	37

The columns, rows and cross diagonals are easily-calculable integer sequences, and many of them appear in the Online Encyclopedia of Integer Sequences.¹

Another way to arrange (almost) all of the positive integers in a two-dimensional grid is to arrange the grid so that each column contains all of the numbers with a given prime signature. In this grid, the first column would contain all the prime numbers, the second column would contain the squares of the prime numbers, and so on.

Here is a partial prime signature table:²

Table S

	p	p2	pq	p3	p2q	p4	p3q	pqr	p5
	{1}	{2}	{1,1}	{3}	{1,2}	{4}	{1,3}	{1,1,1}	{5}
	1	2	3	4	5	6	7	8	9
1	2	4	6	8	12	16	24	30	32
2	3	9	10	27	18	81	40	42
3	5	25	14	125	20	625	54
4	7	49	15	343	28	2401
5	11	121	21	1331	44
6	13	169	22	2197
7	17	289	26
8	19	361
9	23

A key difference between the two tables is that Table S does not include the number 1. This is because the first column starts with the first prime-containing prime signature, e.g. {1}. The number 1 does not contain any prime factors, and would be in a column by itself, since there are no other positive integers with no prime factors.

With the exception of the missing 1 in Table S, both tables contain each of the positive integers exactly once.

Cross-mapping

Similar to the procedure used to create metaprime binary sequences and binary-encoded prime signature sequences, we can use both tables to repeatedly “encode” an integer into its Table 1 coordinate pair, then use that same coordinate pair to “decode” a number in Table S.

Let’s start with the number 1. In Table 1, we see its coordinate is row 1, column 1. Moving to Table S, we see the number occupying row 1, column 1 is the number 2.

Let’s take that “2” and return to Table 1. Its coordinates there are row 2, column 1. Moving to Table S, we see the number occupying row 2, column 1 is “3.”

So far, our sequence looks like this: 1, 2, 3…

By repeating the process, we will see the sequence build to 1, 2, 3, 4, 5, 9, 10, 8, 25, 343, 3969, 13090, 73344 and 77398016.

Table 1	[Row,Column]	Table S
1	[1,1]	2
2	[2,1]	3
3	[1,2]	4
4	[3,1]	5
5	[2,2]	9
9	[2,3]	10
10	[1,4]	8
8	[3,2]	25
25	[4,4]	343
343	[9,18]	3969
3969	[37,53]	13090
13090	[114,49]	73344
73344	[193,191]	77398016
77398016	[9888,2555]	?

Once we reach 77398016, the row and column numbers are so large that it would require a bit of number-crunching to figure out what number resides at that location within Table S.³

Let’s try a new sequence. The smallest positive integer that didn’t appear in the previous sequence is 6, so let’s start with that.

Table 1	[Row,Column]	Table S
6	[1,3]	6

In this case, our number (6) sits at the same place in both tables, so the sequence is simply an infinite series of sixes. Other numbers that map to themselves and thus create sequences that repeat forever are 7, 11, 132 and 568. (These appear to be the only numbers less than 10000 that map to themselves.)

Here is a table of the first few sequences we will encounter, arranged by the lowest number in the sequence (the column labeled “Seq.”) For known repeating sequences, the “Terms” column shows the period; otherwise, the number of terms found so far is shown.

Seq.	Table 1 Sequence	Terms	Type
1 A179223	1, 2, 3, 4, 5, 9, 10, 8, 25, 343, 3969, 13090, 73344, 77398016, ?	>14	non- repeating
6	6, 6, …	1	repeating
7	7, 7, …	1	repeating
11	11, 11, …	1	repeating
12	?, 2303734, 8133, 1172, 3744, 295, 468, 94, 39, 26, 20, 18, 15, 12, 49, 4913, 16312, ?	>16	?
13 A179224	?, 200662, 4691, 8520, 1183, 904, 191, 71, 52, 56, 31, 22, 17, 121, 53, 66, 48, 33, 28, 24, 21, 16, 13, 14, 27, 81, 38, 361, 3844, 2392, 10032, 3910, 20790, ?	>32	?
19	?, 1576212, 18531, 669, 119, 108, 46, 29, 19, 125, 76, 196, 4879681, ?	>12	?
23	?, 85492, 2851, 383, 172, 67, 37, 23, 169, 264, 567, 141158161, ?	>11	?
30	?, 14199, 562, 139, 55, 36, 30, 289, 2565726409, ?	>8	?
32	?, 61779, 1226, 229, 300, 256, 74, 78, 60, 50, 45, 32, 1331, 388, 4225, 25110, ?	>15	?
34	?, 23437, 1327, 239, 174, 58, 34, 625, 1632, 1288408, ?	>9	?
35	?, 38229, 951, 325, 288, 234, 69, 35, 40, 2197, 430336, ?	>10	?

Aside from the sequences containing 6, 7 and 11, which are repeating, the only other sequence whose type we can definitely see is sequence 1. We know that this must continue indefinitely: it cannot loop back to “1” because there is no “1” in Table S for it to loop back to.

The other sequences shown may be shown to be repeating once enough terms are discovered, or they may in fact be shown to be part of a non-repeating sequence, i.e. sequence 1. Sequence 1 can be shown to be the only sequence that has a definitive starting point, but no end: all other sequences must either loop back on themselves, or continue forever in both directions, since 1 is the only number in one table but not the other.

Here is Table 1 again, colored to show which numbers belong to which of the sequences described above:

Table 1 – colored by sequence

	1	2	3	4	5	6	7	8	9
1	1	3	6	10	15	21	28	36	45
2	2	5	9	14	20	27	35	44
3	4	8	13	19	26	34	43
4	7	12	18	25	33	42
5	11	17	24	32	41
6	16	23	31	40
7	22	30	39
8	29	38
9	37

A variation of Table 1

There are a number of ways we can re-arrange Table 1 to see how the cross-mapping might be different.

The simplest way is to simply switch the rows and columns, like so:

Table 1A

	1	2	3	4	5	6	7	8	9
1	1	2	4	7	11	16	22	29	37
2	3	5	8	12	17	23	30	38
3	6	9	13	18	24	31	39
4	10	14	19	25	32	40
5	15	20	26	33	41
6	21	27	34	42
7	28	35	43
8	36	44
9	45

Let’s do the same cross-mapping between Tables 1A and S that we did for Tables 1 and S above.

Starting again with the number 1, we see its Table 1A coordinate is row 1, column 1. Moving to Table S, we see the number occupying row 1, column 1 is the number 2.

Taking that “2” and returning to Table 1A to repeat the process, we see the sequence build to 1, 2, 4, 6, 5, 9, 25, 343 and 844596301.

Table 1A	[Row,Column]	Table S
1	[1,1]	2
2	[1,2]	4
4	[1,3]	6
6	[3,1]	5
5	[2,2]	9
9	[3,2]	25
25	[4,4]	343
343	[18,9]	844596301
844596301	[11851,29250]	?

As before, we reach a number (844596301 in this case) with coordinates that would require some number-crunching to determine the next term in the sequence.⁴

Let’s try a new sequence. The smallest positive integer that didn’t appear in the previous sequence is 3, so let’s start with that.

Table 1A	[Row,Column]	Table S
3	[2,1]	3

It looks like 3 gives us another repeating series, consisting of an infinite series of threes. (Other numbers that repeat in the Table 1A to Table S mapping are 16, which can be found at row 1, column 6 of both tables, and 1416, which can be found at row 38, column 16.)

The next unused number is 7, so let’s use it to start a sequence.

Table 1	[Row,Column]	Table S
7	[1,4]	8
8	[2,3]	10
10	[4,1]	7

In this case, the sequence loops back to its beginning: 7, 8, 10, 7…

Unlike the other repeating series we’ve found, this series has a period of 3, not 1.

Here is a table of the first few sequences we will encounter in the Table 1A/S cross-mapping:

Seq.	Table 1A Sequence	Terms	Type
1 A179225	1, 2, 4, 6, 5, 9, 25, 343, 844596301, ?	>9	non- repeating
3	3, 3, …	1	repeating
7	7, 8, 10, 7 …	3	repeating
11 A179226	?, 1927639, 48828, 2069, 735, 664, 118, 46, 36, 19, 15, 11, 12, 27, 169, 57, 100, 279841, ?	>17	?
13	?, 3126248, 9589, 469, 780, 167, 98, 105, 43, 26, 21, 13, 14, 49, 56, 48, 66, 31, 625, 163047361, ?	>19	?
16	16, 16, …	1	repeating
17	?, 1069453, 12239, 1066, 1128, 211, 210, 71, 78, 37, 32, 28, 17, 18, 125, 132, 76, 35, 289, 234, 448, 8464, 21977344, ?	>22	?
20	?, 13989, 93096, 3001, 253, 79, 64, 34, 22, 24, 20, 121, 120, 47, 243, 496, 127, 676, 1140, 23716, 913680, ?	>20	?
23	?, 34714, 901, 134, 51, 45, 23, 81, 112, 1419857, ?	>9	?
29	?, 37675, 1759, 666, 151, 55, 29, 30, 40, 2401, 6752, 10290, 3773, 36800, 1319936, ?	>14	?
33	?, 1228517, 16460, 1953, 293, 186, 99, 136, 53, 33, 1331, 5292, 19530, 10317, ?	>13	?

Here is Table 1A, colored to show which numbers belong to which of the sequences described above:

Table 1A – colored by sequence

	1	2	3	4	5	6	7	8	9
1	1	2	4	7	11	16	22	29	37
2	3	5	8	12	17	23	30	38
3	6	9	13	18	24	31	39
4	10	14	19	25	32	40
5	15	20	26	33	41
6	21	27	34	42
7	28	35	43
8	36	44
9	45

Open questions

Here are some open questions about these sequences:

• Which of the sequences shown (if any) will connect to other sequences if the sequence is extended far enough?
• Specifically, does Sequence 1 eventually link to any of the other sequences shown?
• What other repeating sequences are there? Are there any that have periods other than 1 or 3? (None less than 10,000 have been found.)

Tables starting with 0

There are a number of other ways to modify Tables 1 and 1A to produce different sets of cross-mapping sequences.

For example, rather than start with the integer 1, these tables could start with 0 instead. Here are two versions of zero-based tables, color-colored as above (the sequences themselves follow.)

Table 0

	1	2	3	4	5	6	7	8	9
1	0	2	5	9	14	20	27	35	44
2	1	4	8	13	19	26	34	43
3	3	7	12	18	25	33	42
4	6	11	17	24	32	41
5	10	16	23	31	40
6	15	22	30	39
7	21	29	38
8	28	37
9	36

Seq.	Table 0 Sequence	Terms	Type
0 A179219	0, 2, 4, 9, 8, 10, 11, 49, 45, 29, 289, 1372, 91125, ?	>13	non- repeating
1 A179220	1, 3, 5, 6, 7, 25, 20, 16, 121, 2209, 5460, 571, 1136, 154963892093, ?	>14	non- repeating
12	12, 14, 12, …	2	repeating
13	?, 21530, 707, 268, 408, 91, 43, 42, 54, 36, 23, 21, 17, 15, 13, 27, 24, 343, 612, 15376, ?	>19	?
18	?, 236162810177, 3296035, 14035, 1130, 155, 57, 34, 40, 44, 32, 28, 19, 18, 125, 923521, ?	>15	?
22	?, 1064380593, 204482, 2285, 498, 95, 68, 35, 30, 22, 169, 2187, 52200625, ?	>12	?
26	?, 153624163, 88417, 2630, 235, 124, 76, 80, 38, 26, 81, 24389, 686016, ?	>12	?
31	?, 55161764, 567656, 11175, 863, 134, 160, 138, 55, 31, 1331, 1982119441, ?	>11	?
33	?, 36795335, 34991, 2852, 249, 396, 700, 1560, 1722, 666, 157, 98, 105, 47, 33, 625, 2357947691, ?	>16	?
72	72, 104, 72, …	2	repeating

Table 0A

	1	2	3	4	5	6	7	8	9
1	0	1	3	6	10	15	21	28	36
2	2	4	7	11	16	22	29	37
3	5	8	12	17	23	30	38
4	9	13	18	24	31	39
5	14	19	25	32	40
6	20	26	33	41
7	27	34	42
8	35	43
9	44

Seq.	Table 0A Sequence	Terms	Type
0 A179221	0, 2, 3, 6, 8, 25, 21, 24, 343, 195, 486, 5929, 35568, 1450800, ?	>14	non- repeating
1 A179222	1, 4, 9, 7, 10, 12, 14, 11, 27, 17, 125, 208, 4489, 42588, ?	>14	non- repeating
5	5, 5, …	1	repeating
13	?, 13104637, 20285, 5560, 925, 1254, 1430, 241, 220, 464, 113, 152, 59, 88, 38, 54, 29, 40, 44, 23, 20, 13, 49, 14641, 33930, 691200, ?	>25	?
15	15, 16, 18, 15, …	3	repeating
19	?, 20253402, 135980, 3733, 627, 115, 75, 35, 19, 121, 160, 304, 510, 9801, 181888, ?	>14	?
22	?, 655310498, 808348, 7257, 398, 230, 73, 52, 33, 22, 81, 225, 7890481, ?	>12	?
26	?, 8490804138, 607711, 116865, 10582, 489, 488, 246, 297, 77, 37, 42, 26, 169, 3481, 711, 2080, 4620, ?	>17	?
28	?, 4121366627, 1577975, 15217, 1173, 155, 264, 228, 65, 31, 28, 30, 625, 244, 147008443, ?	>14	?
32	?, 385517029, 321991, 8380, 1175, 223, 170, 61, 50, 45, 36, 32, 1331, 91125, 72115879936, ?	>14	?

In addition, the following numbers each map to themselves in the Table 0A mapping.

Tables 0A & S	[Row,Column]
120	[1,16]
198	[9,12]
210	[1,21]
1160	[33,16]
6544	[104,11]

Note that the mapping sequences for Table 0 and Table 0A each contain two sequences with a starting term but no ending term: one starting at 0 and another starting at 1.

Tables starting with 2

Instead of starting with 0 or 1, we can adjust Tables 1 and 1A to start with 2 instead. This way these tables will have the same integers that Table S has: all positive integers greater than 1. As above, the numbers have been color-colored to match the sequences listed below.

Table 2

	1	2	3	4	5	6	7	8	9
1	2	4	7	11	16	22	29	37	46
2	3	6	10	15	21	28	36	45
3	5	9	14	20	27	35	44
4	8	13	19	26	34	43
5	12	18	25	33	42
6	17	24	32	41
7	23	31	40
8	30	39
9	38

Seq.	Table 2 Sequence	Terms	Type
2	2, 2, …	1	repeating
3	3, 3, …	1	repeating
4	4, 4, …	1	repeating
5	5, 5, …	1	repeating
6 A179227	?, 46465694290, 1468045, 6445, 382, 87, 102, 441, 188, 270, 408, 109, 46, 32, 22, 16, 12, 11, 8, 7, 6, 9, 25, 21, 18, 121, 96, 29791, 54716, ?	>28	?
10	10, 10, …	1	repeating
13	?, 125207413, 171441, 43960, 1037, 199, 165, 304, 82, 38, 23, 17, 13, 49, 33, 1331, 11697083, ?	>16	?
14	14, 14, …	1	repeating
15	?, 108508559, 159332, 4099, 302, 97, 68, 37, 30, 19, 15, 27, 20, 125, 68921, ?	>14	?
24	?, 6310137, 19114, 679, 380, 107, 47, 29, 24, 169, 352, 360, 222, 464, 660, 19208, 54114, ?	>16	?
26	?, 12384468273, 2122843, 21532, 707, 122, 53, 56, 36, 40, 26, 343, 17249876309, ?	>12	?
28	?, 1424738889, 238399, 2487, 353, 103, 162, 138, 59, 34, 28, 81, 1369, 3420, 2295, 1752, 12744, 9424, 409536, ?	>18	?
31	?, 391314294, 139137, 3246, 668, 157, 57, 31, 289, 234, 5329, 514188, ?	>11	?
35	?, 103788027, 60391, 3668, 950, 142, 92, 64, 70, 35, 625, 16875, 45248, 125914, ?	>13	?
186	186, 675, 285, 186, …	3	repeating
536	536, 536, …	1	repeating
1242	1242, 1242, …	1	repeating

Table 2A

	1	2	3	4	5	6	7	8	9
1	2	3	5	8	12	17	23	30	38
2	4	6	9	13	18	24	31	39
3	7	10	14	19	25	32	40
4	11	15	20	26	33	41
5	16	21	27	34	42
6	22	28	35	43
7	29	36	44
8	37	45
9	46

Seq.	Table 2A Sequence	Terms	Type
2	2, 2, …	1	repeating
3	3, 4, 3, …	2	repeating
5 A179228	?, 49632504515, 1530323, 277884, 2661, 7380, 403, 172, 61, 88, 63, 50, 56, 29, 17, 16, 11, 7, 5, 6, 9, 10, 25, 20, 15, 49, 66, 841, 328509, 528490692608, ?	>30	?
8	8, 8, …	1	repeating
12	12, 12, …	1	repeating
13	?, 229133697534, 3402137, 23417, 5434, 4004, 299, 77, 35, 22, 13, 27, 21, 121, 47, 36, 289, 2565726409, ?	>17	?
14	14, 14, …	1	repeating
18	18, 18, …	1	repeating
19	?, 363730887, 326002, 22785, 1426, 1048, 3080, 254, 79, 37, 19, 125, 117649, ?	>12	?
23	?, 17787148956, 2220772, 11627, 514, 702, 119, 46, 23, 24, 81, 84, 161051, ?	>12	?
26	?, 19128995405, 929567, 11273, 25650, 771, 1377, 166, 232, 73, 104, 39, 42, 44, 26, 343, 3364, 2101707, ?	>17	?
28	?, 5609574, 13042, 947, 191, 67, 31, 40, 54, 33, 28, 169, 103823, ?	>12	?
30	30, 30, …	1	repeating
32	?, 24981836, 75052, 12402, 527, 95, 90, 38, 32, 625, 584, 243087455521, ?	>11	?
34	?, 92704510, 270452, 99232, 5243, 1150, 1710, 194, 400, 230, 65, 34, 1331, 4480, 26520, 6424482779, ?	>15	?
108	108, 108, …	1	repeating
192	192, 192, …	1	repeating

Unlike the sequences for Tables 0, 0A, 1, and 1A, there are no sequences for Tables 2 and 2A that have a starting term but no ending term, since there are no numbers that are in Table 2 or 2A that are not also in Table S (and vice versa.)

If we were to create tables that start with 3 or a larger number, we would find sequences that have an ending term (e.g. 2), but no starting term.

There are other ways to create similar mapping sequences other than simply changing the starting number: different methods of distributing the numbers (such as those described in the pairing function page) could be used.

Depending on the starting number used and the manner in which the numbers are distrubted, new types of sequences will appear, such as finite sequences, and repeating sequences with periods other than what we’ve seen so far.

Footnotes

¹ The first row of Table 1 contains the positive “triangular numbers:” 1, 6, 3, 10, etc., which are included in OEIS sequence A000217. The first column (1, 2, 4, 7, etc.) forms the central polygonal numbers (A000124), and the diagonal starting from the top left corner (1, 5, 13, etc.) forms the centered square numbers (A001844.)

² A larger version of Table S is also available, featuring 300 rows and 160 columns.

As with Table 1, many of the columns in Table S appear as sequences in the OEIS: the first column is the prime numbers (A000040), the second column is the squares of primes (A001248), the third column is the square-free semiprimes (A006881), etc.

The first two rows of Table S also appear as OEIS sequences: A025487 and A077560 respectively. The diagonal starting from the top left corner (2, 9, 14, 343, etc.) is sequence A178849.

There is also an OEIS sequence (A095904) that maps Table S against Table 0. It also maps to Tables 1 and 2 if the offset is adjusted accordingly. Sequence A179216 similarly maps Table S against Tables 0A, 1A and 2A.

Reverse mappings also have OEIS sequences: A179217 (the inverse function of A095904) maps Table 0 to Table S, and A179218 (the inverse function of A179216) maps Table 0A to Table S.

A full list of the OEIS sequences related to the sequences described on this page can be found on the OEIS page.

³ We do know that the next number in the sequence will be larger than 43589145600, which is the value of row 1, column 2555. (Shown as line item 2556 in the OEIS’s extended table of A025487, which matches column 2555 of Table S, due to the different starting offset.) Since each column is sorted smallest to largest, within a given column the numbers increase as the row number increases.

⁴ We do know that it will be much larger than 2 × 10¹⁴, which is the approximate value of the number at row 1, column 10000. Since each column is sorted smallest to largest, and within a given column the numbers increase as the row number increases, we can see that row 1, column 29250 will be larger than row 1, column 10000, and that row 11851, column 29250 will be larger than row 1, column 29250.