Infinite Fractions (extra footage)

[@TheAngelsHaveThePhoneBox]

- Bender, what is it? - Whoa, what an awful dream. Ones and zeros everywhere. And I thought I saw a two. - It was just a dream, Bender. There's no such thing as two.

[@lauralynnasteriahathaway6819]

If you look hard enough, you can actually see the two in Bender's nightmare.

[@Kompre]

So, since the main channel logo is pi, should this channal logo be tau?

[@bluepaint9923]

Ha, I agree :-D

[@MaxJNorman]

Yes!

[@wyattstevens8574]

Yes!

[@ShaunakDesaiPiano]

“I’m Shaunak Desai and I think what Kompre said is ridiculous”

[@CastorQuinn]

"Maybe deep below the mathematical surface ... deeper than we've ever explored there is some fundamental link ... the same bit of mathematical truth. That's what I love about maths." Of all the times Matt's explained why he so loves maths, this is the best.

[@JacobShepley]

love his enthusiasm :P

[@KasabianFan44]

I know right! His enthusiasm makes me enthusiastic myself :D

[@ImAllInNow]

So the problem of drunken binary numbers that use 2's is equivalent to the following problem: How many ways are there to get from 0 to n by adding powers of 2 such that each power of 2 can only be used at most twice. Call this Db(n). To find Db(n), there are two cases to consider, if n is odd or n is even. If n is odd, say 2m+1, then you have to add 2^0 exactly once (since it's the only power of 2 that's an odd number). So taking away that add, we're left with an even number, 2m, and need to find the number of ways to get there using powers of 2 greater than 2^0. So if we divide that number by 2, then it will be a previous instance of our original problem. So Db(2m+1) = Db(m). If n is even, say 2m, then there are again two cases. Either 2^0 is added zero times, or twice. If it is added 0 times, then by dividing 2m by 2, we get a previous instance of our problem. If it is added twice, then dividing 2m-2 by 2, we get a previous instance of our problem. So by adding these two cases together, we get the total number of possibilities. So Db(2m) = Db(m) + Db(m-1). Since this definition is recursive, we need the base cases. For n=0 and n=1, there is 1 way to get from 0 to n. So Db(0) = 1 and Db(1) = 1. So the full definition is as follows: Db(0) = 1, Db(1) = 1, For m = 1..infinity, Db(2m) = Db(m) + Db(m-1) Db(2m+1) = Db(m) This is the exact process that Matt uses to generate the numbers in the first place (adding two numbers together and then tacking on the latter of the two numbers) and shows that this sequence is exactly the sequence in the above video.

[@ghhfhhhhh]

