In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers.
An integer sequence may be specified explicitly by giving a formula for its nth term, or implicitly by giving a relationship between its terms. For example, the sequence 0, 1, 1, 2, 3, 5, 8, 13, … (the Fibonacci sequence) is formed by starting with 0 and 1 and then adding any two consecutive terms to obtain the next one: an implicit description. The sequence 0, 3, 8, 15, … is formed according to the formula n^{2} − 1 for the nth term: an explicit definition.
Alternatively, an integer sequence may be defined by a property which members of the sequence possess and other integers do not possess. For example, we can determine whether a given integer is a perfect number, even though we do not have a formula for the nth perfect number.
YouTube Encyclopedic

1/3Views:283 6232 377598 981

✪ Six Sequences  Numberphile

✪ An Integer Sequence

✪ Solving a consecutive integer problem algebraically  Linear equations  Algebra I  Khan Academy
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 nth 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 selfcontained. 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 nth 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 nth 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 longstanding 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 selffulfilling 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.
Contents
Examples
Integer sequences that have their own name include:
 Abundant numbers
 Baum–Sweet sequence
 Bell numbers
 Binomial coefficients
 Carmichael numbers
 Catalan numbers
 Composite numbers
 Deficient numbers
 Euler numbers
 Even and odd numbers
 Factorial numbers
 Fibonacci numbers
 Fibonacci word
 Figurate numbers
 Golomb sequence
 Happy numbers
 Highly composite numbers
 Highly totient numbers
 Home primes
 Hyperperfect numbers
 Juggler sequence
 Kolakoski sequence
 Lucky numbers
 Lucas numbers
 Motzkin numbers
 Natural numbers
 Padovan numbers
 Partition numbers
 Perfect numbers
 Prime numbers
 Pseudoprime numbers
 Regular paperfolding sequence
 Rudin–Shapiro sequence
 Semiperfect numbers
 Semiprime numbers
 Superperfect numbers
 Thue–Morse sequence
 Ulam numbers
 Weird numbers
 Wolstenholme number
Computable and definable sequences
An integer sequence is a computable sequence if there exists an algorithm which, given n, calculates a_{n}, for all n > 0. The set of computable integer sequences is countable. The set of all integer sequences is uncountable (with cardinality equal to that of the continuum), and so not all integer sequences are computable.
Although some integer sequences have definitions, there is no systematic way to define what it means for an integer sequence to be definable in the universe or in any absolute (model independent) sense.
Suppose the set M is a transitive model of ZFC set theory. The transitivity of M implies that the integers and integer sequences inside M are actually integers and sequences of integers. An integer sequence is a definable sequence relative to M if there exists some formula P(x) in the language of set theory, with one free variable and no parameters, which is true in M for that integer sequence and false in M for all other integer sequences. In each such M, there are definable integer sequences that are not computable, such as sequences that encode the Turing jumps of computable sets.
For some transitive models M of ZFC, every sequence of integers in M is definable relative to M; for others, only some integer sequences are (Hamkins et al. 2013). There is no systematic way to define in M itself the set of sequences definable relative to M and that set may not even exist in some such M. Similarly, the map from the set of formulas that define integer sequences in M to the integer sequences they define is not definable in M and may not exist in M. However, in any model that does possess such a definability map, some integer sequences in the model will not be definable relative to the model (Hamkins et al. 2013).
If M contains all integer sequences, then the set of integer sequences definable in M will exist in M and be countable and countable in M.
Complete sequences
A sequence of positive integers is called a complete sequence if every positive integer can be expressed as a sum of values in the sequence, using each value at most once.
See also
References
 Hamkins, Joel David; Linetsky, David; Reitz, Jonas (2013), "Pointwise Definable Models of Set Theory", Journal of Symbolic Logic, 78 (1): 139–156, arXiv:1105.4597, doi:10.2178/jsl.7801090.
External links
Wikimedia Commons has media related to Integer sequences. 
 Journal of Integer Sequences. Articles are freely available online.