Calculating square roots on a pinwheel calculator

Before electronic calculators became affordable, complex calculations were often done using pinwheel calculators. These were manufactured by several companies, for example, Odhner, Brunsviga, Thales, Schubert, all based on designs of Frank Baldwin and Willgodt Odhner in the 19th century.

Original Odhner 127

Original Odhner 227

Brunsviga 20

Having recently acquired three of these calculators, I set about investigating what they were capable of. As well as the four basic arithmetic operations, addition, subtraction, multiplication and division, square roots can also be calculated. The instruction manual for the Original Odhner 227 describes the procedure to extract the square root of 966289. At first glance, the instructions look like an alchemist's spell, but they are performing the following calculations to derive √966289 = 983:

From Odhner 227 instructions (click to enlarge)

c)	966289  - 10000 - 30000 - 50000 - 70000 - 90000 -110000 - 130000 - 150000 - 170000 = 156289	( 9 subtractions)
d) & e)	156289  - 18100 - 18300 - 18500 - 18700 - 18900 - 19100 - 19300 - 19500 = 5889	( 8 subtractions)
f)	5889 -  1961 - 1963 -1965 = 0	( 3 subtractions)

 The algorithm is based on the fact that the square of n is the sum of the first n odd numbers:

12 = 1     =     1 22 = 4     =     1+3 32 = 9     =     1+3+5 42 = 16    =     1+3+5+7 52 = 25    =     1+3+5+7+9 etc.

The square root of a number can therefore be calculated by subtracting successive odd numbers until the sum is zero. The square root is the number of subtractions performed. For example, to find the square root of 64, successively subtract 1,3,5,... until zero is reached. The number of subtractions required, in this case 8, is the square root of the number. For large numbers, e.g. 966289, this would obviously be impractical, but we can attack large numbers one pair of digits at a time, to produce one digit of the square root at a time:

64 -  1 = 63 63 -  3 = 60 60 -  5 = 55 55 -  7 = 48 48 -  9 = 39 39 - 11 = 28 28 - 13 = 15 15 - 15 =  0

To find the first digit of the square root of 966289, subtract odd ten thousands: 10000, 30000, 50000, ...  until the point just before the result would turn negative, so subtract 10000+30000+...+170000.  Now, 1+3+...+17 = 9² , so 10000+30000+...+170000 = 900² . The first digit of the square root is 9.

To find the first two digits of the square root, we could start with 966289 and subtract odd hundreds: 100, 300, 500,... up to 19500. However, we have already subtracted 900², which is equal to 100+300+500+...+17700+17900, so we can start subtracting at 18100, subtracting only 18100+18300+...+19500.  We have now subtracted a total of 980².

Similarly to find the first three digits of the square root (i.e. the complete square root), we could start with 966289 and subtract 1, 3, 5,...up to 1965. But we have already subtracted 980² = 1+3+5+...+1959, so we can start subtracting at 1961, only needing to subtract 1961+1963+1965

10000+30000+...+170000		= 9002
18100+18300+...+19500	= (100+300+...+19500) - (100+300+...+17900)	= 9802 - 9002
1961+1963+1965	= (1+3+...+1965) - (1+3+...+1959)	= 9832 - 9802

^{The algorithm can also be used to calculate approximations to the square root of numbers that are not perfect squares. Here is a video by James Grime (singingbanana) and Hugh Hunt that demonstrates an Original Odhner being used to calculate √2.}

Feeler Gauges and Magic Circles

I recently came across Sunday Times Teaser puzzle, 777 on Brian Gladman's Puzzling In Python site:

I have half-a-dozen feeler gauges on a ring like keys on a key ring. They are attached in a certain order and by selecting a single gauge or combinations of adjacent gauges it is possible to measure from 1 to 31 thousandths of an inch (thou) inclusive in steps of 1 thou. If I remove two adjacent gauges, replace them with a single gauge and rearrange the five on the ring I can now measure from 1 to 21 thou inclusive in steps of 1 thou with these five gauges by again selecting a single gauge or combinations of adjacent gauges.

What are the thicknesses of the gauges and the order of arrangement on the ring in each case? (start with gauge of unit thickness and then its thinner neighbour for the sets).

