|
%I #24 Aug 17 2017 15:16:26
%S 0,2,3,1,5,6,7,8,9,4,11,12,13,14,15,16,17,18,19,20,21,10,22
%N A canonical permutation designed to thwart a certain naive attempt to guess whether sequences are permutations.
%C 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.
%C a(0)=0. Suppose a(0),...,a(n) have been defined.
%C 1. If the above method guesses that (a(0),...,a(n)) is NOT an initial subsequence of a permutation, then unmark any "marked" numbers.
%C 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)}.
%C 3. Let a(n+1) be the least unmarked number not in {a(0),...,a(n)}.
%C 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.
%H S. Alexander, <a href="http://arxiv.org/abs/1011.6626">On Guessing Whether A Sequence Has A Certain Property</a>, arXiv:1011.6626 [math.LO], 2010-2012, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Alexander/alex2.html">J. Int. Seq. 14 (2011) # 11.4.4</a>
%Y Cf. A030301.
%K nonn
%O 0,2
%A _Sam Alexander_, Nov 26 2010
|
