What day of the week was it?

Among the more esoteric forms of nerd-entertainment is the “day of the week” problem. Specifically, given a date from history, can you determine the day of the week on which it fell? For example, humans first landed on the moon on July 20, 1969, and unless you are old enough and have a great memory, you probably didn’t know that this was a Sunday. Of course you can always look it up somewhere (TimeAndDate.com is my personal favorite), but the challenge is to figure it out in your head.

In one extreme example, it’s said that the mathematician John H. Conway has a password-protection system on his computer that asks him to identify, in rapid succession, the days of the week for three randomly-generated dates. How does he (or anyone) do it?

Well, there are a few convenient and peculiar facts about our calendar that can help us do the math. First, there is a set of “reference dates” that all fall on the same day of the week every year. The first of these are 4/4, 6/6, 8/8, 10/10, and 12/12. For the odd-numbered months, we have some nice dates that also fall on the same day of the week as the first five: 5/9, 7/11, 9/5, and 11/7. (Check out this year’s calendar if you don’t believe me.) Notice that we don’t have any dates for January, February, or March. This is unfortunate, and is partly the result of having a leap day inserted every four years. But there are some ways around that problem. I use the dates 1/9 and 2/6, along with 3/0 (i.e., the last day of February) to do it. Be careful, though—we need to treat January and February of year x as technically being part of year x-1, but the 3/0 date as part of year x.

Thus, once you know the reference day (the day of the week on which all the reference dates will fall) for a given year, you can figure out the day of the week for any date that year by adding and subtracting weeks from a reference day. For example, July 20 is 7/20, which is 9 days after the date 7/11 (which was a Friday). So, 7/20 is one week and 2 days later, on a Sunday.

Next, we need to have a way of finding the reference day from a given year. As you might expect, that reference day moves each year, though this movement is complicated by that leap day every four years. An easy mnemonic is “12 years is but a day”. That is, if you move 12 years forward (say, from July 20 1969 to July 20 1981), the day of the week will move exactly one day forward (from Sunday to Monday). If you take into account that the day of the week skips one day forward in non-leap years and two days in leap years, you can determine the day of the week of a date in any different year. Of course, you can do all of this in reverse if you want to move backward in time.

And that’s it! We can now use the “reference day + “12 years is but a day” + “skip 1-2 days per year” rules to determine the day of the week for historical dates. For example, suppose we want to know what day of the week the stock market crashed in the U.S.—10/29/1929. Here are the steps:

  • The reference day for 2016 is Monday.
  • This means that 10/10/2016 is Monday, so that 10/29/2016 is 2 weeks and 5 days ahead—i.e., a Saturday.
  • Back up seven multiples of 12 from 2016 to 1932 (since 2016 – 7•12 = 1932), so the day of the week shifts 7 days back (to where you started)—still a Saturday.
  • Back up three more years, keeping in mind that you passed the leap day on Feb 29 1932, so you move back four days from Saturday—now on a Tuesday.
  • There you have it—Oct 29 1929 was a Tuesday (which is why it’s often referred to as Black Tuesday!).

As long as you know the reference day for the current year, you can apply this rule to go forward or backward to any date in the Gregorian calendar. In my case, my birthday happens to fall on that reference day of the week, but any of the reference dates will work. (And, for the calendar nerds out there: for historical events, you need to know whether the country in question was using the Gregorian or Julian calendars, which is a whole other can of worms.)

Thanks for reading! I’ll be back for more at an unspecified date in the future.

 

On Euler’s Phi Function

In which we find that Euler’s phi function was neither phi nor a function.

First of all, a shout-out to all of my math(s) friends who are at (or traveling to) the Joint Mathematics Meetings in Baltimore! Now on to some math.

In my research for the “Evolution of…” series of posts, I came across the word totient in Steven Schwartzman’s The Words of Mathematics, which got me thinking about how Euler’s φ (phi) function—also called the “totient function”—came about. The word itself isn’t that mysterious: totient comes from the Latin word tot, meaning “so many.” In a way, it’s the answer to the question Quot? (“how many”?). Schwartzman notes that the Quo/To pairing is similar to the Wh/Th paring in English (Where? There. What? That. When? Then.). So much for the etymology.

