Primes from Primes

I've begun reading "The Man Who Loved Only Numbers" by Paul Hoffman, a biography of Paul Erdös. Figure 1 shows the front cover of the book. It motivated me to be a little more energetic in my daily number analysis at least for today because today was a prime day.

Figure 1

THE STORY OF PAUL ERDÖS AND THE SEARCH FOR MATHEMATICAL TRUTH

***

By that I mean I turned a prime number of days old, specifically 26371. Initially, I'd found that this number was a member of OEIS A255543:

A255543

Unlucky array: Row \(n\) consists of unlucky numbers removed at the stage \(n\) of Lucky sieve.

Figure 2, taken from the OEIS entry comments, shows what is meant by this:

Figure 2

Looking at the first row, it can seen that 2 and all multiples of 2 are removed. In the second row, every third remaining number is removed and so on for successive rows. 26371 lies in the 29th row that lists all the numbers removed when every 29th number is struck off. This was interesting but didn't relate to any specific properties of 26371 as a prime number. A little more research, motivated by Erdös's indefatigable research, led me to OEIS A249350:

A249350

Prime numbers Q such that the concatenation Q, 6, Q is prime.

As a member of this sequence, 26371 has the property that 26371626371 is a prime number. Up to 26371, the list of such primes is:

[13, 23, 29, 41, 53, 59, 71, 73, 89, 107, 149, 167, 173, 197, 239, 241, 257, 293, 349, 379, 383, 397, 439, 457, 461, 479, 503, 521, 547, 569, 607, 617, 631, 643, 677, 691, 727, 733, 757, 821, 887, 919, 941, 947, 953, 967, 1051, 1061, 1069, 1097, 1103, 1187, 1213, 1217, 1237, 1279, 1297, 1373, 1399, 1409, 1423, 1433, 1451, 1453, 1471, 1483, 1499, 1567, 1609, 1619, 1621, 1667, 1709, 1721, 1723, 1783, 1787, 1789, 1861, 1867, 1889, 1913, 1993, 1997, 2011, 2017, 2029, 2063, 2099, 2113, 2251, 2269, 2273, 2357, 2393, 2441, 2473, 2503, 2557, 2609, 2647, 2657, 2659, 2687, 2699, 2711, 2713, 2777, 2843, 2897, 2927, 2953, 3037, 3061, 3079, 3137, 3217, 3271, 3323, 3343, 3499, 3511, 3527, 3547, 3557, 3593, 3631, 3659, 3673, 3733, 3779, 3851, 3911, 4051, 4093, 4129, 4241, 4243, 4253, 4327, 4339, 4373, 4391, 4457, 4493, 4519, 4561, 4583, 4597, 4603, 4639, 4643, 4663, 4723, 4787, 4789, 4801, 4813, 4877, 4933, 4951, 4967, 5011, 5023, 5051, 5179, 5209, 5333, 5413, 5527, 5557, 5647, 5807, 5851, 5857, 5867, 5903, 6067, 6113, 6173, 6199, 6311, 6353, 6379, 6553, 6571, 6659, 6781, 6827, 6841, 6871, 6949, 6997, 7013, 7079, 7151, 7177, 7193, 7237, 7349, 7393, 7459, 7481, 7523, 7529, 7541, 7559, 7573, 7589, 7607, 7621, 7673, 7687, 7793, 7817, 7823, 7841, 7867, 7873, 7907, 8087, 8093, 8101, 8209, 8317, 8369, 8387, 8419, 8429, 8447, 8461, 8467, 8573, 8623, 8647, 8677, 8681, 8699, 8741, 8779, 8803, 8821, 8861, 8971, 8999, 9013, 9059, 9133, 9137, 9181, 9199, 9239, 9283, 9337, 9343, 9419, 9431, 9461, 9473, 9511, 9533, 9539, 9629, 9767, 9883, 10103, 10133, 10223, 10357, 10487, 10559, 10691, 10729, 10847, 10853, 10909, 10957, 10979, 11083, 11093, 11117, 11159, 11177, 11243, 11273, 11321, 11329, 11369, 11393, 11471, 11483, 11489, 11491, 11813, 11887, 12007, 12049, 12119, 12211, 12239, 12253, 12281, 12289, 12379, 12413, 12479, 12517, 12527, 12553, 12647, 12703, 12721, 12889, 12919, 13003, 13037, 13043, 13147, 13163, 13171, 13381, 13499, 13679, 13757, 13877, 14009, 14051, 14057, 14071, 14081, 14207, 14423, 14449, 14627, 14723, 14767, 14813, 14869, 14879, 14939, 15031, 15061, 15101, 15131, 15173, 15193, 15299, 15373, 15377, 15383, 15541, 15559, 15629, 15643, 15649, 15787, 15877, 15919, 15923, 16189, 16333, 16339, 16361, 16427, 16487, 16529, 16607, 16649, 16763, 16871, 16903, 16931, 17011, 17021, 17029, 17033, 17077, 17137, 17419, 17483, 17729, 17747, 17749, 17851, 17903, 17921, 17957, 17981, 18041, 18049, 18169, 18257, 18397, 18413, 18517, 18541, 18583, 18671, 18691, 18701, 18719, 18749, 18757, 18803, 18973, 19069, 19211, 19213, 19289, 19379, 19463, 19471, 19489, 19603, 19819, 19843, 19861, 19919, 20071, 20101, 20147, 20261, 20297, 20399, 20443, 20681, 20707, 20731, 20849, 20897, 20921, 20939, 21001, 21011, 21059, 21089, 21121, 21163, 21169, 21221, 21227, 21313, 21341, 21401, 21407, 21467, 21523, 21569, 22109, 22129, 22171, 22247, 22349, 22639, 22643, 22741, 22769, 22787, 22811, 22961, 23027, 23041, 23143, 23201, 23203, 23339, 23357, 23369, 23459, 23537, 23627, 23629, 23747, 23767, 23819, 23857, 23879, 23887, 24007, 24019, 24029, 24061, 24097, 24151, 24391, 24407, 24421, 24683, 24767, 24851, 24953, 25033, 25147, 25253, 25321, 25439, 25643, 26119, 26189, 26237, 26357, 26371]

