A114144 A variant of the Josephus Problem in which three persons are to be eliminated at the same time.

3, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, 45, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 133

Offset: 1

Author

Satoshi Hashiba, Daisuke Minematsu and Ryohei Miyadera, Feb 03 2006

Keywords

• nonn
• easy

Comments

This is a variant of the Josephus Problem. When there are 3m persons, the first process of elimination starts with the first person, the second with the (m+1)-st person and the third with the (2m+1)-st person. We suppose that the first process comes first, the second process secondly and the third process thirdly. J(n) is the position of the survivor when there are n persons. Our sequence is a(n) = J(3*n).

Examples

			If there are 15 persons, then 2, 7, 12, 4, 9, 14, 6, 11, 1, 10, 15, 5, 3, 13 are to be eliminated and the survivor is 8. Therefore a(5) = J(15) = 8.
		

References

• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley Publishing Company, 1994, pp. 9-10.

Links

• Index entries for sequences related to the Josephus Problem

Crossrefs

Cf. A006257, A113648.

Programs

Mathematica

(*This function is defined only for numbers that are multiples of 3.*)
jose[3] = 3; jose[n_?(IntegerQ[ #/3] &)] := If[Mod[n, 6] == 0, If[jose[n/2] < n/3 + 1, 2jose[n/2] + n/3 - 1,2jose[n/2] - 2n/3 - 1], Which[jose[(n - 3)/2] < (n - 3)/6 +1, 2jose[(n - 3)/2] + (n - 3)/3 + 2, (n - 3)/6 < jose[(n - 3)/2] < (n - 3)/3 + 1, 2jose[(n - 3)/2] + (n - 3)/3 + 3, (n - 3)/3 < jose[(n - 3)/2], 2jose[(n - 3)/2] - 2(n - 3)/3 + 1]];

PARI

a(n) = if(n==0, 1, my(t); if(n%2, t=a(n\2); if(t>n-1, 2*t-2*n+3, if(t>n\2, 2*t+n+2, 2*t+n+1)), t=a(n/2); if(t>n, 2*t-2*n-1, 2*t+n-1))); \\ Jinyuan Wang, Apr 20 2025

Formula

The function J(n) is defined only for integers n that have 3 as a factor. J(6m+3) = 2J(3m)+2m+2 (if J(3m) <= m), J(6m+3) = 2J(3m)+2m+3 (if m+1 <= J(3m) <= 2m) and J(6m+3) = 2J(3m)-4m+1 (if 2m+1 <= J(3m)). J(6m) = 2J(3m)+2m-1 (if J(3m) <= 2m) and J(6m) = 2J(3m)-4m-1 (if J(3m) > 2m).

Extensions

More terms from Jinyuan Wang, Apr 20 2025