NemoClaw Knowledge Wiki

Constructive Proof of Arbitrarily Large Prime Gaps Using Factorials

4 min read

🗂️ Maths, Logic & Crypto · View mindmap

Constructive Proof of Arbitrarily Large Prime Gaps Using Factorials

Clip title: The Biggest Gaps Between Primes - Numberphile Author / channel: Numberphile URL: https://www.youtube.com/watch?v=oax6t6Of2WY

Summary

The Numberphile video “Gaps Between Primes” explores an intriguing aspect of prime numbers beyond their fundamental definition: the spaces, or “gaps,” between them. Beginning with a brief recap of primes as the indivisible building blocks of integers and confirming their infinite quantity, the discussion quickly pivots to the varying sizes of prime gaps. While concepts like “twin primes” (primes separated by a gap of two) represent exceptionally small intervals, the main question posed is whether there exist arbitrarily large gaps between prime numbers, or if these gaps are somehow bounded.

The host, Ben Sparks, aims to demonstrate a constructive proof that such arbitrarily large gaps do exist. Instead of merely asserting their existence, the goal is to provide a method to create a sequence of any desired number of consecutive non-prime numbers. This is distinct from finding the smallest such sequence but provides a concrete example for any chosen magnitude. Sparks illustrates this with an example, choosing to construct a list of nine consecutive non-primes.

The core of the proof lies in a clever application of factorials. For any given number n (representing the desired number of consecutive non-primes), one can construct a sequence starting from (n+1)! + 2, followed by (n+1)! + 3, and continuing up to (n+1)! + (n+1). Each number in this list is guaranteed to be composite. For instance, (n+1)! + 2 is divisible by 2 (since (n+1)! contains 2 as a factor, and 2 is divisible by 2). Similarly, (n+1)! + 3 is divisible by 3, and so on, until (n+1)! + (n+1) is divisible by (n+1). As each term is demonstrably divisible by a number other than one and itself (within the range of 2 to n+1), every number in this constructed sequence is composite, thereby forming a gap of ‘n’ consecutive non-prime numbers.

The conclusion is a powerful one: prime gaps can indeed be as large as one desires. This “constructive proof” means it’s not just a theoretical possibility; a specific sequence of composite numbers can be generated for any given length. However, it’s emphasized that this method produces very large numbers and does not necessarily yield the smallest such gap. The ability to guarantee arbitrarily long runs of non-primes has implications for prime-finding algorithms, suggesting that searching for primes by sequential testing could occasionally involve traversing vast stretches of composite numbers before encountering the next prime.

Video Description & Links

Description

Ben Sparks on why the gaps between primes can be as large as you imagine… More links & stuff in full description below ↓↓↓

See our playlist of videos about prime numbers - https://www.youtube.com/playlist?list=PL0D0BD149128BB06F Including this video which has previously covered the large gaps - https://www.youtube.com/watch?v=BH1GMGDYndo

More Ben on Numberphile: https://www.youtube.com/playlist?list=PLt5AfwLFPxWLDKmnxLg8477hrxY33LL6q

Ben Sparks: http://www.bensparks.co.uk/

Sparks Books…

We are also grateful for support from the Ben Delo Foundation - https://delo.org/

NUMBERPHILE

Videos by Brady Haran

Brady’s videos subreddit: http://www.reddit.com/r/BradyHaran/

Brady’s latest videos across all channels: http://www.bradyharanblog.com/

Tags

numberphile

URLs

YouTube Playlist URLs

Graph View