Introduction

It can be fun to drive a problem all the way into the ground. I don’t always get to do that on paying projects, however sometimes I can do it with hobby projects. In this case I am going to re-solve Dudeney’s Remainder Problem again and again to argue that it can be solved at a pencil and paper scale. The problem is as follows.

A good idea for a solution is noticing that the answer is the greatest common divisor (GCD) of two differences of the puzzle inputs, such as 723217 - 480608 = 242609 and 508811 - 480608 = 28203. However, “every good idea becomes a lifetime’s work for someone” (Shriekback, Sacred City, “Every force evolves a form”, 1992). Can we perform the remaining calculation explicitly at pencil and paper scale? Or must we use a computer (as we did in our original R based solution)?

This note is a somewhat involved series of demonstrations to show one can solve this problem “by hand” (or with minimal tools).

Computer Solution

In my original note, I implemented the greatest common divisor with an iterative reduction- which could also be written as a recursion. We could also have sped than up by calling a library gcd function such as Python’s math.gcd(). Here I am going to slow things down into filling out a table. This places a much larger emphasis on values and how values relate. This is an intermediate step to working out the calculation ourselves by hand.

Each of our result table cells are filled in with a fairly simple calculation (division, multiplication, addition), and there are not that many cells. In principle, a person could perform the calculation on paper. The methodology is outlined here. The following is a short animation (without sound) showing an extended table being filled out. For the original problem, only the first column is needed.

Extended Euclidian Algorithm applied to Dudeney’s Remainder Problem (no sound)

The puzzle answer is 79, the last non-zero entry in the “r” column.

HP15c Calculator Solution (1982 technology)

Now suppose we don’t allow a 2024 era programmable digital computer, as they did not have them 1924 when the note was published in Strand Magazine. We can solve the problem with a calculator, for example the HP15c (which came out in 1982, so they also did not have these in 1924- more on this later).

Here is a video (no sound) of me using a HP15c calculator that has a program stored in “label A” that performs a greatest common divisor step. This method also sets up the calculator for the next step, so no additional data entry is required. I just enter the two starting numbers and repeat “f A” to call the subroutine again and again. The HP15c keystroke macro (or program) is at the end of this note.

hp15c solving Dudeney’s Remainder Problem (no sound)

There was a real joy in working with calculators of this era. They were simple enough you felt you were solving the problem, but powerful enough to shoulder most of the work. I have an older note on this joy here.

Curta Calculator Solution (1948 technology)

Okay what sort of calculators could the public have had in 1924? The answers include:

• Scratch paper
• An Abacus
• An Arithmometer (1851-1915)
  
• An Odhner Arithmometer (1890-1917)
• A Facit Standard mechanical calculator (1923)

The Curta calculator of 1948 operates a lot like a portable arithmometer (though the first uses a stepped Leibniz drum, and the other a pin wheel). They both used digit shifting, an accumulator register, and a reversible revolution counting register. The point is: these types of calculators were commercially available from the 1850s through 1960s. As I don’t have access to an arithmometer, so I’ll start the greatest common divisor calculation by hand with a Curta calculator.

For a user familiar with the Curta the steps are fairly standard. I am not teaching how to use the Curta, but just giving the steps somebody familiar with a Curta could be expected to execute. The steps would be:

• Start with the two positive integers. To find the greatest common divisor write these down in a column, largest first.
• Clear the registers on the Curta, put the Curta in add mode (lever pushed in, and add/subtract slider to “up add”).
• Enter the first number into the input register, add it to the accumulator by turning the crank, and clear the revolution counter.
• Divide by the second number in the usual Curta method (set the add/subtract slider to “down subtract”, and pull the crank up). Pull off the divisor at different shifts until the register is less than the divisor. Record the register as a new quotient at the bottom of our column of numbers. (Optionally) record the remainder next to the quotient.
• Clear the register and then add the previous quotient input as the next dividend. Use the number last written down as the new quotient. Repeat the division step and this until we get a zero remainder.
• The last non-zero quotient is the greatest common divisor.

I show the first few steps in the following video (without sound):

Curta solving Dudeney’s Remainder Problem (no sound)

That took me just under 1.5 minutes. It takes 7 divisions to complete the table. Therefore, the greatest common divisor can be comfortably calculated in under 11 minutes using a mechanical calculator.

The HP15c Program

The HP15c allowed macros (unconditional sequences of key strokes) and even programs (including conditionals and loops). It also has a 4 level value stack, a side register called “LSTx” (which stores one of the inputs of various calculations), and a number of named registers. Designing a calculation for the HP15c was often a joy. When calculation was done by hand, one spent a bit more time designing the result table and calculation steps.

A HP15c program solving the greatest common divisor problem is given below. You could find things like this in the excellent manuals and solutions guides of the time.

The Solution

In case we have lost the plot, I’ll return to the puzzle solution one last time.

The solution is 79. All three numbers have the same remainder relative to 79.