Golomb sequence

Transcription

TONY PADILLA: The guys at Aperiodical launched a little competition to find the integest sequence 2013. It's a little bit fun. It's not a serious thing. But basically, they've looked at the online encyclopedia of integer sequences and they've basically run a competition to see which one is the best. And it's based on various categories, like aesthetics, novelty, explicability, completeness, these sorts of things. But it's just a bit of fun. But we thought we'd go through these sequences. And I'm not going to tell you which one I like best, so I'll leave that to the end. I'm going to do my best poker face to try and keep it a secret. So the first one in the sequence is to do with the decimal expansion of a particular constant. So the decimal expansion of Khinchin's constant is the following 2.6854. OK, so that doesn't look very exciting, just by looking at it. Khinchin's constant is a remarkable number, actually. Basically, if you take any number, or almost all numbers to be more precise-- almost all numbers-- and you work up the continued fraction expansion of that guy. So for example, we just take a general number, x, and we can know that we can write this is a0 plus 1 over a1 plus 1 over a2 plus-- and so on. You keep going on like this. This is called-- these are a0, a1 [INAUDIBLE] and all those are called the continued fraction expansion. Well, let's say I take the product of all these a's. I take a1 times a2-- forget a0-- times a3 and so on, to an. And I take the geometric mean, so I just take an n-th power of that. And I see what that gives me as I go to infinity. So as n goes to infinity, it goes to Khinchin's constant. And this is true of almost any number. That's amazing. I think that's an amazing fact. It's almost like now, obviously, you're going to immediately tell me, well, it's not true of a lot of numbers that you know about. It's not true of a half, for example, because the continued fraction expansion of a half is not-- clearly, just any rational number, you can get basically any number out doing this process. But most numbers do, that's the amazing thing. Almost all numbers. No irrational numbers will do it, but most numbers do. Pi, for example, is thought-- so when you take the expansion and calculate this number for pi, you're expected to get Khinchin's constant. In fact, Khinchin proved that almost all numbers do it. By that, he means all numbers except for a sort of-- potentially, an infinitesimally small set. And the great thing about this is, is that k0 itself, which seems to know about almost all numbers, also knows about itself. Because it's thought, although this hasn't been proven, that k0, when you do this expansion for it, averages to [INAUDIBLE]. Then take this average, it recovers itself. So if you like it, if there was a number that had-- if God had a number, it would be this number, because it knows about almost all of the numbers and itself. It's kind of like beautifully self-contained. OK, so next one in the sequence, this is the Wieferich primes. And basically, there's only two numbers in this sequence that we know of, 1,093 and 3,511. So what are these guys? The Wieferich primes are any prime number p, such that p squared divides 2 to the p minus 1 minus 1. And it's true of these two numbers. We don't know if it's true of any other numbers. In fact, I was interested to see if there were any higher ones than this. And I actually found a paper which says that, well, they've done a search for Wieferich primes all the way up to 6.7 times 10 to the 15th and they haven't found any more. So you got these two low guys, and then nothing all the way up to that. So the next one in the sequence is going to be some huge number if, indeed, it exists. Well, the reason Wieferich was interested in them is they seem to have something to do with Fermat's last theorem. He was trying to prove Fermat's last theorem. The reason is that Wieferich proved the following results. You take x to the p plus y to the p plus z to the p equals 0. X, y, and z are integers. And you say that p does not divide zyx, then you can prove-- this is what Wieferich did-- that p has to be one of these Wieferich primes. OK, so next up is Golomb's sequence. So this is Golomb's sequence. BRADY HARAN: Gollum, like "Lord of the Rings?" TONY PADILLA: Yeah. Well, actually, this guy's got an amazing name-- Solomon Golomb. It's just the coolest names in the world, right? So he's actually quite an interesting guy. He's a mathematician that invented pentominoes, which is this mathematical game. But it was the forerunner of Tetris, actually. So Solomon Golomb was the guy who, essentially, invented Tetris. What is his sequence? His sequence is the following-- 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, and so on. And what does this sequence tell us? Well, this sequence kind of knows about itself, because the sort of n-th position in the sequence tells you how many times the number n appears in the sequence. I'll start with the first position. Then the question is, how many times does 1 appear in the sequence? Well, the answer is it only appears once. It can only appear once. I couldn't put a 2 here, that wouldn't make sense. Then I go to the next point. Now I'm asking, how many times does the number 2 appear in the sequence? Well, you can see that it is 2. It had to be 2. It couldn't be 1, because then 1 would have appeared twice and I'd have had to put 2 here, you see? So it kind of makes sense that it has to be 2. So then I go to the third point in the sequence, which is this position here. Now the question I have to ask is, how many times does 3 appear in the sequence? But I've already said that 2 had to appear 2. So I better put 2 there So the number of times that 3 has to appear in the sequence has to be 2. And so there they are, the next points in the sequence. And you keep going. You keep going in this manner. This position the question is, how many times does 4 appear in the sequence? Well, here you are. It appears 3 times. And so on and so on. And you build the sequence up this way. It kind of knows about itself. It's almost like it doesn't-- maybe it's had a bit of therapy or something. It really knows its inner being sort of thing. Now, there is a little-- another feature of this sequence is that as you get to very, very large numbers, where does this sequence go to? Well, it goes to the following. The n-th put position of this sequence will tend towards phi 2 minus [INAUDIBLE] phi n phi minus 1. Now, what is this? OK, this is n. What's this [INAUDIBLE] phi thing I've written down, this Greek letter? This is the golden ratio. It just appears everywhere. So the next one are the largest metadromes. So what is this? Well, a metadrome is a number which appears in-- where the numbers appear in a strict descending order. Let me write down the sequence first. 0, 1, 5, 27, 194, 1865, and so on. It's the largest metadromes, so the largest number you can write where all the numbers are in strict descending order base n. OK, so the first position. This is 0 base 1. OK, first position, so it's going to be something that's base 1. And it's the largest number we can write at strict descending order base 1 is 0. So this is 0 base 1. This guy, the next one, 1, what is that? Well, that is 1 base 2. So it's the largest number we could have written. They're all in strict descending order, base 2 because we're in the second position. Those two aren't that exciting. It gets a little bit more interesting when you get to the next number. So we know what this number should be. Well, it's five. But what's that? That is 1, 2 base 3. OK, well of course it is, because 1 2 base 3 is basically 3 plus 2. Next one, keep going-- 27. This is 1 2 3 base 4, which is 4 squared plus 2 times 4 plus 3, which is 27. OK, and you keep going like this. And this is how the sequence emerges. Well, the next on the sequence would be 1, 2, 3, 4 base 5. BRADY HARAN: And the next would be 1, 2, 3, 4, 5 base 6? TONY PADILLA: Exactly. And so on. I think that one's a bit duller than that is. That doesn't push my buttons, unfortunately, that sequence. BRADY HARAN: I haven't figured out what one's your favorite yet. I think-- TONY PADILLA: It's not that one. I'll give you a clue on that. BRADY HARAN: OK. TONY PADILLA: OK, so moving swiftly on. It is all the 7's. I think this is your favorite, isn't it, Brady? BRADY HARAN: I have to admit, I don't know why-- I don't know much about it yet, but it appeals to me. TONY PADILLA: OK. So what is all the 7's? Well, it does what it says on the tin. It's 7, 7, 7, 7, 7, and so on. BRADY HARAN: This is just a nonsense sequence? TONY PADILLA: I think it's just a nonsense sequence, but it's a bit of fun. You can relate it to some math if you try hard enough. BRADY HARAN: I'm not sure that's my favorite anymore. TONY PADILLA: Have you gone off it? BRADY HARAN: I thought it, actually, there was some equation for that. TONY PADILLA: OK, so now comes the last of the sequences that's been nominated, and these are the wild numbers. Woo, that sounds exciting. OK, so what are the wild numbers? Well, they are 11, 67, 2. There's supposed to be an infinite number, but what are these? What is this sequence? Well, it's actually a completely made of sequence that has come out of fiction. There was a guy called Philibert Schogt-- I hope I've pronounced that properly-- who wrote a novel about a mathematician and he solved a problem called the wild number problem. So what was the wild number problem? The idea was that you would take any whole number, you would apply some-- what are described as simple operations to that, that would turn that number into fractions. And then you would keep applying these operations until you get back to a whole number again. The claim is that those numbers that you end up with are the wild numbers. And of all the examples that were supposedly known, these were the only numbers that were popping up. So the question would be, are there an infinite number of wild numbers? Are there numbers that aren't wild numbers? Well, in the book, apparently 3 is a tame number. It's been proven that this can never be reached. And what the guy in the story does is-- his idea is that he proves-- he's supposed to be a mediocre mathematician who's disillusioned with his career. But he proves that there are an infinite number of wild numbers, which has been this long-standing problem. There's a nice little account on the archive, actually, that we use by the author of the maths behind it and the ideas behind it. He's written a novel, but this is a paper about the novel. So this is what he's done. He says something quite interesting in it, in that the idea was there would be this mediocre mathematician that ended up sort of solving Fermat's last theorem, which of course at the time hadn't been solved. But of course, now it has by Andrew Wiles, but at the time it hadn't. And so the idea was there's this mediocre mathematician that comes up with a proof of Fermat's last theorem. And OK, he sort of pitched this idea to a mathematician friend of his and the mathematician friend just sort of shot it down straightaway. He Said, there's no way a mediocre mathematician would be able to actually come up with-- solve a longstanding proof like that. It would always be somebody who's an established genius. Now, obviously, that's true in Andrew Wiles's case that a genius did ultimately find a proof for Fermat's last theorem. But recently, of course, we did a video about this prime number theorem, the twin prime conjectures, and that was solved by what was essentially not a star of mathematics. So maybe the author's friend was a little bit unfair there. But anyway, it gave the author license to then go away and invent these wild numbers. BRADY HARAN: So he made up wild numbers instead of using Fermat's last theorem. TONY PADILLA: Exactly. BRADY HARAN: It's a bit of a self-fulfilling prophecy though, isn't it? If you do solve one of these theorems, you become a genius. TONY PADILLA: Well, I think so. Yeah. BRADY HARAN: So it's always going to be a genius. TONY PADILLA: Sure, exactly. But I think the claim was that these people would have been noticed before because they would have-- these theorems get built up and you build towards them. And the proof [INAUDIBLE]. BRADY HARAN: So you've shown me all six? TONY PADILLA: Yeah. BRADY HARAN: Which was your favorite? TONY PADILLA: It's got to be Khinchin's constant, right? The decimal expansion of that. I mean, that number is just-- I'm blown away by that number and what is it. Conceive it-- almost all numbers, when you take this property to do with the continued fraction expansion, almost all numbers give you back this constant. That's amazing. That's an amazing fact. BRADY HARAN: Except the numbers you and I use almost every day. TONY PADILLA: But that's such a tiny fraction-- that's a minuscule fraction of all numbers that are out there. It's a measure zero fraction of it, in fact. So the vast majority of numbers-- the truly vast majority do give back this guy. Pi gives it. Well, that's what we think. So that, for me, is absolutely incredible. And so that's why I like that guy. As I said, if there is a number which has any kind of divinity to it, it's this one. I think I read somewhere that if we're going to send out some information to aliens, we should send out-- and it's going to be numeric, we should tell them about this constant. So I do like that number. But I do have a sequence, a personal sequence that I like more, though. I'd like to share with you, Brady. BRADY HARAN: I don't know what this is going to be. Actually, I know what this is. TONY PADILLA: OK, well, let me write it down, and then you see if you can guess it, Brady. BRADY HARAN: OK. TONY PADILLA: [INAUDIBLE]. BRADY HARAN: You write it down.