|
| |
|
|
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.
|
|
5
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
The largest k for which A220645(n,k) > 0 is k = a(n). That is, a(n) is the largest power of 2 that divides binomial(n,i) for 0 <= i <= n. - T. D. Noe, Dec 18 2012
a(n) is the distance between the first and last 1's in the binary expansion of n+1; see examples and formulae. - David James Sycamore, Feb 21 2023
|
|
|
LINKS
|
|
|
|
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(n) = -valuation(H(n)*n,2) where H(n) is the n-th harmonic number. - Benoit Cloitre, Oct 13 2013
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
|
|
|
EXAMPLE
|
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.
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)
|
|
|
MAPLE
|
a:= n-> ilog2(n+1)-padic[ordp](n+1, 2):
|
|
|
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 *)
|
|
|
PROG
|
(C)
#include <stdio.h>
#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<NMAX; n++) printf("%d, ", sameD(n, n+1)) ; return 0 ; }
(Haskell)
a119387 n = length $ takeWhile (< a070940 n) [1..n]
(PARI) a(n) = n++; local(c); c=0; while(2^(c+1)<n+1, c=c+1); c-valuation(n, 2); /* Ralf Stephan, Oct 16 2013; corrected by Michel Marcus, Jun 28 2021 */
(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
(C)
{
int m=n+1;
while (!(m&1)) m>>=1;
int m_bits = 0;
while (m>>=1) m_bits++;
return m_bits;
}
(Python)
def A119387(n): return (n+1).bit_length()-(n+1&-n-1).bit_length() # Chai Wah Wu, Jul 07 2022
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,nonn,base
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
