login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A025480 a(2n) = n, a(2n+1) = a(n). 45

%I

%S 0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2,10,5,11,1,12,6,13,3,14,7,15,

%T 0,16,8,17,4,18,9,19,2,20,10,21,5,22,11,23,1,24,12,25,6,26,13,27,3,28,

%U 14,29,7,30,15,31,0,32,16,33,8,34,17,35,4,36,18,37,9,38,19,39,2,40,20,41,10

%N a(2n) = n, a(2n+1) = a(n).

%C These are the Grundy values or nim-values for heaps of n beans in the game where you're allowed to take up to half of the beans in a heap. - _R. K. Guy_, Mar 30 2006. See Levine 2004/2006 for more about this. - _N. J. A. Sloane_, Aug 14 2016

%C When n>0 is written as (2k+1)*2^j then k=A000265(n-1) and j=A007814(n), so: when n is written as (2k+1)*2^j-1 then k=A025480(n) and j=A007814(n+1), when n>1 is written as (2k+1)*2^j+1 then k=A025480(n-2) and j=A007814(n-1). - _Henry Bottomley_, Mar 02 2000

%C According to the comment from Deuard Worthen (see Example section), this may be regarded as a triangle where row r=1,2,3... has length 2^(r-1) and values T[r,2k-1]=T[r-1,k], T[r,2k]=2^(r-1)+k-1, i.e., previous row gives first, 3rd, 5th, ... term and 2nd, 4th, ... terms are numbers 2^(r-1),...,2^r-1 (i.e., those following the last one from the previous row). - _M. F. Hasler_, May 03 2008

%C Let StB be a Stern-Brocot tree hanging between (pseudo)fractions Left and Right, then StB(1) = mediant(Left,Right) and for n>1: StB(n) = if a(n-1)<>0 and a(n)<>0 then mediant(StB(a(n-1)),StB(a(n))) else if a(n)=0 then mediant(StB(a(n-1)),Right) else mediant(Left,StB(a(n-1))), where mediant(q1,q2) = ((numerator(q1)+numerator(q2)) / (denominator(q1)+denominator(q2))). - _Reinhard Zumkeller_, Dec 22 2008

%C This sequence is the unique fixed point of the function (a(0), a(1), a(2), ...) |--> (0, a(0), 1, a(1), 2, a(2), ...) which interleaves the nonnegative integers between the elements of a sequence. - Cale Gibbard (cgibbard(AT)gmail.com), Nov 18 2009

%C The following relation holds: 2^A007814(n+1)*(2*A025480(n)+1)=A001477(n+1). (See functions hd,tl and cons in [Paul Tarau 2009].) - Paul Tarau (paul.tarau(AT)gmail.com), Mar 21 2010

%C Also the number of remaining survivors in a Josephus problem after the person originally first in line has been eliminated (see A225381). - _Marcus Hedbring_, May 18 2013

%C A fractal sequence - see Levine 2004/2006. - _N. J. A. Sloane_, Aug 14 2016

%C From _David James Sycamore_, Apr 29 2020: (Start)

%C One of a family of fractal sequences, S_k; defined as follows for k>=2: a(k*n) = n, a(k*n+r) = a((k-1)*n + (r-1)), r = 1..(k-1). S_2 is A025480; S_3 gives: a(3*n) = n, a(3*n + 1) = a(2*n), a(3*n + 2) = a(2*n + 1), which is A263390 (whose name is not expressed entirely in this form, but it is the same sequence).

%C Sequences corresponding to higher k values do not appear to be recorded in oeis. The subsequence of all nonzero terms is A131987. Thus A025480 has a proper subsequence identical to itself and another proper subsequence different from itself, which is also fractal (End).

%C Similar to but different from A108202. - _N. J. A. Sloane_, Nov 26 2020

%D L. Levine, Fractal sequences and restricted Nim, Ars Combin. 80 (2006), 113-127.

%H N. J. A. Sloane, <a href="/A025480/b025480.txt">Table of n, a(n) for n = 0..10000</a>

%H Josef Eschgfäller, Andrea Scarpante, <a href="http://arxiv.org/abs/1603.08500">Dichotomic random number generators</a>, arXiv:1603.08500 [math.CO], 2016.

%H R. Hinze, <a href="https://www.cs.ox.ac.uk/people/ralf.hinze/publications/CSC.pdf">Concrete stream calculus: An extended study</a>, J. Funct. Progr. 20 (5-6) (2010) 463-535, <a href="https://doi.org/10.1017/S0956796810000213">doi</a>, Section 3.2.4.

%H L. Levine, <a href="https://arxiv.org/abs/math/0409408">Fractal sequences and restricted Nim</a>, arXiv:math/0409408 [math.CO], 2004.

