### Recent Posts

### Archives

### Site Stats

- 106,446 hits

Programming Enigma Puzzles

23 November 2015

Posted by on **From New Scientist #2348, 22nd June 2002**

The schoolteacher wanted to choose a certain small number of boys from his class. “In how many ways can I choose that number of boys?” he asked. The answer was a three-figure number. He then wanted to choose a certain smaller number of girls from the class. “In how many way can I choose that number of girls?” he asked. The answer was a three-figure number.

The teacher then wanted to choose a certain smaller number of children from the class as a whole. “In how many ways can I choose that number of children?” he asked. The answer was a three-figure number.

The three-figure answers above between them use all of the digits 1 to 9.

How many children were in the class?

[enigma1192]

20 November 2015

Posted by on **From New Scientist #1468, 8th August 1985** [link]

Edgar’s farm is in the shape of an equilateral triangle (ABC in the diagram). It is divided into seven fields by three straight hedges, AQ, BR and CP. The fields such as BQT are 8 acres, and those such as ASUR are 22 acres. All I want to know is: what is the exact acreage of the middle field, STU?

[enigma320]

16 November 2015

Posted by on **From New Scientist #2349, 29th June 2002**

George has been explaining to his young son the concept of factorials, which are denoted by an exclamation mark. The factorial of three, denoted 3!, is 1 × 2 × 3 = 6. The factorial of 10 (10!) is 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10 = 3,628,800.

“In that case, Dad, the factorial of one million (1,000,000!) must be a very large number.”

“Indeed so — it has more than five million digits, ending with a long string of zeros.”

How many zeros?

This **Enigma** appeared in the styling that was used for the remainder of **Enigma** puzzles, up to December 2013.

[enigma1193]

15 November 2015

Posted by on **From The Sunday Times, 15th November 2015** [link]

King Lear III had a square kingdom divided into sixteen equal-sized smaller square plots, numbered in the usual way. He decided to keep a realm for himself and share the rest into equal realms (larger than his) for his daughters, a “realm” being a collection of one or more connected plots. He chose a suitable realm for himself and one for his eldest daughter and he noticed that, in each case, multiplying together [the] plot numbers within the realm gave a perfect square. Then he found that there was only one way to divide the remainder of the kingdom into suitable realms.

What are the plot numbers of the eldest daughter’s realm and of the king’s realm.

The puzzle text on The Sunday Times website, uses “any” where I have placed “[the]”.

[teaser2773]

13 November 2015

Posted by on **From New Scientist #1467, 1st August 1985** [link]

On the next five Saturdays, Albion, Borough, City, Rangers and United will be competing against each other in a league. There will be two matches each Saturday, each of the five teams having one Saturday without a match. At the end, each team will have played each of the others once, and will have played two home matches and two away matches alternating.

Next Saturday, the competition starts with Albion at home to Borough, and City at home to Rangers. A fortnight later, Borough will be playing at home.

What will be the two matches on the final Saturday (the home team to be named first in each match)?

[enigma319]

9 November 2015

Posted by on **From New Scientist #2350, 6th July 2002**

Harry, Tom, and I have joined the Apathy Party, which as reported in Colin Singleton‘s puzzle Enigma 1154 proposes to reduce the currency to just two denominations. We each want a currency composed of two coins, each a whole number of pence. We have each suggested which two denominations should be chosen.

We have calculated for each of the three suggestions the largest integral amount that

cannotbe paid exactly with any combination of the two coins, and also the largest amount thatcanbe paid exactly by only one combination of the two coins.In each case the answer is a two-digit number. Indeed, the largest integral amount that

cannotbe paid exactly by any combination of my two denominations is the same as the largest amount thatcanbe paid exactly by only one combination of Harry’s two denominations and also the same as the largest amount thatcanbe paid exactly by only one combination of Tom’s two denominations. (A “combination” need not include both denominations).Harry’s denominations are different from Tom’s.

Which two denominations have I suggested?

[enigma1194]

6 November 2015

Posted by on **From New Scientist #1466, 25th July 1985** [link]

Below is an addition sum with letters substituted for digits. The same letter stands for the same digit wherever it appears, and different letters stand for different digits.

Write out the sum with numbers substituted for letters.

[enigma318]

2 November 2015

Posted by on **From New Scientist #2351, 13th July 2002**

You are probably familiar with the word-chain game where you have to get from one word

to another by changing one letter at a time, making a proper word at each stage.

