In 2003 We Discovered a New Way to Generate Primes

TL;DR

A recurrence sequence that generates primes by adding the greatest common divisor (gcd) of two terms is analyzed, revealing patterns and properties.

Transcript

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 tha... Read More

Key Insights

• 🫰 The sequence generates primes by adding the gcd of the index and the previous term, with the jumps determined by the smallest prime divisor of 2n-1.
• 🏃 The primes appear in clusters, and the length of the runs of 1s between clusters is related to the size of the smallest prime divisor.
• 👻 A shortcut formula allows for efficient computation of the sequence, skipping the 1s in each cluster.
• 🍉 The initial term choices and variations of the sequence, such as using lcm instead of gcd, have different properties and behaviors.
• #️⃣ The sequence does not include the prime number 2.
• 👨‍🔬 The computation of the sequence and understanding the patterns of primes generated by the recurrence sequence are ongoing research topics.

Questions & Answers

Q: How does the recurrence sequence for prime generation work?

The sequence starts with an initial term and each subsequent term is obtained by adding the gcd of the index and the previous term. The jump to the next nontrivial gcd (not equal to 1) is determined by the smallest prime divisor of 2n-1.

Q: Why are all the gcds of the sequence prime numbers?

The gcds are related to the smallest prime divisors of 2n-1. In the nice situation where the value of the sequence is 3 times its index, the recurrence generates primes as the next nontrivial gcds.

Q: Can this recurrence sequence be used for prime discovery?

While the sequence generates primes, running the recurrence is not an efficient way to discover large primes. The shortcut formula requires determining primality independently before using it to skip the 1s in the sequence.

Q: What variations and related sequences have been explored?

Variations include starting with different initial terms and replacing the gcd with the least common multiple (lcm). The sequence with lcm generates terms that are always divisible by the previous term, and a separate open question involves the divisibility of the lcm by the previous term.

Key Insights:

• The sequence generates primes by adding the gcd of the index and the previous term, with the jumps determined by the smallest prime divisor of 2n-1.
• The primes appear in clusters, and the length of the runs of 1s between clusters is related to the size of the smallest prime divisor.
• A shortcut formula allows for efficient computation of the sequence, skipping the 1s in each cluster.
• The initial term choices and variations of the sequence, such as using lcm instead of gcd, have different properties and behaviors.
• The sequence does not include the prime number 2.
• The computation of the sequence and understanding the patterns of primes generated by the recurrence sequence are ongoing research topics.
• The relationship between the recurrence sequence and the distribution of prime numbers in arithmetic progressions is a challenging open question.

Summary & Key Takeaways

• The recurrent sequence starts with an initial term and each term is the previous term plus the gcd of the index and the previous term.

• The sequence exhibits repetitive stretches of 1s interrupted by sudden jumps, with the jumps being determined by the smallest prime divisor of 2n-1.

• The sequence shows clusters of primes, and a shortcut formula allows for efficient computation of the sequence.