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

Author

Reinhard Zumkeller, Aug 05 2003

Keywords

• nonn
• base

Comments

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

Examples

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

Links

• 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

Crossrefs

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

Cf. also A007088, A179857, A220466.

Programs

C

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

Haskell

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

Maple

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

Mathematica

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

PARI

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

Python

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

Formula

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