You're reading: Integer Sequence Review

Integer Sequence Review Mêlée Hyper-Battle DX 2000 (Bracket 3)

Last week, A001220 – the Wieferich primes – booked its place in the final. This week, David has picked six sequences all on his own to form Bracket 3 of…

oeis review melee

Here are the rules: we’re judging each sequence on four axes: Aesthetics, Completeness, Explicability, and Novelty. We’re reviewing six sequences each week for four weeks, picking a winner from each. Then, we’ll pick one sequence from the ones we reviewed individually before this thing started, plus a wildcard. Finally, a single sequence will be crowned the Integest Sequence 2013! 

David: Christian, are you ready for my first sequence?

Christian: … I think so. I’m worried that you felt the need to ask, though.

David: In the words of Marty McFly, it’s an oldie but a goodie, and your kids are gonna love it.

Look and Say sequence: describe the previous term! (method A – initial term is 1).

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211, 11131221133112132113212221, 3113112221232112111312211312113211, ...

David: This one is due to Tom Fisher.

Christian: Hang on, you specifically asked to pick all the sequences on your own this week and you’ve let Tom do the first one?

David: I specifically chose to listen to our fans.

Christian: Very well. This one’s a bit old hat. Very low Novelty.

David: I first saw it on How 2. It’s pretty cool.

Christian: I’ve never really liked it. Maybe because it took me ages to work out the trick the first time I saw it.

David: When does the first 4 appear? In fact, when does the first $n$ appear? That might be a good sequence.

David: 4 doesn’t appear, it turns out. Low marks for Completeness.

Christian: That makes as much sense as any of our other Completeness scores.

David: It only uses 3 digits. If only we gave marks for efficiency.

Christian: While you were doing that, I was looking at the other ‘Look and Say’ sequences in the Encyclopedia. There are some crackers! There’s a continuous version (A221646), primes that are still prime when you Look and Say them (A056815), and a spectacularly clever one that just shifts left when you Look and Say it (A088203). So, high marks for Fecundity, if that’s a category.

David: Should we mark this sequence on completely different categories to the others?

Christian: I think we should.

Efficiency $\frac{3}{5}$
Fecundity $\frac{4}{5}$
Repetitiveness $\frac{1}{5}$
Audibility $\frac{5}{5}$
TOTAL $\frac{13}{20}$

3-smooth numbers: numbers of the form $2^i 3^j$ with $i, j \geq 0$.

1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192, 216, 243, 256, 288, 324, 384, 432, 486, 512, 576, 648, 729, 768, 864, 972, 1024, 1152, 1296, 1458, 1536, 1728, 1944, 2048, 2187, 2304, 2592, 2916, 3072, 3456, 3888, ...

Christian: I think this is stupid.

David: It’s not stupid. Explain it for the children at home before you give a review.

Christian: It’s just the numbers with only 2 and 3 in their prime factorisations.

David: Yeah, so they look pretty nice, don’t they? No nasty sevens or fives, and definitely definitely nothing ending with a zero (which I hate, by the way).

Christian: I suppose they look like decent, upstanding members of society. Good mix of digits.

David: If I was going to give them a name, I’d call them the good-looking numbers.

Christian: Incredibly, that name isn’t already taken.

David: Without a doubt, we have to give 5 for Aesthetics, Completeness and Explicability. I’ll let you pick Novelty.

Christian: Underwater-OKBut I’m knocking off points from Explicability because I have no idea why you’d want to look at this sequence.

Aesthetics $\frac{5}{5}$
Completeness $\frac{5}{5}$
Explicability $\frac{3}{5}$
Novelty $\frac{0}{5}$
TOTAL $\frac{13}{20}$

Christian: Next sequence!

David: You’re going to like this one a LOT.

Golomb’s sequence: a(n) is the number of times n occurs, starting with a(1) = 1.

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 19, ...

Christian: It’s nice. But I’ve seen it before.

David: HOLD IT! That does not give you reason to take away from the Novelty score. We are not going through this again.

Christian: Was it new to you?

David: Yes it was.

Christian: Fine. What’s so great about it?

David: It’s self-referential.

Christian: So am I. What’s the big deal?

