A153733 Remove all trailing 1's in the binary representation of n.

0, 0, 2, 0, 4, 2, 6, 0, 8, 4, 10, 2, 12, 6, 14, 0, 16, 8, 18, 4, 20, 10, 22, 2, 24, 12, 26, 6, 28, 14, 30, 0, 32, 16, 34, 8, 36, 18, 38, 4, 40, 20, 42, 10, 44, 22, 46, 2, 48, 24, 50, 12, 52, 26, 54, 6, 56, 28, 58, 14, 60, 30, 62, 0, 64, 32, 66, 16, 68, 34, 70, 8, 72, 36, 74, 18, 76, 38

Offset: 0

Author

Reinhard Zumkeller, Dec 31 2008

Keywords

• nonn
• easy

Comments

a(n) is also the map n -> A065423(n+1) applied A007814(n+1) times. - Federico Provvedi, Dec 14 2021

Links

• Harvey P. Dale, Table of n, a(n) for n = 0..1000
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A000265, A007814, A007088.

Cf. A163575.

Cf. A065423, A331739.

Programs

Haskell

a153733 n = if b == 0 then n else a153733 n'  where (n', b) = divMod n 2
-- Reinhard Zumkeller, Jul 22 2014

Maple

f:= n -> (n+1)/2^padic:-ordp(n+1,2)-1:
map(f, [$0..100]); # Robert Israel, Mar 18 2018

Mathematica

Table[If[EvenQ[n],n,FromDigits[Flatten[Most[Split[IntegerDigits[n,2]]]],2]],{n,0,100}] (* Harvey P. Dale, Feb 15 2014 *)
a[n_] := BitShiftRight[n + 1, IntegerExponent[n+1, 2]] - 1; a[Range[0,100]] (* Federico Provvedi, Dec 21 2021 *)

PARI

A153733(n)=(n+=1)>>valuation(n,2)-1 \\ most efficient variant: use this. - M. F. Hasler, Mar 16 2018

PARI

{a(n)=while(bittest(n,0),n>>=1);n} \\ for illustration: as long as there's a trailing bit 1, remove it. - M. F. Hasler, Mar 16 2018

PARI

a(n)=for(i=0,n,bittest(n,i)||return(n>>i)) \\ scan the trailing 1's, then remove all of them at once. - M. F. Hasler, Mar 16 2018

Python

def a(n):
    while n&1: n >>= 1
    return n
print([a(n) for n in range(100)]) # Michael S. Branicky, Dec 18 2021

Python

def A153733(n): return n>>(~(n+1)&n).bit_length() # Chai Wah Wu, Jul 08 2022

Formula

a(n) = n if n is even, a((n-1)/2) if odd.

a(n)/2 = A025480(n).

a(n) = A000265(n+1) - 1. - M. F. Hasler, Mar 16 2018

a(n) = n - A331739(n+1). - Federico Provvedi, Dec 21 2021