Factor Clock

The factor clock displays the time in the form $\mathrm{Stunden:Minuten:Sekunden}$ , that is, as $\mathrm{hh:mm:ss}$ , and then decomposes the number $\mathrm{hhmmss}$ into prime factors. For example, a quarter of an hour past eleven, that is, 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 seconds) as a decimal number and then factorizing it goes back to the Internet comic series xkcd, see Figure 1 below:

And now … the mathematics:

Part 1: Facts

Because $\mathrm{hh}<24$ , $\mathrm{mm}<60$ and $\mathrm{ss}<60$ must apply, 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 time before midnight is 23:59:51. The number 235951 is number 20903 among all prime numbers, but only number 7669 among factor clock primes. However, the majority of the 7669 prime numbers that the factor clock can display will not be seen by visitors to the MATHS ADVENTURE LAND because they are outside the museum’s opening hours:

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 primes in one minute (that is, 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 from 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). Based on the 3rd binomial formula then

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

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

Although the method is one of the slowest known to do this, this method has some importance in mathematics, since almost all fast factorization methods known today can be traced back to Fermat’s method.

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

To factorize a natural number, calculate $Q(x)\coloneqq x^2-n$ for $x$ starting at $\lceil\sqrt{n}\rceil$ (that is, at the smallest integer greater than the square root of $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 it is then already certain that $n$ is a prime number.

An example will illustrate this in conclusion:

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

$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{(!)}$ .

Thus, we get $x=118$ and $y=39$ , so $x+y=157$ and $x=79$ as prime factors, i.e. $12403=79\cdot 157$ or $24806=2\cdot 79\cdot 157$ on the display of the factor clock in the MATHS ADVENTURE LAND to the time 2:48 o’clock and 6 seconds.

Literature

[1] Bundschuh, P.: Einführung in die Zahlentheorie, 6. Auflage, Berlin, 2008.

[2] Du Sautoy, M.: The music of the prime numbers. On the trail of the greatest riddle in mathematics, Munich, 2004.

[3] Padberg, F.: Elementare Zahlentheorie,3rd edition, Heidelberg, 2008.

[4] Wolfart, J.: Einführung in die Algebra und Zahlentheorie, Braunschweig / Wiesbaden, 1996.