An application of Fourier transforms on finite Abelian groups to an enumeration arising from the Josephus problem

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.