A088442 -id:A088442

Search: a088442 -id:a088442

Displaying 1-8 of 8 results found.

page 1

A006257

Josephus problem: a(2*n) = 2*a(n)-1, a(2*n+1) = 2*a(n)+1.
(Formerly M2216)

+10
103

0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

Write the numbers 1 through n in a circle, start at 1 and cross off every other number until only one number is left.

A version of the children's game "One potato, two potato, ...".

a(n)/A062383(n) = (0, 0.1, 0.01, 0.11, 0.001, ...) enumerates all binary fractions in the unit interval [0, 1). - Fredrik Johansson, Aug 14 2006

Iterating a(n), a(a(n)), ... eventually leads to 2^A000120(n) - 1. - Franklin T. Adams-Watters, Apr 09 2010

By inspection, the solution to the Josephus Problem is a sequence of odd numbers (from 1) starting at each power of 2. This yields a direct closed form expression (see formula below). - Gregory Pat Scandalis, Oct 15 2013

Also zero together with a triangle read by rows in which row n lists the first 2^(n-1) odd numbers (see A005408), n >= 1. Row lengths give A011782. Right border gives A000225. Row sums give A000302, n >= 1. See example. - Omar E. Pol, Oct 16 2013

For n > 0: a(n) = n + 1 - A080079(n). - Reinhard Zumkeller, Apr 14 2014

In binary, a(n) = ROL(n), where ROL = rotate left = remove the leftmost digit and append it to the right. For example, n = 41 = 101001_2 => a(n) = (0)10011_2 = 19. This also explains FTAW's comment above. - M. F. Hasler, Nov 02 2016

In the under-down Australian card deck separation: top card on bottom of a deck of n cards, next card separated on the table, etc., until one card is left. The position a(n), for n >= 1, from top will be the left over card. See, e.g., the Behrends reference, pp. 156-164. For the down-under case see 2*A053645(n), for n >= 3, n not a power of 2. If n >= 2 is a power of 2 the botton card survives. - Wolfdieter Lang, Jul 28 2020

REFERENCES

Erhard Behrends, Der mathematische Zauberstab, Rowolth Taschenbuch Verlag, rororo 62902, 4. Auflage, 2019, pp. 156-164. [English version: The Math Behind the Magic, AMS, 2019.]

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 10.

M. S. Petković, "Josephus problem", Famous Puzzles of Great Mathematicians, page 179, Amer. Math. Soc. (AMS), 2009.

Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Paul Weisenhorn, Josephus und seine Folgen, MNU, 59(2006), pp. 18-19.

LINKS

Iain Fox, Table of n, a(n) for n = 0..100000 (terms 0..1000 from T. D. Noe, terms 1001..10000 from Indranil Ghosh).

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197, ex. 34.

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.

Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.

Daniel Erman and Brady Haran, The Josephus Problem, Numberphile video (2016)

Chris Groër, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.

Alasdair MacFhraing, Aireamh Muinntir Fhinn Is Dhubhain, Agus Sgeul Josephuis Is An Da Fhichead Iudhaich, [Gaelic with English summary], Proc. Royal Irish Acad., Vol. LII, Sect. A., No. 7, 1948, 87-93.

Yuri Nikolayevsky and Ioannis Tsartsaflis, Cohomology of N-graded Lie algebras of maximal class over Z_2, arXiv:1512.87676 [math.RA], (2016), pages 2, 6.

Ralf Stephan, Some divide-and-conquer sequences ...

Ralf Stephan, Table of generating functions

Eric Weisstein's World of Mathematics, Josephus Problem

Wikipedia, Josephus problem

Index entries for sequences related to the Josephus Problem

FORMULA

To get a(n), write n in binary, rotate left 1 place.

a(n) = 2*A053645(n) + 1 = 2(n-msb(n))+1. - Marc LeBrun, Jul 11 2001. [Here "msb" = "most significant bit", A053644.]

G.f.: 1 + 2/(1-x) * ((3*x-1)/(2-2*x) - Sum_{k>=1} 2^(k-1)*x^2^k). - Ralf Stephan, Apr 18 2003

a(n) = number of positive integers k < n such that n XOR k < n. a(n) = n - A035327(n). - Paul D. Hanna, Jan 21 2006

