In mathematics, Gijswijt's sequence (named after Dion Gijswijt by Neil Sloane[1]) is a self-describing sequence where each term counts the maximum number of repeated blocks of numbers in the sequence immediately preceding that term.
The sequence begins with:
The sequence is similar in definition to the Kolakoski sequence, but instead of counting the longest run of single terms, the sequence counts the longest run of blocks of terms of any length. Gijswijt's sequence is known for its remarkably slow rate of growth. For example, the first 4 appears at the 220th term, and the first 5 appears near the rd term.[1]
YouTube Encyclopedic
-
1/3Views:236 1342 9901 045
-
Six Sequences - Numberphile
-
Wrecker Ball Sequences
-
The On-Line Encyclopedia of Integer Sequences: The First Hundred Years Part A
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.
Definition
The process to generate terms in the sequence can be defined by looking at the sequence as a series of letters in the alphabet of natural numbers:
- , and
- , where is the largest natural number such that the word can be written in the form for some words and , with having non-zero length.
The sequence is base-agnostic. That is, if a run of 10 repeated blocks is found, the next term in the sequence would be a single number 10, not a 1 followed by a 0.
Explanation
The sequence begins with 1 by definition. The 1 in the second term then represents the length 1 of the block of 1s that is found immediately before it in the first term. The 2 in the third term represents the length 2 of the block of 1s that are in the first and second term. At this point, the sequence decreases for the first time: The 1 in the fourth term represents the length 1 of the block of 2s in the 3rd term, as well as the length 1 of the block "1, 2" spanning the second and third term. There is no block of any repeated sequence immediately preceding the fourth term that is longer than length 1. The block of two 1s in the first and second term cannot be considered for the 4th term because they are separated by a different number in the 3rd term.
The 1 in the fifth term represents the length 1 of the "repeating" blocks "1" and "2, 1" and "1, 2, 1" and "1, 1, 2, 1" that immediately precede the fifth term. None of these blocks are repeated more than once, so the fifth term is 1. The 2 in the sixth term represents the length of the repeated block of 1s immediately leading up to the sixth term, namely the ones in the 4th and 5th terms. The 2 in the seventh term represents the 2 repetitions of the block "1, 1, 2" spanning terms 1-3 and then 4–6. This "3-number word" occurs twice immediately leading up to the seventh term - so the value of the seventh term is 2.
The 2 in the eighth term represents the length of the repeated block of 2s immediately leading up to the eighth term, namely the twos in the sixth and seventh terms. The 3 in the 9th term represents the thrice-repeated block of single 2s immediately leading up to the 9th term, namely the twos in the sixth, seventh, and eighth terms.
Properties
Only limited research has focused on Gijswijt's sequence. As such, very little has been proven about the sequence and many open questions remain unsolved.
Average value
Though it is known that each natural number occurs at a finite position within the sequence, it has been shown that the sequence has a finite mean. To define this formally on an infinite sequence, where re-ordering of the terms may matter, it is known that
- .[1]
Likewise, the density of any given natural number within the sequence is known to be finite.[2]
Rate of growth and first occurrences
In 2006 Gijswijt proved that the sequence contains every natural number.[3] The sequence grows roughly super-logarithmically, with the first occurrence of any natural positioned at approximately . A closed-form expression for the earliest index at which a given positive integer appears was found by Levi van de Pol, in terms of a constant and a sequence of constants .[2]
For example, the position of the first 5 is given by
where . Expanded out, this number is approximately
- .
The first instance of two consecutive 4's starts at position
- 255,895,648,634,818,208,370,064,452,304,769,558,261,700,170,817,472,823,
- 398,081,655,524,438,021,806,620,809,813,295,008,281,436,789,493,636,144.
These number both have 108 digits, and were first published by van de Pol.
Recursive structure
The sequence can be broken into discrete "block" and "glue" sequences, which can be used to recursively build up the sequence. For example, at the base level, we can define and as the first block and glue sequences, respectively. Together, we can see how they form the beginning of the sequence:
The next step is to recursively build up the sequence. Define . Noting that the sequence starts with , we can define a glue string which gives:
We assigned to a particular sequence which gives the property that also occurs at the top of the sequence.
This process can be continued indefinitely with . It turns out that we can discover a glue string by noting that will never have a 1, and that it stops once it reaches the first 1 to follow .[4] It has also been proven that Gijswijt's sequence can be built up in this fashion indefinitely ‒ that is, and are always finite in length for any .[3]
Clever manipulation of the glue sequences in this recursive structure can be used to demonstrate that Gijswijt's sequence contains all the natural numbers, among other properties of the sequence.
See also
References
- ^ a b c Sloane, N. J. A. (ed.). "Sequence A090822 (Gijswijt's sequence: a(1) = 1; for n>1, a(n) = largest integer k such that the word a(1)a(2)...a(n-1) is of the form xy^k for words x and y (where y has positive length), i.e., the maximal number of repeating blocks at the end of the sequence so far)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
- ^ a b van de Pol, Levi. "The first occurrence of a number in Gijswijt's sequence". arXiv:2209.04657.
- ^ a b Gijswijt, D.C. (2006). "A Slow-Growing Sequence Defined by an Unusual Recurrence". arXiv:math/0602498.
- ^ Sloane, Neil. "Seven Staggering Sequences" (PDF). AT&T Shannon Lab. p. 3.
External links
- First 50 million terms
- OEIS sequence A091579 (Lengths of suffix blocks associated with A090822) -- (the lengths of the glue sequences)