For example one shortest chain for changing DAMN to LOVE is:DAMN – DAME – DOME – DOVE – LOVE.

Your task today is to find a shortest chain from MALE to DIRT. But your chain has to have a further property. You have to consistently replace each letter by a non-zero digit throughout the chain, different digits being used for different letters. For example, one such substitution in the above chain yields:

1863 – 1869 – 1769 – 1749 – 5749.

In that chain some of the four-figure numbers are prime and some are not. But in your substitution for a shortest MALE to DIRT chain all the four-figure numbers must be primes less than 2500.

What is the number for MALE?

[enigma1195]

30 October 2015

Posted by on **From New Scientist #1465, 18th July 1985** [link]

In the fruiterers football league, each of the four teams plays each of the others once. Three points are awarded for a win and one for a draw. The table below shows part of the League Table at the end of last season. As usual, different letters stand consistently for different digits.

The four teams, Appleton Rovers, Banana Splits, Cox’s Pippins and Damsons United are in order of merit, goal differences having to be used just once to divide them.

List all the victories last season (e.g. X beat Y, P beat Q, etc).

[enigma317]

26 October 2015

Posted by on **From New Scientist #2352, 20th July 2002**

The septitude of a two-digit number,

n, is obtained by first dividingnby 7 and noting the remainder,r. We userto calculate a new number as follows:if

ris 0, 1, 2, 3, 4, 5, 6 then the new number isn+ 29,n– 23,n+ 15,n– 40,n+ 31,n+ 25,n– 37 respectively.If the new number is in the range 10 to 99 then it is the septitude of

n, otherwise add or subtract 84 from the new number to get a number in the range 10 to 99, and that latter number is the septitude ofn.For example, the septitudes of 14, 15, and 74 are 43, 76, and 21 respectively.

In the crossnumber puzzle (below):

each of the four answers, 1 Across, 3 Across, 1 Down and 2 Down, equals the septitude of another of these four answers. Also 3 Across is larger than 2 Down.

What are 1 Across and 3 Across?

[enigma1196]

23 October 2015

Posted by on **From New Scientist #1464, 11th July 1985** [link]

This is a game between you and the Devil. It starts with the natural numbers from 1 to

Nwritten in a row. You and the Devil play alternately, you first. The rules are simple:(a) You take any number you choose (subject to rule (d) below) from those remaining in the row and delete it from the row.

(b) He then deletes from the numbers remaining in the row all those which are factors of the number you just took.

(c) Go to (a).

(d) You can never take a number which has no factor remaining in the row; that is, your take must permit the Devil in his turn to delete at least one number.The game stops when you can legally take no more numbers, and you want the sum

Sof all the numbers you have taken to be asas possible.smallThe picture records a game with

N=7 andS=6. You did very well. Now try withN=30.How small can you make

S?

[enigma316]

21 October 2015

Posted by on Following on from my previous articles on programming the Analytical Engine (see Part 1 and Part 2), in this post we will actually translate Ada Lovelace’s diagram that is considered to be the first published program into a directly executable program for the Analytical Engine emulator, where each row in the diagram corresponds directly to a statement in the assembly language program.

As suggested in Part 2, I have written a simple assembler to make it a bit easier to write programs for the Analytical Engine emulator. It allows you to specify the arithmetic operations for the Engine as a single statement (rather than the usual 4 cards), and it keeps track of symbolic labels and automatically computes branch offsets for you.

The assembler is implemented by the `assemble()` function, which I’ve included in the latest version of **analytical_engine.py**.

The `assemble()` function takes a multi-line string representing the program, and returns a list of cards suitable for use as a program in the `AnalyticalEngine` class. It also returns a map from the labels used in the assembler program to the index of the corresponding card in the program.

The factorial program from Part 2 would look like this using the assembler:

from analytical_engine import AnalyticalEngine, Column, assemble n = 40 (program, _) = assemble(""" :init SET 0 <- {n} SET 1 <- 1 SET 2 <- 1 :loop # operation 1: v[2] *= v[0] MUL 0 2 -> 2 # operation 2: v[2] -= 1 SUB 0 1 -> 0 # branch if non-zero to operation 1 BRN loop # end HALT """.format(n=n)) # initialise the engine p = AnalyticalEngine(vars=3, number=Column(digits=50), trace=1) # load the program to compute factorial(n) p.load_program(program) # run the program p.run() # the result is in v[2] print("factorial({n}) = {f}".format(n=n, f=p.v[2]))

