Prime Clockwork

Prime Clockwork – A Simple Automaton to Generate Natural Numbers and Their Prime Factors
15.8.2024, by Michael Emmerich

1. What is the prime clockwork?

This work presents the prime clockwork, an automaton that generates all natural numbers in prime factorization starting from one, using only integer addition and comparison -— no division or multiplication. The prime clockwork is an array of independent prime clocks that generate number sequences and discover prime numbers organically without prior knowledge. The rationale behind this method lies in its potential to shed some light on the intrinsic nature of integers and prime numbers.

While the lemmas are provable with basic number theory and we do not claim they are completely new, we belief the prime clockwork might present a new way to view the natural numbers and compute their prime factorizations. We are inspired by the rich body of past work on this topic area, especially on prime factorization. Recognizing the rich history of prime studies from Euclid to Euler, we may have missed some references and invite reader comments on any important related work.

2. Prime Vector Basics

Prime vectors are basic data structures to represent numbers in a positional notation (see, for instance, \url{https://emmerix.net/2024/07/29/playing-with-primes}). They are based on the fundamental theorem of number theory that states that each natural number can be stated as a prime vector.

Definition 1 For ${z \in \mathbb{N}}$ , represent ${z}$ as ${z = \prod_{i=1}^\infty p_i^{k_i}}$ , where ${p_i}$ are primes and ${k_i \in \mathbb{N}_0}$ . We define a prime vector as an infinite list ${p = (k_1, k_2, \dots)}$ . The mapping between integers and prime vectors is ${P(z)}$ , with the inverse ${P^{-1}(z)}$ . The space of prime vectors is ${\mathbb{P}}$ .

Lemma 2 Prime vectors uniquely represent all natural numbers, establishing a one-to-one correspondence between ${\mathbb{N}}$ and ${\mathbb{P}}$ .

Proof: This follows from the fundamental theorem of arithmetic, which states every integer has a unique prime factorization. $\Box$

Definition 3 Define the ${\odot}$ operator on ${\mathbb{P}}$ as ${a \odot b = (a_1 + b_1, a_2 + b_2, \dots)}$ .

Lemma 4 For ${a = P(u)}$ and ${b = P(v)}$ with ${u, v \in \mathbb{N}}$ , ${P^{-1}(a \odot b) = u \cdot v}$ .

Proof: Since ${a_i}$ and ${b_i}$ denote the non-zero exponents of prime factors of ${b}$ and ${a}$ , respectively, we have ${\prod p_i^{a_i} \prod p_i^{b_i} = \prod p_i^{a_i + b_i}}$ . $\Box$

Prime vectors enable elegant computation of number properties, such as:

Lemma 5 Let ${a = P(u)}$ and ${b = P(v)}$ . The Greatest Common Divisor ${\mathrm{GCD}(u,v)}$ is given by
$\displaystyle \mathrm{GCD}(u,v) = P^{-1}((\min(a_1, b_1), \min(a_2, b_2), \ldots)) \ \ \ \ \ (1)$
The Least Common Multiple ${\mathrm{LCM}(u,v)}$ is given by
$\displaystyle \mathrm{LCD}(u,v) = P^{-1}((\max(a_1, b_1), \max(a_2, b_2), \ldots)) \ \ \ \ \ (2)$

Let us also consider the smallest prime vector representing 1.

Lemma 6 For ${p \in \mathbb{P}}$ , ${p \odot (0, \dots) = p}$ . That is, ${(0, \dots)}$ corresponds to the natural number ${1}$ .

To keep things concise, this discussion will focus only on addition and multiplication defined in natural numbers, and the smallest number taken into account is ${1}$ .

3. Prime Clockwork

We will show that counting natural numbers as prime vectors can be described by a ‘clockwork’ of autonomous ‘clocks’, each linked to a unique prime number and producing prime vector digits independently. Coupling occurs only when all clocks show zero, triggering the birth of a new prime number and a new clock. We first assume primes ${p_i}$ are known and will later discuss their on-the-fly generation.

Definition 7 A prime clock for prime ${p_i}$ , denoted ${\circledast(p_i, t)}$ , is a recursive automaton starting at ${t = 1}$ and generating an output ${o_i(t) \in \mathbb{N}_0}$ each iteration. It has a seconds counter that ${s_i(t)}$ that is increased by one in each iteration, and reset to ${0}$ before it reaches ${p_i}$ , i.e. it holds ${ s_i(t) = t \bmod p_i}$ . It has a minutes counter ${m_i(t)}$ that starts with ${m_i(1) = 0}$ and increases by one after each reset of the seconds counter. The prime clock outputs ${o_i(t) = o_i(m_i(t)) + 1}$ whenever ${s_i(t) = 0}$ , and ${o_i(t) = 0}$ otherwise.

Remark 1 Using a clock metaphor, let ${t}$ be the total seconds passed and ${m_i(t)}$ the minutes. ${s_i(t)}$ is the seconds hand which is reset to 0 when it finished a full round. Each minute has ${p_i}$ seconds on the clock ${\circledast(p_i, \dot)}$ . Unlike real clocks, seconds and minutes are not displayed and there is no cap on minutes.

Lemma 8 The prime clock ${\circledast(p_i, t)}$ generates as output ${o_i(t)}$ the ${i}$ -th digit of the prime vector ${P(t)}$ during the ${t}$ -th iteration.

Proof: The output ${o_i(t)}$ is zero if ${s_i \bmod p_i \equiv 0}$ , i.e., ${t}$ is not divisible by ${p_i}$ . If ${s_i \equiv 0}$ , then ${t = p_i \cdot m_i(t)}$ . In prime vector notation, ${P(t) = P(p_i) \odot P(m_i(t))}$ . By Lemma 4, compute the ${i}$ -th digit of ${P(t)}$ with ${o_i(t) = 1 + o_i(m_i(t))}$ . $\Box$

The recursive definition below implements the prime clockwork without needing the modulo operator:

Definition 9 We operate autonomous prime clocks for each prime ${p_i}$ . For each iteration ${t>0}$ , the prime clocks output a digit ${o_i(t)}$ such that ${(o_1(t), o_2(t), \dots) = P(t)}$ , representing the exponents in the prime factorization of ${t}$ . Let ${s_i(t)}$ and ${m_i(t)}$ be the states of the clock ${\circledast(p_i,t)}$ , where ${s_i(t)}$ is the step (second pointer) and ${m_i(t)}$ is the number of complete cycles (minute pointer).
$\displaystyle s_i(0) = 0 \ \ \ \ \ (3)$

$\displaystyle m_i(0) = 0 \ \ \ \ \ (4)$

$\displaystyle o_i(0) = 0 \ \ \ \ \ (5)$
The next step function is defined recursively as follows:
$\displaystyle s_i(t + 1) = \begin{cases} 0 & \text{if } s_i(t) + 1 = p_i \\ s(t) + 1 & \text{otherwise} \end{cases} \ \ \ \ \ (6)$

$\displaystyle m_i(t + 1) = \begin{cases} m_i(t) + 1 & \text{if } s_i(t) + 1 = p_i \\ m_i(t) & \text{otherwise} \end{cases} \ \ \ \ \ (7)$

$\displaystyle o_i(t + 1) = \begin{cases} 1 + o_i(m(t + 1)) & \text{if } s_i(t + 1) = 0 \\ 0 & \text{otherwise} \end{cases} \ \ \ \ \ (8)$

Remark 2 The prime clocks have three key properties:

Autonomy: Each prime clock ${\circledast(p_i,t)}$ operates independently, without the need to know the states of other clocks. The clockwork array generates the prime vectors sequentially in ascending order.
Efficiency: Prime clocks use only a few constant integer additions and comparisons, and they operate without multiplication, division, and modulo computations.
Periodicity: Prime clocks output non-zero in exactly every ${p_i}$ th iteration starting when ${t=p_i}$ . In particular, a prime factor is blocked for ${p_i-1}$ iterations after it has been used and then will be part of the prime factorization again.

One might argue that this mechanism needs infinite clocks and prior knowledge of the prime number. However, clocks can be added “on the fly” when zero digits appear in all outputs.

Definition 10 {Dynamic Prime Clockwork} Let us assume that we start the counting process with only one active prime clock in the array, the prime clock for ${p_i=2}$ . Let ${\circledast(p_1,t_0), \dots, \circledast(p_{i},t_0)}$ be active prime clocks starting from ${t=1}$ that output ${0}$ simultaneously for the first time, that is, ${o_j(t_0) = 0}$ for all ${j=1, \dots, i}$ . In this case ${t_0}$ is prime, and a new prime clock ${\circledast(p_{i+1},.)}$ is activated and added with ${p_{i+1} = t_0}$ . It is initialized by running it from ${t=1}$ to ${t=t_0}$ . Then the prime vector we output at ${t_0}$ is ${o_i(1), \dots, o_i(t_0) = 0}$ and ${o_{i+1}(p_{i+1}) = 1}$ .

Lemma 11 The dynamic prime clockwork produces all prime vectors of integers one by one and adds prime clocks as soon as they are needed, that is, they produce non-zero output.

Proof: The crucial observation here is that ${p_i = t}$ is prime, and this is concluded from the fact that ${t_0 = p_i}$ and the uniqueness of the prime factorization. Since ${t_0}$ cannot be divided by any of the numbers ${p_1, \dots, p_{i-1}}$ , and certainly not by a number greater than ${t_0}$ , ${p_i}$ must be prime. $\Box$

This dynamic clockwork has been implemented in Python; we include source code and example output for the first 30 natural numbers in the Appendix.

Remark 3 At a given time, most prime clocks output zero, suggesting a high frequency of prime numbers for small numbers of active prime clocks. Over time, the newly added prime clocks have a decreased frequency of output non-zero values, but it still becomes harder for a new prime number to occur, as more clocks need to simultaneously show zero.

In summary, the prime clockwork efficiently generates natural numbers by their prime factorization using integer addition and comparison only. It requires no prior knowledge of primes, with the successor computation being efficient and constant in operations that are restricted to integer addition and comparison. Prime numbers and their clocks are generated on the fly as needed.

4. Addition and Multiplication

The prime clockwork operates clocks independently if it is provided with the primes. Thus, we can define addition and multiplication at the level of a single clock ${\circledast(p_i,t)}$ . This can be done as follows.

Definition 12 {Addition} For two prime clock states ${(s_i', m_i', o_i')}$ in ${t'}$ and ${(s_i'', m_i'', o_i'')}$ in ${t''}$ , the addition ${\oplus}$ is defined as follows:
$\displaystyle s_i = (s_i' + s_i'') \bmod p_i \ \ \ \ \ (9)$

$\displaystyle o_i = \begin{cases} 0 & \mbox{if } s_i \neq 0 \\ o_i(m_i' + m_i'') + 1 & \mbox{ if } s_i = 0 \end{cases} \ \ \ \ \ (10)$

$\displaystyle m_i = \begin{cases} m_i' + m_i'' & \mbox{ if } s_i \neq 0 \\ m_i' + m_i'' + 1 & \mbox{if } s_i = 0 \end{cases} \ \ \ \ \ (11)$

Definition 13 {Multiplication} For two prime clock states ${(s_i', m_i', o_i')}$ in ${t'}$ and ${(s_i'', m_i'', o_i'')}$ in ${t''}$ , the multiplication ${\otimes}$ is defined as follows:

$\displaystyle o_i = o_i' + o_i'' \ \ \ \ \ (12)$

$\displaystyle s_i = (s_i' \cdot s_i'') \bmod p_i \ \ \ \ \ (13)$

$\displaystyle m_i = m_i' \cdot m_i'' \ \ \ \ \ (14)$

Remark 4 This update maintains, as expected, the property that the prime clocks can be run as independent processes.

To know the output of multiplication, it is sufficient to know the output of the clocks ${o_i'}$ and ${o_i''}$ in ${t'}$ and ${t''}$ . This is consistent with Lemma 4. An interesting observation is that the prime numbers are already represented with non-zero values in either one of the two factors. That is, multiplication never adds new prime factors, but only combines the prime factors of the two input integers.
To implement the addition, we also require the current position of the second counter ${s_i}$ and the minute counter ${m_i}$ , as well as the history outputs of the prime clock prior to the two summation factors. In principle, these values can be recomputed with some computational effort using the information stored in the prime vectors ${o'}$ and ${o''}$ . Moreover addition operations on the level of the clockwork might require the activation of additional prime clocks in the dynamic clockwork, as additional prime numbers might be needed to represent the result.
Multiplication may affect the values of ${s_i}$ and ${m_i}$ . Thus, if addition is applied to the result of multiplication, ${s_i}$ and ${m_i}$ need to be updated also in multiplication.
If we are only interested in whether or not ${o_i>0}$ , that is, whether or not ${p_i}$ divides ${t}$ , neither the minute counters ${m_i}$ , nor the history of past outputs are needed. Thus, there is hope that some questions regarding the integers and prime numbers can be answered using a simpler, binary, representation of numbers.
This reveals that multiplication is memoryless when used alone. However, for addition, we need the seconds pointer, minutes pointer, new prime numbers, and preceding clock states to perform it efficiently. Alternatively, we can resort to a step-by-step simulation from ${t=1}$ or any time when the clock state was known, using only the information stored in the prime vectors for addition. Here, restoring the information of ${s_i}$ and ${m_i}$ can be accomplished by dividing the whole by the remainder using ${p_i}$ , but to acquire the knowledge of all ${p_i}$ that are relevant in representing the result of the addition might be difficult to accomplish without a step-by-step simulation of the dynamic prime clockwork. However, this could be computationally inefficient.

Sometimes we can, however, easily conclude the result of addition even if there is incomplete information on the prime clocks’ internal states. The following lemma specifies the prime factors in the sum of two prime vectors.

Lemma 12 Let ${a}$ and ${b}$ denote two vectors and ${c=a \oplus b}$ . Then
$\displaystyle (a_i \geq 0 \mbox{ and } b_i =1) \mbox{ or } (a_i \geq 1 \mbox{ and } b_i =0)\Rightarrow c_i = 0 \ \ \ \ \ (15)$

$\displaystyle (a_i \geq 1) \mbox{ and } (b_i \geq 1) \Rightarrow c_i \geq 1. \ \ \ \ \ (16)$

Proof: The lemma follows from the clockwork mechanism. When ${a_i\geq 1}$ , the seconds pointer of the prime clock for ${p_i}$ hits zero. Therefore, only if ${b_i \geq 1}$ do we add whole minutes to the seconds, as in the lemma 16; otherwise, the non-zero position seconds pointer results in a zero output as in equation 15. We used the fact that all prime clocks run independently. $\Box$

Remark 5 Only in case ${a_i = 0, b_i = 0}$ , the output can be anything ${0}$ or ${1}$ . In all other cases the output of the addition of two prime clocks is well defined by the information provided with ${a_i}$ and ${b_i}$ , without requiring knowledge of the seconds and minutes and past outputs.

5. Python Implementation of the Prime Clockwork

Here is a Python source code for the Prime Clockwork simulation. Prime clocks operate autonomously and are unaware of each other’s outputs. Adding a prime clock occurs upon the birth of a new prime number, which requires the observation that all active prime clocks are in state ${s_i(t) = 0}$ . We use no precomputed primes.

class PrimeClock:
    def __init__(self, prime):
        self.prime = prime
        self.s = 0
        self.m = 0
        self.outputs = [0]  # positive_outputs

    def next(self):
        self.s += 1
        if self.s == self.prime:
            self.s = 0
            self.m += 1
        if self.s == 0:
            output = 1 + self.outputs[self.m]
        else:
            output = 0
        self.outputs.append(output)
        return output

class Clockwork:
    def __init__(self):
        self.t = 0
        self.clocks = []
        for prime in [2, 3]:
            self.clocks.append(PrimeClock(prime))

    def next(self):
        digits = [clock.next() for clock in self.clocks]
        self.t += 1
        return digits, self.t

    def add_new_clock(self):
        new_prime = self.t
        new_clock = PrimeClock(new_prime)
        for _ in range(self.t):
            new_clock.next()
        self.clocks.append(new_clock)
        return new_clock.outputs[-1]

    def run(self, max_iterations):
        for _ in range(max_iterations):
            digits, t = self.next()
            if all(d == 0 for d in digits) and t > 2:
                new_output = self.add_new_clock()
                digits.append(new_output)
            print(f"{t}\t" + "\t".join(map(str, digits)))

if __name__ == "__main__":
    max_iterations = 30
    clockwork = Clockwork()
    clockwork.run(max_iterations)

It produces the following output:

Time	P2	P3	P5	P7	P11	P13	P17	P19	P23	P29
1	0	0	0	0	0	0	0	0	0	0
2	1	0	0	0	0	0	0	0	0	0
3	0	1	0	0	0	0	0	0	0	0
4	2	0	0	0	0	0	0	0	0	0
5	0	0	1	0	0	0	0	0	0	0
6	1	1	0	0	0	0	0	0	0	0
7	0	0	0	1	0	0	0	0	0	0
8	3	0	0	0	0	0	0	0	0	0
9	0	2	0	0	0	0	0	0	0	0
10	1	0	1	0	0	0	0	0	0	0
11	0	0	0	0	1	0	0	0	0	0
12	2	1	0	0	0	0	0	0	0	0
13	0	0	0	0	0	1	0	0	0	0
14	1	0	0	1	0	0	0	0	0	0
15	0	1	1	0	0	0	0	0	0	0
16	4	0	0	0	0	0	0	0	0	0
17	0	0	0	0	0	0	1	0	0	0
18	1	2	0	0	0	0	0	0	0	0
19	0	0	0	0	0	0	0	1	0	0
20	2	0	1	0	0	0	0	0	0	0
21	0	1	0	1	0	0	0	0	0	0
22	1	0	0	0	1	0	0	0	0	0
23	0	0	0	0	0	0	0	0	1	0
24	3	1	0	0	0	0	0	0	0	0
25	0	0	2	0	0	0	0	0	0	0
26	1	0	0	0	0	1	0	0	0	0
27	0	3	0	0	0	0	0	0	0	0
28	2	0	0	1	0	0	0	0	0	0
29	0	0	0	0	0	0	0	0	0	1
30	1	1	1	0	0	0	0	0	0	0

Acknowledgements: I gratefully acknowledge contributions in discussions and feedback provided by Mutlu Özdemir from Dortmund, Germany on the ideas presented in this essay.

Michael Emmerich: Playing with primes, pubished online July 29th, 2024.

Computational Science, Mathematical Playground

Michael Emmerich

Prime Clockwork

One response to “Prime Clockwork”

Leave a reply to Elegant Addition-only Prime Generation in LISP – Michael Emmerich Cancel reply

Prime Clockwork

Share this:

One response to “Prime Clockwork”

Leave a reply to Elegant Addition-only Prime Generation in LISP – Michael Emmerich Cancel reply