Article ID Journal Published Year Pages File Type
4594663 Journal of Number Theory 2010 13 Pages PDF
Abstract

TextWe analyze an enumeration associated with the Josephus problem by applying a Fourier transform to a multivariate generating function. This yields a formula for the enumeration that reduces to a simple expression under a condition we call local prime abundance. Under this widely held condition, we prove (Corollary 3.4) that the proportion of Josephus permutations in the symmetric group SnSn that map t to k (independent of the choice of t and k  ) is 1/n1/n. Local prime abundance is intimately connected with a well-known result of S.S. Pillai, which we exploit for the purpose of determining when it holds and when it fails to hold. We pursue the first case where it fails, reducing an intractable DFT computation of the enumeration to a tractable one. A resulting computation shows that the enumeration is nontrivial for this case.VideoFor a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=DnZi-Znuk-A.

Related Topics
Physical Sciences and Engineering Mathematics Algebra and Number Theory
Authors
, ,