The embedded program for the Analytical Engine is highlighted.

Note that I have used Python’s `format()` function to interpolate the (Python) variable `n` into the string before it is passed to the assembler. So the assembler just sees “… SET 0 <- 40 …”.

By setting the `trace=1` flag on the emulator the actual program cards loaded into the emulator are printed out before execution (as well as the trace of the execution itself).

The format that the assembler accepts should be fairly self-explanatory, from the example above, and from the implementation of Ada’s program given below, but the main points are:

- Comments (as in Perl and Python) are indicated by a
`#`(hash) and continue to the end of the line. - A line that starts with a
`:`(colon) declares a label (which can be used as the target of a branch). - Statements start with an op-code, followed by a number of space separated arguments.
- The multiple cards required for an arithmetical operation (
`ADD`,`SUB`,`MUL`,`DIV`) are replaced by a single statement. Each takes two arguments to indicate the source of the operands: either the index of a variable in the store, or the special token`DATA`, which indicates that the value is loaded from the input data stack. Additional arguments are used to indicate indices in the store where the result is to be stored. - The offset in branch statements can be specified using a symbolic label, by using a symbol that is declared as a label elsewhere in the program. (The label can appear either before or after the branch statement).
- The arrows (
`<-`and`->`) used in the`SET`statement to indicate the value being assigned to a variable in the store, and in arithmetic operations to indicate the variables in the store that the result of the operation is assigned to, are entirely optional. (They are removed during the parsing process, but I think it makes the program a little more readable).

So we can now write Ada’s program for Bernoulli Numbers like this:

from analytical_engine import AnalyticalEngine, Column, assemble from enigma import raw_input, printf # assemble the program (program, labels) = assemble(""" :init SET 0 <- 0 SET 1 <- 1 SET 2 <- 2 SET 3 <- 1 :start MUL 2 3 -> 4 5 6 SUB 4 1 -> 4 ADD 5 1 -> 5 DIV 4 5 -> 11 DIV 11 2 -> 11 SUB 13 11 -> 13 SUB 3 1 -> 10 BRZ finish ADD 2 7 -> 7 DIV 6 7 -> 11 MUL DATA 11 -> 12 ADD 12 13 -> 13 SUB 10 1 -> 10 BRZ finish :loop SUB 6 1 -> 6 ADD 1 7 -> 7 DIV 6 7 -> 8 MUL 8 11 -> 11 SUB 6 1 -> 6 ADD 1 7 -> 7 DIV 6 7 -> 9 MUL 9 11 -> 11 MUL DATA 11 -> 12 ADD 12 13 -> 13 SUB 10 1 -> 10 BRN loop :finish SUB 0 13 PRINT ADD 1 3 -> 3 SET 7 <- 0 SET 13 <- 0 HALT """) # initialise the engine p = AnalyticalEngine(vars=14, number=Column(digits=10, dp=40), trace=1) # load the program p.load_program(program) # indices B[k] k = 1 # input data, initially empty, but each result is added after computation data = [] # instruction to start execution at start = labels['init'] # run the program while True: # load the data and run the program p.load_data(data) p.run(start) # get the computed result from the output transcript r = (p.output[-1] if p.output else None) # display the computed result printf("B[{k}] = {r}") # run the program again? try: raw_input('\n[paused] >>> ') except EOFError: printf() break # add the result to the data and run it again data.append(r) start = labels['start'] k += 2

Again, the highlighted section is the embedded program for the Analytical Engine, and the statements in the program correspond to the lines in Ada’s diagram, with extra statements for the initialisation, branching and output added. So the first row in Ada’s diagram corresponds to the “multiply” statement after the “:start” instruction (line 12 of the above Python program).

We can use the output of the assembler to provide the indices of the cards where we wish to start and subsequently re-start execution.

This, then, is a directly executable representation of the first published program.

19 October 2015

Posted by on **From New Scientist #2353, 27th July 2002**

Triangular numbers are those that fit the formula ½

n(n+1), such as 1, 3, 6 and 10.In the following statement digits have been consistently replaced by capital letters, different letters being used for different digits:

UN, TROIS, SIX, and DIX are all triangular numbers, none of which starts with a zero.

Which numbers are represented by (in this order) UN, TROIS, SIX and DIX?

See also **Enigma 1300**.

[enigma1197]

16 October 2015

Posted by on **From New Scientist #1463, 4th July 1985** [link]

