A152423 A variation of the Josephus problem, removing every other person, starting with person 1; a(n) is the last person remaining.

1, 2, 2, 4, 2, 4, 6, 8, 2, 4, 6, 8, 10, 12, 14, 16, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20

Offset: 1

Author

Suttapong Wara-asawapati (retsam_krad(AT)hotmail.com), Dec 03 2008

Keywords

• easy
• nonn

Comments

Begin with n people standing in a circle, numbered clockwise 1 through n. Until only one person remains, go around the circle clockwise, removing every other person, starting by removing person 1. a(n) is the number of the last person remaining.

Apparently a(n) = 2*A062050(n-1), n > 1. - Paul Curtz, May 30 2011

Examples

			From _Omar E. Pol_, Dec 16 2013: (Start)
It appears that this is also an irregular triangle with row lengths A011782 as shown below:
1;
2;
2,4;
2,4,6,8;
2,4,6,8,10,12,14,16;
2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32;
2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40, 42,44,46,48,50,52,54,56,58,60,62,64;
Right border gives A000079.
(End)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..8192
• Eric Weisstein's World of Mathematics, Josephus Problem
• Wikipedia, Josephus problem
• Index entries for sequences related to the Josephus Problem

Crossrefs

The Index to the OEIS lists 21 entries under "Josephus problem". - N. J. A. Sloane, Dec 04 2008

Cf. A000079, A011782, A062050.

Programs

Maple

a:= n-> 2*n - 2^ceil(log[2](n)):
seq(a(n), n=1..74);  # Alois P. Heinz, Nov 22 2023

Mathematica

A152423[n_]:=2n-2^Ceiling[Log2[n]];Array[A152423,100] (* Paolo Xausa, Nov 23 2023 *)

PHP

function F($in){ $a[1] = 1; if($in == 1){ return $a;} $temp =2; for($i=2;$i<=$in;$i++){ $temp+=2; if($temp>$i){ $temp = 2 ; } $answer[] = $temp; } return $answer; } #change $n value for the result $n=5; #sequence store in $answer by using $a = F($n); #to display a(n) echo $a[n];

Python

m=len(bin(n))-3; print(n if 2**m==n else 2*(n-2**m)) # Nicolas Patrois, Apr 19 2021

Formula

a(1)=1, a(2)=2; for n > 2, a(n)=2 if n < a(n-1) + 2, otherwise a(n) = a(n-1) + 2.

a(n)=n if n is a power of 2, otherwise a(n)=2*(n-2^m) where m is the exponent of the nearest power of 2 below n. - Nicolas Patrois, Apr 19 2021

a(n) = 2*n - 2^ceiling(log_2(n)). - Alois P. Heinz, Nov 22 2023

Extensions

Edited by Jon E. Schoenfield, Feb 29 2020