The puzzle is based on some interesting but relatively obscure mathematics, Perfect Difference Sets, described in A Theorem in Finite Projective Geometry and Some Applications to Number Theory, James Singer, Transactions of the American Mathematical Society Vol. 43, No. 3 (May, 1938), pp. 377-385, but initially analysed by the splendidly titled Rev. Thomas P. Kirkman, A.M., F.R.S., Rector of Croft with Southworth, and Honorary Member of the Literary and Philosophical Society of Manchester, in a paper entitled On the Perfect r-Partitions of $r^2-r+1$, Transactions of the Historical Society of Lancashire and Cheshire, vol 9 (1857), pp 127-142.

The puzzle is slightly contrived, as in reality feeler gauges allow non-adjacent gauges to be combined. The restriction of using only adjacent gauges makes the puzzle equivalent to finding Perfect Difference Sets of length 5 and 6.

Perfect Difference Sets

A Perfect Difference Set (PDS)  is a set of $k+1$ residues ${a_1,...,a_{k+1}}$ modulo $n=k^2+k+1$ such that every nonzero residue can be uniquely expressed in the form $a_i - a_j$

For example, the set {0,1,4,6} is a perfect difference set for $n=3^2+3+1=13$.

A PDS can also be expressed as the sequence of gaps between successive numbers in the sorted PDS with $n=k^2+k+1$ added to the set. For the PDS {0,1,4,6} the sequence of gaps is 1,3,2,7. If the sequence is wrapped round (as in feeler gauges on a ring), sums of adjacent numbers produce all the numbers from 1 to 13. These sequences will be referred to as magic circles.

Magic Circles

The article Magic Circles, David A. James, Mathematics Magazine, Vol. 54, No. 3 (May, 1981), pp. 122-125, describes a related puzzle, where Evariste Galois challenges 18 soldiers to arrange themselves around a circular pond with circumference 307 (=$17^2+17+1$) paces so that the number of paces between any two soldiers is unique. The soldiers would of course form a PDS to achieve this.

The article describes an algorithm to construct a PDS for $p^s+1$ numbers (prime p), using Galois fields (a.k.a. finite fields), and explains the mathematics behind the algorithm. The steps are:

1. Construct the Galois Field $GF(p^{3s})$, by finding an irreducible polynomial over GF(p) of degree $3s$.
   
   For s=1 this is straightforward, as a reducible polynomial of degree 3 always has a factor of degree one, so a polynomial $I(x)$ of degree 3 is irreducible if and only if $ I(x) \ne 0$ mod p for $x = 0,...,p-1$.
   
   For $s >  1$, finding an irreducible polynomial of degree 3s is more involved, so I cheated and pre-programed some that I obtained from the University of Victoria's Polynomial Generator
2. Find a generator, $g$ of the related cyclic group $GF^*(p^{3s})$.
   
   This is best done by making random guesses. I tested guesses by brute force, checking that $g^i  \ne 1$ for $1 \leq i \leq p^{3s}/2$. Typically a generator is found in one or two guesses.


3. Find elements of the subgroup $GF^*(p^s)$ in $GF^*(p^{3s})$
   
   These are the elements $g^i$ for values of $i$ that are multiples of $p^{2s}+p^s+1$ = $\frac{p^{3s}-1}{p^s-1}$
4. Find integers $i$ that satisfy $g^i - g \in GF^*(p^s)$ .
These integers, modulo $p^{2s}+p^s+1$ , together with zero, form a PDS for $p^s+1$

This algorithm will find a single PDS. Other PDS's of the same order can be found by multiplying this PDS by each number between 1 and $ p^{2s}+p^s+1$ that is coprime to $p^{2s}+p^s+1$.

Each PDS found can be be coverted to a magic circle, which can then be arranged to start with 1 followed by its smaller neighbour. Different PDS's can result in the same magic circle when this rearrangement is applied. For all the cases that I have tested, each magic circle is created by $3s$ different PDSs.

In fact, Golay, in Notes on the Representation of 1,2, ……, N by differences, J. London Math. Soc. (1972) s2-4 (4): 729-734, claims that there are $ \frac{\phi(p^{2s}+p^s+1)}{3s}$ magic circles.

Python Code

Python code is located in this folder. The folder contains:

finitefield.py -  implements Galois fields, representing polynomials $a_0+a_1x+...+a_nx^n$ by a python list $[a_0,a_1,...,a_n]$. The module contains procedures to multiply, divide, add, subtract polynomials modulo a prime and to multiply polynomials modulo an irreducible. The module also contains procedures to find an irreducible polynomial (for a limited range of $p^n$) and to find a generator of  $GF^*(p^n)$

