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,2

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

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

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

Example

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

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

Prog

(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
(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

Crossrefs

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

Cf. also A007088, A179857, A220466.

Sequence in context: A338768 A318456 A209085 * A218388 A308340 A161427

Adjacent sequences: A086796 A086797 A086798 * A086800 A086801 A086802

Keyword

nonn,base

Author

Reinhard Zumkeller, Aug 05 2003

Status

approved