I recently met a Continental employer who applies a painless IQ screening test to all prospective employees. His advertisements require that all candidates must ring-in on an ex-directory telephone — but the number to ring is published in a clandestine form.

Recruitment will soon be extended to Britain.

New Scientistreaders are privileged to preview this statement of the telephone number to be used:(1) The international telephone number comprises three discrete groups of numerals. No group commences with the digit 0.

(2) The decimal number represented by the first group to be dialled is equal to the sum of all other digits in the number. The decimal number represented by the second group is the square root of the third group number.

(3) The first 10 numerals to be dialled include all the available digits from 0 to 9; the 11th (last) numeral repeats the 10th numeral.

Good luck with your applications! Please let us know the complete telephone number in correct dialling sequence before you sail.

[enigma315]

14 October 2015

Posted by on Yesterday was Ada Lovelace Day, so following on from my previous post about Ada’s program for computing Bernoulli Numbers, I decided to implement an emulation of the Analytical Engine so that I can directly run the “assembly language” program I produced in that post, rather than translate it into a modern programming language in order to run it.

I haven’t finished reading all the materials I have found about the Analytical Engine, but I think I’ve learned enough to have a crack at doing an emulation sufficient for my needs.

So without further ado, here’s my emulation of the Analytical Engine in Python:

# emulation of the Analytical Engine class HaltException(Exception): pass class AnalyticalEngine(object): # vars = number of variables # number = a function to implement the variables def __init__(self, **kw): # number of variables in the store self.vars = 20 # a method to implement the variables self.number = float # set options for (k, v) in kw.items(): if hasattr(self, k): setattr(self, k, v) else: print('AnalyticalEngine: ignoring "{k}={v}"'.format(k=k, v=v)) self.reset() # reset the machine def reset(self): # representation of zero self.zero = self.number(0) # the variables in the store self.v = [self.zero] * self.vars # the registers in the mill self.index = 0 self.input = [None, None] self.result = None # current operation self.op = None # the program and program counter self.program = None self.pc = None # input data self.data = None self.dc = None # output transcript self.output = None # load the program def load_program(self, program): self.program = program self.pc = 0 # load the data def load_data(self, data): self.data = data self.dc = 0 # run the program (starting at instruction start) def run(self, start=0): print(">>> Running Analytical Engine") self.output = [] self.pc = start try: while True: # get the next instruction assert not(self.pc < 0), "Invalid PC" p = self.program[self.pc] # execute it getattr(self, p[0])(*p[1:]) # increment the program counter self.pc += 1 except Exception as e: print(">>> {e}".format(e=e)) print(">>> Execution halted") # implement the opcodes # SET <i> <x> # set variable <i> in the store to value <x> def SET(self, i, x): self.v[i] = self.number(x) # ADD # set the engine to perform addition def ADD(self): self.op = (lambda a, b: a + b) # SUB # set the engine to perform subtraction def SUB(self): self.op = (lambda a, b: a - b) # MUL # set the engine to perform multiplication def MUL(self): self.op = (lambda a, b: a * b) # DIV # set the engine to perform division def DIV(self): self.op = (lambda a, b: a / b) # execute an operation def _execute(self): self.result = self.op(self.input[0], self.input[1]) # load value v into the input register def _load(self, v): self.input[self.index] = v # loading the second register triggers the execution if self.index == 1: self._execute() # next time load the other input register self.index ^= 1 # LOAD <i> # load the input register from variable <i> in the store def LOAD(self, i): self._load(self.v[i]) # LOAD_DATA # load the input register from next value in the input data stack def LOAD_DATA(self): self._load(self.data[self.dc]) self.dc += 1 # STORE <i> # store the result to variable <i> in the store def STORE(self, i): self.v[i] = self.result # PRINT # print the result def PRINT(self): print(self.result) self.output.append(self.result) # HALT # halt execution of the engine def HALT(self): raise HaltException("HALT instruction encountered") # branch def _branch(self, offset): self.pc += offset # BRZ <offset> # branch if zero: # if the result is zero move the program instructions by <offset> def BRZ(self, offset): if self.result == self.zero: self._branch(offset) # BRN <offset> # branch if non-zero: # if the result is non-zero move the program instructions by <offset> def BRN(self, offset): if self.result != self.zero: self._branch(offset)

Click the link for an expanded version of this implementation that includes code to trace the execution of the Engine. [link]

Before we look at running a program on the Analytical Engine, some notes:

