[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