Stern's sequence.
A famous Göttingen mathematician from the 19th century,
here is his sequence. It can be described in several ways.
It's very important, it's one of the bigger entries in the OEIS. But let me give you the simplest definition.
The first two terms are 1 and 1.
The next two terms, I copy the 1 and the 1 and put their sum in the middle.
So the sequence now begins 1, 1, 1, 2, 1 — and how does it continue?
I copy the previous line and in between I put the sum: 1 plus 2 is 3, 1 plus 2 is 3.
So, I've now shown you
(Brady: You've got a Pascal Triangle)
It's very like Pascal, it's actually like Farey series.
F-A-R-E-Y
It's, it's a very common number theoretic thing. So again, to get the next seven terms
I copy the previous line and in between them
I write the sum of the two terms above that, just, as you said, just like Pascal's triangle.
Now this has a very nice property.
If I omit the last one, it has the property that if you look at ratios of successive terms
Fractions; 1 over 1, 1 over 2, 2 over 1, 1 over 3
— a third, in short. 3 over 2, that's 1 and 1/2
2 over 3,
if we keep doing that we get all the fractions in their lowest terms.
It's a way of enumerating the fractions.
After a while we get seven seventeenths, we'll get 101 over 103,
and so on.
We'll get 103 over 7.
We get all of them, little ones and big ones, and they're always reduced.
So that's the sequence: 1, 1 2, 1
3 2 3 - just read it like you do with Pascal's triangle. If you plot it, you get something that looks pretty nice.
Like Monet
sketching the facades of some
cathedrals.
This is Hofstadter's Q Sequence, and the interesting thing is
that we don't know if this exists or not. It's an open question,
just as we don't know if Schrödinger's cat is alive or dead.
Fibonacci, it says that a of n is equal to
a of n minus 1, plus a of n minus 2, the sum of the two previous terms.
Hofstadter sequences, a of n is a of n
minus a of n minus 1, plus a of n minus a of n minus 2.
(Brady:Can you show me an example how that works?)
Well, I guess...
(Brady: All right)
All right, I'll try. It begins with two 1s, just like the standard naïve Fibonacci version, right?
We don't put a zero in here. You go back one step and you go back two steps, right?
That's how you get Fibonacci, you look at where you are,
you go back one step, and back two steps and add them up.
This one, Hofstadter's Q Sequence,
you look at the previous term, but that's how many terms you have to go back to get the thing you're adding.
So what's 3?
So going back one step gives us a 1. Going back one step because of that 1 gives us a 1.
1 plus 1 is 2.
So 4. What's a of 4? We look at this - 2, so we go back two steps.
Two steps, we get a 1.
We go two steps back and we get a 1 and that says go back one step and we get a 2.
1 plus 2 is 3.
(Brady: So that one - so that one told us go back one step, but one step from our starting point again?)
Yeah, and whatever you see under your finger, you add it to the other one.
(Brady: Let me see if I can get the next one. Let me see if I can get it.)
(So for the fifth term,
that's a 3 so go back three steps: 1, 2, 3.)
(So, a little 1.)
(So then we go back two numbers which says-)
Neil: Go back two numbers. to there. And what do we see?
We see a 2, so we add that to the other number, so we get a 3.
(Brady: Let me see if I can get the next one right there. All right, so the sixth number)
(Three, so 1, 2, 3. So give us a 2)
(2 and now 3,)
(so go back three steps 1, 2, 3 — a 2!)
(That's a 4. And once more to make sure I've got it.)
(So four steps 1, 2, 3... a 2.)
(And three steps: 1, 2, 3: 3. So that's a 5)
Neil: Very good. - (Brady: Okay) - That's the sequence.
Well now if
we're lucky, we can always do that, but suppose
there was a number here, which was too big and that would say
oh you've got to go all the way back here, where it's not defined. If that happens you're dead.
It hasn't happened yet, but we can't prove that it never happens.
Pretty obviously, it's never going to happen, if you look at the graph.
This is 10,000 terms.
So most of the terms are 1/2 of n.
We'd run into trouble if we had a term that was as big as n.
Because this line has slope 1/2, and even though there are some little dots trying to escape,
some little particles trying to get away,
they have to get it all the way up
to here or something before they would kill it.
And it hasn't happened and it's not going to happen - we've checked.
Roman Pearce
computed 10 to the 10th terms, never never a problem. - (Brady: But not proven?) - Not proven.
Here's a picture of a hundred million terms that I got from Douglas Hofstadter, who invented the sequence. And you can see beautiful,
ribbon-like structure, but no proof. It could die at any moment,
beautiful.
(Brady: You got another one?)
And it's a variant. Slightly different rule, but an even more striking picture.
Look at this ribbon-like thing. This one we know exists. It's just a beautiful picture, a beautiful graph.
(Brady: What's the sequence that's a graph of?)
It's called a chaotic cousin.
It's like the other one but but different, and I'm not going to show you the equation because it's an equation and you hate equations,
but it's similar.
(Brady: Ok) - Ok. I mean, it looks like that. That's the definition.
This is a sequence that was invented by Rémy Sigrist.
It's a very simple rule but a little subtle. You've got to put down a
non-negative number and always the smallest possible. So
I'll put a zero, no one is gonna object to that.
Now 1, 2. If you look at them in binary
1 looks like 1, and 2 looks like 1 0 and you notice
there's no place where they both have a 1.
1 in binary and 2 in binary have disjoint sets of ones, they don't overlap a 1. So, there's no constraint.
As long as they don't overlap you can have the same number. Okay now 3, ah
3, 1 1 in binary, and that overlaps both of these two so I can't put a 0 here
because we'd have two numbers that - whose binary representations met, that have the same number.
All right, so it's a 1.
Now 4. 4 is pretty good because it's not over, going to overlap with anything.
So I can put a 0. 5: 1 0 1, now I have to be careful. I can't put a zero here
because it would overlap with that and
I can't put a 1 because 3 and 5
overlap, below is stored a bit, so I can't put a 1 but I can put a 2. 6 is
1 1 0, what can I put here? I can't put a zero because of the 2,
I can't put 1. I can't put a 2 because 5 and 6 overlap. So I have to put a 3. And that's it,
that's the sequence. And what does it look like? It looks like the Alps on a snowy day.
(Brady: Right, that's a strange one that one) - Yeah
Thank you for watching. Also a very special thanks to our Patreon supporters.
Just some of them are the names you're seeing on the screen at the moment and you can join them by going to patreon.com/numberphile
This was the third and final in our trilogy of amazing graphs, at least for now, until Neil shows us some more. If you'd like to
watch them all there are links on the screen and in the video description. And we'll be back again soon with more Numberphile videos.
[Extra video] You're probably wondering what Fibonacci looks like? - (Brady: I was yes, right from the start)
Here it is, it's boring. This is the first 200 terms and they go along and, you know,
they get pretty big. When we do these plots, in the OEIS, the first plot is 200 terms