A182310 - OEIS

%I #39 Jun 29 2021 12:43:51

%S 0,1,2,4,7,5,8,13,12,11,15,9,14,10,16,25,22,30,18,28,19,27,23,29,20,

%T 31,17,26,24,21,32,49,42,64,97,82,124,67,99,83,123,71,101,88,117,80,

%U 121,70,102,86,126,66,100,87,125,68,103,85,128,193,162,244,143

%N a(0)=0, a(n+1) = (a(n) XOR floor(a(n)/2)) + 1, where XOR is the bitwise exclusive-or operator

%C As n -> infinity, a(n) -> infinity.

%H Reinhard Zumkeller, <a href="/A182310/b182310.txt">Table of n, a(n) for n = 0..10000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/XOR.html">XOR</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Binary_and#XOR">Bitwise operation XOR</a>

%F a(n) = A105081(a(n-1)+1). - _Jon Maiga_, Jun 27 2021

%e a(5) = ( a(4) XOR floor(a(4)/2) ) + 1 = (7 XOR 3) + 1 = 4+1 = 5.

%p a:= proc(n) option remember; `if`(n=0, 0, 1+

%p      (t-> Bits[Xor](t, iquo(t, 2)))(a(n-1)))

%p     end:

%p seq(a(n), n=0..100);  # _Alois P. Heinz_, Jun 29 2021

%t NestList[BitXor[#,Floor[#/2]]+1&,0,70] (* _Harvey P. Dale_, Apr 18 2015 *)

%o (C)

%o #include <stdio.h>

%o #include <math.h>

%o typedef unsigned long long ULL;

%o int main(int argc, char **argv) {

%o   ULL a=0, i=0, p, prev;

%o   while(1) {

%o     prev = a,   a = (a^(a/2)) + 1;

%o   #if 0  // "if 1" to print indices of 2^x

%o     ++i;

%o     if ( (i & ((1<<30)-1))==0 )  printf(".");

%o     if ((a^prev) > prev)

%o        printf("\n%llu at %llu,  log2: %llu ", a, i, (ULL)(100.0*log2(i)));

%o   #else

%o     printf("%llu, ", prev);

%o   #endif

%o     // Test reversion:

%o     p=a-1;

%o     ULL t=p/2;

%o     while (t)  p^=t, t/=2;

%o     if (p!=prev) printf("Reversion failed!"), exit(1);

%o   }

%o   return 0;

%o }  // from _Alex Ratushnyak_, Apr 26 2012

%o (Haskell)

%o import Data.Bits (xor)

%o a182310 n = a182310_list !! n

%o a182310_list = 0 : map (+ 1)

%o    (zipWith xor a182310_list $ map (`div` 2) a182310_list) :: [Integer]

%o -- _Reinhard Zumkeller_, Apr 25 2012

%o (PARI) terms(n) = my(x=0, i=0); while(i < n, print1(x, ", "); x=bitxor(x, floor(x/2)) + 1; i++)

%o /* Print initial 200 terms as follows: */

%o terms(200) \\ _Felix Fröhlich_, Jun 29 2021

%Y Cf. A105081, A182417.

%K nonn,base

%O 0,3

%A _Alex Ratushnyak_, Apr 24 2012