login
Self-convolution with "addition" played by bitwise XOR.
4

%I #16 Jun 16 2018 17:44:47

%S 1,0,2,6,18,50,146,426,1282,3810,11394,34082,102338,306658,919874,

%T 2759154,8276898,24828386,74484386,223444258,670326242,2010964770,

%U 6032902242,18098635298,54295809826,162887261410,488661978274,1465985458850,4397955924386

%N Self-convolution with "addition" played by bitwise XOR.

%H Reinhard Zumkeller, <a href="/A199770/b199770.txt">Table of n, a(n) for n = 1..1000</a>

%F a(1)=1, a(n) = sum ( a(i) XOR a(n-i), i = 1 .. n-1).

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

%p Bits[Xor](a(i), a(n-1-i)), i=0..n-1))

%p end:

%p seq(a(n), n=0..35); # _Alois P. Heinz_, Jun 16 2018

%t a[1] = 1; a[n_] := a[n] = Sum[BitXor[a[i], a[n - i]], {i, 1, n - 1}]; Table[a[n], {n, 30}]

%o (Haskell)

%o import Data.Bits (xor)

%o a199770 n = a199770_list !! (n-1)

%o a199770_list = 1 : f [1] where

%o f xs = y : f (y : xs) where

%o y = sum $ zipWith xor xs $ reverse xs :: Integer

%o -- _Reinhard Zumkeller_, Jul 15 2012

%Y Cf. A000108 (Catalan numbers).

%Y Cf. A007462, A192484.

%K nonn,easy

%O 1,3

%A _Jacob A. Siehler_, Nov 10 2011