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

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.

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

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

Example

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.

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

Prog

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

Crossrefs

Bisections: A000265, A153733. Cf. also A227183.

Cf. A136480.

Sequence in context: A347710 A340666 A168068 * A355889 A275736 A276074

Adjacent sequences: A163572 A163573 A163574 * A163576 A163577 A163578

Keyword

base,easy,nonn

Author

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

Extensions

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

Status

approved