- This is an emulation of the function the Analytical Engine, not a simulation of the mechanical workings.
- You can specify the number of variables (columns) in the store of the Analytical Engine with the
`vars`parameter to the`AnalyticalEngine`class. One of Babbage’s designs was for a store with 1000 columns. - You can specify an implementation for the columns using the
`number`parameter to the`AnalyticalEngine`class. Later on I’ll implement a class that more closely emulates the behaviour of the columns in the design for the Engine, but for now we can use Python’s`float`built-in (to use floating point numbers) or`fractions.Fraction`for exact results. - The program is presented as a sequence of instructions (which represent the variable cards and operation cards used to program the Analytical Engine). Each instruction consists of a sequence where the first element is the “op code” and the remaining elements are the corresponding parameters. The program is loaded into the Engine using the
`load_program()`method, and can then be executed using the`run()`method. - The “op codes” are the names of methods on the
`AnalyticalEngine`class. I use upper case methods to indicate the instructions. - I’ve implemented a stack of “input data” cards as I suggested in my comment on the “Running the first program post” [link]. The data is loaded into the Engine using the
`load_data()`method, and the op code used in the program cards to load a register in the mill from the input data is`LOAD_DATA`(rather than`LOAD input`as I suggested in the comment). - I’ve implemented two conditional instructions: “BRZ
*offset*” (branch if zero) and “BRN*offset*” (branch if non-zero). In each case the result register of the mill is checked, and if the condition holds the program counter is moved by*offset*instructions. The*offset*may be positive (to implement conditional execution) or negative (to implement looping). - The Engine will continue to run the program until a (Python) exception occurs, at which point the Engine will stop. There it a
`HALT`instruction provided specifically to raise an exception that will stop the Engine.

This is my own interpretation of the Analytical Engine, for a more rigorous interpretation and Java implementation see the pages at fourmilab.ch.

Below is a simple program to compute *factorial(12)*. The Analytical Engine program is wrapped up in a Python program that creates a suitable instantiation of the `AnalyticalEngine` class (with 3 variables in the store, and using Python’s built-in `int` class to implement the columns).

We then load the program for the Analytical Engine, run it and the computed result is in variable 2 from the store.

from analytical_engine import AnalyticalEngine # initialise the engine p = AnalyticalEngine(vars=3, number=int) # load the program to compute factorial(12) n = 12 p.load_program([ # initialisation ['SET', 0, n], ['SET', 1, 1], ['SET', 2, 1], # operation 1: v[2] *= v[0] ['MUL'], ['LOAD', 0], ['LOAD', 2], ['STORE', 2], # operation 2: v[2] -= 1 ['SUB'], ['LOAD', 0], ['LOAD', 1], ['STORE', 0], # branch if non-zero to operation 1 ['BRN', -9], # end ['HALT'], ]) # run the program p.run() # the result is in v[2] print("factorial({n}) = {f}".format(n=n, f=p.v[2]))

When run you see output like this:

$ python factorial.py >>> Running Analytical Engine >>> HALT instruction encountered >>> Execution halted factorial(12) = 479001600

And indeed this is the correct value for *factorial(12)*.

The difficulty in writing these programs is making sure the branch offsets go to the right place. As statements occupy multiple cards it is easy to branch into the middle of a statement with unexpected results. (What’s really needed is an assembler that can compile a statement like “`mul(0, 2, 2)`” and produce the four instructions that make up the first operation. This would make a program correspond much more closely with the diagrams published to describe the operation of the Analytical Engine. Such an assembler could also allow for symbolic labels to be used in branches so the offsets are computed automatically. I might add this functionality to a future version of **analytical_engine.py**).

Here is the full program to execute Ada Lovelace’s algorithm for computing Bernoulli Numbers. As you can see the actual program for the Analytical Engine is a direct translation from the assembly language program I gave in my comment to the last post (except I’ve actually had to work out the correct offsets for the “branch” instructions).

In this instance we use an AnalyticalEngine with 14 variables, and the numbers are implemented using Python’s `fractions.Fraction` objects, which give exact results for the computation.

The controlling loop collects the results as they are generated and adds them to the input data stack, and then re-runs the program to compute the next Bernoulli Number in the sequence. It pauses between each run of the program to allow the user examine the output and to halt the program if necessary.

(Note that the enclosing Python program uses a couple of utility routines from the **enigma.py** library, available here [link]).