a(n) = n for n = 2^k - 1. - Zak Seidov, Dec 14 2006

a(n) = n - A035327(n). - K. Spage, Oct 22 2009

a(2^m+k) = 1+2*k; with 0 <= m and 0 <= k < 2^m; n = 2^m+k; m = floor(log_2(n)); k = n-2^m; a(n) = ((a(n-1)+1) mod n) + 1; a(1) = 1. E.g., n=27; m=4; k=11; a(27) = 1 + 2*11 = 23. - Paul Weisenhorn, Oct 10 2010

a(n) = 2*(n - 2^floor(log_2(n))) + 1 (see comment above). - Gregory Pat Scandalis, Oct 15 2013

a(n) = 0 if n = 0 and a(n) = 2*a(floor(n/2)) - (-1)^(n mod 2) if n > 0. - Marek A. Suchenek, Mar 31 2016

G.f. A(x) satisfies: A(x) = 2*A(x^2)*(1 + x) + x/(1 + x). - Ilya Gutkovskiy, Aug 31 2019

For n > 0: a(n) = 2 * A062050(n) - 1. - Frank Hollstein, Oct 25 2021

EXAMPLE

From Omar E. Pol, Jun 09 2009: (Start)

Written as an irregular triangle the sequence begins:

1,3;

1,3,5,7;

1,3,5,7,9,11,13,15;

1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31;

1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,

43,45,47,49,51,53,55,57,59,61,63;

...

(End)

From Omar E. Pol, Nov 03 2018: (Start)

An illustration of initial terms, where a(n) is the area (or number of cells) in the n-th region of the structure:

n a(n) Diagram

0 0 _

1 1 |_|_ _

2 1 |_| |

3 3 |_ _|_ _ _ _

4 1 |_| | | |

5 3 |_ _| | |

6 5 |_ _ _| |

7 7 |_ _ _ _|

(End)

MAPLE

a(0):=0: for n from 1 to 100 do a(n):=(a(n-1)+1) mod n +1: end do:

seq(a(i), i=0..100); # Paul Weisenhorn, Oct 10 2010; corrected by Robert Israel, Jan 13 2016

A006257 := proc(n)

convert(n, base, 2) ;

ListTools[Rotate](%, -1) ;

add( op(i, %)*2^(i-1), i=1..nops(%)) ;

end proc: # R. J. Mathar, May 20 2016

A006257 := n -> 2*n - Bits:-Iff(n, n):

seq(A006257(n), n=0..78); # Peter Luschny, Sep 24 2019

MATHEMATICA

Table[ FromDigits[ RotateLeft[ IntegerDigits[n, 2]], 2], {n, 0, 80}] (* Robert G. Wilson v, Sep 21 2003 *)

Flatten@Table[Range[1, 2^n - 1, 2], {n, 0, 5}] (* Birkas Gyorgy, Feb 07 2011 *)

m = 5; Range[2^m - 1] + 1 - Flatten@Table[Reverse@Range[2^n], {n, 0, m - 1}] (* Birkas Gyorgy, Feb 07 2011 *)

PROG

(PARI) a(n)=sum(k=1, n, if(bitxor(n, k)<n, 1, 0)) \\ Paul D. Hanna

(PARI) a(n)=if(n, 2*n-2^logint(2*n, 2)+1, 0) \\ Charles R Greathouse IV, Oct 29 2016

(Haskell)

a006257 n = a006257_list !! n

a006257_list =

0 : 1 : (map (+ 1) $ zipWith mod (map (+ 1) $ tail a006257_list) [2..])

-- Reinhard Zumkeller, Oct 06 2011

(Magma) [0] cat [2*(n-2^Floor(Log(2, n)))+1: n in [1..100]]; // Vincenzo Librandi, Jan 14 2016

(Python)

import math

def A006257(n):

return 0 if n==0 else 2*(n-2**int(math.log(n, 2)))+1 # Indranil Ghosh, Jan 11 2017

(Python)

def A006257(n): return bool(n&(m:=1<<n.bit_length()-1))+((n&m-1)<<1) if n else 0 # Chai Wah Wu, Jan 22 2023