magiccircles.py - implements the algorithm described above and uses the algorithm to solve the Sunday Times Teaser, and to generate magic circles for a range of values including $17^1+1 =18$, Evarise Galois' soldiers.  My algorithm eliminates reflections, producing $ \frac{\phi(p^{2s}+p^s+1)}{6s}$ magic circles.

Three angles

A puzzle recently posted in Enigmatic Code,  Enigma 1329: Height of ignorance, reminded me of a related puzzle:  For three squares laid side by side as shown in the diagram, prove that  α = β + γ

Clearly  α = 45⁰. The obvious approach is to use multiple angle formulae, but there is a more elegant geometrical solution.

Click here to see the geometrical solution
The solution of this puzzle can be used to solve Enigma 1329.

There is also a simple solution using complex numbers which consists of 17 symbols: 

$(3+i)(2+i) = 5(1+i)$

Does this count as a haiku?

Countdown Numbers Game

Several people have already written programs based on the Numbers Game from the TV program Countdown, but anyway here is another one, written in Python.

As has been noted elsewhere, a set of 2 large + 4 small or 1 large + 5 small typically covers a large proportion of  target numbers (101 to 999), and there are typically many ways of expressing each target using some or all of the 6 numbers.

These sets each cover all targets from 101 to 999. The lists of solutions () contain all targets from 0 until a gap above 999 is reached:

 5   6   7   8   9   75  (five consecutive numbers) 

 2   5   7   8   9   10  (six small numbers) 

 4   7   7   10   25  100  (a repeated number) 

 6   7   7   9   9  100  is perhaps more noteworthy,  covering every target number except the number 367 

 8   9   25   50   75  100  is the best set containing all four large numbers, covering 885 targets  


The code constructs solutions for a few games that have appeared on the TV show:

•  3   6   25   50   75  100 with a target of  952 , the James Martin 952 game, which has 2 solutions, (3×75×(6+100)-50)÷25 which was found by the contestant, and 25+(6×75×(3+100))÷50.
  
•  1   4   8   9   10   50  with a target of  500  ,possibly the easiset game ever?  for which my program finds 21 distinct solutions .
  
•  Some games solved by George Ford , one of the best countdown contestants.

Most of the complexity of the program is to do with minimising brackets,
e.g. (((((6)+(7))-(9))×(7))×(9))-(100)=(6+7-9)×7×9-100
and avoiding solutions that are essentially the same, e.g. 152=(6+7-9)×7×9-100=7×(7-9+6)×9-100.

The program also excludes "frivolous" solutions that contain an expression that equates to zero, e.g. 500 = (9-8-1)×4+50×100, solutions that involve multiplying or dividing by 1, e.g. 500 = (9-8)×50×100 or 500 = 50×100÷1 and solutions that have other redundancies, e.g. 500 = 9+10×50-1-8. 

# -*- coding: cp1252 -*-
from itertools import combinations

def wrap(t, condition=True):
    return ''.join(["(",t,")"]) if condition else t

def expressions( A, processed=set() ):
  """ initially, A is an array of numbers

   In recursive calls, A is an array of tuples (n,t,o,x,y,h) where
   n is a number,
   t is a text expression of n,
   o is the last operation applied to x,y to produce n = xoy
   h is the history of the expression, containing all the numbers produced in the construction
     of the expression
  """
  if type(A[0])==int: # inital call, so convert to array of tuples
    A = [ (A[i],str(A[i]),"",0,0, frozenset((A[i],)) ) for i in xrange(len(A))]
    processed=set()
  else: # recursive call, so return the expression formed in the parent
    n,t,o,x,y,h = A[0]
    if (n,t) not in processed:
      yield A[0]
      processed.add( (n,t) )

Contest Center

Due to a prolonged spell of wet weather in the UK, and the demise of New Scientist Enigma, I have recently turned my attention to the Contest Center, which has a lot of interesting maths puzzles.

I concentrated on problems that did not yet have any solvers, and managed to solve a few of them. (hints under plain cover to genuine puzzle enthusiasts only)

Point on Circumcircle (contributed by Fotos Fotiadis) 
 ABC is a triangle whose smallest angle is A. K is a point on the arc BC of the circumcircle. The perpendicular bisectors of AB and AC intersect the line AK at L and M, respectively. The lines BL and CM intersect at T. Prove that BT+CT=AK. 

Greatest Divisor (contributed by Paul Cleary) 
When n=8, the expression ab(aⁿ-bⁿ) is divisible by 30 for all positive integers a and b, and 30 is the greatest such divisor. Find a positive integer n such that the greatest common divisor of ab(aⁿ-bⁿ) for all positive integers a and b is n. 

