[seqfan] Re: A thought on sequences

[israel at math.ubc.ca]

All infinite sequences in the OEIS are, or should be, uniquely determined, 
although there may be some for which no algorithm exists. But if there is 
an algorithm, your "complexity" should never be more than 1. I don't see 
how you can forbid the algorithm from doing intermediate calculations that 
are equivalent to finding a(k) for 0 <= k < n, unless perhaps you try to 
bound the algorithm's usage of time or memory.

Cheers,
Robert

On Apr 3 2018, john.mason at lispa.it wrote:

>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
>__________________________________
>
>--
>Seqfan Mailing list - http://list.seqfan.eu/
>
>