(C#)

static long cs_A006257(this long n) => n == 0 ? 0 : 1 + (1 + (n - 1).cs_A006257()) % n; // Frank Hollstein, Feb 24 2021

(Coq)

Require Import ZArith.

Fixpoint a (n : positive) : Z :=

match n with

| xH => 1

| xI n' => (2*(a n') + 1)%Z

| xO n' => (2*(a n') - 1)%Z

end.

(* Stefan Haan, Aug 27 2023 *)

CROSSREFS

Cf. A005428, A035327, A038572, A049940, A049964, A053644, A053645, A088147, A088442.

Second column, and main diagonal, of triangle A032434.

Cf. A181281 (with s=5), A054995 (with s=3).

Column k=2 of A360099.

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Robert G. Wilson v, Sep 21 2003

STATUS

approved

A145812

Odd positive integers a(n) such that for every odd integer m > 1 there exists a unique representation of m as a sum of the form a(l) + 2a(s).

+10
17

1, 3, 9, 11, 33, 35, 41, 43, 129, 131, 137, 139, 161, 163, 169, 171, 513, 515, 521, 523, 545, 547, 553, 555, 641, 643, 649, 651, 673, 675, 681, 683, 2049, 2051, 2057, 2059, 2081, 2083, 2089, 2091, 2177, 2179, 2185, 2187, 2209, 2211, 2217, 2219, 2561, 2563

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Theorem. An odd number is in the sequence iff in its binary expansion all digits on k-th positions from the end, k=3, 5, 7, ..., are zeros. For example, 169, 171 have binary expansions 10101001, 10101011. Thus both of them are in the sequence. If A(x) is the counting function of a(n) <= x, then A(x) = O(sqrt(x)) and Omega(sqrt(x)).

Every positive odd integer m==3 (mod 2^(2r-1)) is a unique sum of the form a(2^(r-1)*(s-1)+1) + 2a(2^(r-1)*(t-1)+1), r=1,2,..., while the other odd integers are not expressible in such a form (see also the comment to A145818). Problem: Let B be the set of analytical functions f(x), f(0)=0, abs(x) > 1, with (0,1)-Taylor coefficients. Let F(x) be in B. It could be proved that the equation f(x)*f(x^2) = F(x) has no more than one solution in B. In case of F(x) = x^3/(1-x^(2^r)), r=1,2,..., it has one solution, which leads to A145812, A145818, A145849, A145850, etc. Find the conditions of the solvability of this equation in B and give, if it is possible, other examples. [Vladimir Shevelev, Oct 21 2008]

To get the decomposition of odd m as sum a(l) + 2a(s), write m-2 as Sum b_j 2^j, then a(l) = 1 + Sum_{j odd} b_j 2^j. This algorithm follows from our comment to A088442 and the algorithm of calculation of A088442(n). For example, if m=81, then we have 79 = 1*2^0 + 1*2^1 + 1*2^2 + 1*2^3 + 1*2^6. Thus a(l) = 1 + (1*2^1 + 1*2^3) = 11 and the required decomposition is 81 = 11 + 2*35, such that a(s)=35. We see that L=4, s=6, i.e., "index coordinates" of 81 are (4,6). Thus we have a one-to-one map of odd integers > 1 to the positive lattice points in the plane. [Vladimir Shevelev, Oct 24 2008]

LINKS

Klaus Brockhaus, Table of n, a(n) for n=1..8192 [From Klaus Brockhaus, Nov 01 2008]

V. Shevelev, On unique additive representations of positive integers and some close problems, arXiv:0811.0290 [math.NT]

FORMULA

If f(x) = Sum_{n>=1} x^a(n), abs(x) < 1, then f(x)*f(x^2) = x^3/(1-x^2).

To get a(n), write n-1 as Sum b_j 2^j, then a(n) = 1 + 2Sum b_j 2^(2j). Conversely, if an odd number m==r(mod 4), r=1 or 3 has the form which is indicated in the theorem, i.e., 2m - 2r = Sum_{j>=1} b_j 2^(2j), b_j = 0 or 1, then the only solution of the equation a(x)=m is x = Sum_{j>=1} b_j 2^(j-1) + (r+1)/2. [Vladimir Shevelev, Oct 25 2008]

For n >= 2, a(n) = a(n-1) + (4^(t+1) + 2)/3, where t >= 0 is such that n-1 == 2^t (mod 2^(t+1)). [Vladimir Shevelev, Nov 04 2008]

