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

  • @RSLT
    @RSLT4 ай бұрын

    Nice to see a new video after quite some time.

  • @EricRowland

    @EricRowland

    4 ай бұрын

    Thanks! This one almost killed me 😂

  • @tcaDNAp
    @tcaDNAp3 ай бұрын

    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

    @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!

  • @lynxfl
    @lynxfl4 ай бұрын

    He's back!

  • @mebamme
    @mebamme4 ай бұрын

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

  • @emanuellandeholm5657
    @emanuellandeholm56574 ай бұрын

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

  • @_Wombat
    @_Wombat4 ай бұрын

    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

    @EricRowland

    4 ай бұрын

    Thanks! I agree… Examples are essential!

  • @achrafidou537
    @achrafidou5374 ай бұрын

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

  • @mjorozco3786

    @mjorozco3786

    4 ай бұрын

    Exactly

  • @geoff_at_work

    @geoff_at_work

    4 ай бұрын

    Me too

  • @burnstjamp
    @burnstjamp4 ай бұрын

    Mind-boggling. The information here is presented beautifully!

  • @gabitheancient7664
    @gabitheancient76644 ай бұрын

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

  • @Ryloon
    @Ryloon4 ай бұрын

    Im so happy! Thank you for uploading

  • @firozabegum4373
    @firozabegum43733 ай бұрын

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

  • @gabitheancient7664
    @gabitheancient76644 ай бұрын

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

  • @johnchessant3012
    @johnchessant30124 ай бұрын

    Great proof!

  • @debmalyalodh1
    @debmalyalodh12 ай бұрын

    Welcome back

  • @sccur
    @sccur4 ай бұрын

    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

    @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

    @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...

  • @pizzarickk333
    @pizzarickk3334 ай бұрын

    Finally

  • @kaininjago6161
    @kaininjago61614 ай бұрын

    YAY!

  • @johndoyle2347
    @johndoyle23474 ай бұрын

    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

    @drdca8263

    4 ай бұрын

    Sorry? This isn’t particularly clear

  • @johndoyle2347

    @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

    @drdca8263

    4 ай бұрын

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

  • @DOTvCROSS
    @DOTvCROSS4 ай бұрын

    @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

    @disonaroaurelo

    4 ай бұрын

    Very simple but very useful content in number theory.

  • @hylens5111
    @hylens51114 ай бұрын

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

  • @EricRowland

    @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

    @hylens5111

    4 ай бұрын

    Thank you!@@EricRowland

  • @DeathSugar
    @DeathSugar4 ай бұрын

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

  • @disonaroaurelo
    @disonaroaurelo4 ай бұрын

    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

  • @_eagle_299
    @_eagle_2994 ай бұрын

    DAMN THIS MUSIC IS SO FIREEEE

  • @SpinnyDisk
    @SpinnyDisk3 ай бұрын

    Manim! (Or whatever it's called)!

  • @kristofferpaulssonmisc2195
    @kristofferpaulssonmisc21954 ай бұрын

    Could you write an example program in Java using normal integers and BigInteger class?

  • @j.21
    @j.214 ай бұрын

    a

  • @marti7716
    @marti77163 ай бұрын

    *promosm*