The Discrete Charm of the 1, 1, 2, 3, 5, 8, ...

May 5, 2011 10:18 AM

Do you like integer sequences? Do you like poking around in the The On-Line Encyclopedia of Integer Sequences? Do you think, whoa, wait, okay, actually I like integer sequences but the OEIS is a goddam intractable maze of numbers? Do you think, man, what I wish is that someone would make an accessible blog that discusses some of the interesting entries in the OEIS for the casual fan of integer sequences? Well, that's an amazing coincidence; you should take a look at The On-Line Blog of Integer Sequences, by our very own Plutor.
posted by cortex (26 comments total)

I'm embarrassed at how often I refer to, or wish I could refer to, OEIS. Awesome.
posted by DU at 10:19 AM on May 5, 2011

Sweet little blog. I hope you keep it up, Plutor. I'm adding to my reader.
posted by Kutsuwamushi at 10:31 AM on May 5, 2011

That's the nerdiest damn thing I've seen in ages makes bookmark of link
posted by It's Never Lurgi at 10:39 AM on May 5, 2011

"Do you think, whoa, wait, okay, actually I like integer sequences but the OEIS is a goddam intractable maze of numbers?"

Good post, but is the anti-OEIS editorializing necessary every time we discuss this?
posted by orthogonality at 10:40 AM on May 5, 2011 [7 favorites]

I think there are good points to intractable mazes, so you are now my enemy.

but this blog? this blog I like.
posted by jessamyn at 10:43 AM on May 5, 2011

Do you think, whoa, wait, okay, actually I like integer sequences but the OEIS is a goddam intractable maze of numbers?

No, I think the OEIS is awesome.
posted by grouse at 10:45 AM on May 5, 2011

This is one of those great ideas that makes me just a little mad I didn't think of it. Awesome! that means I'll be paying attention. Great blog!
posted by milestogo at 10:45 AM on May 5, 2011

Do like integer sequences?

You know, if you use the contact form, a mod will fix that for you.
posted by y2karl at 10:56 AM on May 5, 2011

