Josephus Problem

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

The "Josephus" problem is to identify the position to stand in a circle of 41 men if every 3rd man will be successively eliminated around the circle and you want to be the last remaining man.  

Background & Techniques

The story is that the Jewish historian/mathematician, Josephus, was running from the Romans during some Roman-Jewish war, sometime around 500 years ago.  They followed him to a cave where we found 40 Jewish soldiers and which the Romans placed under siege.  Seeing no hope of escape and unwilling to surrender, the group decided that suicide was the best way out.  Josephus and one other fellow weren't too happy about the plan so he suggested the circle with every third man committing suicide (or being executed in some versions), until only one man was left.  He was smart enough to figure out where he and his buddy should stand initially so they were the last two standing.  The rest of the story is that Josephus was known thereafter as Josephus Flavius after the family that adopted him when surrendered to the Romans.

These counting-elimination games have been traced back at least to the 12th century.  In the USA most kids learn the selection game that starts "One potato, two potato, three potato four...."  which selects one person for each round.    

Mathematically, the problem is quite simple, especially if you have a computer as a helper.  This version of the program has some simple animation.   User can select the number of people in the circle and the  increment between selected victims.  Selecting your location in the circle starts the elimination process and lists victims in the order of their selection.

Non-programmers are welcome to read on, but may want to skip to the bottom of this page to download executable version of the program.

The main programming challenge was getting the "smileys" and numbers positioned correctly in a circle and identifying which one was clicked to start the process.   An array of people numbers is maintained by eliminating entries as selected and incrementing the pointer the the next selection using modular arithmetic based on the numbr of people currently remaining in the circle.    

Two sizes of smileys are available and the distance between images determines whether the larger or smaller is used.  There are 4 smileys of  each size - normal alive, normal dead, player selected position alive, and player selected position dead.

Addendum October 15,2008:  Version 2 was posted today.  It solves an "inverse" version of Josephus; we are given the final location and must determine where to start counting for the selection process. Numbering relative to 1, the starting location may be calculated as:

Start=(A - F(N,K)  +N - 1) mod N + 1 where

bullet N=number of people
bullet K= choose every Kth person
bullet A= desired final person chosen
bullet F(N,K) is a recursive function defined as:
bullet F(N,K) = (F(N-1,K)  -K) mod N for N>1
bullet F(1,K) = 0 for N=1
 

Running/Exploring the Program 

bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

The bmp Smiley images should be incorporated into a resource file, but I would have had to look up the code to do it, so they are just included are separate files and loaded as required.  I'll bet the whole process of combining images into a "res" file could be automated into an interactive program. Hmmm.   

 

Original Date: July 10, 2005 

Modified: July 29, 2017

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.