OFFSET
1,2
COMMENTS
To construct the sequence: start from the Feigenbaum sequence A035263 = 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, ..., then change 1 -> 0, 2 and 0 -> 1, 1. - Philippe Deléham, Apr 18 2004
This Feigenbaum interpretation is equivalent to writing n+1 = binary "...1 00..00 x" where x is the least significant bit and zero or more 0's. If an odd number of 0's then a(n) = 1, otherwise a(n) = 2*x. In a similar way, if n-1 = binary "...0 11..11 x" with an odd number of 1's then a(n)=1 and otherwise a(n) = 2*x. - Kevin Ryde, Oct 17 2020
From Mikhail Kurkov, Mar 25 2021: (Start)
This sequence can be represented as a binary tree. Each child to the right is obtained by applying mex to the parent, and each child to the left is obtained by applying mex to the set formed by the parent and its second child:
( )
|
...................0...................
2 1
1......../ \........0 2......../ \........0
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
2 0 2 1 1 0 2 1
1 0 2 1 1 0 2 0 2 0 2 1 1 0 2 0
etc.
Here mex means smallest nonnegative missing number.
Each parent and its two children form a set {0,1,2}. (End)
LINKS
Mikhail Kurkov, Table of n, a(n) for n = 1..8192 [verification needed]
FORMULA
a(n) = 0 iff n = A079523(k), a(n) = 1 iff n = A081706(2*k) or n = 1 + A081706(2*k), a(n) = 2 iff n = A036554(k).
a(2*n-1) + a(2*n) = 2.
From Mikhail Kurkov, Oct 10 2020: (Start)
a(2^m-1) = 1 - m mod 2, m > 0,
a(2^m) = 1 + m mod 2, m > 0,
a(2^m+k) = a(k) for 0 < k < 2^m-1, m > 1.
a(2^m-k) = 2 - a(k-1) for 1 < k <= 2^(m-1), m > 1. (End)
a(2n+1) = mex{a(n)}, a(2n) = mex{a(n),a(2n+1)} or a(2n+1) = [a(n)=0], a(2n) = 2 - [a(n)=2] for n > 0 with a(1) = 0. - Mikhail Kurkov, Mar 25 2021
MATHEMATICA
Nest[ Function[ l, {Flatten[(l /. {0 -> {0, 2}, 1 -> {0, 2}, 2 -> {1, 1}}) ]}], {0}, 7] (* Robert G. Wilson v, Mar 03 2005 *)
PROG
(PARI) a(n)={while(1, my(m=logint(n, 2)); if(n==2*2^m-1, return(m%2)); if(n==2^m, return(1 + m%2)); n-=2^m)} \\ Andrew Howroyd, Oct 17 2020
(PARI) a(n) = n++; my(k=valuation(n>>1, 2)); if(k%2==1, 1, 2*(n%2)); \\ Kevin Ryde, Oct 17 2020
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Philippe Deléham, Feb 24 2004
EXTENSIONS
More terms from Robert G. Wilson v, Mar 03 2005
STATUS
approved