cp's OEIS Frontend

A025480 a(2n) = n, a(2n+1) = a(n).

%I A025480 #233 Aug 21 2024 03:35:59
%S A025480 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 A025480 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 A025480 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 A025480 a(2n) = n, a(2n+1) = a(n).
%C A025480 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 A025480 When n > 0 is written as (2k+1)*2^j then k = a(n-1) and j = A007814(n), so: when n is written as (2k+1)*2^j-1 then k = a(n) and j = A007814(n+1), when n > 1 is written as (2k+1)*2^j+1 then k = a(n-2) and j = A007814(n-1). - _Henry Bottomley_, Mar 02 2000 [sequence id corrected by _Peter Munn_, Jun 22 2022]
%C A025480 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 1st, 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 A025480 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 A025480 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 A025480 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 A025480 A fractal sequence - see Levine 2004/2006. - _N. J. A. Sloane_, Aug 14 2016
%C A025480 From _David James Sycamore_, Apr 29 2020: (Start)
%C A025480 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.
%C A025480 The subsequence of all nonzero terms is A131987. (End)
%C A025480 Similar to but different from A108202. - _N. J. A. Sloane_, Nov 26 2020
%C A025480 This sequence can be otherwise defined in two alternative (but related) ways, with a(0)=0, as follows: (i) If a(n) is a novel term, then a(n+1) = a(a(n)); if a(n) has been seen before, most recently at a(m), then a(n+1) = n-m (as in A181391). (ii) As above for novel a(n), then if a(n) has been seen before, a(n+1) = smallest k < a(n) which is not already a term. - _David James Sycamore_, Jul 13 2021
%C A025480 From a binary perspective, the sequence can be seen as even,odd pairs where the odd value is the previous even value, dropping the rightmost bits up to and including the lowest zero bit, aka right-shifted past the lowest clear bit. E.g., (5)101 -> 1, (17)10001 -> (4)100, (29)11101 -> (7)111, (39)100111 -> (2)10. - _Joe Nellis_, Oct 09 2022
%D A025480 L. Levine, Fractal sequences and restricted Nim, Ars Combin. 80 (2006), 113-127.
%H A025480 N. J. A. Sloane, <a href="/A025480/b025480.txt">Table of n, a(n) for n = 0..10000</a>
%H A025480 Josef Eschgfäller and Andrea Scarpante, <a href="http://arxiv.org/abs/1603.08500">Dichotomic random number generators</a>, arXiv:1603.08500 [math.CO], 2016.
%H A025480 Ralf 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 A025480 L. Levine, <a href="https://arxiv.org/abs/math/0409408">Fractal sequences and restricted Nim</a>, arXiv:math/0409408 [math.CO], 2004.
%H A025480 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>.
%H A025480 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>.
%H A025480 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 A025480 <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>.
%F A025480 a(n) = A003602(n+1) - 1. [Corrected by _Max Alekseyev_, May 05 2022]
%F A025480 a(n) = (A000265(n+1)-1)/2 = ((n+1)/A006519(n+1)-1)/2.
%F A025480 a(n) = A153733(n)/2. - _Reinhard Zumkeller_, Dec 31 2008
%F A025480 2^A007814(n+1)*(2*a(n)+1) = n+1. (See functions hd, tl and cons in [Paul Tarau 2009].) - Paul Tarau (paul.tarau(AT)gmail.com), Mar 21 2010
%F A025480 a(3*n + 1) = A173732(n). - _Reinhard Zumkeller_, Apr 29 2012
%F A025480 a((2*n+1)*2^p-1) = n, p >= 0 and n >= 0. - _Johannes W. Meijer_, Jan 24 2013
%F A025480 a(n) = n - A225381(n). - _Marcus Hedbring_, May 18 2013
%F A025480 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 A025480 a(n) = A049084(A181363(n+1)). - _Reinhard Zumkeller_, Mar 22 2014
%F A025480 a(n) = floor(n / 2^A001511(n+1)). - _Adam Shelly_, Mar 05 2019
%F A025480 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
%F A025480 a(n) * 2^(A007814(n+1)+1) + 2^A007814(n+1) - 1 = n (equivalent to the formula given in the comment by Paul Tarau). - _Ruud H.G. van Tol_, Apr 14 2023
%F A025480 Sum_{k=1..n} a(k) = n^2/6 + O(n). - _Amiram Eldar_, Aug 07 2023
%e A025480 From Deuard Worthen (deuard(AT)raytheon.com), Jan 27 2006: (Start)
%e A025480 The sequence can be constructed as a triangle as:
%e A025480   0
%e A025480   0  1
%e A025480   0  2  1  3
%e A025480   0  4  2  5  1  6  3  7
%e A025480   0  8  4  9  2 10  5 11  1 12  6 13  3 14  7 15
%e A025480   ...
%e A025480 At each stage we interleave the next 2^m numbers in the previous row. (End)
%e A025480 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 A025480 A025480 := proc(n)
%p A025480     option remember ;
%p A025480     if type(n,'even') then
%p A025480         n/2 ;
%p A025480     else
%p A025480         procname((n-1)/2) ;
%p A025480     end if;
%p A025480 end proc:
%p A025480 seq(A025480(n),n=0..100) ; # _R. J. Mathar_, Jul 16 2020
%t A025480 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 A025480 Table[BitShiftRight[n, IntegerExponent[n, 2] + 1], {n, 100}] (* _IWABUCHI Yu(u)ki_, Oct 13 2012 *)
%o A025480 (PARI) a(n)={while(n%2,n\=2);n\2} \\ _M. F. Hasler_, May 03 2008
%o A025480 (PARI) A025480(n)=n>>valuation(n*2+2,2) \\ _M. F. Hasler_, Apr 12 2012
%o A025480 (Haskell)
%o A025480 import Data.List
%o A025480 interleave xs ys = concat . transpose $ [xs,ys]
%o A025480 a025480 = interleave [0..] a025480
%o A025480 -- _Cale Gibbard_, Nov 18 2009
%o A025480 (Haskell)  Cf. comments by Worthen and Hasler.
%o A025480 import Data.List (transpose)
%o A025480 a025480 n k = a025480_tabf !! n !! k
%o A025480 a025480_row n = a025480_tabf !! n
%o A025480 a025480_tabf = iterate (\xs -> concat $
%o A025480    transpose [xs, [length xs .. 2 * length xs - 1]]) [0]
%o A025480 a025480_list = concat $ a025480_tabf
%o A025480 -- _Reinhard Zumkeller_, Apr 29 2012
%o A025480 (Sage)
%o A025480 A025480 = lambda n: odd_part(n+1)//2
%o A025480 [A025480(n) for n in (0..83)] # _Peter Luschny_, May 20 2014
%o A025480 (Python)
%o A025480 def A025480(n): return n>>((~(n+1)&n).bit_length()+1) # _Chai Wah Wu_, Jul 13 2022
%Y A025480 The Y-projection of A075300.
%Y A025480 Cf. A108202, A138002, A000265, A003602, A103391, A153733, A220466, A225381, A131987, A263390, A181391, A007814.
%K A025480 easy,nonn,nice,tabf,hear
%O A025480 0,5
%A A025480 _David W. Wilson_
%E A025480 Edited by _M. F. Hasler_, Mar 16 2018