The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A182659 A canonical permutation designed to thwart a certain naive attempt to guess whether sequences are permutations. 1
0, 2, 3, 1, 5, 6, 7, 8, 9, 4, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 10, 22 (list; graph; refs; listen; history; text; internal format)



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.


Table of n, a(n) for n=0..22.

S. Alexander, On Guessing Whether A Sequence Has A Certain Property, arXiv:1011.6626 [math.LO], 2010-2012, J. Int. Seq. 14 (2011) # 11.4.4


Cf. A030301.

Sequence in context: A065883 A214392 A071975 * A197701 A292770 A242107

Adjacent sequences:  A182656 A182657 A182658 * A182660 A182661 A182662




Sam Alexander, Nov 26 2010



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 20 17:42 EDT 2021. Contains 347588 sequences. (Running on oeis4.)