David: I didn’t know you were a Christian. BOOM.

Christian: That’s not what I meant. How is this constructed? Is it fun?

David: I don’t know, but there’s a nice formula for it, involving the golden ratio: \[ a(n) \approx \phi^{2-\phi} n^{\phi-1} \]

Christian: Stop restricting me with your closed forms!

David: It’s one of Sloane’s favourites.

Christian: Yeah, but he doesn’t have anything to say about it. It’s shallowly nice.

David: What’s up with you today?

Christian: Just not feeling it, Dave. Aesthetics and Completeness are easy 4s, but what about Explicability? It’s easy to say what it is, but not easy to say why it is this particular sequence.

David: Three. And Novelty 4.

Aesthetics $\frac{4}{5}$
Completeness $\frac{4}{5}$
Explicability $\frac{3}{5}$
Novelty $\frac{4}{5}$
TOTAL $\frac{15}{20} = \frac{3}{4}$

David: Did you know that when big rocks that orbit me are poorly, I get them “Get Well Moon” cards?


Number of steps to reach a prime under “replace n by concatenation of its prime factors”, or -1 if no such number.

-1, 0, 0, 2, 0, 1, 0, 13, 2, 4, 0, 1, 0, 5, 4, 4, 0, 1, 0, 15, 1, 1, 0, 2, 3, 4, 4, 1, 0, 2, 0, 2, 1, 5, 3, 2, 0, 2, 1, 9, 0, 2, 0, 9, 6, 1, 0, 15, ...

Christian: Ooh, this looks nice.

David: That’s why I picked it. Well, a certain Tom Fisher did.

Christian: Him again! You have squandered this opportunity. Let’s get stuck in. Low Aesthetics, because of all those $-1$s. Fair?

David: Mmm. But, what is Aesthetics? What category does the beauty of the definition fall under? Is that not Aesthetics?

Christian: Yeah.

David: You know what? I think our reviewing system is a sham.

Christian: But we must carry on. Let’s go with middling Aesthetics.

David: I don’t feel as if it can be Complete. There’s lots of factorising and checking for primes. That can’t be easy.

Christian: Yeah, it’ll be hard to get really big entries. Let’s give it 2.

David: And is it that explicable? We haven’t even bothered to explain it.

Christian: We should! Let’s take 4. Its prime factors are 2 and 2. Put them together and you get 22. The prime factors of 22 are 2 and 11. Put them together and you get 211, which is prime. We did the thing twice, so $a(4) = 2$.

David: Correct.

Christian: What if you put the primes in reverse order?

David: You get -1 for every even $n$, because the concatenation of prime factors is always even.

Christian: Bravo! I like it! Oh, and… 5 for Novelty.

David: I wish I could add a “lightening the mood” category, because you’re much happier now.

Christian: I’m so happy I might just do that. But I’m not happy enough to change the table, so that score will be a secret between you and me.

Aesthetics $\frac{3}{5}$
Completeness $\frac{2}{5}$
Explicability $\frac{3}{5}$
Novelty $\frac{5}{5}$
TOTAL $\frac{13+H}{20+\epsilon}$

Sublime numbers, numbers for which the number of divisors and the sum of the divisors are both perfect.

12, 6086555670238378989670371734243169622657830773351885970528324860512791691264, ...?

Christian: <sexual noises>

David: <happy squeals>

David: Pretty sublime, isn’t it?

Christian: It’s… beautiful. How was that second term calculated?

David: I don’t know, but whoever did it deserves a Fields medal. Scrap that, they deserve six, a perfect number of them. And a toffee apple as well. In fact I might find this man and buy him a toffee apple. If you’re out there reading this, please get in contact with me. I know your name’s probably on the OEIS, but I can’t be bothered to go to that much effort.

Christian: It’s K.S. Brown, according to the entry. According to his/her explanation, it involves Mersenne primes.

David: OF COURSE IT DOES. IT’S PERFECT NUMBERS. Perfect numbers are a Mersenne prime multiplied by a power of 2.

Christian: I really should know more about the sequence they named after me.

