A119387 a(n) is the number of binary digits (1's and nonleading 0's) which remain unchanged in their positions when n and (n+1) are written in binary.
0, 0, 1, 0, 2, 1, 2, 0, 3, 2, 3, 1, 3, 2, 3, 0, 4, 3, 4, 2, 4, 3, 4, 1, 4, 3, 4, 2, 4, 3, 4, 0, 5, 4, 5, 3, 5, 4, 5, 2, 5, 4, 5, 3, 5, 4, 5, 1, 5, 4, 5, 3, 5, 4, 5, 2, 5, 4, 5, 3, 5, 4, 5, 0, 6, 5, 6, 4, 6, 5, 6, 3, 6, 5, 6, 4, 6, 5, 6, 2, 6, 5, 6, 4, 6, 5, 6, 3, 6, 5, 6, 4, 6, 5, 6, 1, 6, 5, 6, 4, 6, 5, 6, 3, 6
Offset: 0
Examples
9 in binary is 1001. 10 (decimal) is 1010 in binary. 2 binary digits remain unchanged (the leftmost two digits) between 1001 and 1010. So a(9) = 2.
From _David James Sycamore_, Feb 26 2023: (Start)
Number of bits surviving transition from n to n+1 = distance between first and last 1's in binary expansion of n+1 (no need to compare n and n+1). Examples:
n = 2^k - 1: distance between 1's in n+1 = 2^k is 0; a(n) = 0 (all bits change).
82 in binary is 1010010, and 83 is 1010011 distance between 1's in 83 = 6 = a(82).
Show visually for a(327) = 5:
n = 327 = 101000111
^^^^^ 5 unchanged bits.
n+1 = 328 = 101001000
^ ^ distance between 1's = 5. (End)
Links
- Paolo Xausa, Table of n, a(n) for n = 0..10000 (terms 0..1023 from T. D. Noe)
- Lukas Spiegelhofer and Michael Wallner, Divisibility of binomial coefficients by powers of primes, arXiv:1604.07089 [math.NT], 2016. Mentions this sequence.
- Index entries for sequences related to binary expansion of n
Crossrefs
Programs
-
C
#include
#define NMAX 200 int sameD(int a, int b) { int resul=0 ; while(a>0 && b >0) { if( (a &1) == (b & 1)) resul++ ; a >>= 1 ; b >>= 1 ; } return resul ; } int main(int argc, char*argv[]) { for(int n=0;n -
C
int A119387(int n) { int m=n+1; while (!(m&1)) m>>=1; int m_bits = 0; while (m>>=1) m_bits++; return m_bits; } /* Laura Monroe, Oct 18 2020 */
-
Haskell
a119387 n = length $ takeWhile (< a070940 n) [1..n] -- Reinhard Zumkeller, Apr 22 2013
-
Maple
a:= n-> ilog2(n+1)-padic[ordp](n+1, 2): seq(a(n), n=0..128); # Alois P. Heinz, Jun 28 2021
-
Mathematica
a = {0}; Table[b = IntegerDigits[n, 2]; If[Length[a] == Length[b], c = 1; While[a[[c]] == b[[c]], c++]; c--, c = 0]; a = b; c, {n, 101}] (* T. D. Noe, Dec 18 2012 *) (* Second program, faster *) Array[Last[#] - First[#] &@ Position[IntegerDigits[#, 2], 1][[All, 1]] &, 2^14] (* Michael De Vlieger, Feb 22 2023 *) Table[BitLength[k] - 1 - IntegerExponent[k, 2], {k, 100}] (* Paolo Xausa, Oct 01 2024 *) -
PARI
a(n) = n++; local(c); c=0; while(2^(c+1)
-
PARI
a(n) = my(x=Vecrev(binary(n)), y=Vecrev(binary(n+1))); sum(k=1, min(#x, #y), x[k] == y[k]); \\ Michel Marcus, Jun 27 2021
-
PARI
a(n) = exponent(n+1) - valuation(n+1, 2); \\ Antoine Mathys, Nov 20 2024
-
Python
def A119387(n): return (n+1).bit_length()-(n+1&-n-1).bit_length() # Chai Wah Wu, Jul 07 2022
Formula
a(n) = A048881(n) + A086784(n+1). (A048881(n) is the number of 1's which remain unchanged between binary n and (n+1). A086784(n+1) is the number of nonleading 0's which remain unchanged between binary n and (n+1).)
a(A000225(n))=0. - R. J. Mathar, Jul 29 2006
a(n) = -valuation(H(n)*n,2) where H(n) is the n-th harmonic number. - Benoit Cloitre, Oct 13 2013
a(n) = A000523(n+1) - A007814(n+1) = floor(log(n+1)/log(2)) - valuation(n+1,2). - Benoit Cloitre, Oct 13 2013 [corrected by David James Sycamore, Feb 28 2023]
Recurrence: a(2n) = floor(log_2(n)) except a(0) = 0, a(2n+1) = a(n). - Ralf Stephan, Oct 16 2013, corrected by Peter J. Taylor, Mar 01 2020
a(n) = floor(log_2(A000265(n+1))). - Laura Monroe, Oct 18 2020
Extensions
More terms from R. J. Mathar, Jul 29 2006
Edited by Charles R Greathouse IV, Aug 04 2010
Comments