cp's OEIS Frontend

A038554 Derivative of n: write n in binary, replace each pair of adjacent bits with their mod 2 sum (a(0)=a(1)=0 by convention). Also n XOR (n shift 1).

%I A038554 #56 Jan 24 2024 19:39:51
%S A038554 0,0,1,0,2,3,1,0,4,5,7,6,2,3,1,0,8,9,11,10,14,15,13,12,4,5,7,6,2,3,1,
%T A038554 0,16,17,19,18,22,23,21,20,28,29,31,30,26,27,25,24,8,9,11,10,14,15,13,
%U A038554 12,4,5,7,6,2,3,1,0,32,33,35,34,38,39,37,36,44,45,47,46,42,43,41,40,56,57
%N A038554 Derivative of n: write n in binary, replace each pair of adjacent bits with their mod 2 sum (a(0)=a(1)=0 by convention). Also n XOR (n shift 1).
%C A038554 From _Antti Karttunen_: this is also a version of A003188: a(n) = A003188(n) - 2^floor(log_2(A003188(n))), that is, the corresponding Gray code expansion, but with highest 1-bit turned off. Also a(n) = A003188(n) - 2^floor(log_2(n)).
%C A038554 From _John W. Layman_: {a(n)} is a self-similar sequence under Kimberling's "upper-trimming" operation.
%C A038554 a(A000225(n)) = 0; a(A062289(n)) > 0; a(A038558(n)) = n. - _Reinhard Zumkeller_, Mar 06 2013
%D A038554 Hsien-Kuei Hwang, S Janson, TH Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585
%H A038554 T. D. Noe, <a href="/A038554/b038554.txt">Table of n, a(n) for n = 0..4096</a>
%H A038554 Clark Kimberling, <a href="http://faculty.evansville.edu/ck6/integer/fractals.html">Fractal sequences</a>.
%H A038554 Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, <a href="https://arxiv.org/abs/2012.04625">Finding structure in sequences of real numbers via graph theory: a problem list</a>, arXiv:2012.04625 [math.CO], 2020-2021.
%H A038554 J. W. Layman, <a href="http://intranet.math.vt.edu/people/layman/sequences/sequences.htm">View the fractal-like graph of a(n) vs. n</a>.
%H A038554 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>.
%H A038554 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>.
%F A038554 If 2*2^k <= n < 3*2^k then a(n) = 2^k + a(2^(k+2)-n-1); if 3*2^k <= n < 4*2^k then a(n) = a(n-2^(k+1)). - _Henry Bottomley_, May 11 2000
%F A038554 G.f.: (1/(1-x)) * Sum_{k>=0} 2^k*(t^4-t^3+t^2)/(1+t^2), t=x^2^k. - _Ralf Stephan_, Sep 10 2003
%F A038554 a(0)=0, a(2n) = 2*a(n) + [n odd], a(2n+1) = 2*a(n) + [n>0 even]. - _Ralf Stephan_, Oct 20 2003
%F A038554 a(0) = a(1) = 0, a(4n) = 2*a(2n), a(4n+2) = 2*a(2n+1)+1, a(4n+1) = 2*a(2n)+1, a(4n+3) = 2*a(2n+1). Proof by Nikolaus Meyberg following a conjecture by _Ralf Stephan_.
%e A038554 If n = 18 = 10010_2, derivative is (1+0)(0+0)(0+1)(1+0) = 1011_2, so a(18)=11.
%p A038554 A038554 := proc(n) local i,b,ans; ans := 0; b := convert(n,base,2); for i to nops(b)-1 do ans := ans+((b[ i ]+b[ i+1 ]) mod 2)*2^(i-1); od; RETURN(ans); end; [ seq(A038554(i),i=0..100) ];
%t A038554 a[0] = a[1] = 0; a[n_ /; Mod[n, 4] == 0] := a[n] = 2*a[n/2]; a[n_ /; Mod[n, 4] == 1] := a[n] =  2*a[(n-1)/2] + 1; a[n_ /; Mod[n, 4] == 2] := a[n] = 2*a[n/2] + 1; a[n_ /; Mod[n, 4] == 3] := a[n] = 2*a[(n-1)/2]; Table[a[n], {n, 0, 81}] (* _Jean-François Alcover_, Jul 13 2012, after _Ralf Stephan_ *)
%t A038554 Table[FromDigits[Mod[Total[#],2]&/@Partition[IntegerDigits[n,2],2,1],2],{n,0,90}] (* _Harvey P. Dale_, Oct 27 2015 *)
%o A038554 (Haskell)
%o A038554 import Data.Bits (xor)
%o A038554 a038554 n = foldr (\d v -> v * 2 + d) 0 $ zipWith xor bs $ tail bs
%o A038554    where bs = a030308_row n
%o A038554 -- _Reinhard Zumkeller_, May 26 2013, Mar 06 2013
%o A038554 (PARI) a003188(n)=bitxor(n, n>>1);
%o A038554 a(n)=if(n<2, 0, a003188(n) - 2^logint(a003188(n), 2)); \\ _Indranil Ghosh_, Apr 26 2017
%o A038554 (Python)
%o A038554 import math
%o A038554 def a003188(n): return n^(n>>1)
%o A038554 def a(n): return 0 if n<2 else a003188(n) - 2**int(math.floor(math.log(a003188(n), 2))) # _Indranil Ghosh_, Apr 26 2017
%Y A038554 Cf. A038570, A038571. See A003415 for another definition of the derivative of a number.
%Y A038554 Cf. A038556 (rotates n instead of shifting).
%Y A038554 Cf. A000035.
%Y A038554 Cf. A030308.
%K A038554 nonn,base,look,nice,easy
%O A038554 0,5
%A A038554 _N. J. A. Sloane_
%E A038554 More terms from _Erich Friedman_