Sunday, July 23, 2017

Gary Cipolloni's Clock Puzzle

Gary Cipolloni, my computing teacher in eleventh or twelfth grade, was charismatic, and subtly counter-cultural. Equally comfortable in leather motorcycle gear or the polyester professional-wear of the time, Mr. C. would flit around the lab telling jokes and shelling pistachios, the snack he never stopped eating. The story people told was that in his student days, he'd broken new administrative ground at the University of Michigan's Dearborn campus by using FORTRAN to fulfill the foreign language requirement. (I doubt it.) I learned a great deal from him.

Mr. C. assigned us projects, but often he merely suggested them. One idea he floated was that the class might determine which of the little LED bars in a digital clock stayed lit the longest during a twelve-hour period. I don't think any of us ever found the answer.

I did try the clock LED problem, not in the PASCAL language we were studying in class, but using a BASIC program on my Commodore 128 at home. The 128 was a fantastic machine for its time, and it was a major upgrade from my old Commodore 64—itself practically a Cray compared to the machine I had started on, which was the revolutionary VIC-20.

BEHOLD! The VIC-20. Image from the VIC-20 article on Wikipedia. 

God, the hours I spent on that VIC-20! The machine had 3k of RAM. Until we added a tape drive the following year, whatever program I was writing would be permanently erased as soon as the computer was turned off. So I used to write down my programs in a notebook, and that way if I wanted to run an old program again, I just typed it line by line from the notebook. A couple of years later, I upgraded to the Commodore 64. Then came the Commodore 128, with a much more powerful BASIC language.

I don't remember the answer my program gave to the clock LED problem, but whatever it was, it was probably wrong. Not that the problem is especially hard, just that I remember that I wrote an overly complicated program to solve it and likely ended up with garbage as output.

Over the years I've often thought about Mr. C. and his clock puzzle. Finally this weekend I wrote a little program in Mathematica to solve the problem. The results are below, but first here is how to solve the problem without using a computer.

***

The clock design I worked with looks like this (these are home-made images):




Here are all the digits:


The clock display is of the form AB:CD:EF, where A stands for the hours tens-digit, B the hours ones-digit, C the minute tens-digit, D the minute ones-digit, E the seconds tens-digit, and F the seconds ones-digit. In each digit's place, there are seven LED bars, each turned on or off to form a specific digit. I number the seven LED positions from top to bottom, left to right, as follows:


So, some good quantities to calculate would be A1, …, A7, B1, …, B7, …, F7—where C4, for example, is the total number of seconds when the middle LED in the minutes tens-digit will be lit during the period from 12:00:00 to 11:59:59.

Here are a few examples of calculating these quantities:


  • C4. During the entire twelve-hour period, the minutes tens-digit will cycle a whole number of times through the values 0, 1, 2, 3, 4, 5, so that each digit gets an equal share of the time. Now when 0 and 1 are showing, the middle LED is dark; when 2, 3, 4, and 5 are showing, the middle LED is lit. So the middle LED is lit 4/6 = 2/3 of the time. We can write C4 = 2/3T, where T is twelve hours.

  • C5. When 1, 3, 4, and 5 are showing, the lower-left LED is dark; when 0 and 2 are showing, the lower-left LED is lit. So the lower-left LED is lit 2/6 = 1/3 of the time. Thus C5 = 1/3T.

  • B7. During the twelve-hour period, the hours ones-digit will progress through the values 2, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1. When 1, 4, 7 and 9 are showing, the bottom LED is dark; when 0, 2, 3, 5, 6, and 8 are showing, the bottom LED is lit. So the bottom LED is lit 7/12 of the time. Thus B7 = 7/12T.

  • A3. During the twelve-hour period, the hours tens-digit will show a 1 for three hours and will be blank for nine hours. When the digit is blank, the upper-right LED is dark; when 1 is showing, the upper-right LED is lit. So the upper-right LED is lit 3/12 = 1/4 of the time. Thus A3 = 1/4T.


A shortcut: once you calculate the Ei and Fi values, you've also calculated the Ci and Di values. The same events happen in the seconds display and the minutes display, and each event in the seconds display happens sixty times as often as its corresponding event in the minutes display, but it only lasts for a sixtieth of the time. So the aggregate time for a given event is the same in the seconds display as in the minutes display.

The largest fraction turns out to be 9/10, for D6 and F6. The final answer is therefore a tie between the lower-right LED in the seconds ones-digit and the lower-right LED in the minutes ones-digit, both of which are lit 90% of the time. The next-closest fraction is 5/6, which occurs for six different LEDs.

