A038556 -id:A038556 - 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).

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

N. J. A. Sloane

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

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

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

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.

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.

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

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

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

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

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

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.

More terms from Erich Friedman

A038558 Smallest number with derivative n.

Original entry on oeis.org

0, 2, 4, 5, 8, 9, 11, 10, 16, 17, 19, 18, 23, 22, 20, 21, 32, 33, 35, 34, 39, 38, 36, 37, 47, 46, 44, 45, 40, 41, 43, 42, 64, 65, 67, 66, 71, 70, 68, 69, 79, 78, 76, 77, 72, 73, 75, 74, 95, 94, 92, 93, 88, 89, 91, 90, 80, 81, 83, 82, 87, 86, 84, 85, 128, 129, 131, 130, 135, 134

Offset: 0

N. J. A. Sloane

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Cf. A038554-A038556.

import Data.List (elemIndex)
import Data.Maybe (fromJust)
a038558 = fromJust . (`elemIndex` a038554_list)
-- Reinhard Zumkeller, Mar 06 2013

dtn[ L_ ] := Fold[ 2#1+#2&, 0, L ]; h[ n_ ] := dtn[ {1}~Join~Table[ Mod[ 1+Apply[ Plus, Take[ IntegerDigits[ n, 2 ], k ] ], 2 ], {k, 1, Length[ IntegerDigits[ n, 2 ] ]} ] ]; Table[ h[ n ], {n, 100} ]

More terms from Erich Friedman

a(0)=0 added and offset adjusted by Reinhard Zumkeller, Mar 06 2013

A038557 Periodic derivative of n in base 3.

Original entry on oeis.org

0, 2, 1, 4, 8, 0, 8, 0, 4, 10, 14, 15, 22, 26, 18, 7, 2, 3, 20, 21, 25, 5, 6, 1, 17, 9, 13, 28, 32, 33, 40, 44, 36, 52, 47, 48, 64, 68, 69, 76, 80, 72, 61, 56, 57, 19, 23, 24, 4, 8, 0, 16, 11, 12, 56, 57, 61, 68, 69, 64, 80, 72, 76, 11, 12, 16, 23, 24, 19, 8, 0, 4, 47, 48, 52, 32

Offset: 0

N. J. A. Sloane

			14=112->200 so a(14)=18.

Simmons, G. J. The structure of the differentiation digraphs of binary sequences. Ars Combin. 35 (1993), A, 71-88. Math. Rev. 95f:05052.

Cf. A038554-A038556.

If n=b_k b_{k-1} ... b_0 in base 3, a(n) is number with ternary expansion (b_k+b_{k-1}) (b_{k-1}+b_{k-2}) ... (b_1+b_0) (b_0+b_{k}).

Corrected and extended by Naohiro Nomoto, Apr 08 2001

A355255 Irregular table read by rows: a(n,k) gives the number of distinct necklaces that appear in the following procedure: starting with the n-bead, (0,1)-necklace given by k written in binary, repeatedly take the first differences (mod 2) of the beads. 0 <= k < 2^n.

Original entry on oeis.org

1, 1, 2, 1, 3, 3, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 5, 5, 4, 5, 3, 4, 5, 5, 4, 3, 5, 4, 5, 5, 2, 1, 4, 4, 3, 4, 3, 3, 4, 4, 3, 3, 4, 3, 4, 4, 3, 4, 3, 3, 4, 3, 4, 4, 3, 3, 4, 4, 3, 4, 3, 3, 2, 1, 4, 4, 3, 4, 2, 3, 3, 4, 2, 2, 4, 3, 4, 3, 2, 4, 2, 2, 4, 2, 3, 4, 3, 3, 4, 4, 1, 3, 3, 2, 4, 4, 3, 2, 3, 2, 4, 4, 2, 2, 4, 3, 3, 4, 1, 3, 4, 3, 3, 4, 2, 4, 3, 1, 4, 3, 2, 3, 4, 2, 4, 4, 2

Offset: 0

Peter Kagey, Jun 26 2022

For j >= 1, the sequence a(j,1) begins
2, 3, 2, 5, 4, 4, 8, 9, 8, 8, 32, 8, 64, 16, 16, 17, 16, 16, 512, 16, 64, 64, 2048, 16, 1024, 128, 512, 32, 16384, 32, ...
Conjecture: a(2^m,1) = 2^m + 1 for all m > 1.
Conjecture: a(m,1) is a power of 2 whenever m is not a power of 2.
The sequence of the number of distinct values in the n-th row begins 1, 2, 3, 2, 5, 4, 4, 4, 9, 4, 8, 4, 8, 4, 10, 6, 17, 6, 10, ... - Peter Kagey, Jul 03 2022

			Table begins:
n\k | 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
----+-----------------------------------------------
  0 | 1;
  1 | 1, 2;
  2 | 1, 3, 3, 2;
  3 | 1, 2, 2, 1, 2, 1, 1, 2;
  4 | 1, 5, 5, 4, 5, 3, 4, 5, 5, 4, 3, 5, 4, 5, 5, 2;
... | ...
a(5,13) = 4 because 13 is 01101 in binary; the sequence of first differences is 01101, 10111, 11000, 01001, 11011, ...; and 10111 is the same necklace as 11011.

Peter Kagey, Rows n = 0..12 of the triangle, flattened

Cf. A038556, A334594.

A274063 Numbers whose periodic derivative is equal to the arithmetic derivative.

Original entry on oeis.org

0, 1, 25, 26, 51, 119, 218, 771, 1754, 1799, 1921, 7967, 16147, 32639, 128129, 196611, 458759, 1044143, 2031647, 7190234, 8323199, 33464867, 536581571, 536813567, 1073691551, 2145328183, 7202169026, 8746826298, 17179612627, 68719005499, 797299610790

Offset: 1

Paolo P. Lava, Jun 09 2016

nonn

Solution of the equation A003415(n) = A038556(n).

			25 in base 2 is 11001 and its periodic derivative is (1+1)(1+0)(0+0)(0+1)(1+1) -> 01010 that is 10 in base 10 and 10 is also the arithmetic derivative of 25.

Cf. A003415, A038556, A273993.

with(numtheory): P:=proc(q) local a,b,i,n,p;
for n from 0 to q do a:=0; b:=convert(n,base,2); b:=[1,op(b)];
for i to nops(b)-1 do a:=a+((b[i]+b[i+1]) mod 2)*2^(i-1); od;
if a=n*add(op(2,p)/op(1,p),p=ifactors(n)[2]) then print(n); fi;
od; end: P(10^6);

Select[Range[0, 10^6], Function[n, If[Abs@ n < 2, 0, n Total[#2/#1 & @@@ FactorInteger[Abs@ n]]] == FromDigits[Thread[BitXor[#, RotateLeft@ #]], 2] &@ IntegerDigits[n, 2]]] (* Michael De Vlieger, Jun 10 2016 after Michael Somos at A003415 and Jean-François Alcover at A038556 *)

a(23)-a(31) from Giovanni Resta, Jun 19 2016

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A038558 Smallest number with derivative n.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Mathematica

Extensions

A038557 Periodic derivative of n in base 3.

Views

Author

Keywords

Examples

References

Crossrefs

Formula

Extensions

A355255 Irregular table read by rows: a(n,k) gives the number of distinct necklaces that appear in the following procedure: starting with the n-bead, (0,1)-necklace given by k written in binary, repeatedly take the first differences (mod 2) of the beads. 0 <= k < 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A274063 Numbers whose periodic derivative is equal to the arithmetic derivative.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions