Can you believe it’s been 10 years since I made the “Is this prime?” game? I sort of can, because I set myself a reminder about it in my calendar.
Back in 2016, the game had been played 350,000 times and I wrote a post looking at the collected data.
10 years later, I thought I’d have another look.
Welcome to the 241st Carnival of Mathematics, hosted here at the home of the Carnival, The Aperiodical. The Aperiodical is a shared blog written and curated by Katie Steckles (me), Christian Lawson-Perfect and Peter Rowlett, where we share interesting maths news and content, aimed at people who already know they like maths and would like to know more. The Carnival of Maths is administered by the Aperiodical, and if you’d like to host one on your own blog or see previous editions, you can visit the Carnival of Maths page.
A few weeks ago I heard someone casually refer to ‘that formula of Euler’s that generates primes’. I hadn’t heard of this, but it turns out that in 1772 Euler produced this formula:
\[ f(x) = x^2 + x + 41\text{.} \]
Using this, \(f(0)=41\), which is prime. \(f(1)=43\), which is also prime. \(f(2)=47\) is another prime. In fact this sequence of primes continues for an incredible forty integer inputs until \(f(40)=41^2\). It might generate more primes for higher inputs, but what’s interesting here is the uninterrupted sequence of forty primes.
This got me wondering. Clearly \(f(0)\) is prime because 41 is prime, so that much will work for any function
\[ f(x) = x^2 + x + p \]
for prime \(p\), since \(f(0)=0^2+0+p=p\). Are there other values of \(p\) that generate a sequence of primes? Are there any values of \(p\) that generate longer sequences of primes?
I wrote some code to investigate this. Lately, I’ve taken to writing C++ when I need a bit of code, for practice, so I wrote this in C++.
I figured the cases where \(f(0)\) is prime but \(f(1)\) isn’t weren’t that interesting, since \(f(0)\) is trivially prime. In fact, \(f(x)=x g(x)+p=p\) when \(x=0\) for any prime \(p\), but saying so doesn’t seem worth the effort.
So I kept track of the primes \(p\) whose functions \(f(x)=x^2+x+p\) generate more than one prime, and the lengths of the sequences of primes generated by each of these. This produced a pair of integer sequences.
I put the primes that work into the OEIS and saw that I had generated a list of the smaller twin in each pair of twin primes. I was momentarily spooked by this, until I realised it was obvious. Since \(f(0)=p\) and \(f(1)=1^2+1+p=p+2\), any prime this works for will generate at least a twin prime pair \(p,p+2\).
What about the lengths of the sequences of consecutive primes generated? The table below shows the sequences of consecutive primes generated for small values of \(p\). Most primes that generate a sequence produce just two, and \(p=41\) definitely stands out by generating forty.
| \(p\) | \(f(x)\) | Primes generated | Number of consecutive primes generated |
| 3 | \(x^2+x+3\) | 3, 5 | 2 |
| 5 | \(x^2+x+5\) | 5, 7, 11, 17 | 4 |
| 11 | \(x^2+x+11\) | 11, 13, 17, 23, 31, 41, 53, 67, 83, 101 | 10 |
| 17 | \(x^2+x+17\) | 17, 19, 23, 29, 37, 47, 59, 73, 89, 107, 127, 149, 173, 199, 227, 257 | 16 |
| 29 | \(x^2+x+29\) | 29, 31 | 2 |
I was pleased to see this sequence of lengths of primes generated was not in the OEIS. So I submitted it, and it is now, along with the code I wrote. (I discovered along the way that the version where sequences of length one are included was already in the database.)
Anyway, I amused myself by having some C++ code published, and by citing Euler in a mathematical work. Enjoy: A371896.
In the last Finite Group livestream, Katie told us about emirps. If a number p is prime, and reversing its digits is also prime, the reversal is an emirp (‘prime’ backwards, geddit?).
For example, 13, 3541 and 9999713 are prime. Reversing their digits we get the primes 31, 1453 and 3179999, so these are all emirps. It doesn’t work for all primes – for example, 19 is prime, but 91 is \(7 \times 13 \).
In the livestream chat the concept of primemirp emerged. This would be a concatenation of a prime with its emirp. There’s a niggle here: just like in the word ‘primemirp’ the ‘e’ is both the end of ‘prime’ and the start of ’emirp’, so too in the number the middle digit is end of the prime and the start of its emirp.
Why? Say the digits of a prime number are \( a_1 a_2 \dots a_n \), and its reversal \( a_n \dots a_2 a_1 \) is also a prime. Then the straight concatenation would be \( a_1 a_2 \dots a_n a_n \dots a_2 a_1 \). Each number \(a_i\) is in an even numbered place and an odd numbered place. Now, since
\[ 10^k \pmod{11} = \begin{cases}
10, & \text{if } k \text{ is even;}\\
1, & \text{otherwise,}
\end{cases} \]
it follows that each \(a_i \) contributes a multiple of eleven to the concatenation. A mismatched central digit breaks this pattern, allowing for the possibility of a prime.
I wrote some code to search for primemirps by finding primes, reversing them and checking whether they were emirps, then concatenating them and checking the concatenation. I found a few! Then I did what is perfectly natural to do when a sequence of integers appears in front of you – I put it into the OEIS search box.
Imagine my surprise to learn that the concept exists and is already included in the OEIS! It was added by Patrick De Geest in February 2000, based on an idea from G. L. Honaker, Jr. But there was no program code to find these primes and only the first 32 examples were given. I edited the entry to include a Python program to search for primemirps and added entries up to the 8,668th, which I believe is all primemirps where the underlying prime is less than ten million. My edits to the entry just went live at A054218: Palindromic primes of the form ‘primemirp’.
The 8,668th primemirp is 9,999,713,179,999.
Here’s a game I’ve been trying to make for a while.
For a while I’ve had a hunch that there’s fun to be had in moving between numbers by using something related to the prime numbers.
Over the years I’ve tried out a few different ideas, but none of them ever worked out – they were either too easy, too hard, or just not interesting. This time, I think I’ve found something close enough to the sweet spot that I’m happy to publish it.
Prime Run is a game about adding and subtracting prime numbers. You start at a random number, with a random target. Your goal is to reach the target, by adding or removing any prime factor of your current number.
Following on from the series of ‘Pascal’s Triangle and its Secrets‘ posts, guest author David Benjamin shares another delightful piece of mathematics – this time relating to prime numbers.
At the time of writing the largest known prime number has $24862048$ digits. The number of digits does not reflect the true size of this prime but if we were to type it out at Times New Roman font size 12, it would reach approximately $51.5$ km, or about $32$ miles. Astonishing!
Patrick Laroche from Ocala, Florida discovered this Mersenne prime on December 7, 2018. I was surprised to discover that it’s exponent $82589933$ is the length of the hypotenuse of a primitive Pythagorean triple where $82589933^{2} = 30120165^{2} + 76901708^{2}$ as indeed are 8 of the exponents of those currently ranked from 1 to 10.
The Greek mathematician Euclid of Alexandria ($\sim$325 BC-265 BC) was arguably the first to prove that there are an infinite number of primes – and since then, people have been searching for new ones. Some do it for kudos, for the prize money, to test the power of computers and the need to find more of the large primes used to help protect the massive amount of data which is being moved around the internet.
Mersenne primes, named after the French monk Marin Mersenne, are of the form $2^{p} -1$, where the exponent $p$ is also prime. Mersenne primes are easier to test for primality, which is one reason we find so many large ones (all but one of the top ten known primes are Mersenne). When Mersenne primes are converted to binary they become a string of $1$s, which makes them suitable for computer algorithms and an excellent starting point for any search.
Since generally testing numbers for primality is slow, some have tried to find methods to produce primes using a formula. Euler’s quadratic polynomial $n^2+n+41$ produces this set of $40$ primes for $n = 0$ to $39$. When $n=40$, the polynomial produces the square number $1681$. Other prime-generating polynomials are listed in this Wolfram Mathworld entry.
The French mathematician Lejeune Dirichlet proved that the linear polynomial $a+nb$ will produce an infinite set of primes if $a$ and $b$ are coprime for $n=0,1,2,3,4,…$. Then again, it also produces an infinite number of composite numbers! However, this gem: $224584605939537911 + 1813569659748930n$ produces 27 consecutive primes for $n=0$ to $n=26$ – and of course, all the primes are in arithmetic progression.
The primes are unpredictable, and become less common as they get larger. Consequently there is no formula that will generate all the prime numbers. However, there is a finite sequence of fractions, that – given an infinite amount of time – would generate all the primes, and in sequential order.
They are the fruitful fractions, created by the brilliant Liverpool-born mathematician, John Horton Conway (1937–2020) who, until his untimely death from complications related to COVID-19, was the John von Neumann Emeritus Professor in Applied and Computational Mathematics at Princeton University, New Jersey, USA.
The fruitful fractions are
| $\frac{17}{91}$ | $\frac{78}{85}$ | $\frac{19}{51}$ | $\frac{23}{38}$ | $\frac{29}{33}$ | $\frac{77}{29}$ | $\frac{95}{23}$ | $\frac{77}{19}$ | $\frac{1}{17}$ | $\frac{11}{13}$ | $\frac{13}{11}$ | $\frac{15}{44}$ | $\frac{15}{2}$ | $\frac{55}{1}$ |
| A | B | C | D | E | F | G | H | I | J | K | L | M | N |
The first time I encountered this set of fractions was in the wonderful book, The Book of Numbers, by Conway and Guy. I was so intrigued as to how Conway came up with his idea, I emailed him to ask. I was delighted to receive an outline of an explanation and even a second set of fractions, neither of which I can now find – it was 1996 and pre-cloud storage! But no worries… Conway explains everything in this lecture, which also demonstrates his passion for mathematics and his ability to express his ideas in a relaxed and humorous way, even when he searches for an error in his proof on 26 minutes. The lecture also includes an introduction to Conway’s computer language, FRACTRAN, which includes the statement:
‘It should now be obvious to you that you can write a one line fraction program that does almost anything, or one and a half lines if you want to be precise‘.
Here’s how the fractions are used to generate primes.
The 19 steps needed to produce the first prime number are:
$2 \overset{ \times M}{\rightarrow} 15 \overset{ \times N}\rightarrow 825\overset{ \times E} \rightarrow 725 \overset{ \times F}\rightarrow 1925\overset{ \times K} \rightarrow 2275 \overset{ \times A}\rightarrow 425 \overset{ \times B}\rightarrow 390 \overset{ \times J}\rightarrow 330 \overset{ \times E}\rightarrow 290 \overset{ \times F}\rightarrow 770 \overset{ \times K}\rightarrow 910\overset{ \times A} \rightarrow 170\overset{ \times B} \rightarrow 156\overset{ \times J} \rightarrow 132\overset{ \times E} \rightarrow 116 \overset{ \times F}\rightarrow 308\overset{ \times K} \rightarrow 364\overset{ \times A} \rightarrow 68 \overset{ \times I}\rightarrow 4 \equiv2^{2}$
The number of steps needed to produce the first 7 primes are shown in the table below:
| Prime | 2 | 3 | 5 | 7 | 11 | 13 | 17 |
| Steps | 19 | 69 | 281 | 710 | 2375 | 3893 | 8102 |
And here is the start and end of the sequence of fractions used to produce the next prime number from $2^{2}$:
$4 \overset{ \times M}{\rightarrow} 30 \overset{ \times M}\rightarrow 225\overset{ \times N} \rightarrow 12375 \overset{ \times E}\rightarrow 10875 \rightarrow \cdots \rightarrow 232 \overset{ \times F}{\rightarrow} 616 \overset{ \times K}\rightarrow 728\overset{ \times A} \rightarrow 136 \overset{ \times I}\rightarrow 8\equiv2^{3}$
The steps needed for the first 34 primes are given as OEIS A007547 and the first 8102 products in the B-list for A007542.
The successive primes are produced almost like magic – but the number of multiplications needed to produce each new prime becomes larger and larger, and so the method, though wonderfully inventive, is not at all efficient.
Edit: Since this article was first published, the exponent $82589933$ of the Laroche prime has been accepted as the next term in the sequence http://oeis.org/A112634
There are many sequences of numbers to be found in Pascal’s triangle. The Natural numbers occur in the second diagonal, running in either direction, and the next two diagonals after that contain other important sequences:
This is the second in a series of guest posts by David Benjamin, exploring the secrets of Pascal’s Triangle.
There are many sequences of numbers to be found in Pascal’s triangle. The Natural numbers occur in the second diagonal, running in either direction, and the next two diagonals after that contain other important sequences: