But why Google when you can OEIS? http://www.research.att.com/~njas/sequences/

Only after they posted the puzzle did solutions pop up on their own search engine. :)

Yeah, the "next # in the sequence" things are in theory dubious but in practice the theoretical unsoundness doesn't really cause issues (in the sense that: the people you'd want to select for will often find the pattern you want them to find, and many of the people you want to select against won't find that pattern).

The real meaning of what they're asking for is something like:

- I assert that there's a simple-but-nontrivial "algorithm" that generates this sequence. Find that algorithm, and use it to find the "next number in the sequence".

...but then you need a definition of "trivial", which is a lot of work (and most applicants know "trivial" when they see it:

  def sequence(i): return [1,11,21,1211,111221, 312211][i % 5] 

...is "trivial", so why bother explaining it that way when most applicants already "know" that's the wrong answer?

Doing a more-formal definition probably gets you into issues of Komolgorov complexity, which most applicants will not know much about.