a(n) = 2*A000695(n-1) + 1. [Vladimir Shevelev, Nov 07 2008]

From Robert Israel, Aug 20 2017: (Start)

a(2n-1) = 4*a(n)-3.

a(2n) = 4*a(n)-1.

G.f. g(z) satisfies g(z) = (4 + 4/z) g(z^2) - (z^2 + 3 z)/(1-z^2). (End)

EXAMPLE

If n=13, we have n-1 = 12 = 2^3 + 2^2. Therefore a(13) = 1 + 2(4^3 + 4^2) = 161. If m=521 and thus 2(521-1) = 1040 = 2^10 + 2^4, then the equation a(x)=521 has the unique solution x = 2^4 + 2^1 + 1 = 19. [Vladimir Shevelev, Oct 25 2008]

MAPLE

filter:= proc(n) local L; L:= convert(n, base, 2);

andmap(i -> L[2*i+1]=0, [$1..(nops(L)-1)/2])

end proc:

select(filter, [seq(i, i=1..10000, 2)]); # Robert Israel, Aug 20 2017

MATHEMATICA

a[1]=1; a[2]=3; a[n_] := a[n] = If[OddQ[n], 4*a[(n+1)/2]-3, 4*a[n/2]-1];

Array[a, 50] (* Jean-François Alcover, Nov 14 2017, after Robert Israel *)

PROG

(PARI) isok(n) = {if (! (n % 2), return (0)); b = binary(n); forstep (i = #b, 1, -1, rpos = #b - i + 1; if ((rpos > 1) && (rpos % 2) && b[i], return (0)); ); return (1); } \\ Michel Marcus, Jan 19 2014

(Haskell)

a145812 n = a145812_list !! (n-1)

a145812_list = filter f [1, 3 ..] where

f v = v == 0 || even w && f w where w = v `div` 4

-- Reinhard Zumkeller, Mar 13 2014

CROSSREFS

Cf. A000695.

KEYWORD

nonn,look

AUTHOR

Vladimir Shevelev, Oct 20 2008

EXTENSIONS

Extended beyond a(16) by Klaus Brockhaus, Oct 22 2008

STATUS

approved

A063694

Remove odd-positioned bits from the binary expansion of n.

+10
13

0, 1, 0, 1, 4, 5, 4, 5, 0, 1, 0, 1, 4, 5, 4, 5, 16, 17, 16, 17, 20, 21, 20, 21, 16, 17, 16, 17, 20, 21, 20, 21, 0, 1, 0, 1, 4, 5, 4, 5, 0, 1, 0, 1, 4, 5, 4, 5, 16, 17, 16, 17, 20, 21, 20, 21, 16, 17, 16, 17, 20, 21, 20, 21, 64, 65, 64, 65, 68, 69, 68, 69, 64, 65, 64, 65, 68, 69, 68

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

a(n) is the formal derivative of x*n (evaluated at x=2 after being lifted to Z[x]) where n is interpreted as a polynomial in GF(2)[x] via its binary expansion. - Keith J. Bauer, Mar 17 2024

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Ralf Stephan, Some divide-and-conquer sequences ...

Ralf Stephan, Table of generating functions

FORMULA

a(n) = Sum_{k>=0} (-1)^k*2^k*floor(n/2^k).

a(n) + A063695(n) = n.

a(n) = n - 2*a(floor(n/2)). - Vladeta Jovovic, Feb 23 2003

G.f.: 1/(1-x) * Sum_{k>=0} (-2)^k*x^2^k/(1-x^2^k). - Ralf Stephan, May 05 2003

a(n) = 4*a(floor(n/4)) + (n mod 4) mod 2. - Reinhard Zumkeller, Sep 26 2015

a(n) = Sum_{k>=0} A030308(n,k)*A199572(k). - Philippe Deléham, Jan 12 2023

EXAMPLE

a(25) = 17 because 25 = 11001 in binary and when we AND this with 10101 we are left with 10001 = 17.

MAPLE

every_other_pos := proc(nn, x, w) local n, i, s; n := nn; i := 0; s := 0; while(n > 0) do if((i mod 2) = w) then s := s + ((x^i)*(n mod x)); fi; n := floor(n/x); i := i+1; od; RETURN(s); end: [seq(every_other_pos(j, 2, 0), j=0..120)];

MATHEMATICA

a[n_] := BitAnd[n, Sum[2^k, {k, 0, Log[2, n] // Floor, 2}]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 28 2016 *)

PROG

(PARI) a(n)=sum(k=0, n, (-1)^k*2^k*floor(n/2^k)) /* since n> ceil(log(n)/log(2)) */

(PARI) a(n)=if(n<0, 0, sum(k=0, n, (-1)^k*2^k*floor(n/2^k))) /* since n> ceil(log(n)/log(2)) */

(Haskell)

a063694 0 = 0

a063694 n = 4 * a063694 n' + mod q 2

where (n', q) = divMod n 4

-- Reinhard Zumkeller, Sep 26 2015

(Magma)

function A063694(n)

if n le 1 then return n;

else return 4*A063694(Floor(n/4)) + ((n mod 4) mod 2);

end if; return A063694;

end function;

[A063694(n): n in [0..120]]; // G. C. Greubel, Dec 05 2022

(SageMath)

def A063694(n):

if (n<2): return n

else: return 4*A063694(floor(n/4)) + ((n%4)%2)

[A063694(n) for n in range(121)] # G. C. Greubel, Dec 05 2022

(Python)

def A063694(n): return n&((1<<(m:=n.bit_length())+(m&1))-1)//3 # Chai Wah Wu, Jan 30 2023

CROSSREFS

Cf. A004514, A063695 (remove even-positioned bits), A088442.

KEYWORD

nonn,base,easy

AUTHOR

Antti Karttunen, Aug 03 2001

STATUS

approved

A090569

The survivor w(n,2) in a modified Josephus problem, with a step of 2.

+10
7

1, 1, 3, 3, 1, 1, 3, 3, 9, 9, 11, 11, 9, 9, 11, 11, 1, 1, 3, 3, 1, 1, 3, 3, 9, 9, 11, 11, 9, 9, 11, 11, 33, 33, 35, 35, 33, 33, 35, 35, 41, 41, 43, 43, 41, 41, 43, 43, 33, 33, 35, 35, 33, 33, 35, 35, 41, 41, 43, 43, 41, 41, 43, 43, 1, 1, 3, 3, 1, 1, 3, 3, 9, 9, 11, 11, 9, 9, 11, 11, 1, 1

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

Arrange n persons {1,2,...,n} consecutively on a line rather than around in a circle. Beginning at the left end of the line, we remove every q-th person until we reach the end of the line. At this point we immediately reverse directions, taking care not to "double count" the person at the end of the line and continue to eliminate every q-th person, but now moving right to left. We continue removing people in this back-and-forth manner until there remains a lone survivor w(n,q).

Or a(n) is in A145812 such that 2n+1-2a(n) is in A145812 as well. Note also that 2a(n)+A088442(n-1)=2n+1. - Vladimir Shevelev, Oct 20 2008

LINKS

Table of n, a(n) for n=1..82.

Chris Groër, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.

Index entries for sequences related to the Josephus Problem

FORMULA

w(n, 2) = 1 + Sum_{odd j=1..k} b(j)*(2^j), where Sum_{j=0..k} b(j)*(2^j) is the binary expansion of either n or n-1, whichever is odd.

a(n) = A063695(n-1) + 1.

EXAMPLE

a(2)=11, since people are eliminated in the order 2, 4, 6, 8, 10, 12, 9, 5, 1, 7, 3, leaving 11 as the survivor.

PROG

(Python)

def A090569(n): return (n-1&((1<<(m:=(n-1).bit_length())+(m&1^1))-1)//3)+1 # Chai Wah Wu, Jan 30 2023

CROSSREFS

Cf. A088443, A088452.

KEYWORD

nonn

AUTHOR

John W. Layman, Dec 02 2003

STATUS

approved

A004514

Generalized nim sum n + n in base 4.

+10
5

0, 2, 0, 2, 8, 10, 8, 10, 0, 2, 0, 2, 8, 10, 8, 10, 32, 34, 32, 34, 40, 42, 40, 42, 32, 34, 32, 34, 40, 42, 40, 42, 0, 2, 0, 2, 8, 10, 8, 10, 0, 2, 0, 2, 8, 10, 8, 10, 32, 34, 32, 34, 40, 42, 40, 42, 32, 34, 32, 34, 40, 42, 40, 42, 128, 130, 128, 130, 136, 138, 136, 138, 128

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Index entries for sequences related to Nim-sums

FORMULA

Generalized nim sum m + n in base q: write m and n in base q and add mod q with no carries, e.g., 5 + 8 in base 3 = "21" + "22" = "10" = 1.

From Vladeta Jovovic, Feb 23 2003: (Start)

a(n) = 2*(n - a(floor(n/2))).

a(n) = 2*A063694(n). (End)

a(n) = A088442(n) - 1. - Chris Groer (cgroer(AT)math.uga.edu), Nov 10, 2003

a(n) = n + A053985(n). - Reinhard Zumkeller, Dec 27 2003

a(n) = A063695(2*n+1). - Reinhard Zumkeller, Sep 26 2015

a(n) = Sum_{k>=0} A030308(n,k)*A103424(k+1). - Philippe Deléham, Jan 12 2023

MATHEMATICA

A004514[n_]:= A004514[n]= If[n==0, 0, 2*n -2*A004514[Floor[n/2]]];

Table[A004514[n], {n, 0, 90}] (* G. C. Greubel, Dec 05 2022 *)

PROG

(Haskell)

a004514 = a063695 . (+ 1) . (* 2) -- Reinhard Zumkeller, Sep 26 2015

(Magma)

function A063694(n)

if n le 1 then return n;

else return 4*A063694(Floor(n/4)) + ((n mod 4) mod 2);

end if; return A063694;

end function;

A004514:= func< n | 2*A063694(n) >;

[A004514(n): n in [0..90]]; // G. C. Greubel, Dec 05 2022

(SageMath)

def A063694(n):

if (n<2): return n

else: return 4*A063694(floor(n/4)) + ((n%4)%2)

def A004514(n): return 2*A063694(n)

[A004514(n) for n in range(91)] # G. C. Greubel, Dec 05 2022

(PARI) a(n) = if(n, bitand(n, 2<<bitor(1, logint(n, 2)) \ 3)) << 1; \\ Kevin Ryde, Dec 10 2022

(Python)

def A004514(n): return (n&((1<<(m:=n.bit_length())+(m&1))-1)//3)<<1 # Chai Wah Wu, Jan 30 2023

CROSSREFS

Cf. A053985, A063694, A063695, A088442.

KEYWORD

base,easy,nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Reinhard Zumkeller, Dec 27 2003

STATUS

approved

A088452

The survivor w(n,4) in a modified Josephus problem, with a step of 4.

+10
4

1, 1, 1, 3, 2, 6, 5, 1, 3, 10, 7, 9, 1, 2, 6, 5, 17, 18, 11, 13, 15, 10, 2, 1, 11, 10, 7, 9, 17, 30, 31, 31, 19, 22, 22, 27, 26, 23, 18, 1, 1, 1, 6, 19, 17, 18, 17, 13, 15, 14, 30, 29, 53, 50, 55, 55, 50, 33, 34, 38, 38, 39, 49, 47, 46, 46, 41, 29, 31, 1, 2, 6, 1, 1, 3, 10, 34, 34, 34, 30

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

LINKS

Table of n, a(n) for n=1..80.

Chris Groër, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110(9) (2003), 812-825.

Index entries for sequences related to the Josephus Problem

MATHEMATICA

w4[1] = v4[1] = u4[1] = 1; w4[n_] := w4[n] = Switch[ Mod[n, 4], 0, n + 1 - Ceiling[4w4[ Ceiling[3n/4]]/3], 1, n + 1 - Floor[(4w4[ Ceiling[3n/4]] + 1)/3], 2, n + 1 - Floor[4v4[ Ceiling[3n/4]]/3], 3, n + 1 - Floor[(4u4[ Ceiling[3n/4]] - 1)/3]]; v4[n_] := v4[n] = Switch[ Mod[n, 4], 0, n + 1 - Floor[(4w4[ Ceiling[3n/4]] + 1)/3], 1, n + 1 - Floor[(4v4[ Ceiling[3n/4]])/3], 2, n + 1 - Floor[(4u4[ Ceiling[3n/4]] - 1)/3], 3, n + 1 - Ceiling[ 4w4[ Floor[3n/4]]/3]]; u4[n_] := u4[n] = Switch[ Mod[n, 4], 0, n + 1 - Floor[ 4v4[ Ceiling[3n/4]]/3], 1, n + 1 - Floor[ (4u4[ Ceiling[3n/4]] - 1)/3], 2, n + 1 - Ceiling[ 4w4[ Floor[3n/4]]/3], 3, n + 1 - Floor[(4w4[ Floor[3n/4]] + 1)/3]]; Table[ w4[n], {n, 81}] (* from Chris Groer modified by Robert G. Wilson v Nov 15 2003 *)

CROSSREFS

Cf. A006257, A088442, A088443, A090569.

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Nov 09 2003

EXTENSIONS

Terms computed by Chris Groer (cgroer(AT)math.uga.edu)

STATUS

approved

A088443

A linear version of the Josephus problem: a(n) = the function w_3(n).

+10
3

1, 2, 1, 4, 1, 1, 7, 8, 8, 1, 2, 1, 2, 5, 14, 14, 17, 17, 17, 17, 14, 2, 1, 4, 1, 1, 2, 4, 4, 5, 11, 32, 31, 34, 31, 31, 37, 38, 38, 38, 41, 37, 38, 37, 38, 31, 31, 1, 4, 5, 1, 7, 8, 8, 1, 2, 1, 2, 5, 4, 1, 8, 8, 8, 8, 11, 11, 20, 23, 25, 71, 71, 68, 70, 68, 76, 74, 68, 68, 68, 70, 82, 83, 82

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

The survivor w(n,3) in a modified Josephus problem, with a step of 3.

See A090569 or the reference for the definition of w(n,q).

LINKS

Table of n, a(n) for n=1..84.

Chris Groër, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.

Index entries for sequences related to the Josephus Problem

FORMULA

A recurrence is given in the reference.

CROSSREFS

Cf. A006257, A088442, A088452, A090569.

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Nov 09 2003

EXTENSIONS

Terms computed by Chris Groer (cgroer(AT)math.uga.edu)

More terms from John W. Layman, Feb 05 2004

STATUS

approved

A225489

Elimination order for the first person in a linear Josephus problem.

+10
1

1, 2, 2, 3, 5, 6, 5, 6, 8, 9, 8, 9, 12, 13, 11, 12, 17, 18, 14, 15, 21, 22, 17, 18, 23, 24, 20, 21, 27, 28, 23, 24, 32, 33, 26, 27, 36, 37, 29, 30, 38, 39, 32, 33, 42, 43, 35, 36, 48, 49, 38, 39, 52, 53, 41, 42, 53, 54, 44, 45, 57, 58, 47, 48, 65, 66, 50, 51

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

The process is identical to that of A090569 where n persons are arranged on a line and every second person is eliminated. When we reach the end of the line the direction is reversed without double-counting the person at the end. a(n) is the order in which the person originally first in line is eliminated.

LINKS

Table of n, a(n) for n=1..68.

Chris Groër, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.

Index entries for sequences related to the Josephus Problem

FORMULA

For n=4m then a(n) = 3*n/4;

for n=4m+1 then a(n) = a(1+(n-1)/4) + 3*(n-1)/4;

for n=4m+2 then a(n) = a(1+(n-2)/4) + 3*(n-2)/4 + 1;

for n=4m+3 then a(n) = 3*(n-3)/4 + 2.

EXAMPLE

If there are 7 persons to begin with, they are eliminated in the following order: 2,4,6,5,1,7,3. So the first person (the person originally first in line) is eliminated as number 5. Therefore a(7) = 5.

MATHEMATICA

t = {1}; Do[AppendTo[t, Switch[Mod[n, 4], 0, 3*n/4, 1, t[[1 + (n-1)/4]] + 3*(n-1)/4, 2, t[[1 + (n-2)/4]] + 3*(n-2)/4 + 1, 3, 3*(n-3)/4 + 2, 4, Mod[n, 4] + 1]], {n, 2, 100}]; t (* T. D. Noe, May 17 2013 *)

CROSSREFS

Cf. A090569, A088442.

KEYWORD

nonn

AUTHOR

Marcus Hedbring, May 08 2013

STATUS

approved

page 1

Search completed in 0.013 seconds