[seqfan] A thought on sequences

[john.mason at lispa.it]

Define the complexity of an integer sequence to be the number of data 
required to allow the calculation of a single, isolated term, a(n); define 
the complexity to be -1 if the number of data required is without limit.
The words ?single, isolated? are included in the definition so as to imply 
that the data counted should allow the calculation of a single term 
without the necessity of calculating all previous terms.
For example:
- A000004 (a(n)=0 for all n) has a complexity of 0, as no datum is 
required in order to calculate a(n).
- A000027 (a(n)=n for all n) has a complexity of 1, as a single value, n, 
is required to calculate a(n).
- A000040 (a(n) = the n?th prime) has a complexity of 1, as a single 
value, a(n-1), is required to determine, using a simple search algorithm, 
a(n).
- A000045 (the Fibonacci series) would have had a complexity of 2 before 
the year 1720, as the two values a(n-2) and a(n-1) would have been 
required to calculate a(n). Now the sequence has a complexity of 1, as a 
formula for calculating a(n) from n was found in that period.
- A254077 (a(n) = n if n <= 3, otherwise the smallest number not occurring 
earlier such that gcd(a(n),a(n-2)) > gcd(a(n),a(n-1)))  has a complexity 
of -1, as the number of terms needed to determine a(n) is without limit.
- A006450 (primes such that their position in A000040 is prime), has, I 
believe, a complexity of 2, as determining a(n) from just a(n-1) would 
seem to be difficult. On the other hand, knowing both n-1 and a(n-1) 
should be sufficient.
If we were to define a sequence a(n) to be the complexity of the OEIS 
sequence A(n), then the first few terms would be:
1,-1,1,0,1,1,1,1,1,1,1,0,...
The value a(2) = -1 is due to A000002 being the Kolakoski sequence.
If we were to insert a(n) into OEIS, with (say) sequence number A345678, 
then the self-referential value a(345678) would be 1. I think.

john
__________________________________