login
A canonical permutation designed to thwart a certain naive attempt to guess whether sequences are permutations.
1

%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