A337191 A version of the Josephus problem: a(n) is the surviving integer under the skip-eliminate-eliminate version of the elimination process.

1, 1, 1, 4, 4, 1, 7, 4, 1, 7, 4, 10, 7, 13, 10, 16, 13, 1, 16, 4, 19, 7, 22, 10, 25, 13, 1, 16, 4, 19, 7, 22, 10, 25, 13, 28, 16, 31, 19, 34, 22, 37, 25, 40, 28, 43, 31, 46, 34, 49, 37, 52, 40, 1, 43, 4, 46, 7, 49, 10, 52, 13, 55, 16, 58, 19, 61, 22, 64, 25, 67

Offset: 1

Author

Robert W. Vallin, Aug 18 2020

Keywords

• nonn

Comments

This variation of the Josephus problem is related to under-down-down card dealing. - Tanya Khovanova, Apr 14 2025

Examples

			Consider 4 people in a circle in order 1,2,3,4. In the first round, person 1 is skipped and persons 2 and 3 are eliminated. Now people are in order 4,1. In the second round, person 4 is skipped and person 1 is eliminated. Person 4 is freed. Thus, a(4) = 4. - _Tanya Khovanova_, Apr 14 2025
		

Links

• Harvey P. Dale, Table of n, a(n) for n = 1..1000
• Index entries for sequences related to the Josephus Problem

Crossrefs

Cf. A006257, A225381, A321298, A378635, A381048, A381049, A382528.

Programs

Mathematica

nxt[{n_,a_,b_}]:={n+1,b,If[Mod[a+3,n+1]!=0,Mod[a+3,n+1],n+1]}; NestList[nxt,{2,1,1},70][[;;,2]] (* Harvey P. Dale, Jul 27 2024 *)

PARI

a(n) = if (n <= 2, 1, my(x = (a(n-2) + 3) % n); if (x, x, n)); \\ Michel Marcus, Aug 20 2020

PARI

a(n) = if (n<=1, return(1)); my(v=vector(n, i, i), w); while (#v > 3, if (#v <=3, w = [], w = vector(#v-3, k, v[k+3])); w = concat(w, Vec(v, 1)); v = w;); v[1]; \\ Michel Marcus, Mar 25 2025

Formula

a(1) = 1, a(2) = 1, a(n) = (a(n-2) + 3) (mod n) if (a(n-2) + 3) (mod n) is not 0; a(n) = n if (a(n-2) + 3) (mod n)=0.

Any number n can be written as either 2*(3^k) + 2m (where 0 <= m < 3^k, k = 0,1,2,...) or 3^k + 2m (where 0 <= m < 3^k, k = 0,1,2,...), in either case a(n) = 3m + 1.

Extensions

More terms from Michel Marcus, Aug 20 2020

Title corrected by Tanya Khovanova, Apr 14 2025