English Ukrainian German

Are primes computable?

The short answer is yes, the long answer is, that the effort to identify them by certain methods grows vastly the bigger a prime number should be.


Chapter 1 – Basics of natural numbers and primes

Let’s remember, what prime numbers are. There are several definitions in the internet, saying:

“A prime number is a whole number greater than 1 that cannot be exactly divided by any whole number other than itself and 1“

Well, sounds good, but there appear two questions: what is a “whole number” and what means “exactly divided”?

To make it vivid, take an amount of coins or something other countable. The attribute “countable” is the key to understand “whole number”, also known as “natural numbers”.

Now try to lay out rectangles with all coins.


If you cannot archive to build more than “two” rectangles without any remaining coins, than the number of all used coins of the tried rectangle (including the remainders) is a prime number. “Exactly divided” means: the ability to lay out at least one rectangle with a specific number of countable things without any remainder. Coins in one line do not count as rectangle.

As you can see, the bigger the number of coins the more rectangles and space we need.

Could we speed up this method?

Well, yes, you could actually lay out rectangles only until a square. And it is not important, if this square has remainders or not. Rectangles after reaching a square are just in another position as former ones. There are some more improvements, but this article is on learning about the nature of prime numbers and this method – including those “unneeded” rectangles – is very suitable for showing their nature. And there are also other procedures, to testing if a number is prime or not.

OK, last question for now: How many prime numbers exist or are there infinitely many of them?

The ancient Greek Euclid said, yes, there are infinitely many primes. He argued, that if you multiply all known prime numbers together and add one, than there must be a yet unknown prime number either being the result of this calculation or being able to divide the result without any remainder.

Ups, sounds complicated! Thus, forget about it, we did not want to do math – we wanted to predict primes. I mean, what is the next prime from a given number?

top

Chapter 2 – Finding the next prime number(s) without calculation

Well, take your rectangles made out of coins back and follow these instructions:

  1. Add a coin to each rectangle – either in a new row or after the remaining coins
  2. If one of the rectangles has no remainder, repeat step 1
  3. If all rectangles have remainders, the amount of coins within a line is the next prime number

If you want to find further prime numbers, do following step and repeat the instruction:

  1. Copy the coins in a line and place new coins for the previous line in a new row

Wow! Amazing! Can we improve this method?

We can discover, that only the remainders of each rectangle are important to decide, if a number is prime or not. Thus, we can remove all rectangles and concentrate on the remainders, while the last “one row rectangle” contains the amount of coins of the number to be examined. But to memorize the respective rectangle, we lay out another row containing the amount of coins, how many of them are necessary to complete the next row of the rectangle. Let’s call this row “completer”.

Now the algorithm changes a bit:

  1. Instead of adding a new coin to each rectangle, move one coin of the “completer row” to the “remainder row” and only at the last row, which does not have a “completer row”, we add a new coin
  2. If a “completer row” is empty (all coins are in the respective “remainder row”), move all coins from the “remainder row” to the respective “completer row” and for the next round repeat step 1
  3. If all “completer rows” contain coins, the amount of coins at the last row is the next prime number

For further prime numbers, step 4 does not change:

  1. Copy the last line with coins and use the line before as new “completer row” for the next round by repeating step 1


top

Chapter 3 – Diagram of remainder and “completion”

Actually, using only the remainders is mathematically spoken the usage of modulo for a number. The “completers” are just for a better orientation. We can use a diagram to analyse the results – even for larger numbers:


There is a lot to tell what you can glean from this diagram:

The “flags” within the diagram represent the rows of the former rectangles:


If we compare the first five bars for the numbers 60, 120, 180, 240, 300 (and so on +60), we see no change. The same happens for other numbers like 67, 127, 187, 247, 307 (and so on +60). There are intervals, when patterns repeat.


Sometimes, the pattern looks chaotic (for example for the first 200 bars of number 700) and other times an arc seems to appear (for example for the first 200 bars of number 2500). This behaviour indicates oscillations and interferences.