***

Here is the computer output, shown several ways.

The fractions:

A: 0, 0, 1/4, 0, 0, 1/4, 0
B: 2/3, 1/2, 5/6, 2/3, 5/12, 5/6, 7/12
C: 2/3, 1/2, 5/6, 2/3, 1/3, 5/6, 2/3
D: 7/10, 3/5, 4/5, 7/10, 2/5, 9/10, 3/5
E: 2/3, 1/2, 5/6, 2/3, 1/3, 5/6, 2/3
F: 7/10, 3/5, 4/5, 7/10, 2/5, 9/10, 3/5

A heat map. Pure blue corresponds to never being lit, and pure red corresponds to always being lit:


A 3-D plot, where the height of each prism corresponds to the total time the LED is lit:


Coding has changed a lot since my high school days. The old acronyms are no more, and the tools are vastly more powerful; but many of the principles I learned as a kid are still relevant. Thanks Mr. C. for all you taught me.

Friday, July 21, 2017

A Syllable Word Game

I made up a word game just to illustrate how my syllable-counting algorithm gets used.

In each puzzle below, strike a letter to create a new word. Repeat for the indicated number of times. Constraint: every time you strike a letter, the new word has to have the same number of syllables as the old word.

Example:

   DULLY → DULY is allowed, but DULLY → DULL is not.


1. CLOVEN  →  ________  →  ________

2. ATRIAL  →  ________  →  ________

3. WAIVERS  →  ________  →  ________  →  ________

I found the three words cloven, atrial, and waivers by writing a computer program that used the syllable-counting function to help identify potentially interesting cases.

By the way, here is a simpler syllabification algorithm that I saw online.
  • Count the number of vowels in the word.
  • Do not count double-vowels ("rain" has 2 vowels but is only 1 syllable)
  • If last letter in word is vowel do not count ("side" is 1 syllable)
These instructions aren't 100% clear, but I implemented a version of this and compared it to the algorithm I've been using. It's not as good. Words in red are the 3 cases where my algorithm fails and the new one succeeds. Words in green are the 21 cases where my algorithm succeeds and the new one fails; 7 of these have an asterisk that is explained below. Words in blue are the 4 cases where both algorithms fail.

PYRAMIDALLY 5 4*
MISERICORDS 4 4
THYROXINS 3 3
PLICATION 3 3
PERTINACIOUS 5 4
LEAL 1 1
LYCOPOD 3 3
FRIPPERIES 3 3
INTERDEPENDENCY 6 5*
RITORNELLOS 4 4
PRESSORS 2 2
TINNY 2 1*
POOFTER 2 2
PETTLED 2 2
BACKPEDALLING 4 4
CHERRYLIKE 3 3
INTERCONVERT 4 4
VILLEIN 2 2
STALEST 2 2
PREVISION 3 3
TERRITORIALITY 7 5
ALKYLS 2 2
WAMBLED 2 2
TRILINGUAL 3 3
MONKSHOOD 2 2
UNSCREWED 2 3
SCOTIAS 3 2
SYMPHONY 3 2*
DREADFULS 2 2
FOCALIZATION 5 5
CONTRARIETY 4 3
HABERDASHER 4 4
UNCURIOUS 4 3
UNSWORE 2 2
MULTIVOLUME 4 4
CHEF 1 1
PITH 1 1
PENTAMIDINE 4 4
VISITATIONS 4 4
STEEPEN 2 2
SYNCOPATING 4 4
INTRIGANTS 3 3
SCANDIAS 3 2
BREGMATE 2 2
INACTIVATION 5 5
UNDERUTILIZES 6 6
FLOC 1 1
TUBAE 2 1
UNSYSTEMATIZED 5 6
HELLENIZE 3 3
VEXT 1 1
MUDSLINGERS 3 3
PHILANTHROPISTS 4 4
TALLISH 2 2
DOWNER 2 2
HODAD 2 2
OCHERS 2 2
ENFOLDING 3 3
CATWALKS 2 2
RAMPANT 2 2
PREORDAINMENT 4 3
TROUSSEAU 2 1
GRAVIDA 3 2
POLYWATER 4 4
INSUFFLATOR 4 4
MODERATENESSES 6 6
OUTCROWING 3 3
ACCOUCHEMENTS 4 4
UNDERDOGS 3 3
BRAIZE 1 1
VICEROYSHIP 4 4
CACHEXIAS 4 3
CUDDLIER 3 2
ASSIGNOR 3 3
SUEDED 2 2
TACTILITIES 4 4
SPHENOIDS 2 2
BANKROLLERS 3 3
OCTANTS 2 2
ANNUNCIATORY 6 4
BLACKLEAD 2 2
TITLEHOLDERS 4 4
REPRESSOR 3 3
RECKONERS 3 3
FAVOURS 2 2
OSAR 2 2
EDUCATION 4 4
UNCREATES 2 3
MEASURABILITIES 6 6
AROUSERS 3 3
DISASSEMBLY 4 3*
LICHEE 2 1
MOTIVATOR 4 4
CONCEDEDLY 4 3*
VELLUM 2 2
MERCHANDIZE 3 3
CONCOURSES 3 3
PHILISTIA 4 2
COUNTERINSURGENCY 6 5*
DUMBWAITERS 3 3


