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