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).

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, 0, 16, 17, 19, 18, 22, 23, 21, 20, 28, 29, 31, 30, 26, 27, 25, 24, 8, 9, 11, 10, 14, 15, 13, 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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• base
• look
• nice
• easy

Comments

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)).

From John W. Layman: {a(n)} is a self-similar sequence under Kimberling's "upper-trimming" operation.

a(A000225(n)) = 0; a(A062289(n)) > 0; a(A038558(n)) = n. - Reinhard Zumkeller, Mar 06 2013

Examples

			If n = 18 = 10010_2, derivative is (1+0)(0+0)(0+1)(1+0) = 1011_2, so a(18)=11.
		

References

• 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

Links

• T. D. Noe, Table of n, a(n) for n = 0..4096
• Clark Kimberling, Fractal sequences.
• Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625 [math.CO], 2020-2021.
• J. W. Layman, View the fractal-like graph of a(n) vs. n.
• Ralf Stephan, Some divide-and-conquer sequences ....
• Ralf Stephan, Table of generating functions.

Crossrefs

Cf. A038570, A038571. See A003415 for another definition of the derivative of a number.

Cf. A038556 (rotates n instead of shifting).

Cf. A000035.

Cf. A030308.

Programs

Haskell

import Data.Bits (xor)
a038554 n = foldr (\d v -> v * 2 + d) 0 $ zipWith xor bs $ tail bs
   where bs = a030308_row n
-- Reinhard Zumkeller, May 26 2013, Mar 06 2013

Maple

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) ];

Mathematica

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 *)
Table[FromDigits[Mod[Total[#],2]&/@Partition[IntegerDigits[n,2],2,1],2],{n,0,90}] (* Harvey P. Dale, Oct 27 2015 *)

PARI

a003188(n)=bitxor(n, n>>1);
a(n)=if(n<2, 0, a003188(n) - 2^logint(a003188(n), 2)); \\ Indranil Ghosh, Apr 26 2017

Python

import math
def a003188(n): return n^(n>>1)
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

Formula

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

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

a(0)=0, a(2n) = 2*a(n) + [n odd], a(2n+1) = 2*a(n) + [n>0 even]. - Ralf Stephan, Oct 20 2003

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.

Extensions

More terms from Erich Friedman