26371 is the 2897th prime and the primes listed above total 502. This means that of all the primes up 26371, 502 or about 16.8% generate a new prime according the Q + 6 + Q concatenation. I wondered what numbers arise when the digits 1, 2, 3, 4, 5, 7, 8 and 9 are used instead. Inserting 0 between the two primes cannot produce a prime because the resulting concatenated number is always divisible by Q. Here are the figures for the digits from 1 to 9:

1     278

2     238

3     528

4     242

5     258

6     502

7     296

8     247

9     512

total is 3101

It can be seen that the record is held by the digit 3, although 6 and 9 are close behind. Well back however, are the digits 1, 2, 4, 5, 7 and 8. I thought I'd extend this to the first one million primes and Figure 3 shows the results obtained:

Figure 3

The proportions remain about the same with the exception of the digit 7. Figure 4 shows a table summarising the results:

Figure 4

Why do the digits 3, 6 and 9 produce about twice as many primes as the digits 1, 2, 4, 5 and 8? Why does the digit 7 produce significantly fewer primes that 1, 2, 4, 5 and 8? These are questions that I don't know the answer to but I'm keen to investigate.

One doesn't have to stop at the digit 9. What happens for the digits 10 to 19? Figure 5 tells the tale.

Figure 5

Figure 6 shows the same results in tabular form. It's clear that the multiples of 3 (12, 15 and 18) always win the day and with consistent frequency. The digits 10, 16 and 17 produce about half as many primes as their multiple of 3 counterparts, while 11, 13, 14 and 19 produce less than a third of even this number.

Figure 6

One might surmise that the frequency for multiples of 3 remains relatively constant as we investigate higher digits. After all, the numbers for 3, 6, 9, 12, 15 and 18 have been quite consistent. However, 21 = 3 x 7 breaks the pattern. See Figure 7.

Figure 7

The figure for 21 is not as low as for 22, 26 and 28 but it significantly lower than even the figures for 20, 23, 25 and 29. Figure 8 presents the results in tabular form.

Figure 8

Multiples of 7, 11 and 13 seem to produce far fewer primes when concatenated using Q + digit + Q. Figure 9 provides an overview of the digits from 1 to 99:

Figure 9

Clearly, there is more to be discovered here but I'll finish up at this point. What this post teaches us more than anything else is to not let a good prime go to waste and to be a little more energetic in my investigations.

Hamiltonian Paths and Knight's Tours

I encountered Hamiltonian paths before but never in the context of my daily number count. The reason is clear when we look at Figure 1 showing the initial members of OEIS A003216:

A003216

Number of Hamiltonian graphs with \(n\) nodes.

Figure 1: source

Looking at Figure 1, it can be seen that \(n\)=8 yields a value of 6196 but \(n\)=9 yields a value of 177083. This is a massive jump that completely misses the numbers that I am traversing as I track my diurnal age. Currently I am 26241 days old and one of the properties of this number is that it is a member of OEIS A283420 where \(n\)=9:

A283420

Number of simple (not necessarily connected) untraceable graphs on \(n\) nodes.

Even in the A283420 sequence the numbers get large very quickly. Here are the values from \(n\)=1 to 11: 0, 1, 2, 6, 16, 65, 310, 2316, 26241, 522596, 18766354. My current diurnal age just happened to be a member of this sequence and this is what led me to reacquaint myself with Hamiltonian graphs. Figure 2 shows all the possible non-Hamiltonian graphs for the case of \(n\)=5:

Figure 2: source

Looking at Figure 2, the distinction between graphs that are connected and those that are disconnected is apparent. But what about the terms simple and untraceable? At this point, it's a good idea to define separately what is meant by a simple graph and traceable graph (which will then explain an untraceable graph).

To quote from WolframMath World:

A simple graph, also called a strict graph, is an unweighted, undirected graph containing no graph loops or multiple edges. A simple graph may be either connected or disconnected. Figure 3 shows the differences between a simple graph and a nonsimple one:

Figure 3: source

A traceable graph is a graph that possesses a Hamiltonian path. Hamiltonian graphs are therefore traceable, but the converse is not necessarily true. The numbers of traceable graphs on \(n\)=1, 2, ... are 1, 1, 2, 5, 18, 91, 734, ... (OEIS A057864), where the singleton graph \(K_1\) is conventionally considered traceable. The first few are illustrated in Figure 4, with a Hamiltonian path indicated in orange for each. Source.

Figure 4: source

Comparing Figures 2 and 4, it can be seen what it is that defines a Hamiltonian path and a Hamiltonian cycle:

A Hamiltonian path or traceable path is a path that visits each vertex of the graph exactly once. A graph that contains a Hamiltonian path is called a traceable graph ... A Hamiltonian cycle, Hamiltonian circuit, vertex tour or graph cycle is a cycle that visits each vertex exactly once. A graph that contains a Hamiltonian cycle is called a Hamiltonian graph. Source.

Figure 5 shows a Hamiltonian cycle for the dodecahedron. 

Figure 5: source

A knight's tour can be viewed as either a Hamiltonian cycle or path when each square is regarded as a vertex:

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed; otherwise, it is open. The knight's tour problem is an instance of the more general Hamiltonian path problem in graph theory. The problem of finding a closed knight's tour is similarly an instance of the Hamiltonian cycle problem. Unlike the general Hamiltonian path problem, the knight's tour problem can be solved in linear time. Source.

Figure 6 shows an open knight's tour that is a Hamiltonian path but not a cycle:

Figure 6: source

It has been shown that closed knight's tours are possible on any \(m\) x \(n\) board with \(m\) ≤ \(n\) unless one or more of these three conditions are met:

• \(m\) and \(n\) are both odd
• \(m\) = 1, 2, or 4
• \(m\) = 3 and \(n\) = 4, 6, or 8

On an 8 × 8 board, there are exactly 26,534,728,821,064 directed closed tours (i.e. two tours along the same path that travel in opposite directions are counted separately, as are rotations and reflections). The number of undirected closed tours is half this number, since every tour can be traced in reverse. Source. 

Finally let's not fail to mention the great mathematician, Sir William Rowan Hamilton, after whom the Hamiltonian paths and cycles were named. Figure 7 shows a photograph of him.

Figure 7: Hamilton (1805-1865)

For a brief account of his life, follow this link.