I like this idea: the OEIS-complexity of a sequence (= how early it comes in the encyclopedia). But yes, what I thought of was what the other commenter wrote: given some primitive operations, how long a program can generate the sequence?