Factor clock

The factor clock displays the time in the form $\mathrm{hours:minutes:seconds}$ , that is, as $\mathrm{hh:mm:ss}$ , and then decomposes the number $\mathrm{hhmmss}$ into prime factors. For example, a quarter of an hour after eleven o’clock, at 11:15:00, the following is displayed: $111500=2\cdot 2\cdot 5\cdot 5\cdot 223$ . The somewhat strange idea of reading the time (including the seconds) as a decimal number and then factorizing it goes back to the Internet comic series xkcd, see Figure 1 below:

Figure 1: The deciding xkcd comic (license xkcd, Creative Commons)

And now … the mathematics of it:

Part 1: Facts

Because $\mathrm{hh}<24$ , $\mathrm{mm}<60$ and $\mathrm{ss}<60$ must be valid, not all of the 1000000 six-digit numbers occur, but only as many as the day has seconds, namely 86400. Among them are 7669 prime numbers. The last prime number time before midnight is 23:59:51. The number 235951 is number 20903 among all prime numbers, but only number 7669 among the factor clock primes. However, the majority of the 7669 prime numbers that the factor clock can display are not seen by the visitors of the MATHEMATICS ADVENTURE LAND because they are outside the opening hours of the museum:

Between 9:00 and 18:00 there are 2731 factor clock primes.
Of these, 2440 are in the weekday opening hours 9:00–17:00 and 2407 are in the weekend opening hours 10:00–18:00.
About five prime numbers can be expected per minute, with a slightly higher frequency in the morning than in the evening.
At most there are nine prime numbers in one minute (i.e. from $\mathrm{hh:mm:00}$ to $\mathrm{hh:mm:59}$ . This occurs ten times, at 9:00, 10:05, 11:09, 11:31, 11:53, 12:13, 12:20,13:06, 14:04, and 15:28).
Between 11:52:49 and 11:53:43 there are 11 prime numbers within 54 seconds.
You have to wait more than a minute for the next prime number from 10:12:21 (62 seconds), 10:27:01 (70 seconds), 12:17:27 (76 seconds) and 14:29:49 (64 seconds).
There are 859 prime twins among the factor clock primes.
Between 9:00 a.m. and 6:00 p.m., there are 278 twins, of which 255 are in the 9:00 a.m.-5:00 p.m. opening time and 242 are in the 10:00 a.m.-6:00 p.m. opening time.
Approximately every two minutes a prime twin is to be expected, whereby the frequency is somewhat higher in the morning than in the evening.
Prime twins are especially common around 9:40, 12:20, and 15:20.
You have to wait especially long for a prime twin starting at 10:55:29 (7:52), 12:27:43 (8:08), 15:02:23 (7:24), 16:34:11 (7:36), and 17:49:31 (7:00).
Curiously, there is even a “factor clock prime triple”: 11:52:59, 11:53:01, 11:53:03.

Part 2: The algorithm of Fermat

The basic method for decomposing a given natural number into prime factors is based on an algorithm first given by Pierre de Fermat (c. 1608–1668).

Fermat’s factorization method looks for two square numbers $x^2$ and $y^2$ that satisfy the equation $x^2-n=y^2$ (with $n$ a natural number). Then, based on the 3rd binomial formula,

$n=x^2-y^2=(x+y)(x-y)$

and $a=x+y$ and $b=x-y$ are the sought divisors of $n$ . The Fermat’s method thereby finds exactly those divisors $a$ and $b$ that are closest to the root of $n$ .

Although the method is one of the slowest known procedures that do this, this method has a certain importance in mathematics, since almost all fast factorization procedures known today go back to Fermat’s method.

In detail, the following procedure is to be carried out:

To factorize a natural number, one computes for $x$ starting at $\lceil\sqrt{n}\rceil$ (i.e., at the smallest integer greater than the square root of $n$ ) $Q(x)\coloneqq x^2-n$ . As soon as one of these numbers is a square number, e.g. $x^2-n=y^2$ , one can specify a multiplicative decomposition of $n$ , whose two factors then have to be subjected to the procedure again. It is namely according to the 3rd binomial formula $n=x^2-y^2=(x-y)(x+y)$ . The search can be terminated when $x$ exceeds $\frac{n+9}{6}$ , since then it is already certain that $n$ is a prime number. However, this termination condition is only valid for odd numbers $n$ , but this can always be achieved by multiplicatively splitting off the highest power of 2 before starting this procedure.

An example shall illustrate this:

The number $24806$ (i.e. the time 2:48 o’clock and 6 seconds) is to be factorized. Then first the factor 2 is to be multiplicatively split off and one receives $24806=2\cdot 12403$ and can apply the procedure to $n=12403$ . Since the square root of 12403 is approximately 111.368, one begins by determining $Q(x)$ for $x=112$ . In this case we get

$Q(112)=1122-12403=141$
$Q(113)=366$
$Q(114)=593$
$Q(115)=822$
$Q(116)=1053$
$Q(117)=1286$
$Q(118)=1521=39^2\quad\text{(!)}$ .

Consequently, $x=118$ and $y=39$ , i.e. $x+y=157$ and $x=79$ are obtained as prime factors, i.e. $12403=79\cdot 157$ or $24806=2\cdot 79\cdot 157$ on the display of the factor clock in MATHEMATICS ADVENTURE LAND at the time 2:48 o’clock and 6 seconds.