A268718 - OEIS

%I #24 Jun 07 2017 12:26:47

%S 0,1,4,2,6,8,3,7,10,12,15,11,5,13,16,14,18,20,23,19,29,21,24,22,9,25,

%T 28,26,30,32,27,31,34,36,39,35,45,37,40,38,57,41,44,42,46,48,43,47,17,

%U 49,52,50,54,56,51,55,58,60,63,59,53,61,64,62,66,68,71,67,77,69,72,70,89,73,76,74,78,80,75,79,113,81

%N Permutation of natural numbers: a(0) = 0, a(n) = 1 + A003188(A006068(n)-1), where A003188 is binary Gray code and A006068 is its inverse.

%H Antti Karttunen, <a href="/A268718/b268718.txt">Table of n, a(n) for n = 0..8191</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F a(0) = 0, and for n >= 1, a(n) = A105081(A006068(n)) = 1 + A003188(A006068(n)-1).

%F Other identities. For all n >= 1:

%F a(A128309(n)) = A128309(n)+2. [Maps any even odious number to that number + 2.]

%t {0}~Join~Table[1 + BitXor[#, Floor[#/2]] &[BitXor @@ Table[Floor[n/2^m], {m, 0, Floor[Log[2, n]]}] - 1], {n, 81}] (* _Michael De Vlieger_, Feb 29 2016, after _Jean-François Alcover_ at A006068 and _Robert G. Wilson v_ at A003188 *)

%o (Scheme) (define (A268718 n) (if (zero? n) n (A105081 (A006068 n))))

%o (PARI)

%o a003188(n)=bitxor(n, n>>1);

%o a006068(n)= {

%o     my( s=1, ns );

%o     while ( 1,

%o         ns = n >> s;

%o         if ( 0==ns, break() );

%o         n = bitxor(n, ns);

%o         s <<= 1;

%o     );

%o     return (n);

%o } \\ by _Joerg Arndt_

%o a(n)=if(n==0, 0, 1 + a003188(a006068(n) - 1)); \\ _Indranil Ghosh_, Jun 07 2017

%o (Python)

%o def a003188(n): return n^(n>>1)

%o def a006068(n):

%o     s=1

%o     while True:

%o         ns=n>>s

%o         if ns==0: break

%o         n=n^ns

%o         s<<=1

%o     return n

%o def a(n): return 0 if n==0 else 1 + a003188(a006068(n) - 1) # _Indranil Ghosh_, Jun 07 2017

%Y Inverse: A268717.

%Y Cf. A003188, A006068, A105081, A128309.

%Y Row 1 of array A268830.

%Y Cf. A092246 (fixed points).

%Y Cf. A268818 ("square" of this permutation).

%Y Cf. A268822 ("shifted square"), A268824 ("shifted cube") and also A268826, A268828 and A268832 (higher "shifted powers").

%K nonn

%O 0,3

%A _Antti Karttunen_, Feb 12 2016