And it seems, that something is moving, when the charts are played one after the other:


top

Chapter 4 – Clocks and sine waves with prime numbers

As we could see in the last chapters, each bar of remainders and “completers” resets their position, after a remainder is “full”. This behaviour can be illustrated like this:


Thus, we can replace each bar of the diagram with clocks. Another idea is to use gears or pendulums. The main insight is, that the difference between this “natural counting” and our human counting is, that we use number systems, where “clocks” do not move simultaneously, but after reaching a specific position.


Because we are pressing prime numbers into a human number system, it seems for us, that prime numbers appear spontaneously and randomly. However, we love to discover patterns by ordering the number line in two dimensions.

Here you can see, that prime numbers (and their squares) do only pop up within specific columns, if we choose a special number of columns (for example 4, 6, 10, 24, 30). If you choose other number of columns, the distribution seems chaotic.


Well, we could say, the attribute “prime” just means “portioning” numbers on the number line. And there is a children’s toy, showing exactly this:


Maybe you already know the function, doing something similar: the sine function. Using several sine curves, each with a period length of two times a prime, mark at the zero points in the graph composite numbers. The sine curves leave out new prime numbers.


top

Chapter 5 – Two methods to Predicting prime numbers

Actually, the “Sieve of Eratosthenes” uses this idea to predict new primes. It is mainly used to show in a 10x10 square, how to cross out none primes:


You can find new primes in a package, if you mark all multiplies of all prime numbers which you found within a specific range. You can stop marking the multiplies, if a found prime number is greater than the square root of the range you want to find primes. All unmarked numbers are now prime numbers.

Well, it is an indirect method to identify prime numbers: what is left, is prime. However, prime numbers generate new primes by reusing them in the same method (sieves, sine waves, clocks, gears, pendulums…). It is a kind of iteration / recursion. And we know from fractals, that self-similarities occur. Such properties can also be found in graphical representations of prime numbers. However, these structures are “destroyed” by using another prime number.


The charts with remainders lead us to detect primes with the so called “Chinese remainder theorem.” This is a method to find a number X for different modulo remainders. And a prime number is defined to have always a remainder. So why not to use the algorithm putting in known primes with different remainders? Actually, I do not want to explain this method in detail (you can find articles and videos explaining the “Chinese remainder theorem”).

Unfortunately, the algorithm does not only spit out prime numbers, but also composite numbers. Another advantage is, that the received pool of numbers does not contain any composite number made of the used primes. Thus, the method reduces the numbers to be tested enormously. And maybe there is a “pattern” within the output to speed up it even more?


top

Chapter 6 – Conclusion

The described thoughts on prime numbers might be useful to understand the nature of numbers. There is much more to explore and to tell about primes. I wonder if great mathematicians like Euclid, Fermat, Goldbach, Euler, Fourier, Gauss, Riemann and others also imagined prime numbers this way.

Based on the idea that prime numbers “reveal” new prime numbers, I'm wondering not asking, how many prime numbers "generate" how many new prime numbers? However, I am not a specialist to answer this question. I think, there is a way to calculate it accurately.

If you expected to read something in this article regarding the twin prime conjecture, Goldbach's conjecture, the Ulam spiral or the Riemann hypothesis, I have to disappoint you. I even have no idea, if the thoughts described here can contribute to solution approaches. Actually, I am not a specialist at all in the field of prime numbers. But I object to the notion that prime numbers are “random.”

Well, I did not figure out the method to find primes without calculation. Some years ago, I watched a video, which explained this method without any derivation. I wanted to understand, how and why it works. I like to explore problems and to explain, how I understood them. This was the reason for this article.

Other methods to find prime numbers can be found in the internet. There are a lot of more theories and estimations on primes – some are serious, even from none-experts, others make me smile. However, I never saw a video or article having a chart of remainders as topic or the idea with sine waves and its possible consequences. But maybe I did not spend too much effort on searching for such content.

top


Written by Joerg Drescher, Kyiv, January 2024

    https://creativecommons.org/licenses/by-sa/4.0/