A163575 Remove all trailing bits equal to (n mod 2) in binary representation of n.

0, 1, 0, 1, 2, 3, 0, 1, 4, 5, 2, 3, 6, 7, 0, 1, 8, 9, 4, 5, 10, 11, 2, 3, 12, 13, 6, 7, 14, 15, 0, 1, 16, 17, 8, 9, 18, 19, 4, 5, 20, 21, 10, 11, 22, 23, 2, 3, 24, 25, 12, 13, 26, 27, 6, 7, 28, 29, 14, 15, 30, 31, 0, 1, 32, 33, 16, 17, 34, 35, 8, 9, 36, 37, 18, 19, 38, 39, 4, 5, 40, 41, 20

Offset: 1

Author

Helmut Kreindl (euler(AT)chello.at), Jul 31 2009

Keywords

• base
• easy
• nonn

Comments

The original name was: "The changepoint a(n) is the first predecessor from n in a binary tree with: a(n) mod 2 <> n mod 2."

In a binary tree (node(row,col)=2^(row-1)+(col-1))

_________________________________1_________________________________

_________________2__________________________________3________________

_______4_________________5________________6__________________7_____

____8_______9_______10_______11_______12_______13_______14_______15__

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

any node has 2 successors and one predecessor. a(n) is the first predecessor from n (going back, step by step) with another last digit (in binary sight) as n.

The subsequences from a(2^k) to a(2^(k+1) - 1) are permutations from the natural numbers from 0 to 2^k-1.

Examples

			a(7) = a(111_2) = 0_2 = 0 (when the rightmost and only run of bits in 7's binary representation has been shifted off, only zero remains).
a(17) = a(10001_2) = 1000_2 = 8.
a(8) = a(1000_2) = 1_2 = 1.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..8192
• Francis Laclé, 2-adic parity explorations of the 3n+ 1 problem, hal-03201180v2 [cs.DM], 2021.
• Wikipedia, Calkin Wilf Tree
• Wikipedia, Stern-Brocot Tree

Crossrefs

Bisections: A000265, A153733. Cf. also A227183.

Cf. A136480.

Programs

BASIC

FUNCTION CHANGEPOINT
INPUT n
IF EVEN(n)
  WHILE EVEN(n)
    n = n/2
ELSE
  WHILE NOT EVEN(n)
    n = (n-1)/2
OUTPUT n

Haskell

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

Mathematica

f[n_] := Block[{idn = IntegerDigits[n, 2], m = Mod[n, 2]}, While[ idn[[-1]] == m, idn = Most@ idn]; FromDigits[ idn, 2]]; Array[f, 83] (* or *)
f[n_] := Block[{m = n}, If[ OddQ@ m, While[OddQ@m, m--; m /= 2], While[ EvenQ@ m, m /= 2]]; m]; Array[f, 83] (* Robert G. Wilson v, Jul 04 2015 *)

PARI

a(n) = {odd = n%2; while (n%2 == odd, n \= 2); return(n);} \\ Michel Marcus, Jun 20 2013

PARI

a(n)=if(n%2,(n+1)>>valuation(n+1,2)-1,n>>valuation(n,2)) \\ Charles R Greathouse IV, Jul 05 2013
(MIT/GNU Scheme) (define (A163575 n) (floor->exact (/ n (expt 2 (A136480 n))))) ;; Antti Karttunen, Jul 05 2013

Formula

a(A042963(n)) = n - 1. - Reinhard Zumkeller, Jul 22 2014

a(2^n -1) = 0 and a(2^n) = 1. a(2n-1) is 2x and a(2n) is 2x+1. - Robert G. Wilson v, Jul 04 2015

a(n) = floor(n/(2^A136480(n))). - Antti Karttunen, Jul 05 2013

Extensions

Name changed and b-file computed by Antti Karttunen, Jul 05 2013