cp's OEIS Frontend

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

%I A163575 #39 Sep 21 2023 19:25:52
%S A163575 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,
%T A163575 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,
%U A163575 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
%N A163575 Remove all trailing bits equal to (n mod 2) in binary representation of n.
%C A163575 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."
%C A163575 In a binary tree (node(row,col)=2^(row-1)+(col-1))
%C A163575 __________________________________1__________________________________
%C A163575 _________________2__________________________________3________________
%C A163575 ________4_________________5________________6__________________7______
%C A163575 ____8_______9_______10_______11_______12_______13_______14_______15__
%C A163575 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
%C A163575 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.
%C A163575 The subsequences from a(2^k) to a(2^(k+1) - 1) are permutations from the natural numbers from 0 to 2^k-1.
%H A163575 Antti Karttunen, <a href="/A163575/b163575.txt">Table of n, a(n) for n = 1..8192</a>
%H A163575 Francis Laclé, <a href="https://hal.archives-ouvertes.fr/hal-03201180v2">2-adic parity explorations of the 3n+ 1 problem</a>, hal-03201180v2 [cs.DM], 2021.
%H A163575 Wikipedia, <a href="http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree">Calkin Wilf Tree</a>
%H A163575 Wikipedia, <a href="http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree">Stern-Brocot Tree</a>
%F A163575 a(A042963(n)) = n - 1. - _Reinhard Zumkeller_, Jul 22 2014
%F A163575 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
%F A163575 a(n) = floor(n/(2^A136480(n))). - _Antti Karttunen_, Jul 05 2013
%e A163575 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).
%e A163575 a(17) = a(10001_2) = 1000_2 = 8.
%e A163575 a(8) = a(1000_2) = 1_2 = 1.
%t A163575 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 *)
%t A163575 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 *)
%o A163575 (BASIC)
%o A163575 FUNCTION CHANGEPOINT
%o A163575 INPUT n
%o A163575 IF EVEN(n)
%o A163575   WHILE EVEN(n)
%o A163575     n = n/2
%o A163575 ELSE
%o A163575   WHILE NOT EVEN(n)
%o A163575     n = (n-1)/2
%o A163575 OUTPUT n
%o A163575 (PARI) a(n) = {odd = n%2; while (n%2 == odd, n \= 2); return(n);} \\ _Michel Marcus_, Jun 20 2013
%o A163575 (PARI) a(n)=if(n%2,(n+1)>>valuation(n+1,2)-1,n>>valuation(n,2)) \\ _Charles R Greathouse IV_, Jul 05 2013
%o A163575 (MIT/GNU Scheme) (define (A163575 n) (floor->exact (/ n (expt 2 (A136480 n))))) ;; _Antti Karttunen_, Jul 05 2013
%o A163575 (Haskell)
%o A163575 a163575 n = f n' where
%o A163575    f 0 = 0
%o A163575    f x = if b == parity then f x' else x  where (x', b) = divMod x 2
%o A163575    (n', parity) = divMod n 2
%o A163575 -- _Reinhard Zumkeller_, Jul 22 2014
%Y A163575 Bisections: A000265, A153733. Cf. also A227183.
%Y A163575 Cf. A136480.
%K A163575 base,easy,nonn
%O A163575 1,5
%A A163575 Helmut Kreindl (euler(AT)chello.at), Jul 31 2009
%E A163575 Name changed and b-file computed by _Antti Karttunen_, Jul 05 2013