The Mandelbear's Musings

I really need to write my memoirs, preferably before my memory deteriorates to the point where I can't. (I am inspired by my mom, who published the third edition of hers last year.) I have, however, given up on the idea of following the King of Hearts' advice to "begin at the beginning, [...] and go on till you come to the end: then stop". (I note in passing that I haven't come to the end yet.) So I'm just going to dive in at whatever point seems interesting at the moment. I'll tag these by year, so that anyone interested (possibly as many as two of you) can sort them out later.

This particular point was suggested by somebody's mention of their Erdős number, so I suppose I ought to explain that first. Content Warning: contains math, which you can safely skip over if you're math-phobic. Deciding which parts to skip is left as an exrcise for the reader.

You have perhaps heard of the parlor game called "Six Degrees of Kevin Bacon", based on the concept of "six degrees of separation". The idea is to start with an actor, and figure out the shortest possible list of movies that links them with Kevin Bacon. The length of that list is the actor's "Bacon number", with Bacon himself having the number zero, anyone who acted in a movie with him having the number one, and so on. As far as I know I don't have a finite Bacon number, but it's not outside the realm of possibility if, as most people do, you include TV shows and so on. I think I've been in at least one brief local TV news item.

But sometime during my senior year at Carleton College, I co-authored a paper with one of my math professors, Ken Wegner, which gave me an Erdős number of 7. The paper, published in 1970 in The American Mathematical Monthly, was "Solutions of Φ(x) = n , Where Φ is Euler's Φ-Function" [Wegner, K., & Savitzky, S. (1970), The American Mathematical Monthly, 77(3), 287-287. doi:10.2307/2317715].

So now I have three things to explain: What is an Erdős number? What is Euler's Φ function? And finally, What was my contribution to the paper?

Erdős number: As you might expect from the introduction about the Bacon Number, a mathematician's Erdős number is the smallest number of co-authored papers connecting them to Paul Erdős (1913–1996), an amazingly prolific (at least 1,525 papers) 20th Century mathematician. He spent the latter part of his life living out of a suitcase, visiting his over 500 collaborators (who thus acquired an Erdős number of 1. The Erdős number was first defined in print in 1969, so about the time I was collaborating with Wegner on Euler's Φ function.

Euler's Φ function, Φ(n), also called the Totient function, is defined as the number of positive integers less or equal to n that are relatively prime to n; or in other words the numbers in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n,k) = 1. (You will also see it written in lower-case as "φ", or in Latin as "phi".)

The totient function is pretty easy to compute, at least for sufficiently small numbers. The inverse is rather less straightforward, and has been the subject of a considerable number of StackExchange queries. (This answer includes a good set of links.) I was thinking of including some detail about that, and was barely able to keep myself from falling down the usual rabbit-hole, which almost always ends up somewhere in group theory. For example, φ(n) is the order of the multiplicative group of integers modulo n. See what I mean?

My contribution to the paper was not very closely related to the actual mathematics of the problem; what I did was write the computer program that computed and printed out the table of results. That involved a hack. A couple of hacks, actually.

In 1969, Carleton College's computer lab contained an IBM 1620 and a couple of keypunches. The 1620 was fairly primitive even by 1960s standards; its memory consisted of 20,000 6-bit words, with a cycle time of 20 microseconds. Each word contained one BCD-coded decimal digit, a "flag" bit, and a parity check bit. It did arithmetic digit-by-digit using lookup tables for addition and multiplication. It was not particularly fast -- about a million times slower than the CPU in your phone. But it was a lot of fun. Unlike a mainframe, it could sit in one corner of a classroom (if it was air-conditioned), it was (comparatively) inexpensive, and it could stand up to students actually getting their hands on it.

A lot of the fun came from the fact that the 1620's "operating system" was the human operator sitting at the console, which consisted mainly of an electric typewriter and a row of buttons and four "sense switches" that the program could read. If you wanted to run a program, you put a stack of punched cards into the reader and pushed the "load" button, which read a single 80-column card into the first 80 characters of memory, set the program counter to zero, and started running. My program was written in FORTRAN. Not even FORTRAN II. Just FORTRAN.

Computing the table that occupied most of the paper took about a week.

Here's where it gets interesting, because obviously I wasn't the only student who wanted to use the 1620 that week. So I wrote an operating system -- a foreground/background system with my program running in the background, with everyone else's jobs running in the "foreground". That would have been easy except that the 1620 could only run one program at a time. Think about that for a moment.

My "operating system" consisted mainly of a message written on the back of a Hollerith card that said something like: "Flip sense switch 1 and wait for the program to punch out a deck of cards (about a minute). When you're done, put the deck in the reader and press LOAD."

Every time the program went around its main loop, it checked Sense Switch 1, and if it was set, it sent the contents of memory to the card punch. Dumping memory only took one instruction, but it wasn't something you could do from FORTRAN, so I put in a STOP statement (which FORTRAN did have) and changed it to a dump instruction. By scanning the program's object code (remember this is a decimal machine; an instruction took up 12 columns on the card) and replacing the HALT instruction with DUMP.

It worked.

    MR: Collaboration Distance
     MR Erdos Number = 7
     S. R. Savitzky 	  coauthored with    Kenneth W. Wegner 		MR0260667
     Kenneth W. Wegner 	  coauthored with    Mark H. Ingraham 		MR1501805
     Mark H. Ingraham 	  coauthored with    Rudolph E. Langer 		MR1025350
     Rudolph E. Langer 	  coauthored with    Jacob David Tamarkin 	MR1501439
     Jacob David Tamarkin coauthored with    Einar Hille 	        MR1555331
     Einar Hille 	  coauthored with    Gábor Szegő 	        MR0008279
     Gábor Szegő 	  coauthored with    Paul Erdős 	        MR0006783
     MR0260667 points to: K. W. Wegner and S. R. Savitzky, (1970)
     Solutions of φ (x) = n, Where φ is Euler's φ-Function on JSTOR,
     The American Mathematical Monthly, 77(3), 287-287.
     DOI: 10.1080/00029890.1970.11992471.

There are two other numbers of interest: the Shūsaku Number, measuring a Go player's distance from the famous 19th-Century Go player Hon'inbō Shūsaku, and the Sabbath Number, measuring a musician's distance from the band Black Sabbath. I'm pretty sure I have a Sabbath number through filkdom. I definitely have a Shūsaku number of 5 from having lived down the hall from Jim Kerwin, Shūsaku Number 4, my sophomore and junior years at Carleton. That's another story.

And if I expect to write more journal entries about math, I'm going to have to extend my posting software to allow entries written in LaTeX. Hmm.

The Mandelbear's Memoirs