from analytical_engine import AnalyticalEngine from fractions import Fraction from enigma import raw_input, printf # initialise the engine p = AnalyticalEngine(vars=14, number=Fraction) # load the program p.load_program([ # initialisation ['SET', 0, 0], ['SET', 1, 1], ['SET', 2, 2], ['SET', 3, 1], # operation 1 ['MUL'], ['LOAD', 2], ['LOAD', 3], ['STORE', 4], ['STORE', 5], ['STORE', 6], # operation 2 ['SUB'], ['LOAD', 4], ['LOAD', 1], ['STORE', 4], # operation 3 ['ADD'], ['LOAD', 5], ['LOAD', 1], ['STORE', 5], # operation 4 ['DIV'], ['LOAD', 4], ['LOAD', 5], ['STORE', 11], # operation 5 ['DIV'], ['LOAD', 11], ['LOAD', 2], ['STORE', 11], # operation 6 ['SUB'], ['LOAD', 13], ['LOAD', 11], ['STORE', 13], # operation 7 ['SUB'], ['LOAD', 3], ['LOAD', 1], ['STORE', 10], # branch if zero to operation 24 ['BRZ', +66], # operation 8 ['ADD'], ['LOAD', 2], ['LOAD', 7], ['STORE', 7], # operation 9 ['DIV'], ['LOAD', 6], ['LOAD', 7], ['STORE', 11], # operation 10 ['MUL'], ['LOAD_DATA'], ['LOAD', 11], ['STORE', 12], # operation 11 ['ADD'], ['LOAD', 12], ['LOAD', 13], ['STORE', 13], # operation 12 ['SUB'], ['LOAD', 10], ['LOAD', 1], ['STORE', 10], # branch if zero to operation 24 ['BRZ', +45], # operation 13 ['SUB'], ['LOAD', 6], ['LOAD', 1], ['STORE', 6], # operation 14 ['ADD'], ['LOAD', 1], ['LOAD', 7], ['STORE', 7], # operation 15 ['DIV'], ['LOAD', 6], ['LOAD', 7], ['STORE', 8], # operation 16 ['MUL'], ['LOAD', 8], ['LOAD', 11], ['STORE', 11], # operation 17 ['SUB'], ['LOAD', 6], ['LOAD', 1], ['STORE', 6], # operation 18 ['ADD'], ['LOAD', 1], ['LOAD', 7], ['STORE', 7], # operation 19 ['DIV'], ['LOAD', 6], ['LOAD', 7], ['STORE', 9], # operation 20 ['MUL'], ['LOAD', 9], ['LOAD', 11], ['STORE', 11], # operation 21 ['MUL'], ['LOAD_DATA'], ['LOAD', 11], ['STORE', 12], # operation 22 ['ADD'], ['LOAD', 12], ['LOAD', 13], ['STORE', 13], # operation 23 ['SUB'], ['LOAD', 10], ['LOAD', 1], ['STORE', 10], # branch if non-zero to operation 13 ['BRN', -45], # operation 24 ['SUB'], ['LOAD', 0], ['LOAD', 13], # print ['PRINT'], # operation 25 ['ADD'], ['LOAD', 1], ['LOAD', 3], ['STORE', 3], # reset working variables ['SET', 7, 0], ['SET', 13, 0], # end ['HALT'], ]) # indices B[k] k = 1 # input data, initially empty, but each result is added after computation data = [] # instruction to start execution at, initially 0, but subsequently 4 start = 0 # run the program while True: # load the data and run the program p.load_data(data) p.run(start) # get the computed result from the output transcript r = (p.output[-1] if p.output else None) # display the computed result printf("B[{k}] = {r}") # run the program again? try: raw_input('\n[paused] >>> ') except EOFError: printf() break # add the result to the data and run it again (from instruction 4) data.append(r) start = 4 k += 2

By running this we can check that the Engine does indeed produce the list of Bernoulli Numbers:

B[1] = 1/6, B[3] = −1/30, B[5] = 1/42, B[7] = −1/30, B[9] = 5/66, B[11] = −691/2730, …

The computation that Ada outlines in *Note G* is the calculation of B[7] = −1/30. This involves 10 ADD operations, 11 SUB operations, 8 MUL operations and 7 DIV operations. The Analytical Engine was estimated to do be able to perform an addition or subtraction in about 1 second, but multiplication and division could take up to a minute (the actual time would vary depending on the operands), and also branching would take some time to step through the required number of cards. So altogether we might expect the Engine to take around 15 to 20 minutes to compute B[7]. And as we compute further numbers in the sequence the number of operations and the corresponding time would increase.