Correct. Also, if you take up competitive programming (or maybe just programming which I'm think you do) the method you just said was a top-down dynamic programming (dp) approach. The sequence generated is just a bottom-up dp approach. Imagine a number n, whose number of ways can be expressed by the drunken binary thing is i. Therefore, the number 2n+1 will have the same number. Same goes for another number n and n+1. This two added up will result in the case of if the original number is even. So instead of taking a number and simplifying it, we take a number and use to calculate greater numbers. This is essentially what the original sequence is. Db(n)+db(n+1) = db(2n + 2) / db(n + 1)=db(2n+3). So it IS RELATED AFTER ALL AND THIS IS THE LINK (In laymans term, I simplified the function that the guy above posted. Therefore now, if you take a number n and the number n+1, which are the pair in the sequence, and you add them to the back which is at position 2n+2 and 2n+3, you get both the original sequence as well as why the drunken binary thing works Cheers I really do hope someone reads this

[@Magnasium038]

Awesome; such a simple connection

[@conoroneill8067]

For anyone who watches this from in the future, this also proves why the fraction formed by dividing one number by the other in the sequence it will exist in it's most simplified form. This is equivalent to saying that Db(k) has a maximum coprime factor of 1 with Db(k+1). Now, either way, one of k, k+1 is even, and we can apply the recursive formula to both. They'll have a common term of Db(m) or Db(m-1) (depending on whether the first or second was odd), which can be subtracted off without changing how relatively coprime both numbers are. This gives us the same problem back again, but further towards the start of the sequence. We can apply this recursively till we get back to Db(0), and Db(1), which are both 1, so obviously have a maximum coprime factor of 1.

[@conoroneill8067]

I don't know why we can't have repeats, though.

[@WriteWordsMakeMagic]

​@@conoroneill8067 I bet you can prove we can't have repeats by contradiction. Assume there are two indicies m and n in this sequence where Db(m) = Db(n) and Db(m+1) = Db(n+1) and m != n and show there's a contradiction.

[@msclrhd]

Looking at the position each number occurs in the sequence ... The 1s occur at positions 1,3,7,15,31,.... Adding 1 gives 2,4,8,16,32,.... Divide that by 2 gives 1,2,4,8,16,... which is 2^(n-1). Therefore, the 1s occur at position 2(2^(n-1))-1. The 2s occur at positions 2,5,11,23,.... Adding 1 gives 3,6,12,24,.... Divide that by 3 gives 1,2,4,8,... which is 2^(n-1). Therefore, the 2s occur at position 3(2^(n-1))-1. The 3s occur at positions 4,6,9,13,19,27,.... Adding 1 gives 5,7,10,14,20,... These do not appear to follow a pattern on first glance. However, you can split them into 2 sub-sequences -- 5,10,20,.... and 7,14,.... I suspect these will play out like the other sequences and end up being 5(2^(n-1))-1 and 7(2^(n-1))-1. I haven't generated enough of the sequence to find patterns in the other numbers. Therefore, I cannot spot any higher-level patterns other than the sequences appear to be multiples of primes. I am also not sure why the 3s have 2 sequences.

[@aithne99]

Now THAT is interesting. If you use the "original" sequence, with a double-1 start, 1's appear at positions 1, 2, 4, 8, 16, 32, etc. I find that sequence easier to use since there's no substracting one. From position i to j there is exactly j-i pairs, so if you have a 1 at position four, and it was generated by position 2, you have to count the pairs between position 2 and 4. Since each pair generates two numbers, those two pairs generate 4 numbers, and the 4th will be a 1. Same with twos. Now the threes are different, since they appear by being "the last number" and being a sum (of 1+2). From there on, both sequences are pretty obvious. From there on, each number will have n/2 sequences if even, (n+1)/2 sequences if odd.

[@00poikl]

2(2^(n-1))-1 === 2^n-1 ;)

[@msclrhd]

00poikl I am aware of that :). The point of writing it in the form 2(2^(n-1))-1 is to identify the pattern for the other numbers. That is, there is a general sequence x(2^(n-1))-1 that appears in the positions of the numbers.Thus, for n=1 you have x=2; for n=2 you have x=3; for n=3, you have the sequences x=5 and x=7 interleaved.

[@Improbabilities]

Another interesting point about this is that 4 (2^2) has a sequence that starts at 9 (3^2), and 8 (2^3) has a sequence that starts at 27 (3^3). If the pattern holds, it should be possible to find any power of two, since 2^*k* should be found at position 3^*k*. 9 seems to have a sequence starting at position 35, which is the product of the starting numbers for both sequences of threes, 7 and 5. It is possible that this is also a pattern? What if any number *n*, that has *k* sequences related to it, can be linked to the number *n*^*k*, that has a sequence starting at the position given by the product of the starting sequence numbers for *n*? I didn't go further than position 44, but if my theory is correct, there should be a 16 at position 135. That won't prove the theory, though, since that only proves it works for *k*=2. Edit: put in missing words, for extra clarity.

[@Improbabilities]

msclrhd This is great! I'd probably be doing it myself, if my engineering studies didn't hog so much time and brainspace. I'll give it a look!

[@SmileyMPV]

It's not binary, it's more like 'amount of ways you can write the number as a sum of powers of two where each power can not appear more than twice' Maybe a bit of a mouth full but at least it is mathematically correct this way :P

[@prlivesey]

It's the partitions of a number when you're restricted to only powers of two.

[@landsgevaer]