It seems to me, though, that the more interesting questions are: who first defined it? how did the notation change over time? I did some digging, and here’s what I’ve discovered.

The first stop on my investigative tour was Leonard Dickson’s History of the Theory of Numbers (1952). At the beginning of Chapter V, titled “Euler’s Function, Generalizations; Farey Series”, Dickson has two things to say about Leonhard Euler:

“L. Euler… investigated the number φ(n) of positive integers which are relatively prime to n, without then using a functional notation for φ(n).”

“Euler later used πN to denote φ(N)…”

Each of these quotations contains a footnote, the first one to Euler’s paper “Demonstration of a new method in the theory of arithmetic” (written in 1758)  and the second to “Speculations about certain outstanding properties of numbers” (written in 1775). In the first paper, Euler is more interested in proving Fermat’s little theorem, which, true to form, he had already proven twice before. However, Euler does define the phi function (on p. 76, though as Dickson says, he doesn’t use function notation), and proves some basic facts about it, including the facts that φ(pm) = pm-1(p-1) [Theorem 3] and φ(AB) = φ(A)φ(B) when and B are relatively prime [Theorem 5]. This paper is in Latin, and while we do see the use of the words totidem and tot, they don’t seem to hold any special mathematical significance.

In the second paper, Euler returns to the phi function, having decided by this time to use π to represent it. Hard-core nerd that he is, Euler provides us with a table of values of πD for D up to 100, and replicates many of the facts he proved in the first paper. It’s interesting to note that, while Euler wrote this second paper in 1775, it wasn’t published until 1784, a year after his death.

It wasn’t until 1801, in Disquisiones Arithmeticae, that Carl Gauss introduced φN to indicate the value of the totient of N. So why did he pick φ rather than Euler’s π? Well, I checked the English translation by Arthur Clarke (no not, that Arthur Clarke), and I think it’s quite likely that he chose it for no discernible reason. In Clarke’s translation, Gauss introduces φ on page 20—and Gauss loved using Greek letters. In pages 5-19 (the beginning of Section II), he uses α, β, γ, κ, λ, μ, π, δ, ε, ξ, ν, ζ — and only after these does he use φ. As to the use of π, which was Euler’s notation, it’s possible that Gauss knew of Euler’s latter work and chose φ because he had already used π, but there’s no way to know for sure. (Also, π was already used for 3.14159… by this point, but if that was his reasoning, it’s odd that he used the symbol π at all.) Most likely, he just picked another Greek letter off the top of his head. It is important to remember that at no point did Gauss use function notation for the totient—it always appears as φN, never φ(N). (Also: Gauss goes on to use Γ and τ before getting tired of Greek and moving on to the fraktur letters 𝔄, 𝔅, and 𝖅.)

The next significant change came nearly a century later in J. J. Sylvester‘s article “On Certain Ternary Cubic-Form Equations,” published in the American Journal of Mathematics in 1879. On page 361, Sylvester examines the specific case npi, and says

pi-1(p-1) is what is commonly designated as the φ function of pi, the number of numbers less than pi and prime to it (the so-called φ function of any number I shall here and hereafter designate as its τ function and call its Totient).

While Sylvester’s usage of the word totient has become commonplace, mathematicians continue to use φ instead of τ. It just goes to show that a symbol can become entrenched in the mathematical community, even if a notational change would make more sense. Also of note is the fact that while Sylvester refers to the totient as a function, he doesn’t use the modern parenthesis notation, as in τ(n), but continues in Euler and Gauss’s footsteps by using τn.

And this is where our story ends. Sylvester’s use of the word totient, Gauss’s use of the letter φ, and Euler’s original definition all contributed to the modern construct that we call the phi/totient function. Even though Euler’s original definition came in a Latin paper, it wasn’t until Sylvester that the use of totient became commonplace.

However, Euler had proven many of the basic facts about it as early as 1758. So, while the original phi function was neither phi nor a function, it was undoubtedly Euler’s.