A086784 -id:A086784 - cp's OEIS frontend

A086799 Replace all trailing 0's with 1's in binary representation of n.

1, 3, 3, 7, 5, 7, 7, 15, 9, 11, 11, 15, 13, 15, 15, 31, 17, 19, 19, 23, 21, 23, 23, 31, 25, 27, 27, 31, 29, 31, 31, 63, 33, 35, 35, 39, 37, 39, 39, 47, 41, 43, 43, 47, 45, 47, 47, 63, 49, 51, 51, 55, 53, 55, 55, 63, 57, 59, 59, 63, 61, 63, 63, 127, 65, 67, 67, 71, 69, 71

Offset: 1

Reinhard Zumkeller, Aug 05 2003

a(k+1) = smallest number greater than k having in its binary representation exactly one 1 more than k has; A000120(a(n)) = A063787(n). - Reinhard Zumkeller, Jul 31 2010
a(n) is the least m >= n-1 such that the Hamming distance D(n-1,m) = 1. - Vladimir Shevelev, Apr 18 2012
The number of appearances of k equals the 2-adic valuation of k+1. - Ali Sada, Dec 20 2024

			a(20) = a('10100') = '10100' + '11' = '10111' = 23.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Binary Carry Sequence
Eric Weisstein's World of Mathematics, Odd Part
Index entries for sequences related to binary expansion of n

Cf. A000051, A000079, A000120, A000265, A001620, A006519, A007814, A023416, A038712, A063787, A086784.

Cf. also A007088, A179857, A220466.

int a(int n) { return n | (n-1); } // Russ Cox, May 15 2007

a086799 n | even n    = (a086799 $ div n 2) * 2 + 1
          | otherwise = n
-- Reinhard Zumkeller, Aug 07 2011

nmax:=70: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 1 to ceil(nmax/(p+2)) do a((2*n-1)*2^p) := 2^(p+1)*n-1 od: od: seq(a(n), n=1..nmax); # Johannes W. Meijer, Feb 01 2013

Table[BitOr[(n + 1), n], {n, 0, 100}] (* Vladimir Joseph Stephan Orlovsky, Jul 19 2011 *)

a(n)=bitor(n,n-1) \\ Charles R Greathouse IV, Apr 17 2012

def a(n): return n | (n-1)
print([a(n) for n in range(1, 71)]) # Michael S. Branicky, Jul 13 2022

a(n) = n + 2^A007814(n) - 1.
a(n) is odd; a(n) = n iff n is odd.
a(a(n)) = a(n); A007814(a(n)) = a(n); A000265(a(n)) = a(n).
A023416(a(n)) = A023416(n) - A007814(n) = A086784(n).
A000120(a(n)) = A000120(n) + A007814(n).
a(2^n) = a(A000079(n)) = 2*2^n - 1 = A000051(n+1).
a(n) = if n is odd then n else a(n/2)*2 + 1.
a(n) = A006519(n) + n - 1. - Reinhard Zumkeller, Feb 02 2007
a(n) = n OR n-1 (bitwise OR of consecutive numbers). - Russ Cox, May 15 2007
a(2*n) = A038712(n) + 2*n. - Reinhard Zumkeller, Aug 07 2011
a((2*n-1)*2^p) = 2^(p+1)*n-1, p >= 0. - Johannes W. Meijer, Feb 01 2013
Sum_{k=1..n} a(k) ~ n^2/2 + (1/(2*log(2)))*n*log(n) + (3/4 + (gamma-1)/(2*log(2)))*n, where gamma is Euler's constant (A001620). - Amiram Eldar, Nov 24 2022

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.

Original entry on oeis.org

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

Leroy Quet, Jul 26 2006

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

			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)

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

Cf. A048881, A086784.
Cf. A070940.
Cf. A000265.
Cf. A001511, A070939.
Cf. A373709 (partial sums).

#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;nR. J. Mathar, Jul 29 2006 */

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

a119387 n = length $ takeWhile (< a070940 n) [1..n]
-- Reinhard Zumkeller, Apr 22 2013

a:= n-> ilog2(n+1)-padic[ordp](n+1, 2):
seq(a(n), n=0..128);  # Alois P. Heinz, Jun 28 2021

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