The new algorithm has lots of problems with a final Y…maybe the person forgot to specify an exception to rule (3) when the end vowel is Y. Doing that would repair the 7 cases with an asterisk.

Here is the comparison with the list of 34 more peculiar cases:

AIDE 1 1
IDEA 3 1
IDEAS 2 2
IDEE 2 1
IDE 1 1
AIDA 2 1
PROUSTIAN 3 2
CHRISTIAN 3 2
CLICHE 1 1
HALIDE 2 2
TELEPHONE 3 3
TELEPHONY 4 3*
DUE 1 0
IDEAL 2 2
DEE 1 0
UREA 3 1
VACUO 3 1
SEANCE 1 1
SAILED 1 2
RIBBED 1 2
MOPED 1 2
BLESSED 1 2
AGED 1 2
TOTED 2 2
WARRED 1 2
UNDERFED 2 3
JADED 2 2
INBRED 2 2
BRED 1 1
RED 1 1
STATES 1 2
TASTES 1 2
TESTES 1 2
UTILIZES 4 4

There are some inevitable flip-flops here…for example, if a simple algorithm get testes right, then it's going to get tastes wrong, and conversely. Likewise for Proustian/Christian. But altogether there's a lot more green than red, even after fixing the asterisk cases.

Thursday, July 20, 2017

An Algorithm For Counting Syllables

A while ago I was talking to a friend who works for a startup company doing natural-language processing. At some point we got to talking about syllabification, and I mentioned a syllable-counting algorithm I'd made ten years ago. He seemed to think that there weren't many such things floating around, so I thought I'd post the algorithm here. It's kind of interesting even if you aren't in the syllable-counting industry.

The algorithm is described below. The code is also included. Given a word as a string of A–Z letters, the algorithm returns a number which is likely to be the number of syllables in the word. The algorithm doesn't tell you where the syllable breaks should be; it just guesses how many syllables there are.

How good is the algorithm? I don't have much data on that, but it seems to work well enough for my purposes (making word games). The algorithm gets 93 of the following 100 words correct:

PYRAMIDALLY 5
MISERICORDS 4
THYROXINS 3
PLICATION 3
PERTINACIOUS 5
LEAL 1
LYCOPOD 3
FRIPPERIES 3
INTERDEPENDENCY 6
RITORNELLOS 4
PRESSORS 2
TINNY 2
POOFTER 2
PETTLED 2
BACKPEDALLING 4
CHERRYLIKE 3
INTERCONVERT 4
VILLEIN 2
STALEST 2
PREVISION 3
TERRITORIALITY 7
ALKYLS 2
WAMBLED 2
TRILINGUAL 3
MONKSHOOD 2
UNSCREWED 2
SCOTIAS 3
SYMPHONY 3
DREADFULS 2
FOCALIZATION 5
CONTRARIETY 4
HABERDASHER 4
UNCURIOUS 4
UNSWORE 2
MULTIVOLUME 4
CHEF 1
PITH 1
PENTAMIDINE 4
VISITATIONS 4
STEEPEN 2
SYNCOPATING 4
INTRIGANTS 3
SCANDIAS 3
BREGMATE 2
INACTIVATION 5
UNDERUTILIZES 6
FLOC 1
TUBAE 2
UNSYSTEMATIZED 5
HELLENIZE 3
VEXT 1
MUDSLINGERS 3
PHILANTHROPISTS 4
TALLISH 2
DOWNER 2
HODAD 2
OCHERS 2
ENFOLDING 3
CATWALKS 2
RAMPANT 2
PREORDAINMENT 4
TROUSSEAU 2
GRAVIDA 3
POLYWATER 4
INSUFFLATOR 4
MODERATENESSES 6
OUTCROWING 3
ACCOUCHEMENTS 4
UNDERDOGS 3
BRAIZE 1
VICEROYSHIP 4
CACHEXIAS 4
CUDDLIER 3
ASSIGNOR 3
SUEDED 2
TACTILITIES 4
SPHENOIDS 2
BANKROLLERS 3
OCTANTS 2
ANNUNCIATORY 6
BLACKLEAD 2
TITLEHOLDERS 4
REPRESSOR 3
RECKONERS 3
FAVOURS 2
OSAR 2
EDUCATION 4
UNCREATES 2
MEASURABILITIES 6
AROUSERS 3
DISASSEMBLY 4
LICHEE 2
MOTIVATOR 4
CONCEDEDLY 4
VELLUM 2
MERCHANDIZE 3
CONCOURSES 3
PHILISTIA 4
COUNTERINSURGENCY6
DUMBWAITERS 3

