A note on the generalized Josephus problem

DOI10.21099/TKBJM/1496164893MaRDI QIDQ819265zbMATH OpenOpenAlexFDO

Authors Saburô Uchiyama

Publication date 28 March 2006

Published in Tsukuba Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.21099/tkbjm/1496164893

zbMATH Keywords

Josephus number

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Special sequences and polynomials (11B83)

Review text

Supposing that \(n\) objects, numbered from \(1\) to \(n\), are arranged in a circle, starting with object number \(1\) and counting each object in turn around the circle, clockwise or anticlockwise in the same direction fixed once for all, we eliminate every \(m\)th \((m\geq 2)\) object until all the objects are removed. The \(k\)th Josephus number \(a_m(k, n)\) \((1\leq k\leq n)\) is defined to be equal to \(\ell\) \((1\leq\ell\leq n)\), if \(\ell\) is the number attached to the object to be removed at the \(k\)th step of reduction. There is plainly \(1\leq a_m(k,n)\leq n\). For a given \(m\geq 1\) in general \(m\) induces a permutation \(\sigma_m= \sigma_{m,n}\) of the array \(\langle 1,2,\dots, n\rangle\), that is the Josephus permutation. There are shown some propositions on Josephus permutations. A generalisation of the Josephus problem is to determine Josephus numbers \(a_m(k, n)\) in which the integers \(m\) may be not necessarily the same in each step of eliminating the \(n\) given objects. It is presented an algorithm for determining the Josephus numbers \(a_m(k, n)\) with an arbitrarily given sequence \((m)= (m_1,m_2,m_3,\dots)\) of positive integers.

Recommendations

• scientific article; zbMATH DE number 4135942
• A further note on the generalized Josephus problem
• The Josephus problem
• On the generalized Josephus problem
• scientific article; zbMATH DE number 6843437

Cited in

(15)

• The Josephus problem
• On the generalized Josephus problem
• A further note on the generalized Josephus problem
• Generalizations of the Josephus problem
• Functional iteration and the Josephus problem
• scientific article; zbMATH DE number 1061000 (Why is no real title available?)
• The Mathematics of Survival: From Antiquity to the Playground
• scientific article; zbMATH DE number 6843437 (Why is no real title available?)
• A variant on the feline Josephus problem
• Serial execution Josephus problem
• On the switchback version of Josephus problem
• Analytical Study and Efficient Evaluation of the Josephus Function
• Randomisation in the Josephus problem
• The feline Josephus problem
• Survival probabilities of counting-out games on a line

This page was built for publication: A note on the generalized Josephus problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q819265)