Skip to main content
Loading Explore guides…
Prime Generating Recurrence · Acedra
Home
Explore
Mathematics
Prime Generating Recurrence
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
69 segments
Copy
Hide video
0:00
This is a recurrence that generates primes. It defines a sequence where the nth term R(n) is the previous term R(n - 1) plus the greatest common divisor of n and the previous term. You can think of it as a warped version of the Fibonacci recurrence, where the nth term is the previous term plus the term before that. One big difference though, is that, for the Fibonacci sequence, we need two initial terms to get things going, since each later term depends on two previous terms.
0:28
But for the sequence R(n), we only need one initial term. Let's start off by choosing it to be 7. This is mostly arbitrary, so we'll come back to this later and explore other options. But with the initial term 7, the second term is 7 plus the gcd of 2 and 7.
0:45
The gcd is 1, so we get 8. The third term is 8 plus the gcd of 3 and 8. This gcd is also 1, so we get 9.
0:57
The next gcd is the gcd of 4 and 9, which is also 1. So at the fourth term, we also step up by 1, to 10. The terms so far are 7, 8, 9, and 10. So far this is a pretty boring sequence! But now something interesting happens, because the gcd of 5 and 10 is 5, so here the sequence jumps up by 5 rather than 1. The next gcd is the gcd of 6 and 15, which is 3, so the sequence jumps up again, this time by 3. Then we go back to stepping up by 1 for a few terms.
1:31
And we reach the bottom of the frame, so let's make room for more terms. This sequence was discovered in 2003 when Stephen Wolfram initiated several experiments exploring the space of possible recurrences. Initially, what seemed to be remarkable about this sequence is that it exhibits long stretches of boring behavior, interrupted by sudden jumps, and it's not obvious that we can predict the jumps in advance. But even more surprising is what the jumps are doing.
1:57
Let's look at the gcds on their own, because they determine whether the terms of the sequence are increasing by 1 or making a jump. Collecting the gcds into their own sequence makes the behavior a little easier to see.
2:10
Let's gray-out the boring 1s and include some more data.
2:16
Notice anything?
2:18
Let's be really drastic and remove the 1s entirely.
2:24
Here's even more data.
2:30
Surprisingly, all these numbers are prime.
2:34
Remember that they are gcds, so it's not crazy that they have something to do with divisibility, but why on earth are they necessarily prime? Pause the video if you'd like to stare at these primes for a bit, because there are some patterns that may jump out if you look at them long enough. If you see something, let me know in the comments which numbers first gave it away. This way, we can do a little psychology experiment and see whether the same numbers jump out to most people.
2:58
For me, here's what jumps out first. 60647 is very close to 2 times 30323.
3:07
In fact they're just off by 1.
3:10
There are other pairs like this too. 2 * 5 + 1 is 11. 2 * 11 + 1 is 23.
3:18
And 2 * 23 + 1 is 47. Unfortunately, this pattern doesn't continue, since 2 * 47 + 1 is 95, which doesn't appear and also isn't prime. But there are several other pairs sprinkled across the data that do satisfy this doubling relation. Why does it work in certain places and not others? Also, why is there a 3 sandwiched between each pair? And again, why are all these numbers prime? This was the state of things in 2003; no one knew. I had just graduated from college.
3:51
I was eager to prove an interesting new result about primes, so I worked on this sequence for a bit but didn't get anywhere. But several years later, I had an idea to try something I hadn't thought of before. To see what's going on with this sequence, it turns out that we need some information that we threw away. So let's put the primes back in their positions and bring back all the 1s.
4:13
The information we shouldn't have thrown away is the index n corresponding to each of these gcds. After all, each gcd is the gcd of n and R(n - 1). Now we can safely throw away the 1s again.
4:29
My idea was to make a plot of this data, but ignore the primes themselves and only plot the index n where each prime appears, so that's 5, 6, 11, 12, and so on.
4:44
Since there are many 1s in the sequence of gcds, this sequence -- the indices of gcds that aren't 1 -- grows quite quickly. To fit more data onto this plot, we need to rescale the vertical axis.
4:57
Now the next few values of n fit. We can even include a bit more data.
5:04
But by rescaling to include more data, we lost some visual information about the first few values, because now they're all bunched together at the bottom of the plot. The solution is to rescale the vertical axis again -- not in a linear way like we just did, but in a logarithmic way. Ordinarily, the distance between 1000 and 2000 on the vertical axis is the same as the distance between 2000 and 3000. What we'll do is rescale
5:31
so that the distance between 10 and 100 is the same as the distance between 100 and 1000. This is called a logarithmic scale, so the plot becomes a logarithmic plot. It's called "logarithmic" because now it's the logarithms of 1, 10, 100, and so on that form a linear sequence. This is true for any choice of the base of the logarithm, but for example the base-10 logarithms are 0, 1, 2, and so on. Logarithmic scales are used in some settings you're already familiar with.
6:00
For example, the Richter scale describes earthquake intensities on a logarithmic scale. The possible amount of energy released by an earthquake covers such a large range that the logarithm of the energy is a more intuitive number to work with. So, instead of having earthquakes with magnitude 10,000 and magnitude 1,000,000,000, we call them magnitude 4 and magnitude 9. Getting back to our primes, this log plot of the indices where primes appear reveals that the primes appear in clusters.
6:29
This really surprised me. And not only that, but the spacing between clusters is extremely even. If we average the indices in each cluster, the vertical distances between the averages appear to be the same. If this were an ordinary plot, then adding that vertical distance to one cluster would give the location of the next cluster. But since this is a log plot, a fixed vertical distance corresponds to multiplication by some constant, not addition. So the location of each cluster is given by
6:59
some constant times the location of the previous cluster. To guess the constant, we should divide neighboring cluster averages by each other. So let's rearrange the primes according to their clusters
7:11
and compute the cluster averages numerically.
7:14
Now divide them. The first ratio is roughly 2.09, the second is 2.04, and here are the others. They're not quite equal to each other, but they're all close to 2. This means that the long runs of 1s separating clusters roughly double in length from one to the next. In hindsight, we saw evidence of this already. If we look at the beginning of each cluster, we see the doubling relations we found earlier. Apparently 5 produces 11, 11 produces 23, 23 produces 47, and so on.
7:48
But the doubling relations only reliably predict where some of the clusters begin, not all. For example, where does 101 come from? Since the runs of 1s separating clusters roughly double in length, we know it should be roughly twice 47, but how do we get it exactly? Well, this plot suggests something else. Maybe we shouldn't be using the beginning of a cluster to get the next cluster, like the doubling relations suggested.
8:11
Since the primes within a cluster are close together, why not try using the end of a cluster to get the beginning of the next cluster? So instead of trying to get 101 from 47, can we get it from the previous prime, 3? Not in an obvious way, but 101 is suspiciously close to 2 * 51. In fact 2 * 51 - 1 is 101. Perfect! But wait; to predict the beginnings of other clusters, we were using the primes, not their indices, so it's unfortunate that this cluster seems to be different
8:44
in that 101 comes from 51 and not 3. But at the beginning of each cluster, each prime gcd seems to be equal to the index where that prime appears. If that's true in general, then the doubling relations describe not just the primes but also their indices, and maybe it's a relation among their indices that generalizes. For the earlier clusters, we can get 11 from the index 6 at the end of the previous cluster. 23 comes from 12. And 47 comes from 24.
9:15
For the later clusters, 233 comes from 117, 467 comes from 234, 941 comes from 471, and so on. This seems to be a reliable way to predict when each cluster begins. So the doubling relations involving primes were misleading. It's not that the first prime in a cluster comes from an earlier prime; it comes from the index of the previous prime. Specifically, the first prime in each cluster is 2 n - 1, where n is the index of the previous prime. What about within a cluster?
9:50
Let's take a look at this big cluster, beginning with 101. At index 101, if we try the same formula, we get 201, and the prime we want is 3. That's not promising! But let's not give up quite yet. At index 102, we get 203, and the prime we want is 7. Here are the rest.
10:14
Since we're expecting primes, are the numbers we're getting in fact primes? No, 201 is not prime; it's 3 times 67. Here are the prime factorizations of the others.
10:26
Now we see what appears to be going on. The prime we're looking for in each case isn't 2 n - 1; it's the smallest prime divisor of 2 n - 1. This even works at the beginning of the cluster, where we got 101. 101 is prime, so its smallest prime divisor is itself. Apparently this is how we can predict not just the beginning of each cluster of prime jumps but every prime jump the sequence undergoes. Isn't that beautiful? So here's our conjecture.
10:54
If the gcd of n and R(n - 1) is not 1, then the next nontrivial gcd that appears, that is, the next gcd that is not 1, is the smallest prime divisor of 2 n - 1. Let's call it p.
11:11
When does this next nontrivial gcd appear? In other words, if we're currently at index n, then running the recurrence will take us to n + 1, n + 2, and so on, and we want to know the smallest value of i for which the gcd at n + i is the prime p.
11:28
Going from 51 to 101 is an increase of 50. 101 to 102 is an increase of 1. Then we have an increase of 3, then 5, then 1, then 6. Can we tell what i is in advance, without computing all the intermediate steps using the recurrence? The hint is to look at the value of p.
11:55
It looks like i is (p - 1)/2.
11:58
Great! So we think we know what the next nontrivial gcd is and also where it appears. That means we have a shortcut for computing the sequence of gcds. This shortcut lets us jump directly from one prime gcd to the next, skipping over all the 1s. Let's check that it correctly generates the cluster beginning with 467. Suppose we're at n = 467, and pretend that we don't know what the next nontrivial gcd is or where it appears.
12:27
According to the conjecture, we should determine the smallest prime divisor of 2 n - 1. 2 n - 1 is 933, which factors as 3 times 311. The smallest prime divisor is 3, so the next nontrivial gcd that appears is 3. To find out when we'll reach this 3, we compute i, which is (3 - 1)/2.
12:50
So we'll see the gcd 3 one step later, during the computation of R(468). Checks out so far. Now let n be 468. 2 n - 1 is 935, whose smallest prime divisor is 5. So now i is 2, and the next nontrivial gcd appears 2 steps later, during the computation of R(470). If we keep going, when n is 470, 2 n - 1 is 939. Its smallest prime divisor is 3, and the next nontrivial gcd appears 1 step later.
13:26
When n is 471, 2 n - 1 is 941. 941 is prime, so the next nontrivial gcd appears 470 steps later. This is a long run of 1s, so 941 marks the beginning of a new cluster. The conjecture is able to reproduce this cluster exactly! But is it true in general? To determine that, we need one final observation. We've been able to compute the sequence of gcds without actually knowing any terms of the original sequence R(n). But let's look at the values of R(n) for this cluster.
13:59
If you compute them using the recurrence, you'll find that R(467) is 1401. By continuing to iterate the recurrence, we can compute these other values.
14:10
Do you see the pattern? Here's a hint.
14:15
In all cases, R(n) is exactly 3 times n. This is the last key piece of information that explains why this recurrence generates primes. It turns out that, whenever we're in a situation where R(n) is 3 n, that is, the value of the sequence is 3 times its own index, then, when we advance the recurrence by (p - 1)/2 steps, we end up in another situation where the value of the sequence is 3 times its index. So this puts us right back in the situation we started in,
14:46
which means we can advance the recurrence again by a known amount and end up again in a situation where the value of the sequence is 3 times its index. And over and over and over, returning to the same nice situation at every step.
14:58
So if we can also establish that the first two parts of the conjecture are true whenever we're in that nice situation, then we'll be able to conclude that this sequence generates primes. The details will take a little more time to explain than I want to spend in this video, but it's quite fun to see exactly how this all works, so we'll go through them in my next video. For now, suffice it to say that this conjecture is a theorem. This theorem lets us answer several questions.
15:24
First, it shows that, yes, this recurrence does generate primes. But if you're trying to discover large primes, is this a good way to do it? No, running the recurrence is actually a pretty bad way to discover large primes. When the gcd is a prime p, that gcd shows up only after (p - 1)/2 steps where the gcds are all 1, which is quite a lot of steps. For example, suppose we wanted to find a 10-digit prime.
15:50
Every 10-digit prime is between 1 billion and 10 billion, so we'd have to run the recurrence for at least 500 million steps before seeing a 10-digit prime.
16:01
But there's no need for that, you might say. The theorem gives us a shortcut for running the recurrence, right? If we just use that shortcut, we can skip those 500 million 1s and go directly to the next prime. Well yes, but to run the shortcut, we have to compute the smallest prime divisor of 2 n - 1. If 2 n - 1 turns out to be the large prime we're trying to find, then the shortcut requires us to first determine that it is prime
16:25
before we know that it's the next nontrivial gcd and therefore prime. So the shortcut is no help here, because to use it we need an independent way to test primality before we can conclude that the recurrence produces a given number as a gcd.
16:41
The theorem also explains why the primes appear in clusters. The reason is that when 2 n - 1 isn't prime, then its smallest prime divisor p is quite small relative to n, so the run of 1s we pass through before reaching the next nontrivial gcd is quite short. But when 2 n - 1 happens to be prime, the number of 1s we pass through is (2 n - 1 - 1)/2, which is n - 1. This run of 1s is much longer than its neighbors, so the next nontrivial gcd starts a new cluster.
17:14
Since we're generating primes, a natural question is: Which primes appear? Does the recurrence eventually generate all primes? Well, the prime 2 is conspicuously absent. This is because 2 n - 1 is odd, so its smallest prime divisor will never be 2. Other than that, I don't know how to rule out any primes. After 10,000 applications of the shortcut, the smallest prime other than 2 that has not yet appeared is 587. Granted this is not a ton of evidence, since 587 is only the 107th prime,
17:44
so there may be a lot more to say on the matter. In 2011, Chamizo, Raboso, and Ruiz-Cabello made some progress by proving that infinitely many distinct primes do appear.
17:55
The one pattern we haven't explained yet is why each pair of primes involved in a doubling relation sandwiches a 3 between them. If we look back at the clusters, we can see that we can actually strengthen this to say that in every cluster the second prime is 3. Since the theorem tells us how to go directly from one prime to the next, it is possible to explain this, but I'll leave it to you to find the reason.
18:19
Let's finish with some variations.
18:22
Define a sequence s(n) using the same recurrence, but instead of starting with 7 for the initial term, what if we start with 1?
18:31
The first gcd is 1, so we get 2.
18:34
The second gcd is 1, so we get 3.
18:38
The third gcd is 1, so we get 4. In fact every gcd is 1, since the gcd of n and n - 1 is 1. So this sequence is really boring. If we change the initial term to 2 or 3 instead, the sequences we get are also not interesting. When we use the initial term 4, the first gcd is 2, so s(2) is 6. The next gcd is 3, so s(3) = 9. But guess what. R(3) this is also 9, so from this point on the sequence is exactly the same as the sequence with initial term 7.
19:16
If you look hard enough though, you do find some genuinely new behavior. With the initial term 532, we get a gcd of 2, then a gcd of 3, then some 1s,
19:30
then 13, 1, 5, 1, 1, and -- surprise surprise -- a non-prime!
19:39
So far, this sequence hasn't ever been in the nice situation where the nth term is 3 times n, so the theorem doesn't apply and we're not guaranteed to get primes. Eventually we do get there, however: s(279) is 3 times 279. From that point on, all the gcds will be primes or 1s. It seems likely that, if you start with any initial condition that's at least 4, then this will eventually happen. But this is still an open question.
20:08
Shortly after my paper appeared, Benoit Cloitre looked at an interesting variant that we'll call C(n). He replaced the greatest common divisor with the least common multiple. Starting with the initial term 1, we don't get a boring sequence. The first lcm is 2.
20:25
The next lcm is 3. The lcm is never 1 here, since the lcm of n and C(n - 1) is divisible by both n and C(n - 1). Here's some more data.
20:43
Obviously the lcms aren't primes, so this sequence doesn't generate primes in the same way. But, because the lcm is divisible by the previous term and then we're adding the previous term, this means that the nth term C(n) is divisible by the previous term. For example, C(5) is the previous term, 18, plus the lcm of 5 and 18. So C(5) is divisible by 18. So it makes sense to look at the ratio C(n) divided by C(n - 1). This is equal to 1 plus the lcm divided by C(n - 1).
21:19
Let's subtract 1 from this ratio, so that we're looking at the value obtained by dividing the lcm by the previous term. Let's compute some of these values.
21:32
Astonishingly, this number is apparently always prime or 1! And no one has proved this or found a counterexample yet. There's good reason to think that this is much harder than proving that the sequence R(n) generates primes. In 2015, Ruiz-Cabello showed that it's related to a difficult open question about primes in arithmetic progressions. I'll leave a link to the paper in the description, so you can check it out if you're interested.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat