[00:00] Happy Halloween everybody. I got you these  mysterious 14 fractions. And it turns out   they encode all the prime numbers. That's  right. Infinitely many prime numbers in just   [00:12] 14 fractions. It's become a bit of a tradition  here at Standup Maths to have spooky ways of   generating prime numbers at Halloween. And  these are these fractions. My goodness. If   you pass these in order, so if you start  with 17 over 91, then you got 78 over 85,   [00:29] you got 19 over 51. I'm not going to read them  all out. Eventually, you work your way down to   17th and then 55 combination, as you can see,  opens a portal to the prime realm, which Oh,   [00:44] hey Skye. What's this? You want this? There you  are. Good girl. My dog. That seven took my dog. [00:59] Great. My dog is now in the prime realm. And I  haven't got that incantation from last time. So,   here's what we're going to have to do. We have to  understand why these 14 fractions give us all the   prime numbers. Use those to go to the prime realm.  Rescue my dog. You know, regular YouTube stuff.   [01:18] By the way, this video is brought to you by Jane  Street's multi-day insight program for women.   Applications are open now for the Hong Kong and  London offices. Right, let's explain how these 14   fractions give us all the prime numbers. Well,  they're actually a thing called Fractan. John   [01:33] Conway came up with a method where fractions  can do computations. And the way it works is   you start with an input number and we're going  to use two for our example. And then you find the   first fraction where you can multiply the input  by that fraction and get a whole number out the   [01:50] other side. If we set the two moving, it'll go  all the way down until ah here it is 15 on two.   That works. And then we multiply the input by the  fraction that gives a whole number. In this case,   [02:02] it gives us 15. And then we take that output 15.  We put it back in the top. And then we repeat.   We just keep scanning along with every new number  till we oh right to the end that time until we   [02:15] find something which will multiply the input and  give us a whole number and that becomes the new   input. And we do this over and over again. And if  you're thinking, well, hang on. I'm seeing a whole   bunch of ridiculous numbers. I mean 1,925 just  became 2275. When do we get to the primes? Well,   [02:32] if you pay very close attention, every time you  see a power of two, and the first one will happen   after 19 steps, the the exponent, the index on  the power of two, will list out sequentially   [02:48] all of the primes. So, in a moment, we'll see  four, which is two squared, and two is the first   prime. And then after 69 steps, we'll see 2 cubed  because three is the third prime. And then after   [03:02] 281 steps, I mean this is deeply inefficient.  We will finally see 2 ^ 5 when five is the third   prime number. And it just takes so long. But the  point is if you leave this system running, it will   [03:19] continue to churn out not only every prime without  missing any, but it won't give you any other   numbers in between. This exactly gives you all of  the primes in order. And I think we can forgive   [03:33] how inefficient it is by how just just ridiculous  that is. 14 fractions giving us the primes. Okay,   let's try to understand how a bunch of fractions  can do computation. In this case, they're doing   [03:48] a prime basically a divisibility civ to pull out  the primes. And this is what John Conway realized   originally inspired when the coats conjecture was  all the rage back in the middle of last century.   [04:03] So Conway was thinking about computations like  you know what I reckon you could recreate a full   computer that can do any calculation you want  using prime fractions if you're very clever with   your use of their prime factors. So, while this  machine has I've just left it running, as it's   [04:22] seeing now, like 1,650, what does that tell us?  Like, what is that keeping track of? Well, if   we also put in the prime factors of whatever the  active number is at any point in time, and I've   [04:37] listed them all the way up to the maximum possible  one. you will see that each time it goes through   a fraction, it's dropping some of their indices  and increasing other ones. If you think about it,   [04:52] every time you multiply by a fraction, you're  you're dividing by the bottom of the fraction,   the denominator, and you're multiplying by  the numerator. And that means whatever is in   [05:04] the denominator, you're incrementing those prime  factors in the active number down one each. And   whatever's in the numerator, you're incrementing  them up one each. Actually, it's a little more   [05:16] obvious if I switch to the prime factors of all  the numbers in the fractions. Okay, there we go.   So now I've split everything apart into its prime  factors so you can see. Uh so when 616 goes along,   [05:29] it's going to be processed by 11. So it's prime  factor 11 has its power go down by one. And that   time there, seven and 13 both went down by one.  And now this time 17's going down by one. Now   it's merely eight. Where's eight going to go?  Probably the two again. So now one of its twos   [05:45] goes down by one and three and five both go up by  one. And so what this computer actually is is a   series of values in registers. And every register  is just one of the prime factors. And actually,   [05:58] you know what? I'm going to switch to the super  fast version of this. Give me a moment. Okay,   look at it go. Right, this one super speedy. And  you can kind of see what's happening now. It's   cycling through all the different spots. And you  can see the various indices going up and down on   [06:13] the prime factors. And the first four of them  are actually keeping track of the divisibility   tests. Whereas the final five of them are just  flags. They all just flip between zero and one.   [06:28] And they're just there to keep track of how far  through the different cycles within the program   we are. So the whole thing it's just a computer  changing values in registers. Like it's just it's   [06:42] so good. like fundamentally like a step or two  above logic gates making a computer, you're just   shuffling numbers between registries and that's  what these fractions are doing. Oh, a bunch of   low ones then. That's what these fractions are  doing. I think it's super clever that you can   [06:58] put in these prime divisibility testing loops with  a bunch of extra ones as flags to keep track of   where you're up to. And when so when you're doing  the divisibility tests, if there are no factors,   [07:12] all the other values hit zero exactly. And that's  why you only read out the numbers when they're   powers of two and everything else is set to zeros  because all the other checks have cleared. And   [07:26] whatever number was stored in the two registry,  that's your prime. Now, if you want to skip this   bit, you have my full permission, but here is the  flowchart that helped me understand what's going   [07:38] on. And it's in the state at the moment where it's  just finished showing that four is not prime. So,   sure, it ended up on two to the four, but there's  still a one over here. They're not all zero. And   um what we do now is um first of all, and I can  click through this a step at a time. First of all,   [07:54] we move whatever our previous number m was from  registry 2 into three and five. So here you can   see we divide by two each time which takes two  down and we multiply by 15 which is increasing   [08:06] uh three and five. So you end up like that. So now  the four that was there is here and here. Then the   next step is we just clear registry 7. That's the  only thing that can be non zero actually at the   end of a previous calculation. Now previously it  was a power of two which is why it went all the   [08:21] way down here before it would activate a fraction.  Now it goes one further to 17th and that gets rid   of whatever's in the seventh position. And then uh  the last one, the 55 over one is just a way to set   [08:33] the 11 flags. Now 11 is flagged and increase  five by one. So I mean just so happens we're   Now here we hit the loop. First of all, we move  everything from register three over to register   [08:50] seven. And while we do that, if you watch 11  and 29 bounce backwards and forwards and they   one goes whenever we take down register 3 by one  and the other one goes up whenever we increase   [09:02] register 7. And if you wonder, well, why do we  need these? It's because we don't want this part   of the algorithm triggering every time there's  anything in three. Has to be something in three   [09:14] and something in 11 before that trips. But now  when register 3 is empty, we will overshoot all   of these fractions and we will activate 1113.  And that takes off the 11 flag and activates   [09:27] the 13 flag. And now we're in this big box here.  So this is a little confusing. What it's doing is   we're now seeing if four in the seven's registry  goes into five or not. And the way we do that is   [09:41] we move four into both two and three. It's always  destructive. You can't read something in Fractram   without destroying it. So, as you watch, seven  disappears very slowly and appears in both two   and three. At the same time, it decrements.  It takes down five as it moves over. And so,   [09:58] what you're initially doing is you're subtracting  the seven register from the five register. And   then, if the five register is not zero, you then  reset by moving whatever's in the three register,   [10:10] then gets moved back over to the seven register.  And then we subtract again. So now we've reset   that to be four. And once again, we move it over  and we subtract. Uh oh, nope. We've popped out   because we ran out of number on five. Then we  now know because five didn't zero out the same   [10:28] time as three, we reset everything back over  again. So if you watch, two gets copied back   into five to reset the number we're testing. And  then seven, the seven registry gets set to the   next number smaller. As you may have noticed, that  means we actually test every single number smaller   [10:44] than the main number we're looking at, which is  the most inefficient way to do it. And when I   say inefficient, I mean that seriously, here's how  long it takes to get up to the fifth prime number,   checking 11 is 750 steps alone, and you won't get  there until a total of 2375 steps. I mean, sure,   [11:02] you could do the, you know, square root and find  primes, but finding primes is what we're trying   to do. So, we don't get that for free. and the  square root algorithm would be complicated. And   the whole point of this algorithm is it's simple  and doesn't care how inefficient it is. Now,   [11:16] if you do this forever, eventually you will  check all the numbers smaller than it. And   the very final check, I've kind of skipped over  how it resets the next divisor. You can look at   this in detail if you want, but very eventually  you end up um over here. And at the very end,   [11:31] it checks if the seven is zero or not. And the  only time the seven register is zero when five and   three are both zero, which means they ran out at  the same time. And they only run out at the same   [11:43] time. And seven is zero if our divisor was one.  So if we get all the way to the end and it's not   zero, it means we had a different divisor that  wasn't one. It must be composite. If it's zero,   [11:55] it was prime. That's how it works. There's a 0%  chance you understand it from what I've just said.   you have to sit with it like I have for a long  time to get your head around it. But the point   is it's a very clever registry value algorithm  made entirely from fractions. So here's the   [12:12] thing. Frackran is cheuring complete. And I'm  aware that's a ridiculous sentence. Frackran is   a pun on forran which was hilarious like 50 years  ago. And then cheuring complete just means can run   [12:27] any computer algorithm. I'll put it that way.  And so the sentence fracturing complete means   a series of fractions with these rules can compute  anything. It can compute easy things. So actually   [12:41] the fraction just three on two that's an algorithm  that does addition. So if you want to add two   numbers I don't know a and b and you just do two  to the a* 3 to the b that's your original input.   [12:56] And the fraction three on two just gradually  subtracts from the two power and adds it to the   three power. Then eventually when you overshoot  the fraction because it's not divisible by two   anymore, you read off the answer the power of B  and that's your sum. But why just add when you can   [13:13] multiply? These six fractions are a fra program  that can multiply any two numbers together. Isn't   that ridiculous? Then the loops for multiplying  are basically the reverse of what we were trying   [13:26] to do before which was checking divisibility to  find prime numbers. Once you understand fraction   the numerator is the limit. We had a lot of  fun here at standup maths industries taking   [13:39] the world's oldest algorithm Uklid's algorithm  for finding the greatest common denominator.   So clever. Get two numbers. Replace the bigger  number by the difference between the two numbers.   and then repeat. It gives you the greatest common  denominator. Amazing. We turned it into Fractan,   [13:57] world's oldest algorithm in the world's most  ridiculous computation system. And of course,   someone has already made a Frack program which  processes Fractan. It's cuz if you're thinking,   [14:13] well, what does the Fractan run in? [music]  Turns out more Frackan. Jesse Jesse Bada made   a self frack um analyzer. So of course of course  that's happened. And also obviously there have   [14:28] been developments in generating primes with  frack. Conway's original 14 14 that's a bit   wasteful. Fractions is now down. Someone called  Devon Kilminster got it all the way down to a   [14:42] mere 10 fractions and then they were beaten by  themselves to nine fractions. That's the current   world record. I mean if you can write a Frack  program which can generate all the primes or it   [14:56] has to be all the primes and with nothing else in  the way in order. If you can do that, the smallest   fract prime algorithm award is yours. Put it in  the comments below. I want all the comments on   [15:11] this video to be exclusively in Fractan. Now, we  still have some important business to deal with   before we get too distracted by ridiculous Fractan  programs. For example, the one that generates the   digits of pi. Of course, that exists. These  40 fractions, deeply inefficient. If you   [15:28] turn the handle on this 775 times, you will have  calculated pi to three. It takes that long to get   the zeroth digit. Anyway, the point is I have to  go rescue my dog from the prime realm. And thanks   [15:42] to understanding Fractan, I have a new way to get  there. But even more importantly, I have to thank   the sponsor of this video, Jane Street. They work  solving complex problems in the financial world.   [15:54] And if you've been interested in the ridiculous  puzzles around using fractions to do computation,   my goodness, have I got a multi-day insight  program for you where you can learn about the   [16:06] specific concepts and tools that Jane Street use  in their daily work. If you've not heard of Jane   Street before, they are a quantitative trading  firm who use techniques from machine learning,   distributed systems, programmable hardware, and  statistics to trade on markets all around the   [16:22] world. And their insight program for women is  running out of the London and Hong Kong offices   with applications closing soon. And that's all  self-identifying women, transgender, any gender   expansive university students who want to attend.  Jane Street are committed to make sure as many   [16:37] people as possible have the chance to learn  more about working in quantitive finance. And   the program officers class and activities across  three separate strands. You got the trading and   research program, there's the software engineering  program, and the strategy and product program.   [16:51] No prior knowledge of finances necessary to apply,  only an interest in seeing what a career at Jane   Street might look like for you. And there's no  cost to participate since Jane Street will cover   all travel, meals, housing, and social events,  plus a daily allowance and all other program   [17:06] expenses. All the details are in the description  below or use the QR code on the screen. Now,   huge thanks to Jane Street for sponsoring this  and indeed so many of my videos. They're good   people. Oh, speaking of which, I've got a good dog  I have to go and rescue from the Prime Realm. So   [17:21] I guess I just say the fract fractions and off  I go. So here we go. 17 over 91. 78 over 85. Is   it working? 19 over 51 is working. 23 over 38.  39 over 33. There's so many. 77 over 29, etc.,   [17:35] etc., etc. I mean I It's getting brighter, so it  must be working. 11 over 13. It's like someone's   shining a light in my face and enjoying it more  than they should. All the way down to 55 over one. [17:49] Okay, it worked. Got to find my dog.  Skye. Skye. Wait. Oh, why this again?   Skye. Skye. I hate the prime realm. Skye,  where's Oh, where is she? Skye. Skye. Skye,   [18:04] where are you? Oh, come on. Where's Skye?  How far can a dog get? Skyab. Council [18:27] the best prime. I'm just here to find  my dog. Have you seen her? Thank you. [18:42] Who's that little girl? Oh, put it there. Now, I  got some bad news. I don't know how to get us out   of the prime realm. Oh, you got a plan. I guess  we just live in the prime realm now. I used to   [18:56] have a home address, but did I did I sell that on  eBay? Huh? What? Oh, come on. Can you just come   and go from the prime realm? Is this because you  ate that number two dogs? Hey, we're back. Good   [19:17] girl. You want this? There you go. That's for you.  Off you go. There you are. Okay. Well, thank you   for joining us on yet another Halloween adventure  here at Standup Math. Huge thanks to Haim Goodman   [19:29] Strauss, fantastic mathematician who I h caught  up with. I had lunch with them when I was at the   International Mathematical Congress and they told  me about Fractan. I had never heard of it before.   Absolutely amazing. So, huge thanks to them. I'll  link to their work below. They were part of the   [19:44] a dog now crunching. Huge thanks to Skylab who  has been very well remunerated for [music] her   role in this video. I think she may have had  her own body weight and treats over the course   [19:58] of filming this video. Uh and thank you so much  everyone for watching his videos. Huge thanks to   Jenry as always. We'll see you at the next uh  you know tenuous holiday justification for a