So far we have been using Python’s built-in number classes to implement the columns, which can provide arbitrary precision. But the actual columns for the Analytical Engine would have been able to store 50 decimal digits, and a sign (to indicate if the number was positive or negative).

Here’s an implementation of a class suitable for use as the `number` parameter when constructing an `AnalyticalEngine` instance, that more closely replicates the columns of the Analytical Engine.

# implementation of the columns in the Analytical Engine class OverflowException(Exception): pass # a column with <digits> whole decimal digits and <dp> fractional decimal digits def Column(digits=50, dp=0): shift = (10 ** dp) overflow = (10 ** (digits + dp)) - 1 fmt = '<{s}{m:0' + str(digits) + 'd}' + ('.{d:0' + str(dp) + 'd}' if dp > 0 else '') + '>' class Column(object): # create a value, and check for overflow def __init__(self, n=0, shift=shift): if shift: n *= shift if abs(n) > overflow: raise OverflowException("Overflow in column") self.n = n # output format def __repr__(self): n = self.n (m, d) = divmod(abs(n), shift) s = ('-' if n < 0 else '+') return fmt.format(s=s, m=m, d=d) # arithmetic operations def __add__(self, value): return Column(self.n + value.n, shift=0) def __sub__(self, value): return Column(self.n - value.n, shift=0) def __mul__(self, value): return Column((self.n * value.n) // shift, shift=0) def __div__(self, value): return Column((self.n * shift) // value.n, shift=0) # Python 3 uses __truediv__ __truediv__ = __div__ # branch tests def __eq__(self, value): return self.n == value.n def __ne__(self, value): return self.n != value.n return Column

Notes:

- We can specify the number of whole decimal digits for the column with the
`digits`parameter. The columns can also be used to implement fixed point decimal numbers by specifying how many additional*fractional*decimal places are required with the`dp`parameter. - I’m not sure what happened when an overflow happened in the Analytical Engine, so I throw an exception.
- The columns support the four arithmetical operations that the Analytical Engine supports (addition, subtraction, multiplication and division), and also the two conditionals for the branches (is zero, is non-zero).
- The columns display as a fixed with string “<{sign}{digits}.{digits}>”.

The **Column** class is included in **analytical_engine.py**.

So we can use the following program to compute *factorial(40)* using columns containing 50 decimal digits:

from analytical_engine import AnalyticalEngine, Column # initialise the engine p = AnalyticalEngine(vars=3, number=Column(digits=50)) # load the program to compute factorial(40) n = 40 p.load_program([ # initialisation ['SET', 0, n], ['SET', 1, 1], ['SET', 2, 1], # operation 1: v[2] *= v[0] ['MUL'], ['LOAD', 0], ['LOAD', 2], ['STORE', 2], # operation 2: v[2] -= 1 ['SUB'], ['LOAD', 0], ['LOAD', 1], ['STORE', 0], # branch if non-zero to operation 1 ['BRN', -9], # end ['HALT'], ]) # run the program p.run() # the result is in v[2] print("factorial({n}) = {f}".format(n=n, f=p.v[2]))

$ python factorial2.py >>> Running Analytical Engine >>> HALT instruction encountered >>> Execution halted factorial(40) = <+00815915283247897734345611269596115894272000000000>

And similarly by using `number=Column(10, 40)` in the implementation of Ada’s program we can compute Bernoulli numbers to 40 decimal places.

In divisions we will potentially lose precision in the final decimal places of the result, and as later numbers in the sequence are calculated from earlier numbers we will see the precision deteriorate as we go on.

Here are the results of running the program:

B[1] = <+0000000000.1666666666666666666666666666666666666666> B[3] = <-0000000000.0333333333333333333333333333333333333332> B[5] = <+0000000000.0238095238095238095238095238095238095233> B[7] = <-0000000000.0333333333333333333333333333333333333302> B[9] = <+0000000000.0757575757575757575757575757575757575464> B[11] = <-0000000000.2531135531135531135531135531135531131568> B[13] = <+0000000001.1666666666666666666666666666666666593360> B[15] = <-0000000007.0921568627450980392156862745098037431432> B[17] = <+0000000054.9711779448621553884711779448621498550887> B[19] = <-0000000529.1242424242424242424242424242422111802933> B[21] = <+0000006192.1231884057971014492753623188306059856832> B[23] = <-0000086580.2531135531135531135531135525557263098091> B[25] = <+0001425517.1666666666666666666666666299288036638424> ...

