

A025480


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


33



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

These are the nimvalues 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
When n>0 is written as (2k+1)*2^j then k=A000265(n1) and j=A007814(n), so: when n is written as (2k+1)*2^j1 then k=A025480(n) and j=A007814(n+1), when n>1 is written as (2k+1)*2^j+1 then k=A025480(n2) and j=A007814(n1)
According to the comment from Deuard Worthen, this may be regarded as a triangle where row r=1,2,3... has length 2^(r1) and values T[r,2k1]=T[r1,k], T[r,2k]=2^(r1)+k1, i.e. previous row gives first, 3rd, 5th... term and 2nd, 4th... terms are numbers 2^(r1),...,2^r1 (i.e. those following the last one from the previous row).  M. F. Hasler, May 03 2008
Let StB be a SternBrocot tree hanging between (pseudo)fractions Left and Right, then StB(1) = mediant(Left,Right) and for n>1: StB(n) = if a(n1)<>0 and a(n)<>0 then mediant(StB(a(n1)),StB(a(n))) else if a(n)=0 then mediant(StB(a(n1)),Right) else mediant(Left,StB(a(n1))), where mediant(q1,q2) = ((numerator(q1)+numerator(q2)) / (denominator(q1)+denominator(q2))). [Reinhard Zumkeller, Dec 22 2008]
a(n) = A153733(n)/2. [Reinhard Zumkeller, Dec 31 2008]
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
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
a(3*n + 1) = A173732(n). [Reinhard Zumkeller, Apr 29 2012]
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]
a(n) = A049084(A181363(n+1)).  Reinhard Zumkeller, Mar 22 2014


REFERENCES

L. Levine, Fractal sequences and restricted Nim, Ars Comb., Ars Combin. 80 (2006), 113127.


LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
L. Levine, Fractal sequences and restricted Nim
R. Stephan, Some divideandconquer sequences ...
R. Stephan, Table of generating functions
Paul Tarau. A Groupoid of Isomorphic Data Transformations. Calculemus 2009, 8th International Conference, MKM 2009, pp. 170185, Springer, LNAI 5625.


FORMULA

a(n) = (A000265(n+1)1)/2 = ((n+1)/A006519(n+1)1)/2.
a((2*n+1)*2^p1) = n, p >= 0 and n >= 0.  Johannes W. Meijer, Jan 24 2013
a(n) = n  A225381(n).  Marcus Hedbring, May 18 2013
G.f.: 1/(1x) + sum(k>=0, x^(2^k1)/(12*x^2^(k+1)+x^2^(k+2))).  Ralf Stephan, May 19 2013


EXAMPLE

Comment from Deuard Worthen (deuard(AT)raytheon.com), Jan 27 2006: This sequence can be constructed as a triangle, thus:
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
...
at each stage we interpolate the next 2^m numbers in the previous row.
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


MAPLE

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:
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^p1) := n od: od: seq(a(n), n=0..nmax); # Johannes W. Meijer, Jan 24 2013


MATHEMATICA

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 *)
Table[BitShiftRight[n, IntegerExponent[n, 2] + 1], {n, 100}] (* IWABUCHI Yu(u)ki, Oct 13 2012 *)


PROG

(PARI) A025480(n)={while(n%2, n\=2); n\2} \\  M. F. Hasler, May 03 2008
(PARI) A025480(n)=n>>valuation(n*2+2, 2) \\  M. F. Hasler, Apr 12 2012
(Haskell)
import Data.List
interleave xs ys = concat . transpose $ [xs, ys]
a025480 = interleave [0..] a025480
 _Cale Gibbard_, Nov 18 2009:
(Haskell) Cf. comments by Worthen and Hasler.
import Data.List (transpose)
a025480 n k = a025480_tabf !! n !! k
a025480_row n = a025480_tabf !! n
a025480_tabf = iterate (\xs > concat $
transpose [xs, [length xs .. 2 * length xs  1]]) [0]
a025480_list = concat $ a025480_tabf
 Reinhard Zumkeller, Apr 29 2012
(Sage)
A025480 = lambda n: odd_part(n+1)//2
[A025480(n) for n in (0..83)] # Peter Luschny, May 20 2014


CROSSREFS

The Yprojection of A075300.
a(n) = A003602(n)1.
Cf. A108202, A138002, A000265, A003602, A103391, A153733, A220466, A225381.
Sequence in context: A081171 A062778 A108202 * A088002 A030109 A208571
Adjacent sequences: A025477 A025478 A025479 * A025481 A025482 A025483


KEYWORD

easy,nonn,nice,tabf,hear


AUTHOR

David W. Wilson


EXTENSIONS

Additional comments from Henry Bottomley, Mar 02 2000


STATUS

approved