David: In fact, in Stephen Hawking’s book God Created the Integers, on roughly page 12, he has this fact that a perfect number can be generated from a Mersenne prime. But he gets the formula wrong! And his publisher still has not replied to my emails trying to tell them this fact.

(For legal reasons, The Aperiodical wishes to make it clear that David doesn’t know if this has been corrected in any editions published after the one he bought, but nonetheless he hasn’t received an email from Penguin.)

Christian: Scores! We’re not doing a good job of getting round to scoring today. Aesthetics?

David: I don’t know. My brain says 1 but my heart says 5. Since I do most of my mathematics with my heart, I say 5.

Christian: Well, I made some regrettable noises when I saw it, so I’ll go 5 too. Completeness: I reckon really low. Explicability: in the past we’ve knocked points off for referring to “proper divisors” in the definition.

David: The problem with novelty is that it seems to be picked at random –

Christian: Unlike the other categories?

David: I mean the properties which need to be perfect. It’s as though they picked them because it makes a surprising sequence.

Christian: That’s good though. They did the hard work so we don’t have to.

David: Let’s score it up and get on to the sixth, and winning, sequence. I’m pretty sure the last sequence will get a perfect score, so whatever we do here doesn’t matter.

Christian: Bold words.


Aesthetics $\frac{5}{5}$
Completeness $\frac{1}{5}$
Explicability $\frac{3}{5}$
Novelty $\frac{4}{5}$
TOTAL $\frac{13}{20}$


(David steps back to announce the next sequence, in case Christian hits him)

The natural numbers. Also called the whole numbers, the counting numbers or the positive integers.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, ...

Christian: <stares for a long time>

David: Scores?

Christian: You know this is wrong?

David: It isn’t wrong, it’s perfectly natural.

Christian: Take a coin from the pun jar!

David: Don’t mind if I do!

Christian: But seriously, this is the wrong sequence.

David: How?

Christian: Zero is a natural number.

David: No it bloody well isn’t.

Christian: The Roman empire crumbled and fell 1600 years ago. They can’t hurt zero any more. It’s safe to come out and say zero is natural. There’s NOTHING wrong with it.

David: We don’t use zero to label things.

Christian: I do!

David: Look at any sequence in the OEIS. It goes $a(1), a(2), a(3), \dots$ Even the sequences themselves start with A000001.

Christian: So the injustice is inherent in the system! <sigh> But maybe now isn’t the right time to have this fight. How do you want to score this?

David: Explicability has to be 5. Completeness has to be 5.

Christian: Wrong! It’s missing zero. Also, all the negative numbers.

David: Fine, Completeness $2.5 – \epsilon$. Novelty… I don’t know!

Christian: It’s the first sequence I ever heard about.

David: Is that novel, or unnovel?

Christian: It’s unnovel. It’s the very definition of not novel.

David: Why is it not novel?

Christian: There’s nothing new about it.

David: It’s THE sequence.

Christian: I reckon that makes it not novel. I won’t settle for anything above 0.

David: I refuse to score this sequence then.

natural sending offDISQUALIFIED due to too much arguing.

And the winner is…

A001462, Golomb’s sequence!

A001462 advances to the final with a respectable score of $\frac{3}{4}$.

David: The moral of the story is that it’s not OK to act natural.

Christian: You’ve never acted naturally.

Ipso Post Facto Navigato

7 Responses to “Integer Sequence Review Mêlée Hyper-Battle DX 2000 (Bracket 3)”

  1. Tom

    I have a few comments about the “explicability” of 3-smooth numbers (whether or not they are justified is another discussion :) ):

    1. The standard proof that $ |\mathbb{N}\times\mathbb{N}|=|\mathbb{N}|$ is to show that the function $f(i,j)=2^i\cdot3^j$ is injective.

    2. The smooth numbers are useful for the quadratic sieve (used for factoring large numbers). See for instance (or anything else by Pomerance on the subject).

    • David Cushing

      Our rule of explicability is that the more you have to explain it the worse it is. Like a bad joke. So even though your comments are very good they probably lower the 3-smooth numbers’ explicability to 2.

  2. Tom

    Oh, and I agree with Brent – this is a great series of posts… Thanks!


Leave a Reply

  • (will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>