Why Does this Algorithm Generate Primes?

Рет қаралды 10,102

Күн бұрын

The recurrence R(n) = R(n - 1) + gcd(n, R(n - 1)) generates primes. But why? It turns out it's essentially implementing trial division in disguise.
Previous video on this sequence: • In 2003 We Discovered ...
----------------
Reference:
Eric Rowland, A natural prime-generating recurrence, Journal of Integer Sequences 11 (2008) 08.2.8 (13 pages).
cs.uwaterloo.ca/journals/JIS/...
----------------
0:00 Generating primes
1:26 Shortcut
4:42 What if 2 n - 1 is prime?
9:31 What if 2 n - 1 isn't prime?
14:46 Trial division
----------------
Animated with Manim. www.manim.community
Music by Callistio.
Audio recorded at the Lawrence Herbert School of Communication at Hofstra University. www.hofstra.edu/communication/
Web site: ericrowland.github.io
Twitter: / ericrowland

Пікірлер: 40

@RSLT 4 ай бұрын

Nice to see a new video after quite some time.

@EricRowland 4 ай бұрын

Thanks! This one almost killed me 😂

@tcaDNAp 3 ай бұрын

I'm sure it's equally cathartic for the viewers and Eric to end without a cliffhanger this time! I never would've learned the meaning of this paper without the animations and explanation 👏

@tcaDNAp 3 ай бұрын

One of the only math research papers I have read was in the back of the Prime Suspects graphic novel, so thank you to all artists connecting math and media!

@_Wombat 3 ай бұрын

This style of video and explanation is really good. I appreciate how you constantly pause to run an example rather than always talking in terms of n, p and i. My brain needs examples to understand the algebra.

@EricRowland 3 ай бұрын

Thanks! I agree… Examples are essential!

@achrafidou537 4 ай бұрын

It's how unlikely that i rewatched the first part yesterday and now i find this

@mjorozco3786 4 ай бұрын

Exactly

@geoff_at_work 4 ай бұрын

Me too

@gabitheancient7664 3 ай бұрын

oh my god I love how elementary this all is, must have been really satisfying to figure this all out

@mebamme 4 ай бұрын

Dangit, right before I meant to call it a day. :D This will be the first video I'll watch tomorrow!

@emanuellandeholm5657 4 ай бұрын

You made me wait an entire year. Totally worth it!

@lynxfl 4 ай бұрын

He's back!

@burnstjamp 4 ай бұрын

Mind-boggling. The information here is presented beautifully!

@firozabegum4373 2 ай бұрын

Primes are my favourite. This video is really really great, I like it! Waiting for the next one.

@Ryloon 4 ай бұрын

Im so happy! Thank you for uploading

@gabitheancient7664 3 ай бұрын

oh damn I need to rewatch the previous video but damn great this video came out

@johnchessant3012 3 ай бұрын

Great proof!

@debmalyalodh1 2 ай бұрын

Welcome back

@sccur 3 ай бұрын

I am probably not understanding something, but it seems obvious to me that this sequence would generate primes in this manner having GCD as one of the operations and the rest basic arithmetic. And you can probably make a million different formulas with GCD that will have patterns generating primes. I am sure I just don't understand because I'm just finishing calculus, but what makes this interesting?

@mebamme 3 ай бұрын

You can sometimes get composite numbers if you start the sequence with a number other than 7. (the previous video explains it a little more.)

@keagangrahamcallis7857 3 ай бұрын

You're using smaller primes in a neat way to find bigger primes. Which is kinda what you always do; like q is a prime if all primes less than q don't divide into it. But that standard way requires you to know all the primes less than q. This way doesn't. I think...

@johndoyle2347 4 ай бұрын

Willans' Formula for primes: 2 to the n part = vertical asymptote and p-adic numbers. 1/n part = vertical tangent. Factorial part = vertical line. These tensors from differential calculus determine singularities in stable matter as represented as primes.

@drdca8263 4 ай бұрын

Sorry? This isn’t particularly clear

@johndoyle2347 3 ай бұрын

@@drdca8263 Yes. I am referring to "functions" in differential calculus that are continuous, yet not differentiable at points. There are 5 cases: a corner/cusp, which fits with dark matter singularities. A ring/cylinder/horn, which fits with singularities in baryonic matter. A vertical asymptote, a vertical tangent, and a vertical line, which are tensors that are involved in both keeping matter stable and are involved in Big Bounce events.

@drdca8263 3 ай бұрын

@@johndoyle2347 Vertical asymptotes aren’t continuous (unless, I guess, if you compactify the codomain?). They also are not tensors.

@DOTvCROSS 4 ай бұрын

@11:49 the reason for 'circular logic' 2n-1=2n-1 2n-1=(3-1)n-1+(i-i) 2n-1=3n-n-1+i-i 2n-1=3n+i-1-n-i 2n-1=(3n+i-1)-(n+i) Basic Algebra trick of adding and subtracting. Then put LHS and RHS into the same function, of course it is equal. Don't get lost in basic algebra. i is an ~'eigenvalue'~ on a 2n-1 plane maybe 'parameter' is a better word.

@disonaroaurelo 3 ай бұрын

Very simple but very useful content in number theory.

@disonaroaurelo 3 ай бұрын

I have a technique to obtain semi-random primes but in an increasing manner. Which is multiplying a number by 6.67-> 0.67 for 1 to 10; 6.7 from 10 to 100; 6.67 for 100 to 999; 6.667 to 1000 to 9999.The problem is that the numbers grow and you have to factor them in a common way. '--' Multiply only by multiples of 3. And it's okay, they come kind of randomly but increasingly, and they all come. My sieve is thick, it's a bad thing. Take everything, just the bulk! Skdkdndjndndj

@pizzarickk333 4 ай бұрын

Finally

@DeathSugar 3 ай бұрын

I wonder if this could be displayed as some kind of L function

@kaininjago6161 3 ай бұрын

YAY!

@hylens5111 4 ай бұрын

Did I miss it? Why does the sequence start with 7?

@EricRowland 3 ай бұрын

No great reason to start with 7, other than it's not too small. If you start with a number other than 7, you get similar behavior. I explored this a little in my other video on the topic: kzfaq.info/get/bejne/hdaRftOrsqyzoJs.html

@hylens5111 3 ай бұрын

Thank you!@@EricRowland