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

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, 31, 17, 26, 24, 21, 32, 49, 42, 64, 97, 82, 124, 67, 99, 83, 123, 71, 101, 88, 117, 80, 121, 70, 102, 86, 126, 66, 100, 87, 125, 68, 103, 85, 128, 193, 162, 244, 143

Offset

0,3

Comments

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

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Eric Weisstein's World of Mathematics, XOR

Wikipedia, Bitwise operation XOR

Formula

a(n) = A105081(a(n-1)+1). - Jon Maiga, Jun 27 2021

Example

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

Maple

a:= proc(n) option remember; `if`(n=0, 0, 1+
     (t-> Bits[Xor](t, iquo(t, 2)))(a(n-1)))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Jun 29 2021

Mathematica

NestList[BitXor[#, Floor[#/2]]+1&, 0, 70] (* Harvey P. Dale, Apr 18 2015 *)

Prog

(C)
#include <stdio.h>
#include <math.h>
typedef unsigned long long ULL;
int main(int argc, char **argv) {
  ULL a=0, i=0, p, prev;
  while(1) {
    prev = a,   a = (a^(a/2)) + 1;
  #if 0  // "if 1" to print indices of 2^x
    ++i;
    if ( (i & ((1<<30)-1))==0 )  printf(".");
    if ((a^prev) > prev)
       printf("\n%llu at %llu,  log2: %llu ", a, i, (ULL)(100.0*log2(i)));
  #else
    printf("%llu, ", prev);
  #endif
    // Test reversion:
    p=a-1;
    ULL t=p/2;
    while (t)  p^=t, t/=2;
    if (p!=prev) printf("Reversion failed!"), exit(1);
  }
  return 0;
}  // from Alex Ratushnyak, Apr 26 2012
(Haskell)
import Data.Bits (xor)
a182310 n = a182310_list !! n
a182310_list = 0 : map (+ 1)
   (zipWith xor a182310_list $ map (`div` 2) a182310_list) :: [Integer]
-- Reinhard Zumkeller, Apr 25 2012
(PARI) terms(n) = my(x=0, i=0); while(i < n, print1(x, ", "); x=bitxor(x, floor(x/2)) + 1; i++)
/* Print initial 200 terms as follows: */
terms(200) \\ Felix Fröhlich, Jun 29 2021

Crossrefs

Cf. A105081, A182417.

Sequence in context: A136790 A073158 A035311 * A244591 A299324 A261076

Adjacent sequences: A182307 A182308 A182309 * A182311 A182312 A182313

Keyword

nonn,base

Author

Alex Ratushnyak, Apr 24 2012

Status

approved