Here are 34 words that I used while developing the algorithm—they are tricky cases or else illustrate some of the exceptions being handled. The algorithm gets 27 of them correct.

AIDE 1
IDEA 3
IDEAS 2
IDEE 2
IDE 1
AIDA 2
PROUSTIAN 3
CHRISTIAN 3
CLICHE 1
HALIDE 2
TELEPHONE 3
TELEPHONY 4
DUE 1
IDEAL 2
DEE 1
UREA 3
VACUO 3
SEANCE 1
SAILED 1
RIBBED 1
MOPED 1
BLESSED 1
AGED 1
TOTED 2
WARRED 1
UNDERFED 2
JADED 2
INBRED 2
BRED 1
RED 1
STATES 1
TASTES 1
TESTES 1
UTILIZES 4

Some of the failures are interesting, because when you see the number of syllables assigned by the computer, you get a sense of how the computer is "misreading" the words. For example, cliché gets one syllable, so from the point of view of the algorithm, it is as if CLEE-SHAY were being read as CLEESH. (My dictionary doesn't include diacritic marks.) Some of the mispronunciations aren't far off the mark, in terms of patterns of pronunciation in English: testes gets one syllable, as if it were pronounced analogously to tastespertinacious gets 5 syllables, as if it were pronounced PER-TIN-A-SEE-US.

I'm surprised to see that the algorithm gets idea right but ideas wrong. I remember that an early version of the algorithm dropped terminal S's before applying the logic, but maybe that rule was worse, on balance. Clearly the algorithm could be improved in any number of ways, for example by adding more exception handling.

***

Here is the description from the comments to the code:

(*

Algorithm for counting syllables.


If the word has no consonants, then the number of syllables is the number of distinct letters in the word. Otherwise:

We count the 'leading' syllables by advancing through the word from left to right, examining pairs of consecutive letters.  If the pair is (vowel)(consonant), then we increment the syllable count by 1. Otherwise, we do nothing.

We next add syllables for each appearance of the vowel combination IA (as in EDITORIAL)

We next add syllables for each appearance of the vowel combination EO (as in PREORDAINED)

We add a syllable if the word ends in -IOUS or -IER

We next correct unwanted syllabification of (consonant+ED) endings.  We would be satisfied with giving certain ED endings their own syllable (BLESSED), but we don't want all ED endings to get a syllable.  The rule adopted here is that we deduct a syllable for an ED ending unless the prior letter is D, T, or ((consonant other than R)+R) or (consonant+L).

We next correct unwanted syllabification of ES endings.  The rule adopted here is that we deduct a syllable for an ES ending unless the prior letter is C, G, X, S, Z, or (consonant+L).

We now add 'final' syllables if necessary.  If the last letter is a consonant, or if the second-last letter is a consonant and the last letter is an E, then there are no final syllables. Otherwise, if the final string of 1 or more vowels matches one of a specified set of disyllabic pairs, then there are two final syllables; otherwise, there is one final syllable.

Finally, if the syllable count is less than 1, set the syllable count to 1.

The disyllabic combinations are specified to be EA,II,IO,UA,UO. (We don't have to include IA and EO because they have been handled above.)

*)

***

Here is a Mathematica implementation. It's ugly, in part because it's from ten years ago but mostly because I tend to code a project like this just about as fast as I can type, not worrying about planning or elegance.

Alphabet={"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"};

Vowels={"A","E","I","O","U","Y"};

Consonants=Complement[Alphabet,Vowels];

VowelPositionTFList[LetterListArg_]:=
Table[
MemberQ[Vowels,LetterListArg[[k]]],
{k,1,Length[LetterListArg]}];

ConsonantPositionTFList[LetterListArg_]:=
Map[Not,VowelPositionTFList[LetterListArg]];

LastConsonantPosition[LetterListArg_]:=
Max[
Position[
ConsonantPositionTFList[LetterListArg],
True
]
];

CountVowels[LetterListArg_]:=
Count[
VowelPositionTFList[LetterListArg],
True
];

DisyllabicVowelPairs={{"E","A"},(* {"E","O"}, {"I","A"},*) {"I","I"},{"I","O"},{"U","A"},{"U","O"}};

CountSyllables[WordArg_]:=
{
CharacterList=Characters[WordArg];
NCharacters=Length[CharacterList];
If[
CountVowels[CharacterList]==NCharacters,
Length[Union[CharacterList]],
RawSyllableCount=0;
Do[
TempCharacter1=CharacterList[[LetterIndex]];
TempCharacter2=CharacterList[[LetterIndex+1]];
If[MemberQ[Vowels,TempCharacter1]&&MemberQ[Consonants,TempCharacter2],
RawSyllableCount=RawSyllableCount+1
],
{LetterIndex,1,NCharacters-1}];
CurrentSyllableCount=RawSyllableCount;
CurrentSyllableCount=CurrentSyllableCount+Length[StringPosition[WordArg,"IA"]];
CurrentSyllableCount=CurrentSyllableCount+Length[StringPosition[WordArg,"EO"]];
If[
NCharacters>4&&StringTake[WordArg,-4]=="IOUS",
CurrentSyllableCount=CurrentSyllableCount+1
];
If[
NCharacters>3&&StringTake[WordArg,-3]=="IER",
CurrentSyllableCount=CurrentSyllableCount+1
];
If[
NCharacters>2&&CharacterList[[-1]]=="D"&&CharacterList[[-2]]=="E"&&MemberQ[Consonants,CharacterList[[-3]]],
EDCorrection=-1;
If[
MemberQ[{"D","T"},CharacterList[[-3]]],
EDCorrection=0,
If[
((NCharacters>3)&&CharacterList[[-3]]=="R"&&CharacterList[[-4]]!="R")||((NCharacters>3)&&CharacterList[[-3]]=="L"&&MemberQ[Consonants,CharacterList[[-4]]]),
EDCorrection=0
]
],
EDCorrection=0
];
CurrentSyllableCount=CurrentSyllableCount+EDCorrection;
If[
NCharacters>2&&CharacterList[[-1]]=="S"&&CharacterList[[-2]]=="E"&&MemberQ[Consonants,CharacterList[[-3]]],
ESCorrection=-1;
If[
MemberQ[{"C","G","X","S","Z"},CharacterList[[-3]]],
ESCorrection=0,
If[
((NCharacters>3)&&CharacterList[[-3]]=="L"&&MemberQ[Consonants,CharacterList[[-4]]]),
ESCorrection=0
]
],
ESCorrection=0
];
CurrentSyllableCount=CurrentSyllableCount+ESCorrection;
TempPosition=LastConsonantPosition[CharacterList];
If[
(TempPosition==NCharacters)||((TempPosition==NCharacters-1)&&(CharacterList[[-1]]=="E")),
FinalSyllableCount=0,
VowelChunk=Take[CharacterList,{TempPosition+1,NCharacters}];
FinalSyllableCount=
If[
MemberQ[DisyllabicVowelPairs,VowelChunk],
2,
1
]
];
CurrentSyllableCount=CurrentSyllableCount+FinalSyllableCount;
Max[CurrentSyllableCount,1]
]
}[[1]];

Wednesday, July 19, 2017

A Table in D'Arcy Thompson's "On Growth and Form" Has Some Inconsistencies

I was dipping into my 1992 edition of On Growth and Form, D'Arcy Thompson's magnum opus of mathematical biology, and I found some inconsistencies in one of the tables. These inconsistencies don't appear to be logged anywhere else, so I thought I'd note them here. They were present in the very first edition, published in 1917, and they're still in the newest edition, which was published in 2014.

Here is how the table looked in the 1917 edition, which is available online.


The point of the table is that the listed animals bear the majority of their weight on their front feet, not their hind feet. Weights are given in units of "cwt," which stands for "hundredweight." Unless I'm misunderstanding the data, the first three rows of the table all have inconsistencies. I don't see any inconsistencies in the last two rows.

First row (Bactrian camel)

The table says that a Bactrian camel puts 9.25 cwts on its fore-feet and 4.5 cwts on its hind-feet. One inconsistency I see is that 9.25 + 4.5 = 13.75, yet the table gives the gross weight of the camel as 14.25 cwts, not 13.75 cwts. The weight on the fore-feet plus the weight on the hind-feet should equal the gross weight.

The stated percentages, 67.3 and 32.7, have essentially the same ratio as the stated parts, 9.25 cwts and 4.5 cwts; but the parts don't agree with the whole.

Changing the gross weight from 14.25 cwts to 13.75 cwts would make the row self-consistent.

Second row (llama)

The inconsistency in the second row is of the same kind as the inconsistency in the first row. The table says that a llama puts 1.75 cwts on its fore-feet and 0.875 cwts on its hind-feet. Although 1.75 + 0.875 = 2.625, the table gives the gross weight of the llama as 2.75 cwts.

The stated percentages, 66.7 and 33.3, have the same ratio as the stated parts, 1.75 cwts and 0.875 cwts; but the parts don't agree with the whole.

Changing the gross weight from 2.75 cwts to 2.625 cwts would make the row self-consistent.

Third row (Indian elephant)

The inconsistency in the third row is of the same kind as the inconsistency in the first two rows. The table says that the elephant puts 20.5 cwts on its fore-feet and 14.75 cwts on its hind-feet. Although 20.5 + 14.75 = 35.25, the table gives the gross weight of the elephant as 35.75 cwts. (One ton = 20 hundredweight in this system.)

The stated percentages, 58.2 and 41.8, have essentially the same ratio as the stated parts, 20.5 cwts and 14.75 cwts; but the parts don't agree with the whole.

Changing the gross weight from 1 ton and 15.75 cwts to 1 ton and 15.25 cwts would make the row self-consistent. 

***

The inconsistencies are still being printed. Here is what the table looks like in the 2014 edition, according to a snippet from Google Books:


The data are unchanged from the 1917 edition. (This is also what my 1992 edition has.)

***

On Growth and Form celebrates its centenary this year, with events in science and the arts being held all over the globe. It was a landmark work—Stephen Jay Gould called it "one of the great lights of science (and of English prose)." The book will be read (or at least dipped into) for another hundred years…maybe in a future edition somebody will add a footnote to the table.

Sunday, July 16, 2017

Best-Fit Line To A Regular Polygon

In real life, the (x, y) points of a data set will never form a perfect polygon in the coordinate plane…but once that fanciful thought occurs to you, you can't help wondering what the best-fit line would look like.

So, imagine that the n data points (x1, y1), … (xn, yn) form the n vertices of a regular n-gon. Then the best-fit line turns out to be easy to describe:


  • The best-fit line will pass through the center of the regular n-gon. This is because the coordinates of the center point can be found by averaging the data values—and the best-fit line always passes through the point whose coordinates are the averages of the data values.



  • For any number of vertices, and for any location of the center, and for any orientation of the n-gon, the slope of the best-fit line will be zero.


To illustrate this, I made an animation with 7 data points. In the first phase of the animation, the data points are moving around chaotically. Over time, they coalesce into the form of a regular 7-gon. Then the 7-gon rotates for a while. After that, the animation simply reverses: the 7-gon begins to rotate in the opposite direction, and then the points chaotically drift apart. For each frame of the animation, a best-fit line to the 7 data points is shown. You'll see that whenever the points form a 7-gon, the best-fit line is horizontal.


There's no cheating here—for each frame of the animation, the computer calculates the best-fit line based on where the data points are. It would have made for a nicer animation if I had also imparted an overall motion to the center of the heptagon…maybe some other time. I didn't go the trouble because the location of the center doesn't actually affect the slope. The slope of a best-fit line is invariant under an overall translation of the data.

How does the math work out? Here is one view of the problem. The image below shows 7 data points that form a heptagon. A candidate best-fit line through the center is shown. The total squared error will be the sum of the squared lengths of the vertical segments.


The winning candidate however is the horizontal line through the center:


This is fine I guess, but to my eye it isn't obvious that the total squared-error of the horizontal line is best. I don't have an insightful argument for why, in the case of n points equally spaced around a circle, the total distance-squared to a line through the center is minimized by making the line horizontal. What I'll give instead is a calculation leading to that conclusion.

Let the n-gon be inscribed in a circle with radius R and center (hx, hy). Then the vertices of the n-gon will have coordinates

(hx + R cos(θ + 2πk/n), hy + R sin(θ + 2πk/n))

for k = 0, … n − 1. The parameter θ allows for different orientations of the n-gon.

The total distance-squared to a line of slope m that passes through (hx, hy) can be calculated as a function E(m), quadratic in the variable m. (The parameters hx and hy drop out, as expected.) Minimizing E leads to the optimum value for m, expressed as a ratio of sums:
\[m_{\rm best} = \frac{\sum_0^{n-1}{\cos\lambda_k\sin\lambda_k}}{\sum_0^{n-1}{\cos^2\lambda_k}}\]
where \(\lambda_k \equiv \theta + \frac{2\pi k}{n}\). The vanishing of the slope amounts to the proposition that the n-gon's horizontal and vertical coordinates have zero correlation.

A straightforward evaluation of the sum in the numerator shows that it vanishes:
\[m_{\rm best} \propto \sum_0^{n-1}{\cos\lambda_k\sin\lambda_k}\]
\[ m_{\rm best} \propto  \sum_0^{n-1}{\sin 2\lambda_k}\,.\]
It should be possible to see intuitively why that sum vanishes, but let's keep going to the end:
\[ m_{\rm best} \propto  \sum_0^{n-1}{\left(e^{2i\lambda_k}-e^{-2i\lambda_k}\right)}\]
\[ = e^{2i\theta}\sum_0^{n-1}{e^{\frac{4\pi i k}{n}}} +  e^{-2i\theta}\sum_0^{n-1}{e^{\frac{-4\pi i k}{n}}}\]
\[ = e^{2i\theta}\cdot \frac{1-(e^{4\pi i/n})^n}{1-e^{4\pi i/n}} +  e^{-2i\theta}\cdot \frac{1-(e^{-4\pi i/n})^n}{1-e^{-4\pi i/n}}\]
\[ = e^{2i\theta}\cdot \frac{1-1}{1-e^{4\pi i/n}} +  e^{-2i\theta}\cdot \frac{1-1}{1-e^{-4\pi i/n}}\]
\[ = 0\,.\]
So mbest = 0 and the best-fit line to a polygon is always horizontal. If you have an explanation that's more insightful than mechanically summing a finite series of complex exponentials, please pass it along!

Tuesday, July 4, 2017

Newton's Problem of the Oxen in the Pasture

The Arithmetica Universalis of 1707 reproduces a set of lecture notes by Isaac Newton from the period 1669–1702 when Newton was Lucasian Professor of Mathematics at Cambridge. In 1720 there appeared an English translation, called Universal Arithmetick, which underwent various further editions, including one in 1769. On page 191 of the 1769 edition, the following difficult problem appears:


If 12 Oxen eat up 3-1/3 Acres of Pasture in 4 Weeks, and 21 Oxen eat up ten Acres of like Pasture in 9 Weeks; to find how many Oxen will eat up 24 Acres in 18 Weeks?
A version of the problem later appeared (with a disastrous typographical error) as the final challenge in Frederick Emerson's North American Arithmetic, Part Third, For Advanced Scholars (1834). The typographical error was the use of the value 3-1/2 in place of the original 3-1/3; this alteration causes the solution for the number of oxen to take a bizarre fractional value. Perhaps in part because of this twist, the problem "became famous overnight in the United States," according to Steven L. Jordan's article in Historia Mathematica (vol. 8, 1981, 145–160).

In 1835, the National Teachers' Association turned the problem into a contest, with a prize of $50 offered for the most lucid solution. Only 48 of 112 entries provided the correct answer. The prize was awarded to Mr. James Robinson, principal of the Department of Arithmetic at Bowdoin School, Boston. (His solution can be read in Ken Clements and Nerida Ellerton's account, which situates the Pasturage Problem in a larger discussion about mathematical elegance.)

The trend in the 1800s of posing difficult problems to schoolchildren was heavily criticized in 1890 by the great American historian Florian Cajori (1859–1930). (Cajori was a translator of Newton's Principia, and Cajori also wrote what must be the most abstruse book in my personal library, A History of the Logarithmic Slide Rule). In The Teaching and History of Mathematics in the United States, Cajori wrote

Think of it! Out of 112 of, presumably, the best arithmeticians in the country, only 48 got correct results; and yet this problem was intended to be solved by boys and girls. 

Clements and Ellerton however believe that the problem was fair, since it was the last problem in the last volume, intended for Advanced Scholars.

In any case, it's a hard problem. And beware, the text in the 1720 edition reads differently: "to find how many Oxen will eat up 36 Acres in 18 Weeks." (Compare the previous, "to find how many Oxen will eat up 24 Acres in 18 Weeks.") I don't know if this is a typographical error or an intentionally different version of the problem.

***

I found the Universal Arithmetick strange. The book explains basic problems like 2099.6 ÷ 72.4, yet it also treats advanced problems of analysis using clever methods that were probably discovered by Newton himself. I wondered what kind of reader such a book was meant for. Could it be that Newton was forced to teach students with a range of mathematical knowledge? Or was this actually Newton's idea of a coherent course?

Newton's pedagogical method in the book is to take up different problem types in turn. He explains the general idea of the type, then he derives a formula that applies to any problem of the given type. To answer any particular version of the problem, just plug values into the formula. Here's an example of the approach:


Having worked out the reasoning once, Newton doesn't bother doing it again; the "reason" this problem has the answer 24 is that "if 8 be substituted for d, 15 for c, 405 for a, and 9 for b, the Number ad/bc will become 405 × 8 / 9 × 15, that is, 3240/135, or 24." Newton did however break his routine for the Pasturage Problem. After plugging numbers into the complicated general formula for such problems, Newton recapitulated the general reasoning in the specific context of the problem at hand.

All that said, in interpreting this book I don't think we should go very far in attributing authorial intent to Newton. The Arithmetic Universalis was published by his successor, William Whiston, and apparently Newton wasn't happy about that. Whiston claimed to have permission from Newton to publish the book, but it is also said that Newton tried to buy up all of the printed copies. I don't even know for sure that Newton wrote passages like this one, where we learn something of the "progressions" thinking behind the book:



(First the pupil learns formal manipulation, then he learns how to model in context.)

In any case, Newton's solution to the Pasturage Problem can be most easily found in this 1876 article by Alexander Evans (The Analyst, vol. 3, no. 3, 75–78), where the history of the problem is discussed. My own solution in a contemporary physicist's style is here.

Sunday, July 2, 2017

The Maniacal Clock-Maker

No longer merely whimsical, the clock-maker has fashioned all three hands of his clock to be the same len—

OK, I'm going to have to stop him right there, because trying to read a clock with three equal-length hands turns out to be not much fun. Furthermore, unless I'm mistaken there are no times when such a clock display is ambiguous (more on this below). The best I could do was find some near-miss times, perhaps the nicest example being this one:


In this image, a clock with white hands has been overlaid atop one with gray hands. As you can see, the overlap is very close. And it's not because the two times are correspondingly close; the times being shown by the two clocks are about thirteen minutes and forty-five seconds apart. Here are the two times displayed in the usual way:


(I added hash marks! I also went back and added hash marks to item (d) in the previous post and all four items in the post before that.)

The left clock shows fifteen minutes and 101,085,300/970,394,113 seconds past noon, while the right clock shows one minute and 15 1,943,925/970,394,113 seconds past noon. To a close approximation, the hands on the right-hand clock have been permuted in relation to the hands on the left-hand clock by (H → M, M → S, S → H).

I found this case and several others by generalizing the approach in the previous post. We seek two distinct times x and y such that any of the following permutations obtains:

H(x) = H(y)
M(x) = S(y)
S(x) = M(y)


H(x) = M(y)
M(x) = H(y)
S(x) = S(y)


H(x) = M(y)
M(x) = S(y)
S(x) = H(y)


H(x) = S(y)
M(x) = H(y)
S(x) = M(y)


H(x) = S(y)
M(x) = M(y)
S(x) = H(y)

Before going any further, you see the problem: each of these systems consists of three equations in only two unknowns; such systems typically have no solution. It's possible to get lucky and I did check, but as expected there are no solutions to any of these systems, and hence no ambiguous times.

To look for near-miss times, I generalized the approach from last time by defining the variables

x = m + j/60 + Δx
y = n + k/60 + Δy

where m, n are in {0, 1, 2, …, 11} and j, k are in {0, 1, 2, …, 59}. These equations express x and y as amounts of time "past the minute." This led to five systems of three equations in the two unknowns Δx and Δy, with each system containing the integer parameters m, n, j, and k.

Because all the systems are inconsistent for all possible parameter values, I did the standard thing and found the times that come "closest" to solving the system, in a least-squares sense. (Linear algebra people: for each system Ax = b, I solved ATAx* = Ab.) That done, one sees that how "close" the solution looks depends a lot on the values of the parameters m, n, j, and k. Instead of sussing out the dependence, I did the cheaper thing and set up a simple objective function (the sum of the three handtip-to-handtip distances) and used the objective function to sort the half-million or so solutions. The result was a "best" pair of times for each permutation. The pair of times shown in the image above was the best pair of times for the permutation (H → M, M → S, S → H), that is, the best pair of times that emerged from analyzing the third system of equations listed above.