PRIMES

PRIMES

Relating Factorials and Primes

I originally published this work in 1961, in the Bronx High School of Science Mathematics Bulletin. A scan of the article is online. Here is a simplified summary.

The following notation is used throughout:

P1...Pm

the first m primes

The prime factors of a factorial

It is easily shown that the prime factors of n! are given by this formula:

A relation among primes

The formula above can be solved for Pm to obtain the following relation between Pm and all primes that precede it:

A way to generate every prime

From the above relations, one can derive the following formula that involves only p1...pm-1:

Evaluate the formula with c=1, 2, ... until Rc is not 1. The first non-unitary value of Rc is Pm.

How this work shaped my life

My math teacher explained to me that the procedure above was an algorithm. He suggested that I program it on a computer. In 1960, our high school did not have a computer, but he found me an IBM 650 machine language manual, which I brought to the cafeteria to study.

By chance, a student named Paul Schneck saw me reading the manual and introduced himself. He had access to an IBM 650 computer at Columbia University and offered to help me get time on it. He also gave me a manual for a Fortran-like language, Fortransit.

I ended up getting 30 minutes of computer use every Saturday morning for a few months during the 1960-61 school year. This blissful period lasted until I accidentally broke the drive belt of the magnetic drum memory. The administrator banished me from the facility. But I had become irreversibly hooked on programming.

My official project at the Columbia facility was to implement the prime number algorithm. However, the multi-pass compiler was frustrating to use. I had to feed in the compiler's Pass One deck and my source code deck, then wait as the compiler punched out the first intermediate deck. Then I had to feed in the compiler's Pass Two deck and the first intermediate deck and wait for the second intermediate deck to be punched. And so it went until the object code deck was produced some passes later.

If any errors were reported by the compiler, I had to look up their error numbers in a manual, decide a cure, and try to keypunch a correction before my half-hour time slot elapsed. If a valid object code deck miraculously emerged, I could begin to test it. First I had to feed in a boot deck, then the object deck. Then I had to debug in decimal using console lights and switches.

After several week of this tedious process, I had made little progress. I decided what the world needed more than a prime number generator was a cleaner language than Fortransit and a fast two-pass compiler. I set myself to that task.

Debugging the compiler was difficult to begin with, but became disastrous when it culminated with the snapping of the drum belt and my loss of privileges. The final words of the administrator were, "The world already has too many programming languages." That was 1961.

I dreamed of the day when I could have computer of my own in my home and more civilized memory and I/O devices.

When I arrived at Stanford University the following autumn, I immediately met Douglas Hofstadter, who introduced me to Professors George Forsythe and John Herriot. A Burroughs 220 had rendered the IBM 650 in the basement of Encina Hall obsolete. I was allowed all the 650 time that I wanted. However, I soon realized that a little time on the 220 was far more productive than unlimited time on the old 650. The 220 used magnetic tape instead of intermediate card decks, and had an operating system and a professional operator.

I moved my prime number project to the Burroughs 220 and finally completed a Subalgol implementation in October 1961. I still have in my possession a 40-line listing of an almost-final version of that code.

By that time, my interest in computing had overwhelmed my interest in mathematics. I committed my life to what was then an uncharted field with an uncertain future. But it all started with a little formula relating primes and factorials.

©1998, 2010 Larry Tesler