|
%I #56 Jan 24 2024 19:39:51
%S 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 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 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 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 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 From _John W. Layman_: {a(n)} is a self-similar sequence under Kimberling's "upper-trimming" operation.
%C a(A000225(n)) = 0; a(A062289(n)) > 0; a(A038558(n)) = n. - _Reinhard Zumkeller_, Mar 06 2013
%D 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 T. D. Noe, <a href="/A038554/b038554.txt">Table of n, a(n) for n = 0..4096</a>
%H Clark Kimberling, <a href="http://faculty.evansville.edu/ck6/integer/fractals.html">Fractal sequences</a>.
%H 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 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 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>.
%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>.
%F 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 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 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 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 If n = 18 = 10010_2, derivative is (1+0)(0+0)(0+1)(1+0) = 1011_2, so a(18)=11.
%p 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 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 Table[FromDigits[Mod[Total[#],2]&/@Partition[IntegerDigits[n,2],2,1],2],{n,0,90}] (* _Harvey P. Dale_, Oct 27 2015 *)
%o (Haskell)
%o import Data.Bits (xor)
%o a038554 n = foldr (\d v -> v * 2 + d) 0 $ zipWith xor bs $ tail bs
%o where bs = a030308_row n
%o -- _Reinhard Zumkeller_, May 26 2013, Mar 06 2013
%o (PARI) a003188(n)=bitxor(n, n>>1);
%o a(n)=if(n<2, 0, a003188(n) - 2^logint(a003188(n), 2)); \\ _Indranil Ghosh_, Apr 26 2017
%o (Python)
%o import math
%o def a003188(n): return n^(n>>1)
%o 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 Cf. A038570, A038571. See A003415 for another definition of the derivative of a number.
%Y Cf. A038556 (rotates n instead of shifting).
%Y Cf. A000035.
%Y Cf. A030308.
%K nonn,base,look,nice,easy
%O 0,5
%A _N. J. A. Sloane_
%E More terms from _Erich Friedman_
|