prlivesey *and* you can have only 0, 1, or 2 (but not 3 or more) parts of equal size...

[@prlivesey]

Dave Langers Oh yes, absolutely.

[@borisnot]

Wouldn't it be called base 3?

[@borisnot]

Boris Pi Oh, of course not!! Forget that, please!

[@stephenbeck7222]

That's a real Parker Square version of binary! (are we still doing parker square?)

[@CraftQueenJr]

Stephen Beck absolutely.

[@richardgaule9415]

I could listen to matt forever

[@151bar151]

1:46 MattParker.exe is not responding

[@CaptTerrific]

Aww, I was hoping to see some interesting proofs in this "extra" video :( This is a very fascinating effect of the sequence, but after these two videos, I feel like something huge is missing - like we just saw the most amazing thing, but only understand 1% of what it's capable of! Bring back this sequence in the future, please!!!

[@indjev99]

I took it as challange. And I'm proud to say that I managed to proof both why it generates all fractions and the ting with the binary with 2s. Also I'm working on a program that generates such sequence for any base with any digits.

[@rngwrldngnr]

indjev99 Come on, your just going to Fermat us? Publish it somewhere; this one's been driving me crazy.

[@kevina5337]

"It also shows all the different ways you can write that number in binary... if you're allowed to include 2's!!" LOL what who came up with that idea???

[@leppie]

Might be obvious, but I noted result of each line multiplying all together is 1. Also, doing the same with the left hand half results in 1/2 and the right hand half results in 2.

[@gregvandenberg257]

I think "drunk binaries" need to be a standardized term..... lol

[@eamonnsiocain6454]

'Drunk Binaries?' That's hilarious!

[@stephenjames9962]

There is a link with the Euclidean algorithm, if we take the terms as pairs of integers. The path from any term back up the tree to 1/1 gives a sequence of pairs that follows the Euclidean algorithm by repeated subtraction. The parent of p/q is (p-q)/q for p>q; or p/(q-p) for p

[@Tokkemon]

He reminds me so much of Michael Palin. I'm just waiting for him to break out in songs about Lumberjacks!

[@kevina5337]

Parker Binary

[@sethamajig228]

I guess the binary part explains why there is a 1 in every mersenne number's place.

[@bobthegiraffemonkey]

That's pretty cool. If the reason is known, I would like a video explaining it.

[@gerritzimmermann3688]

Another way of putting it, without using confusing number systems: the Stern-Brocot number is always the number of ways of expressing it's positional number by the sum of two binary numbers. For the pair 3 / 9: 1001 => 1001 + 0000 201 => 101 + 100 121 => 111 + 010

[@robtanniru6561]

but what about 11 + 110? That also equals 121 but is the sum of two different binary numbers.

[@gerritzimmermann3688]

Rob Tanniru Hmm, interesting. Yes, I missed that.

[@ImAllInNow]

Interesting tidbit: If Fib(n) is the nth Fibonacci number (where Fib(0) = 1 and Fib(1) = 1). Then Fib(n) counts the number of ways to represent n in unary if you're allowed to use 2s. As an example, 5 can be represented in Fib(5) = 8 different ways: 11111, 1112, 1121, 1211, 2111, 122, 212, and 221. So in some respects, this sequence in the video is a "stretching out" of the fibonacci sequence where you use binary instead of unary. If you stretch it out even further to use ternary, then you just get a sequence of 1s, since there's only 1 way to represent each number in ternary if you're allowed to use 2s (you were already allowed to use 2s!).

[@robtanniru6561]

***** I see how the Fibonacci sequence works for your new definition, but not quite sure if that's right for the Stern-Brocot sequence. Take 9, for example. You can represent 9 as 1 + 1000, 10 + 111, 11 + 110, or 100 + 101. But the Stern-Brocot number for 9 is 3, not 4. As for extending to ternary sequences, I wrote a program to generalize this idea. You can get the sequence for any base that allows any maximum digit. For example, ternary sequences that are allowed to use 3's, the sequence is: 111211211322311211322311211433522422533411...

[@atimholt]

Another way to think of the “binary with twos” thing is in terms of shifting ones rightward into a two (overtop a zero). With a bit of thought, you can get the count of possible “augmented-binary” representations by taking every consecutive group of ones left of the least-significant zero (e.g., 101110011 has two such groups of ones), and multiplying their sizes+1 together (e.g. 371, normally 101110011 in binary, has “two-able” groups of size 1 and 3. (1+1)×(3+1) = 8, so there are 8 ways to write it in augmented binary).

[@cherrynoize]

Infinite Fractions (extra footage) or The Most Underconsidered Numberphile Video. You should have put this inside the main video, it's the most interesting thing I've found in my entire life.

[@razorborne]

if we don't know why it happens, how do we know it continues like that indefinitely? is that proven?

[@lsvivivi]

3:46 lol that face is gold

[@XBrainstoneX]

For anyone interested in the proof for why the sequence ratios give all rational numbers. Read "proofs from THE BOOK" p. 113-116 [second run 2004].* Now for why the sequence a(n) Matt has given equals the number of hyperbinary represantations of n: That proof is actually quite simple. (Warning: Don't read on if you want to figure it out by yourself!) The recursive definition Matt has implicitely given is as follows: a(0) = 1, a(1) = 1 and a(2n + 2) = a(n + 1) + a(n) and a(2n + 1) = a(n) for all non-negative integers. We proof that h(n) - the number of represantations in hyperbinary of n - follows the same rules. h(0) = 1, h(1) = 1 is obvious. Consider h(2n + 1): As n + 1 is uneven, any hyperbinary represantation must end with "1". When read without the last "1" the other digits must therefore be a represantation of 2n/2 = n. There are h(n) possibilities for that. Therefore h(2n +1) = h(n) Consider h(2n + 2): All hyperbinary represantations ending with "1" are uneven. Therefore the represantation we are looking for ends with "0" or "2". If it ends with "0", the other digits must be a represantation of (2n + 2)/2 = n + 1. If it ends with "1" the other digits must be a represantation of 2n/2 = n. Therefore h(2n +2) = h(n) + h(n+1). *On the run I found on google books, it seems to be on page 94 and onwards. Sadly, these pages aren't free.

[@LB_]

Wow, that's crazy!

[@coolbrunno]

This is why math is beautiful. Because we haven't even scratched the layers.

[@reyrodrigues]

Well done Brady for not picking seven! (kzbin.info/www/bejne/iamzZGObqtxmY5I)

[@DonCYHaute]

Why not just call it "trinary"?

[@oyahfftlisawsome]

But why not just call it ternary?

[@anonymoususer2756]

Because it isn't ternary.

[@rngwrldngnr]

So, was that last connection described in the paper? It just seems like a very odd connection to stumble upon, since as you said, there's no obvious reason to think there would be a link.

[@NNOTM]

Hm, I suppose the obvious next step is trying to find similar sequences for every other possible numeral system and how to generate those sequences. That should illuminate the connection somewhat, I think.

[@indjev99]

I'm working on such program.

[@codebeard]

What sequences would you need to give the number of ways to write numbers in other bases? For example, in base 10 where 10 is allowed as a digit - or do you need to allow 10 through 19 as digits too?

[@NNOTM]

I'm fairly certain that you can allow any number of digits, and the resulting systems will have different sequences. I don't know how to generate those sequences, though.

[@codebeard]

I wrote a program to find the number of ways to output each number in different bases and found, for example: Ways to write n in ternary if 3 is allowed: 1,1,2,1,1,2,1,1,3,2,2,3,1,1,2,1,1,3,2,2,3,1,1,2,... Ways to write n in ternary if 3 and 4 are allowed: 1,1,2,2,1,2,2,1,3,3,2,4,4,2,3,3,1,3,3,2,4,4,2,... I found these both appear in OEIS as A054390 and A117535, respectively. The second one has a link to something called "age determined insertion trees" as a way to generate these sequences.

[@wi11camp82]

It also feels like you should be able to write in base n using n+1 digits and the position would still tell you all the ways.

[@serkval7025]

why is it unlisted ?? ( wouldn't it be better for you to put it public ?? )Numberphile2

[@PEisner98]

Is Matt's book available in german?

[@Natalie-cx3cp]

What is it called when it's 0,1 & 2s is it just binary with twos? Or is there a special name?

[@CraftQueenJr]

Natalie ternary.

[@007bistromath]

Sometimes I think you guys make videos like this just to crowdsource new mathematical research to obsessive-compulsives on the internet instead of using a supercomputer. :V

[@DKRCecer]

You figured it out! You're hired!

[@Hecatonicosachoron]

So this sequence also yields the number of partitions of an integer in powers of two with no more than two parts of the same magnitude. I wonder what the dual subset of partitions actually represents (also given by the same sequence)... Is it the number of partitions to a number of parts that is a power of 2? I also wonder if there are any interesting congruences in this sequence.

[@grabern]

Question: are the Stern-Brocot numbers in Pascal's triangle?

[@grabern]

Just found it out. They're in the diagonals of a mod 2 Pascal's triangle.

[@magicalpencil]

some deep shit man, it's deep because of how un-deep we are. Deep.

[@Yakhashe]

using 2s in binary is like using hexadecimals in decimals: 120 could be written as C0 or BA (mind that 120dec=78hex)

[@ImAllInNow]

The number of ways to do that are: 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 1 1 1 1 2 2 2 2 2 2 1 1 1 1 2 2 2 2 2 2 1 1 1 1 2 2 2 2 2 2 1 1 1 1 2 2 2 2 2 2 1 1 1 1 2 2 2 2 2 2 1 1 1 1 2 2 2 2 2 2 1 1 1 1 2 2 2 2 2 2 1 1 1 1 2 2 2 2 2 2 1 1 1 1 3 3 3 3 3 3 2 2 2 2 4 4 4 4 4 4 2 2 2 2 4 4 4 4 4 4 2 2 2 2 4 4 4 4 4 4 2 2 2 2 4 4 4 4 4 4 2 2 2 2 4 4 4 4 4 4 2 2 2 2 3 3 3 3 3 3 ...

[@ImAllInNow]

120 can be written 4 ways: 120, C0, BA, and 11A

[@NijosoSefzaps]

Right. Now I think of mathematicians as dwarves, digging deeper and deeper into the maths before them. I'm curious as to when you'll find a mathematical Balrog. :P

[@Nemelis0]

Hmm, 2s in binary... I believe I'm a bit to technician ;-) I would call a number-system with 0,1 and 2 ternary numbers, but than again the logic rules would apply and 221 would be 31(d) (or 11111b, or 37o or 0x1Fh or whatever established number-system you like ;-) ). So ....this breaks my set rules and thus is fun with number-systems 8-)> I like it.

[@ChrisBenjamon]

Just watching Matt Parker videos hoping for another Parker square incident. haha

[@jesusthroughmary]

Ternary?

[@bengtbengt3850]

Nope its not ternary since the base they counted with is still 2

[@frankharr9466]

Numberphile nerdsnipes me.

[@rogerdotlee]

That smug look speaks volumes.

[@ShimmerFaerie]

That's a real Parker Square of a binary system of counting there.

[@trevorsettles3328]

so that works, except for #2. you can writ 2 as 2 or 10. the sequence says there should only be 1 way to write 2

[@DrGerbils]

The sequence connected to the drunken binaries starts 1, 2, 1, 3, 2, 3 ..., not 1, 1, 2, 1, 3, 2, 3 .... Apparently, the first 1 in the S-B sequence is discarded.

[@Invariel]

DrGerbils Alternately, you could say that the first 1 is at position 0, and there is one way to write 0 in "base 2, now with more 2s."

[@Yakhashe]

Invariel does this have something to do with 0!=1 ?

[@ImAllInNow]

Yakhashe I suppose so. It's just that there's always exactly 1 way to arrange nothing: that way.

[@theblackwidower]

Binary if you're allowed twos... Isn't that trinary?

[@wyattstevens8574]

You using Misali numbering?

[@FedericoYulita]

Isn't binary with 2 just not binary?

[@zacmg]

"binary but you're allowed twos" so base 3?

[@anonymoususer2756]

No. There's only one way to write every number in base 3 if you're "allowed 2s".

[@kibromfesseha9960]

So when you say binary with twos you really mean trinary?

[@siprus]

Actually not exactly. in trinary there is 1:s column 3:s column 9:s column. (and each of these columns can have 3 different values) now this is some kind of binary trinary hybrid where you can use twos but each column consist of potence of tow (and ones column)

[@kibromfesseha9960]

Your use of colons confuses me...

[@Kino-Imsureq]

6 is 20 in ternary.

[@anonymoususer2756]

...which isn't the same thing as binary with 2s.

[@lucashoffses9019]

The link isn't too hard to find.

[@KriegsMeister27]

Wouldn't "binary" with 2's be "trinary"

[@QuotePilgrim]

Oh yeah, there is one pretty obvious difference between ternary and “binary with twos” that other people failed to mention: In the same way that you have precisely one way to write the number 9 in the decimal system, you only have one way to write “9” in ternary, which is 100. However, as the video shows, there are three different ways to write “9” in binary with twos.

[@TheRealFlenuan]

KriegsMeister27 No; this still uses exponents of 2 for digit places and is thus binary.

[@AV1461]

Really good. haha

[@darthtorus9341]

so.. sort of like ternary...

[@cameodamaneo]

No, because we're still using powers of two. Ternary uses powers of three.

[@kajoel]

Hey, you should really show the proof for that (don't expect everybody to believe you without a proof, it's probably true but anyways). It would be nice to understand why this serie is/seems to be so special. Moreover it would be awesome to spread some awesome maths but that requires the proof.

[@NotaWalrus1]

The proof is unfortunately pretty high-level math, so it wouldn't be suitable for this channel's target audience.

[@NiftyFingers]

I don't think a proof for everything is necessary, and the proofs are out there. It's entertainment mostly though, it's not a channel of proofs.

[@kajoel]

True, the channel is for entertainment. The proof would however be the most entertaining part

[@NotaWalrus1]

Joel Karlsson Not if it involves too high-level maths. There was a video on topography lately that dealt with pretty advanced concepts and after a certain point I just had to stop watching it and most of the commenters felt the same way. Some proofs can be entertaining, but many are just plain uncomprehensible.

[@kajoel]

well, I didn't say that YOU had to watch the proof (could be in separate video)

[@birthsonbluebell3654]

1 can be an infinite fraction: 1/1/1/1/1/1/1/1/1/1/1/1/1/1/1/1/1/1/1/1/1/1/...

[@benhbr]

"Drunk binary numbers" :)

[@CreeperSausageHarry]

ternary!

[@CreeperSausageHarry]

bu counting in 2^n instead of 3^n

[@GravelLeft]

I've just discovered an amazing sequence where the n'th position gives you the number of ways to write n in regular binary: It goes 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... (Edit: Forgot a 1)

[@anonymoususer2756]

Technically there are infinitely many ways to represent a number in binary. For example, 5 is 101, 0101, 00101, 101.0, 0101.0, 0101.00, 00101.0, 101.00, 000101, 0000000000000101, 101.000000000000000000 etc...

[@modal_derp]

Trinary.

[@Tassdo]

Yeah except it's not. 9 in ternary would be 100 and 6 would be 20 :) It's really more related to binary than to ternary, except in the symbols used (0,1 and 2)

[@anothermoth]

Tassle It's like the sum of two binary numbers, but you haven't carried the carries yet.

[@zamfofex]

That should be the name for the thing! xP

[@almoglevin]

That's brilliant! But... why would you want to write binary with 2s... oh, becuase the binaries got drunk, ok. :-D

[@TheEgglet]

wtf i said 6 too

[@iVilius]

Brady chose 6 and 9? Really? Really, man?

[@BloodSprite-tan]

meh trinary not binary