I would like to request a blog entry on the Catalan numbers, which are pretty much my favourite number sequence ever. They count hundreds of interesting combinatorial objects, such as 321-avoiding permutations, complete binary trees, and the number of ways you can put together n ('s and n )'s to form a 'valid' parenthetical sequence. (ie, something that could (if one wanted) appear in a sentence (or even a paragraph (or book)) without pissing ff one's editor (or reader).) The parentheses in that last sentence form the sequence (()(())()), which has 5 opening parentheses and 5 closing parentheses.

Catalans also count 'ascii mountain ranges', which you can draw using '/' and '\' in such a way that the mountains never fall below the left-starting elevation... Like so:

    /\
 /\/  \/\
/        \

(If you squish the mountain range into a single line and turn all of the / into ( and \ into ), you get a valid parenthetical sequence...)

Catalans also count non-crossing partitions, which give a basis for the hot, hot Temperley-Lieb algebra.

ok, I'll stop now.
posted by kaibutsu at 10:56 AM on May 5, 2011 [5 favorites]

God damn you, y2karl.

God damn you!!!!

I was so excited to see no one had made that joke then, then the "2 new comments" thing popped up while I was typing. Hell.
posted by kavasa at 10:58 AM on May 5, 2011

You know, if you use the contact form, a mod will fix that for you.

I HAVE NO EARTHLY IDEA WHAT YOU MEAN.
posted by cortex at 11:00 AM on May 5, 2011

I HAVE NO EARTHLY IDEA WHAT YOU MEAN.

DON'T MEAN HAVE NO EARTHLY IDEA WHAT MEAN ?</
posted by y2karl at 11:13 AM on May 5, 2011

2, 4, 6, 8, who do we appreciate? Plutor! Plutor! Yaaaaaaaaaay Plutor!

(That's about as mathy as I get.)
posted by Metroid Baby at 11:16 AM on May 5, 2011

kaibutsu: "I would like to request a blog entry on the Catalan numbers, which are pretty much my favourite number sequence ever."

Math nerd and contributing an almost fully-written post. I like your style.
posted by Plutor at 11:17 AM on May 5, 2011 [1 favorite]

So basically, no prime can be highly anundant.

If σ(n) > σ(m) is true for for all m < n, that number is called highly abundant.

σ(2) = 1, yes?
σ(3) = 1, yes?
σ(3) > σ(2) is false, yes? Is it really σ(3) ≥ σ(2)?


Hey, Plutor, how about a hyperlink for "proper divisor" and maybe some more examples.

I think it's:

n    σ(n)    σ(n)/n  highly  super
1    0        0        y          y
2    1        1/2      y          y
3    1        1/3      y?         n
4    3        3/4      y          y
5    1        1/5      n          n
6    6        1        y          y
7    1        1/7      n          n
8    7        7/8      y          n
9    4        4/9      n          n
10   8        4/5      y          n
11   1       1/11      n          n
12  16        4/3      y          y

posted by orthogonality at 11:18 AM on May 5, 2011

Agh, you're right, I screwed up my definition of highly and super abundant numbers. The divisor function σ(n) doesn't just include proper divisors (which is all divisors that aren't n itself). It's all divisors. The restricted divisor function (which doesn't include n) is s(n).

So σ(2) = 1 + 2 = 3, and σ(3) = 1 + 3 = 4, which is why both are highly abundant. My bad. I'll update that post.
posted by Plutor at 11:30 AM on May 5, 2011 [1 favorite]

Ok, including all divisors, not just posh proper ones:

n    σ(n)    σ(n)/n  highly  super
1    1         1       y          y
2    3        3/2      y          y
3    4        4/3      y         n
4    7        7/4      y          y
5    6        6/5      n          n
6    12        2       y          y
7    8        8/7      n          n
8    15      15/8      y          n
9    13      13/9      n          n
10   18       9/5      y          n
11   12     12/11      n          n
12   28       7/3      y          y

posted by orthogonality at 11:42 AM on May 5, 2011

That's really a depressing series. You can get on board only if you exceed every number prior to you.

Look at poor eleven; he's as good as six, and better than everyone below six, and he's better than seven too, but because eight came by and raised the bar, he's off the list.

The bar is monotonically increasing and there's no way to stop it. It's like, if today you have an idea that's better that the idea Wozniak and Jobs had in the seventies, it doesn't matter, because now thew bar has been set by Page and Brin.

FML.
posted by orthogonality at 11:51 AM on May 5, 2011

Looks right to me. Thanks for the bug report. Entry corrected.
posted by Plutor at 11:51 AM on May 5, 2011

Plutor: but the second paragraph is still wrong. (That's the bit that made me confused and have to go consult wikipedia.)
posted by aspo at 12:15 PM on May 5, 2011

Yeah, looks like you've mixed sigmas with esses.
posted by orthogonality at 12:21 PM on May 5, 2011

Double fixed. Stupid math. Grumble.

Thanks, guys.
posted by Plutor at 12:23 PM on May 5, 2011

(I recommend that you blame board-brain. That's what I always do.)
posted by kaibutsu at 9:07 PM on May 5, 2011

I was having a hell of a time figuring out where you got your ASCII mountain ranges point until I realized that they were equivalent to Dyck Paths (which are neat and useful, but also have a name that's fun to say).
posted by Plutor at 6:43 AM on May 6, 2011

See also functions from the set 1...N to 1...N such that:
a) f(i)<=i and
b) f(i)<=f(j) whenever i<=j.
(hint, draw the graph of such a function f as a step function...)
The collection of such functions has the bonus property of being closed under function composition, providing a very nice monoid structure on something Catalan-counted...
posted by kaibutsu at 7:25 PM on May 7, 2011

Sneak preview: I'm planning another theme week next week, using Catalan numbers as a jumping off point. Now I just have to get through this week.
posted by Plutor at 8:04 AM on May 9, 2011