Why Does this Algorithm Generate Primes?
ฝัง
- เผยแพร่เมื่อ 31 พ.ค. 2024
- 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
Nice to see a new video after quite some time.
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 👏
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!
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.
Thanks! I agree… Examples are essential!
It's how unlikely that i rewatched the first part yesterday and now i find this
Exactly
Me too
oh my god I love how elementary this all is, must have been really satisfying to figure this all out
You made me wait an entire year. Totally worth it!
Dangit, right before I meant to call it a day. :D This will be the first video I'll watch tomorrow!
He's back!
Mind-boggling. The information here is presented beautifully!
Primes are my favourite. This video is really really great, I like it! Waiting for the next one.
Im so happy! Thank you for uploading
oh damn I need to rewatch the previous video but damn great this video came out
Great proof!
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?
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.)
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...
Welcome back
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.
Sorry? This isn’t particularly clear
@@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.
@@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.
Very simple but very useful content in number theory.
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
Did I miss it? Why does the sequence start with 7?
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: th-cam.com/video/OpaKpzMFOpg/w-d-xo.html
Thank you!@@EricRowland
YAY!
I wonder if this could be displayed as some kind of L function
Finally
Manim! (Or whatever it's called)!
Could you write an example program in Java using normal integers and BigInteger class?
DAMN THIS MUSIC IS SO FIREEEE
a
*promosm*