a(n) = n++; local(c); c=0; while(2^(c+1)Ralf Stephan, Oct 16 2013; corrected by Michel Marcus, Jun 28 2021 */

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

a(n) = exponent(n+1) - valuation(n+1, 2); \\ Antoine Mathys, Nov 20 2024

def A119387(n): return (n+1).bit_length()-(n+1&-n-1).bit_length() # Chai Wah Wu, Jul 07 2022

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
a(n) = A070939(n+1) - A001511(n+1). - David James Sycamore, Feb 24 2023

More terms from R. J. Mathar, Jul 29 2006

Edited by Charles R Greathouse IV, Aug 04 2010

A353654 Numbers whose binary expansion has the same number of trailing 0 bits as other 0 bits.

Original entry on oeis.org

1, 3, 7, 10, 15, 22, 26, 31, 36, 46, 54, 58, 63, 76, 84, 94, 100, 110, 118, 122, 127, 136, 156, 172, 180, 190, 204, 212, 222, 228, 238, 246, 250, 255, 280, 296, 316, 328, 348, 364, 372, 382, 392, 412, 428, 436, 446, 460, 468, 478, 484, 494, 502, 506, 511, 528, 568

Offset: 1

Mikhail Kurkov, Jul 15 2022

Numbers k such that A007814(k) = A086784(k).
To reproduce the sequence through itself, use the following rule: if binary 1xyz is a term then so are 11xyz and 10xyz0 (except for 1 alone where 100 is not a term).
The number of terms with bit length k is equal to Fibonacci(k-1) for k > 1.
Conjecture: 2*A247648(n-1) + 1 with rewrite 1 -> 1, 01 -> 0 applied to binary expansion is the same as a(n) without trailing 0 bits in binary.
Odd terms are positive Mersenne numbers (A000225), because there is no 0 in their binary expansion. - Bernard Schott, Oct 12 2022

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000045, A000120, A000523, A007814, A010056, A025480, A030109, A054429, A060142, A072649, A084471, A086784, A091892, A132665, A133512, A200650, A213911, A232559, A280514, A343152, A348366.
Cf. A356385 (first differences).
Subsequences with same number k of trailing 0 bits and other 0 bits: A000225 (k=0), 2*A190620 (k=1), 4*A357773 (k=2), 8*A360573 (k=3).

N:= 10: # for terms <= 2^N
S:= {1};
for d from 1 to N do
  for k from 0 to d/2-1 do
    B:= combinat:-choose([$k+1..d-2],k);
    S:= S union convert(map(proc(t) local s; 2^d - 2^k - add(2^(s),s=t) end proc,B),set);
od od:
sort(convert(S,list)); # Robert Israel, Sep 21 2023

Join[{1}, Select[Range[2, 600], IntegerExponent[#, 2] == Floor[Log2[# - 1]] - DigitCount[# - 1, 2, 1] &]] (* Amiram Eldar, Jul 16 2022 *)

isok(k) = if (k==1, 1, (logint(k-1, 2)-hammingweight(k-1) == valuation(k, 2))); \\ Michel Marcus, Jul 16 2022

from itertools import islice, count
def A353654_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:(m:=(~n & n-1).bit_length()) == bin(n>>m)[2:].count('0'),count(max(startvalue,1)))
A353654_list = list(islice(A353654_gen(),30)) # Chai Wah Wu, Oct 14 2022

a(n) = a(n-1) + A356385(n-1) for n > 1 with a(1) = 1.
Conjectured formulas: (Start)
a(n) = 2^g(n-1)*(h(n-1) + 2^A000523(h(n-1))*(2 - g(n-1))) for n > 2 with a(1) = 1, a(2) = 3 where f(n) = n - A130312(n), g(n) = [n > 2*f(n)] and where h(n) = a(f(n) + 1).
a(n) = 1 + 2^r(n-1) + Sum_{k=1..r(n-1)} (1 - g(s(n-1, k)))*2^(r(n-1) - k) for n > 1 with a(1) = 1 where r(n) = A072649(n) and where s(n, k) = f(s(n, k-1)) for n > 0, k > 1 with s(n, 1) = n.
a(n) = 2*(2 + Sum_{k=1..n-2} 2^(A213911(A280514(k)-1) + 1)) - 2^A200650(n) for n > 1 with a(1) = 1.
A025480(a(n)-1) = A348366(A343152(n-1)) for n > 1.
a(A000045(n)) = 2^(n-1) - 1 for n > 1. (End)

A089311 Write n in binary; a(n) = number of 0's in rightmost block of zeros, after dropping any trailing 0's.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, Dec 22 2003

			9 = 1001 so a(9) = 2.

Harvey P. Dale, Table of n, a(n) for n = 0..1000

Cf. A089309-A089313. Different from A086784.

bd[n_]:=Module[{s=Split[IntegerDigits[n,2]]},Which[Length[s]<3,0,MemberQ[ Last[s],1],Length[s[[-2]]],True,Length[s[[-3]]]]]; Array[bd,120,0] (* Harvey P. Dale, Dec 29 2013 *)

a(n)=local(b,c,s):b=binary(n):c=length(b):while(!b[c],c=c-1):while(c>0&&b[c],c=c-1): if(c<=0,0,s=0:while(!b[c],c=c-1:s=s+1):s) \\ Ralf Stephan

More terms from Ralf Stephan, Feb 01 2004

A091892 Numbers k having only one partition into parts which are a sum of exactly as many distinct powers of 2 as there are 1's in the binary representation of k.

Original entry on oeis.org

0, 1, 3, 5, 7, 11, 13, 15, 19, 23, 27, 29, 31, 39, 43, 47, 51, 55, 59, 61, 63, 79, 87, 91, 95, 103, 107, 111, 115, 119, 123, 125, 127, 143, 159, 175, 183, 187, 191, 207, 215, 219, 223, 231, 235, 239, 243, 247, 251, 253, 255, 287, 303, 319, 335, 351, 367, 375, 379, 383, 399

Offset: 1

Reinhard Zumkeller, Feb 10 2004

nonn

All positive terms are odd. - Alois P. Heinz, Dec 12 2021

Conjecture: if the second leftmost bit in the binary expansion of k+1 equals 0, then k is a term if and only if A007814(k+1) >= 2^(f(k)-1) + f(k). Otherwise, k is a term if and only if A007814(k+1) >= 2^f(k). Here f(k) = A086784(k+1). - Mikhail Kurkov, Oct 03 2022

			From _David A. Corneth_, Oct 03 2022: (Start)
11 is in the sequence as numbers with 3 bits and are <= 11 are 7, 11. The only partition of 11 into parts of size 7 and 11 are 11.
9 is not in the sequence as numbers with 2 bits, like 9, are 3, 5, 6, 9. 9 can be partitioned as 3+3+3 = 3+6 = 9 into these parts. As these are 3 > 1 partitions, 9 is not here. (End)

David A. Corneth, Table of n, a(n) for n = 1..2053 (first 375 terms from Andrew Howroyd, n = 376..764 from Alois P. Heinz)

Cf. A018819, A091889, A091890, A091891, A000120, A000041.

etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[j]}] b[n - j], {j, 1, n}]/n]; b];
EulerT[v_List] := With[{q = etr[v[[#]]&]}, q /@ Range[Length[v]]];
okQ[k_] := If[k == 0, True, If[EvenQ[k], False, EulerT[Table[DigitCount[j, 2, 1] == DigitCount[k, 2, 1] // Boole, {j, 1, k}]][[k]] == 1]];
Reap[For[k = 0, k <= 1000, k++, If[okQ[k], Print[k]; Sow[k]]]][[2, 1]] (* Jean-François Alcover, Dec 17 2021 *)

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
upto(n)={Set(concat(vector(logint(n,2)+1, k, my(u=vector(n,i,hammingweight(i)==k), v=EulerT(u)); select(i->u[i]&&v[i]==1, [1..n], 1))))} \\ Andrew Howroyd, Apr 20 2021

A091891(a(n)) = 1.

Terms a(40) and beyond from Andrew Howroyd, Apr 20 2021

a(1)=0 inserted by Alois P. Heinz, Dec 12 2021

cp's OEIS Frontend

A086799 Replace all trailing 0's with 1's in binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Haskell

Maple

Mathematica

PARI

Python

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

C

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A353654 Numbers whose binary expansion has the same number of trailing 0 bits as other 0 bits.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A089311 Write n in binary; a(n) = number of 0's in rightmost block of zeros, after dropping any trailing 0's.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A091892 Numbers k having only one partition into parts which are a sum of exactly as many distinct powers of 2 as there are 1's in the binary representation of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions