login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A163575 Remove all trailing bits equal to (n mod 2) in binary representation of n. 9
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 (list; graph; refs; listen; history; text; internal format)
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.

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

LINKS

Antti Karttunen, Table of n, a(n) for n = 1..8192

Wikipedia, Calkin Wilf Tree

Wikipedia, Stern Brocot Tree

FORMULA

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: A320354 A285320 A168068 * A275736 A276074 A317613

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 22:34 EDT 2019. Contains 328335 sequences. (Running on oeis4.)