|
| |
|
|
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).
|
|
30
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
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
|
|
|
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
C. 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, Dec 08, 2020
J. W. Layman, View the fractal-like graph of a(n) vs. n
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
|
|
|
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) = 2a(n) + [n odd], a(2n+1) = 2a(n) + [n>0 even]. - Ralf Stephan, Oct 20 2003
a(0) = a(1) = 0, a(4n) = 2a(2n), a(4n+2) = 2a(2n+1)+1, a(4n+1) = 2a(2n)+1, a(4n+3) = 2a(2n+1). Proof by Nikolaus Meyberg following a conjecture by Ralf Stephan.
|
|
|
EXAMPLE
|
If n=18=10010, derivative is (1+0)(0+0)(0+1)(1+0) = 1011, so a(18)=11.
|
|
|
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 *)
|
|
|
PROG
|
(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
(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
|
|
|
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.
Sequence in context: A167666 A115352 A275808 * A100329 A193535 A332645
Adjacent sequences: A038551 A038552 A038553 * A038555 A038556 A038557
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
N. J. A. Sloane
|
|
|
EXTENSIONS
|
More terms from Erich Friedman
|
|
|
STATUS
|
approved
|
| |
|
|
