W

 Will Nicholes

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-6 in the second, and so on.

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

Table 1

123456789
1136101521283645
22591420273544
3481319263443
471218253342
51117243241
616233140
7223039
82938
937

 

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

Another way to arrange (almost) all of the positive integers in a two-dimensial 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:2

Table S

p p2pq p3p2qp4p3qpqr p5
{1}{2}{1,1}{3}{1,2}{4}{1,3}{1,1,1}{5}
123456789
124681216243032
239102718814042
3525141252062554
474915343282401
51112121133144
613169222197
71728926
819361
923

 

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

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 SequenceTermsType
1 A1792231, 2, 3, 4, 5, 9, 10, 8, 25, 343, 3969, 13090, 73344, 77398016, ?>14non- repeating
66, 6, ...1repeating
77, 7, ...1repeating
1111, 11, ...1repeating
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

123456789
1136101521283645
22591420273544
3481319263443
471218253342
51117243241
616233140
7223039
82938
937

 

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

123456789
112471116222937
23581217233038
3691318243139
4101419253240
51520263341
621273442
7283543
83644
945

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

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 SequenceTermsType
1 A1792251, 2, 4, 6, 5, 9, 25, 343, 844596301, ?>9non- repeating
33, 3, ...1repeating
77, 8, 10, 7 ...3repeating
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?
1616, 16, ...1repeating
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

123456789
112471116222937
23581217233038
3691318243139
4101419253240
51520263341
621273442
7283543
83644
945

 

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

123456789
102591420273544
21481319263443
3371218253342
461117243241
51016233140
615223039
7212938
82837
936

 
Seq.Table 0 SequenceTermsType
0 A1792190, 2, 4, 9, 8, 10, 11, 49, 45, 29, 289, 1372, 91125, ?>13non- repeating
1 A1792201, 3, 5, 6, 7, 25, 20, 16, 121, 2209, 5460, 571, 1136, 154963892093, ?>14non- repeating
1212, 14, 12, ...2repeating
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?
7272, 104, 72, ...2repeating

 

Table 0A

123456789
101361015212836
22471116222937
3581217233038
491318243139
51419253240
620263341
7273442
83543
944

 
Seq.Table 0A SequenceTermsType
0 A1792210, 2, 3, 6, 8, 25, 21, 24, 343, 195, 486, 5929, 35568, 1450800, ?>14non- repeating
1 A1792221, 4, 9, 7, 10, 12, 14, 11, 27, 17, 125, 208, 4489, 42588, ?>14non- repeating
55, 5, ...1repeating
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?
1515, 16, 18, 15, ...3repeating
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

123456789
1247111622293746
236101521283645
3591420273544
481319263443
51218253342
617243241
7233140
83039
938

 
Seq.Table 2 SequenceTermsType
22, 2, ...1repeating
33, 3, ...1repeating
44, 4, ...1repeating
55, 5, ...1repeating
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?
1010, 10, ...1repeating
13?, 125207413, 171441, 43960, 1037, 199, 165, 304, 82, 38, 23, 17, 13, 49, 33, 1331, 11697083, ?>16?
1414, 14, ...1repeating
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?
186186, 675, 285, 186, ...3repeating
536536, 536, ...1repeating
12421242, 1242, ...1repeating

 

Table 2A

123456789
123581217233038
24691318243139
37101419253240
4111520263341
51621273442
622283543
7293644
83745
946

 
Seq.Table 2A SequenceTermsType
22, 2, ...1repeating
33, 4, 3, ...2repeating
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?
88, 8, ...1repeating
1212, 12, ...1repeating
13?, 229133697534, 3402137, 23417, 5434, 4004, 299, 77, 35, 22, 13, 27, 21, 121, 47, 36, 289, 2565726409, ?>17?
1414, 14, ...1repeating
1818, 18, ...1repeating
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?
3030, 30, ...1repeating
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?
108108, 108, ...1repeating
192192, 192, ...1repeating

 

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

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

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

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

4 We do know that it will be much larger than 2 × 1014, 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.

 

Validate this page