The powerful integer sequence website OEIS

强大的整数数列网站OEIS 苏剑林 · 2014-07-17 · Mathematics number theory integer

OEIS?: http://oeis.org/

Lately I've been studying analytic number theory, and I keep feeling more strongly that number theory really is a wonderful thing — through it, seemingly all facets of mathematics, discrete and continuous, real and complex, and even physics, turn out to be connected. It's easy to see why Gauss once said, "Mathematics is the queen of sciences, and number theory is the queen of mathematics." Today, while thinking about the bounds on the number of primes, I needed to figure out the binomial coefficient

$$C_{n}^{2n}=\binom{2n}{n}=\frac{(2n)!}{n!\ n!}$$

what the highest power of 2 that divides it is. Intuition tells me the exponent should increase as $n$ grows, but that's not actually the case — for instance, $C_{15}^{30}$ is divisible by 16, while $C_{20}^{40}$ is only divisible by at most 4. It seemed to follow no pattern at all, so I asked around in the group. Among the replies, Wayne suggested:

You could write a little program to compute some data, and then search for it on OEIS.

Following his suggestion, I wrote the Python code below

import math

def cout2(n):
  s = 0
  while n%2==0:
      s = s+1
      n = n//2
  return s

for n in range(1,100):
    m = math.factorial(2*n)//math.factorial(n)//math.factorial(n)
    print(cout2(m), end=', ')

which outputs the result

1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,

I directly plugged this string of numbers into OEIS to search, and got

http://oeis.org/A000120

It turns out this sequence had already been studied and had long since been catalogued by OEIS. Each term of the sequence is exactly the number of 1's in the binary expansion of n (that is, the number of 1's in the binary representation corresponding to the decimal number n). The overall trend of the sequence is to increase as $n$ grows, but locally it doesn't necessarily follow a fixed pattern. If you truncate the sequence at each point where the value is 1, you get a series of finite sub-sequences, and the pattern in these sub-sequences turns out to be relatively clearer (binary numbers with a fixed number of digits, arranged in increasing order, with the count of 1's tallied). The page also lists various properties of the sequence, reference links, and so on. I really have to say OEIS is incredibly powerful! I recall having referenced its material a long time ago, but only now do I realize just how powerful it is. Here's its description from Wikipedia:

OEIS, short for The On-Line Encyclopedia of Integer Sequences, can be translated into Chinese as "整数数列线上大全" (Online Encyclopedia of Integer Sequences). It is a searchable online database of integer sequences. It's an important mathematical resource, since each entry records the first several terms of an integer sequence, along with keywords, links, and more. As of June 2009, OEIS already contained more than 160,000 sequences.