Regarding Ariel's WU above, thats what you would need to do to interpolate anyway-calculate successive differences!.
But my primary point is about rp's WU above. There are two problems. The first is that it is only very very rarely that this 'generating function' happens to be a polynomial. The second point is about the definition of complexity above. I dont think that this it's valid to use a Turing Machine criterion to decide simplicity because thats not the way the human brain works. Here's an example. Consider the sequence:
3,5,7,11,13,17...
Next number? Well 19 obviously. However, that would probably be the very last number tried by a computer, using the above definition of complexity. Generating prime numbers is very very difficult indeed, so it would be much simpler for a computer to fit a 6th order polynomial(which would fit perfectly).
Other number sequence puzzles might depend on extra 'wordly' knowledge. For example, each number might represent a character of the alphabet. As long as the sequence involves simple things like adding or multiplying the preceeding numbers the above definition of simplicity might work. However, the human brain is far too complex, so there are lots of things which would be obvious to a human, but very difficult to guess for a machine.
My primary point is that (at least at our current level of computational theory) it is impossible to develop any relationship between what humans perceive as simple or difficult and what machines perceive as simple or difficult(Isnt that the problem everyone's trying to crack anyway?).
Okay here's a footnote after some discussion with rp. The basic point above is that 'obvousness' or lack of it is a social construct. For example consider 3,1,4-5,9. What do you fit into the dash. Well 1 obviously but the reason its 1 and not something else is that the digits of pi are 'socially common'. There's nothing computationally simple involved here, but the answer is obvious because the society we live in uses pi such a lot . The same thing holds for prime numbers. We are taught about them and classify them as a seperate block in our minds, which is why the answer is obvious.
It is this very important intangible factor that I'm talking about. This is something which cannot be duplicated mechanically...