Why Does this Algorithm Generate Primes?
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
Nice to see a new video after quite some time.
@EricRowland
4 ай бұрын
Thanks! This one almost killed me 😂
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!
He's back!
Dangit, right before I meant to call it a day. :D This will be the first video I'll watch tomorrow!
You made me wait an entire year. Totally worth it!
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
4 ай бұрын
Thanks! I agree… Examples are essential!
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
Mind-boggling. The information here is presented beautifully!
oh my god I love how elementary this all is, must have been really satisfying to figure this all out
Im so happy! Thank you for uploading
Primes are my favourite. This video is really really great, I like it! Waiting for the next one.
oh damn I need to rewatch the previous video but damn great this video came out
Great proof!
Welcome back
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
4 ай бұрын
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
4 ай бұрын
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...
Finally
YAY!
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
4 ай бұрын
@@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
4 ай бұрын
@@johndoyle2347 Vertical asymptotes aren’t continuous (unless, I guess, if you compactify the codomain?). They also are not tensors.
@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
4 ай бұрын
Very simple but very useful content in number theory.
Did I miss it? Why does the sequence start with 7?
@EricRowland
4 ай бұрын
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: kzread.info/dash/bejne/gaSVrdKzfam1oMo.html
@hylens5111
4 ай бұрын
Thank you!@@EricRowland
I wonder if this could be displayed as some kind of L function
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
DAMN THIS MUSIC IS SO FIREEEE
Manim! (Or whatever it's called)!
Could you write an example program in Java using normal integers and BigInteger class?
a
*promosm*