By the time we reach B[25] the last 15 digits of our 40 digits of decimal precision have been lost (B[25] = 8553103/6 = 1425517 + 1/6), but the computation is still correct to 25 decimal places.

**Note:** The Python programs presented should run under Python 2 or Python 3, but as I used the new-style `print()` function, so if you are running them under Python 2 you will need to put the following line at the start of the programs:

from __future__ import print_function

12 October 2015

Posted by on **From New Scientist #2354, 3rd August 2002** [link]

George, Fred and Harry have been doodling with pencil and paper — each has drawn a right-angled triangle. The three triangles are similar — that is to say all the same shape but different sizes.

Although they are different sizes, each of the three triangles has one side measuring exactly 10 cm. None of the other sides are integers. One of the non-integer sides of George’s triangle is the same length as one side of Fred’s, and the other non-integer side of George’s triangle is the same length as one side of Harry’s triangle.

One side of Fred’s triangle has no exact equal in the other two triangles, and the same is true of one side of Harry’s triangle. Of those two sides, Harry’s is the longer.

How much longer?

[enigma1198]

9 October 2015

Posted by on **From New Scientist #1462, 27th June 1985** [link]

In the following football table and addition sum, letters have been substituted for digits (from 0 to 9). The same letter stands for the same digit wherever it appears, and different letters stand for different digits.

(1) The four teams are eventually going to play each other once, or perhaps they have already done so. With one exception, all the matches were won by a margin of only one goal.

(Two points are given for a win and one point to each side in a drawn match).

(2)

Find the scores in the football matches, and write out the addition sum with numbers substituted for letters.

This is the 900th **Enigma** puzzle to be posted to the site. The archive currently contains *Enigmas* 1 – 314 (Feb 1979 – Jun 1985) and *Enigmas* 1199 – 1780 (Aug 2002 – Dec 2013).

[enigma314]

7 October 2015

Posted by on **From New Scientist #1052, 19th May 1977** [link]

There has been a lot of excitement recently about an examination which four of our employees — Alf, Bert, Charlie and Duggie — have been having in French and mathematics.

Now that we are in the Common Market it is important that we should move with the times and learn some French. And in a modern factory such as ours we must know about all the latest mathematical ideas.

It is interesting that Bert’s French place was a much above his mathematics place as Charlie’s mathematics place was below his French place. Alf’s place was even at both subjects, and Duggie’s place was odd at both. Bert was not top at either subject, and no one had the same place at both. There were no ties.

Find the order in both subjects.

This was the first in a series of puzzles called *Puzzle* set by Eric Emmet in **New Scientist** between May 1977 and February 1979 (when it was replaced by *Enigma*). As with his *Enigma* puzzles these seem to consist mostly of substituted sums, substituted divisions and football table problems.

[puzzle1]

5 October 2015

Posted by on **From New Scientist #2355, 10th August 2002** [link]

In the numbers ENIGMA, MEANING and IDEA digits have been consistently replaced by letters, with different letters used for different digits. I have tested the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 and 12 to see if they are a common factor of both ENIGMA and MEANING.

Of course 1 is a common factor of them, and it turns out that nine of the numbers 1-12 are common factors of ENIGMA and MEANING (and indeed the other three numbers are factors of IDEA).

What is the numerical value of ENIGMA?

[enigma1199]

2 October 2015

Posted by on **From New Scientist #1461, 20th June 1985** [link]

I showed my son the famous 21 card trick. I used 21 cards numbered from 1 to 21, which remained face upwards throughout the trick. I started with them in numerical order in a pile, 1 being on the top. I dealt them into three piles (1 on to the first, 2 on to the second, 3 on to the third, 4 on to the first again, and so on) and asked my son to choose one of the numbers without telling me which. Then he had to tell me which pile his number was in.

I then picked up the piles, placing his chosen pile in the middle of the three. With this new pile I started all over again and repeated the performance twice more, my son pointing out the pile which contained his chosen number each time. After the third and final collecting up of the cards his chosen card was (of course) in 11th place.

He then tried it on me, but he didn’t know the trick. He started with the cards in order as I had done, I chose a number, he went through the three deals (but collecting up the piles in his own fashion) and, not surprisingly, the trick went wrong.

The number I had chosen ended up in the 10th place, not the 11th. The number in the 11th place was in fact half my number. And the number which was twice mine ended up in the same place in the pile as it had started in.

What was my chosen number?

[enigma313]

## Recent Comments