---
title: 'FRACTRAN: 14 fractions that produce infinite primes'
source: 'https://youtube.com/watch?v=zuaVFnj4SWY'
video_id: 'zuaVFnj4SWY'
date: 2026-10-31
duration_sec: 1212
channel: 'Stand-up Maths'
---

# FRACTRAN: 14 fractions that produce infinite primes

> Source: [FRACTRAN: 14 fractions that produce infinite primes](https://youtube.com/watch?v=zuaVFnj4SWY)

## Summary

In this Halloween special, Matt Parker of Standup Maths explores FRACTRAN, a Turing-complete programming language invented by John Conway that uses just 14 fractions to generate all prime numbers. The video explains how FRACTRAN works, demonstrates its computational power, and humorously frames the explanation as a quest to rescue his dog from the 'prime realm'.

### Key Points

- **The 14 Fractions** [00:00] — The video introduces 14 mysterious fractions that encode all prime numbers. Starting with 17/91, these fractions, when applied in sequence, eventually produce powers of two whose exponents are the primes.
- **How FRACTRAN Works** [01:33] — FRACTRAN is a method by John Conway where you start with an input number, find the first fraction that multiplies to a whole number, and repeat. Each step updates the input, and powers of two appear at specific steps, revealing primes.
- **Computational Power** [03:48] — FRACTRAN is Turing-complete, meaning it can run any algorithm. It works by using prime factors as registers, incrementing and decrementing exponents to perform computations.
- **Registers and Flags** [05:45] — The system uses prime factors as registers. Some registers track divisibility tests, while others act as flags to control program flow. The algorithm checks divisibility by subtracting and resetting values.
- **Flowchart Explanation** [07:38] — A flowchart helps visualize the algorithm. It shows how the program moves values between registers, tests divisibility, and determines if a number is prime by checking if the divisor reaches zero.
- **Inefficiency and Simplicity** [11:16] — The algorithm is extremely inefficient, checking every number smaller than the candidate. For example, reaching the fifth prime takes 2375 steps. However, its simplicity is its strength.
- **FRACTRAN Programs** [12:12] — FRACTRAN can perform arithmetic like addition and multiplication. For instance, the fraction 3/2 adds numbers, and six fractions can multiply. Even the oldest algorithm, Euclid's algorithm, can be implemented.
- **Optimizations and Records** [14:28] — Conway's original 14 fractions have been reduced. Devon Kilminster got it down to 10, then 9 fractions, the current world record. There's also a FRACTRAN program that generates digits of pi.
- **Sponsor and Conclusion** [15:42] — The video is sponsored by Jane Street, a quantitative trading firm. The sponsor segment highlights their insight program for women. The video concludes with a humorous rescue of the dog from the prime realm.

### Conclusion

FRACTRAN is a fascinating demonstration of how simple fractions can perform complex computations, including generating all primes. Despite its inefficiency, it showcases the elegance of mathematical algorithms and the power of Turing-complete systems.

## Transcript

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