cp's OEIS Frontend

A252867 a(n) = n if n <= 2, otherwise the smallest number not occurring earlier having in its binary representation at least one bit in common with a(n-2), but none with a(n-1).

%I A252867 #87 Nov 12 2024 22:18:10
%S A252867 0,1,2,5,10,4,3,12,17,6,9,18,8,7,24,33,14,32,11,36,19,40,16,13,48,15,
%T A252867 80,34,20,35,28,65,22,41,66,21,42,68,25,38,72,23,64,26,69,50,73,52,67,
%U A252867 44,81,46,129,30,97,130,29,98,132,27,100,131,56,70,49,74,37,82
%N A252867 a(n) = n if n <= 2, otherwise the smallest number not occurring earlier having in its binary representation at least one bit in common with a(n-2), but none with a(n-1).
%C A252867 Conjectured to be a permutation of the nonnegative integers. [Comment modified by _N. J. A. Sloane_, Jan 10 2015]
%C A252867 This is a purely set-based version of A098550, using the binary representation of numbers.
%C A252867 An equivalent definition in terms of sets: S(0) = {}, S(1) = {0}, S(2) = {1}; thereafter S(n) is the smallest set (different from the S(i) with i < n) of nonnegative integers such that S(n) meets S(n-2) but is disjoint from S(n-1). - _N. J. A. Sloane_, Mar 27 2022; corrected Aug 01 2022.
%H A252867 Chai Wah Wu, <a href="/A252867/b252867.txt">Table of n, a(n) for n = 0..50002</a> (First 10000 terms from Reinhard Zumkeller)
%H A252867 David L. Applegate, Hans Havermann, Bob Selcoe, Vladimir Shevelev, N. J. A. Sloane, and Reinhard Zumkeller, <a href="http://arxiv.org/abs/1501.01669">The Yellowstone Permutation</a>, arXiv preprint arXiv:1501.01669 [math.NT], 2015 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Sloane/sloane9.html">J. Int. Seq. 18 (2015) 15.6.7</a>.
%H A252867 Chai Wah Wu, <a href="/A252867/a252867.png">Scatterplot of first million terms</a>
%H A252867 Chai Wah Wu, <a href="/A252867/a252867_1.png">Scatterplot of first million terms</a>, with red lines powers of 2.
%H A252867 Chai Wah Wu, <a href="/A252867/a252867.zip.txt">Gzipped file with first million terms</a> [Save file, delete .txt suffix, then open]
%e A252867 The sequence of sets is {}, {0}, {1}, {0,2}, {1,3}, {2}, {0,1}, {2,3}. After the initial 3 terms, S(n) is the minimum set (as ordered by A048793) that has a nonempty intersection with S(n-2) but empty intersection with S(n-1). [Typos corrected by _N. J. A. Sloane_, Aug 01 2022 at the suggestion of _Michel Dekking_.]
%e A252867 Comment from _N. J. A. Sloane_, Dec 31 2014: The binary expansions of the first few terms are:
%e A252867 0  = 000000
%e A252867 1  = 000001
%e A252867 2  = 000010
%e A252867 5  = 000101
%e A252867 10 = 001010
%e A252867 4  = 000100
%e A252867 3  = 000011
%e A252867 12 = 001100
%e A252867 17 = 010001
%e A252867 6  = 000110
%e A252867 9  = 001001
%e A252867 18 = 010010
%e A252867 8  = 001000
%e A252867 7  = 000111
%e A252867 24 = 011000
%e A252867 33 = 100001
%e A252867 14 = 001110
%e A252867 32 = 100000
%e A252867 11 = 001011
%e A252867 36 = 100100
%e A252867 19 = 010011
%e A252867 40 = 101000
%e A252867 ...
%p A252867 read("transforms") : # define ANDnos
%p A252867 A252867 := proc(n)
%p A252867     local a,known,i ;
%p A252867     option remember;
%p A252867     if n <=2 then
%p A252867         n;
%p A252867     else
%p A252867         for a from 3 do
%p A252867             known := false ;
%p A252867             for i from 1 to n-1 do
%p A252867                 if procname(i) = a then
%p A252867                     known := true;
%p A252867                     break;
%p A252867                 end if;
%p A252867             end do:
%p A252867             if not known then
%p A252867                 if ANDnos(a, procname(n-1)) = 0 and ANDnos(a,procname(n-2)) > 0 then
%p A252867                     return a;
%p A252867                 end if;
%p A252867             end if;
%p A252867         end do:
%p A252867     end if
%p A252867 end proc:
%p A252867 seq(A252867(n),n=0..200) ; # _R. J. Mathar_, May 02 2024
%t A252867 a[n_] := a[n] = If[n<3, n, For[k=3, True, k++, If[FreeQ[Array[a, n-1], k], If[BitAnd[k, a[n-2]] >= 1 && BitAnd[k, a[n-1]] == 0, Return[k]]]]];
%t A252867 Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Oct 03 2018 *)
%o A252867 (PARI) invecn(v,k,x)=for(i=1,k,if(v[i]==x,return(i)));0
%o A252867 alist(n)=local(v=vector(n,i,i-1), x); for(k=4, n, x=3; while(invecn(v, k-1, x)||!bitand(v[k-2], x)||bitand(v[k-1],x), x++); v[k]=x); v
%o A252867 (Haskell)
%o A252867 import Data.Bits ((.&.)); import Data.List (delete)
%o A252867 a252867 n = a252867_list !! n
%o A252867 a252867_list = 0 : 1 : 2 : f 1 2 [3..] where
%o A252867    f :: Int -> Int -> [Int] -> [Int]
%o A252867    f u v ws = g ws where
%o A252867      g (x:xs) = if x .&. u > 0 && x .&. v == 0
%o A252867                    then x : f v x (delete x ws) else g xs
%o A252867 -- _Reinhard Zumkeller_, Dec 24 2014
%o A252867 (Python)
%o A252867 A252867_list, l1, l2, s, b = [0,1,2], 2, 1, 3, set()
%o A252867 for _ in range(10**2):
%o A252867     i = s
%o A252867     while True:
%o A252867         if not (i in b or i & l1) and i & l2:
%o A252867             A252867_list.append(i)
%o A252867             l2, l1 = l1, i
%o A252867             b.add(i)
%o A252867             while s in b:
%o A252867                 b.remove(s)
%o A252867                 s += 1
%o A252867             break
%o A252867         i += 1 # _Chai Wah Wu_, Dec 27 2014
%Y A252867 Cf. A098550, A252865, A048793, A252868.
%Y A252867 Reading this sequence mod 2 gives A253050 and A253051.
%Y A252867 Cf. A253581, A253582, A253589 (binary weight), A253603.
%Y A252867 Analyzed further in A303596, A303597, A303598, A303599, A305368.
%Y A252867 The graphs of A109812, A252867, A305369, A305372 all have roughly the same, mysterious, fractal-like structure. - _N. J. A. Sloane_, Jun 03 2018
%K A252867 nonn,look,base
%O A252867 0,3
%A A252867 _Franklin T. Adams-Watters_, Dec 23 2014