26 Numbers (Contributed by Paul Cleary) 
There are infinitely many sets of 26 real numbers where their sum is 200 and the sum of their squares is S. The difference between the smallest and largest of the numbers in these sets is 60/13. What is the value of S? 

Sums of Polynomials 
Let p_i(x) = x²+m_ix+n_i for i=1,2,3,4 be four given polynomials with m_i and n_i integers, and m₁ through m₄ not all odd. Show that there is an integer N such that any integer n > N can be expressed as the sum p₁(a₁)+p₂(a₂)+p₃(a₃)+p₄(a₄) for some integers a₁ through a₄. 

Rational Powers (contributing the criterion gcd(a,b,c)=1)
 Let x be a rational number x=p/q with q>1 and gcd(p,q)=1. Let a, b and c be positive integers, with a^x+b^x=c^x and gcd(a,b,c)=1. Prove that a, b and c must be q-th powers, or find a counterexample. 


Repeated Digits  (not a first to solve, but most solutions found to date)
The square of 88 is 7744, where each digit of the square is repeated. Find additional squares (not ending with 0) where every digit is part of a repeated sequence, such as 11000555544. We will list the number of squares found by each solver. The notation +F indicates that the solver also found an infinite family of solutions. 

Update June 2014:
Square Heronian (contributed by Lee Morgenstern) 
A Heronian triangle has integer sides and integer area. Find a Heronian triangles where all 3 sides are squares. [Only one solution is known. Extra credit for anyone who finds a second solution.] 

Update September 2014:
** Square Rearranger 
Find the smallest three distinct whole numbers A, B and C such that you can rearrange the digits of A and B to get C², the digits of A and C to get B², and the digits of B and C to get A². [Leading zeroes are not allowed.] 

New Scientist Enigma 1354: Sound idea

     Here is a solution to Enigma 1354 which appeared recently in Enigmatic Code

The problem is this:

Joe’s daughter has been asking him for weeks to make a wind chime. So this week Joe cut a length of stainless steel tubing into 10 lengths from 1 cm to 10 cm in steps of 1 cm. He also cut out a disc from a sheet of stainless steel and drilled 10 evenly spaced holes round the perimeter and one in the centre.

Joe hung one tube from each hole and hung the disc up by a thread from its centre. That was a big mistake as the disc tilted right over.

So Joe rearranged the tubes until the disc balanced perfectly. In making a note of the lengths of the tubes in order round the disc the result was an 11-digit number.

What is the smallest of all the 11-digit numbers Joe could have written down?

In order for the wind chime to balance, moments about the axis af must balance

$ (b+e-g-j)sin(\frac{π}{5}) + (c+d-h-i)sin(\frac{2π}{5}) = 0 $ ..................... (1)

Noting that $sin( \frac{2π}{5}) = 2 sin(\frac{π}{5}) cos(\frac{π}{5})$ , dividing (1) through by $sin(\frac{π}{5})$

$ (b+e-g-j) +2 (c+d-h-i)cos(\frac{π}{5}) = 0 $ ..................... (2)

Substituting $ cos(\frac{π}{5}) = \frac{(1+\sqrt{5})}{4} $ into (2)

$ b+e-g-j +\frac{c+d-h-i}{2} +\frac{(c+d-h-i)\sqrt{5}}{2} = 0$

As a,b,...,i,j are all integers,$ c+d-h-i = 0$ and $b+e-g-j +\frac{c+d-h-i}{2}     =0$

So $c+d=h+i$ and $b+e=g+j$

So knowing five adjacent values, say, a,b,c,d,e, allows the other five to be deduced:

$f = 55 - a - (b+c+d+e) - (g+h+i+j) = 55-a-2(b+c+d+e)$

And so on round the circle.

So, some code:

from itertools import permutations as perm

a=10
onetoten=frozenset(range(1,11))

for b,c,d,e in perm(range(1,10),4):
  f=55-a-2*(b+c+d+e)
  g=55-b-2*(c+d+e+f)
  h=55-c-2*(d+e+f+g)
  i=55-d-2*(e+f+g+h)
  j=55-e-2*(f+g+h+i)

  s=(a,b,c,d,e,f,g,h,i,j)
  if set(s)==onetoten:

    # sanity check
    if all( sum(s[i%10] for i in xrange(m,m+4))
            ==sum(s[i%10] for i in xrange(m+5,m+9))
            for m in xrange(10)):
      print "solution", a,b,c,d,e,f,g,h,i,j
      break