%H R. Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H R. Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H Paul Tarau, <a href="http://scholar.google.com/scholar?cluster=284705751770513453">A Groupoid of Isomorphic Data Transformations</a>, Calculemus 2009, 8th International Conference, MKM 2009, pp. 170-185, Springer, LNAI 5625.

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

%F a(n) = (A000265(n+1)-1)/2 = ((n+1)/A006519(n+1)-1)/2.

%F a(n) = A153733(n)/2. - _Reinhard Zumkeller_, Dec 31 2008

%F a(3*n + 1) = A173732(n). - _Reinhard Zumkeller_, Apr 29 2012

%F a((2*n+1)*2^p-1) = n, p >= 0 and n >= 0. - _Johannes W. Meijer_, Jan 24 2013

%F a(n) = n - A225381(n). - _Marcus Hedbring_, May 18 2013

%F G.f.: -1/(1-x) + Sum_{k>=0} x^(2^k-1)/(1-2*x^2^(k+1)+x^2^(k+2)). - _Ralf Stephan_, May 19 2013

%F a(n) = A049084(A181363(n+1)). - _Reinhard Zumkeller_, Mar 22 2014

%F a(n) = floor( n/ 2^A001511(n+1) ). - _Adam Shelly_, Mar 05 2019

%F Recursion: a(0) = 0; a(n + 1) = a(a(n)) if a(n) is a first occurrence of a term, else a(n + 1) = n - a(n-1). - _David James Sycamore_, Apr 29 2020

%e From Deuard Worthen (deuard(AT)raytheon.com), Jan 27 2006: (Start)

%e The sequence can be constructed as a triangle as:

%e 0

%e 0 1

%e 0 2 1 3

%e 0 4 2 5 1 6 3 7

%e 0 8 4 9 2 10 5 11 1 12 6 13 3 14 7 15

%e ...

%e At each stage we interleave the next 2^m numbers in the previous row. (End)

%e Left=0/1, Right=1/0: StB=A007305/A047679; Left=0/1, Right=1/1: StB=A007305/A007306; Left=1/3, Right=2/3: StB=A153161/A153162. - _Reinhard Zumkeller_, Dec 22 2008

%p a:=array[0..10001]; M:=5000; for n from 0 to M do a[2*n]:=n; a[2*n+1]:=a[n]; od: for n from 0 to 2*M do lprint(n,a[n]); od:

%p nmax := 83: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 0 to ceil(nmax/(p+2))+1 do a((2*n+1)*2^p-1) := n od: od: seq(a(n), n=0..nmax); # _Johannes W. Meijer_, Jan 24 2013

%p A025480 := proc(n)

%p option remember ;

%p if type(n,'even') then

%p n/2 ;

%p else

%p procname((n-1)/2) ;

%p end if;

%p end proc: # _R. J. Mathar_, Jul 16 2020

%t a[n_] := a[n] = If[OddQ@n, a[(n - 1)/2], n/2]; Table[ a[n], {n, 0, 83}] (* _Robert G. Wilson v_, Mar 30 2006 *)

%t Table[BitShiftRight[n, IntegerExponent[n, 2] + 1], {n, 100}] (* _IWABUCHI Yu(u)ki_, Oct 13 2012 *)

%o (PARI) a(n)={while(n%2,n\=2);n\2} \\ _M. F. Hasler_, May 03 2008

%o (PARI) A025480(n)=n>>valuation(n*2+2,2) \\ _M. F. Hasler_, Apr 12 2012

%o (Haskell)

%o import Data.List

%o interleave xs ys = concat . transpose $ [xs,ys]

%o a025480 = interleave [0..] a025480

%o -- _Cale Gibbard_, Nov 18 2009:

%o (Haskell) Cf. comments by Worthen and Hasler.

%o import Data.List (transpose)

%o a025480 n k = a025480_tabf !! n !! k

%o a025480_row n = a025480_tabf !! n

%o a025480_tabf = iterate (\xs -> concat $

%o transpose [xs, [length xs .. 2 * length xs - 1]]) [0]

%o a025480_list = concat $ a025480_tabf

%o -- _Reinhard Zumkeller_, Apr 29 2012

%o (Sage)

%o A025480 = lambda n: odd_part(n+1)//2

%o [A025480(n) for n in (0..83)] # _Peter Luschny_, May 20 2014

%Y a(n) = A003602(n)-1.

%Y The Y-projection of A075300.

%Y Cf. A108202, A138002, A000265, A003602, A103391, A153733, A220466, A225381, A131987, A263390.

%K easy,nonn,nice,tabf,hear

%O 0,5

%A _David W. Wilson_

%E Edited by _M. F. Hasler_, Mar 16 2018

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 April 14 06:59 EDT 2021. Contains 342946 sequences. (Running on oeis4.)