cp's OEIS Frontend

A surjection N->N designed to spite a guesser who is trying to guess whether it's a surjection, using the following naive guessing method: Guess that (n0,...,nk) is a subsequence of a surjection iff it contains every natural less than log_2(k+1).

This sequence causes the would-be guesser to change his mind infinitely often.

a(0)=0. Assume a(0),...,a(n) have been defined.

If the above guesser guesses that (a(0),...,a(n)) IS the beginning of a surjective sequence, then let a(n+1)=0. Otherwise let a(n+1) be the least number not in (a(0),...,a(n)).

A naive way to guess whether a function f:N->N is a permutation, based on just an initial subsequence (f(0),...,f(n)), is to guess "no" if (f(0),...,f(n)) contains a repeated entry or if there is some i in {0,...,n} such that i is not in {f(0),...,f(n)} and 2 i<=n; and guess "yes" otherwise. a(n) thwarts that method, causing it to change its mind infinitely often as n->infinity.

a(0)=0. Suppose a(0),...,a(n) have been defined.

1. If the above method guesses that (a(0),...,a(n)) is NOT an initial subsequence of a permutation, then unmark any "marked" numbers.

2. If the above method guesses that (a(0),...,a(n)) IS an initial subsequence of a permutation, then "mark" the smallest number not in {a(0),...,a(n)}.

3. Let a(n+1) be the least unmarked number not in {a(0),...,a(n)}.

A030301 can be derived by a similar method, where instead of trying to guess whether sequences are permutations, the naive victim is trying to guess whether sequences contain infinitely many 0s.