Prime numbers

The author of the article proposes to look at what are the sets of prime numbers, if you look at them in a geometric way. This is not a professional job, but a simple, amateurish study of some interesting patterns. Therefore, the article will not be difficult mathematics, and we will not climb deep into its jungle. In general, if you are not very familiar with prime numbers, their structure and centuries-old research in the field of number theory, this article is for you.



I emphasize especially for qualified mathematicians and those readers who consider themselves to them: the article is not a professional work. This is an illustration of some properties and patterns of composite numbers, solely for clarity and identifying the emphasis on the patterns of structure, which can then be expressed analytically
')
Probably, the reader is aware of many problems associated with prime numbers. Their location in the set of natural numbers is not obvious. Large primes are hard to find, it takes a lot of effort to test a large number for simplicity. Many modern cryptography methods are based on this difficulty. We can easily multiply and multi-valued primes, but knowing the result, finding the original factors is a very difficult task.

There are many optimization methods that are much faster than a simple search, but even if the optimization speeds up the search by 10 times, it is enough to increase the number by 2 decimal places (that is, 100 times) to slow down the search by 100 times.

This means that the complexity of the algorithm is exponential, and therefore, no matter how fast the supercomputer is, we can choose the length of the number even more so that such supercomputers need a billion. True, it is worth clarifying again: to find simple numbers for multiplication, it also becomes more and more difficult.

By the way, mathematicians did not find any proof or refutation of the fact that it is impossible to find a factorization algorithm, the complexity of which would not be exponentially dependent on the length of the number. But by proving or disproving this, as some mathematicians believe, it may be possible, at the same time, to solve a mathematical problem known as the Riemann hypothesis. For her proof, Clay's mathematical institute promises a million dollars. Although it may turn out that the factorization problem will turn out to be polynomial, but the Riemann hypothesis will neither prove nor deny it.

Do numbers cast shadows?

Since we do not know the patterns by which simple numbers would easily be found, maybe we will take a closer look at the patterns of composite numbers? Speaking mathematically, consider the set of natural numbers, additional to the set of simple.

The idea of ​​compound numbers is very simple. Take some natural numbers and multiply them. Thus, we get a composite number.

We can easily find the infinity of composite numbers simply by multiplying n by 2.



The same applies to multiplication by 3.



This is followed by 4, but here we will not find new numbers, all of them are already equal to 2n. Then follow 5n, then 6n, which we have already found twice, as 2n and 3n at the same time. This does not increase the number of composite numbers, but leads us to believe that the regularity of composite numbers lies in the product of simple.

But if we go a little further, we find an interesting pattern: the number 6 is a product of 2 and 3. This means that we will have many conveniently located in the table of composite numbers:



Looking at the table, we understand that in lines 2, 3, 4 and 6 there can never be prime numbers. This means that the probability of finding a prime number cannot exceed 2/6. We understand that the numbers of this probability is even smaller, but how much?

Let's try and continue to look for a convenient structure of composite numbers, and for this, let us think, what does 2x3 = 6 mean? What if we take the work of 2x3x5 as a basis? We get the following interesting table (so that it does not take up much space, reduce the font):



We see that:
- 15 lines of type 2n,
- 5 lines of type 3n (plus 5 types of 6n are already taken into account in 2n)
- and 2 lines of the form 5n (three more types of 10n are already crossed out in the numbers 2n and one 15n among the lines 3n)
cannot contain prime numbers (we expected this, right?)

Only eight lines of the form 30n + i remain, where i = 1, 7, 11, 13, 17, 19, 23, 29. If you look closely, you can see symmetry in them. 1 + 29 = 7 + 23 = 11 + 19 = 13 + 17.

Therefore, we can compactly write as 30n + - i, where i = 1, 7, 11, 13,17

And we understand that the probability of finding an arbitrary prime number is not greater than 8/30. On 2/30 it became less ...

What next? Following the logic, the following table should be 2x3x5x7 = 210 lines. Even further 210x11 = 2310, then 2310x13, and so we will consistently multiply simple numbers, getting more and more baseline "line scan", which will keep its banding.

It looks as if prime numbers cast “shadows” at infinity of multiples of numbers, if they are arranged in a row according to the base of the number, we denote it by P (i), equal to the successive product of i prime numbers.

You can see that the line of lines lying between the first and the next, which may contain prime numbers, grows according to a very simple law: if there are 6 lines, that is, 2x3, then simple numbers can be in line 5, if 2x3x5, then starting from line 7 that is logical. Thus, in the matrix with the number of rows 30,030 (2x3x5x7x11x13) after the first row there will be a wide band of composite numbers, up to the row following the number 17. And if we take the matrix for 9,699,690 rows (2x3x5x7x11x13x17x19), then the band with prime numbers no, it will stretch to line 21. What is characteristic, due to symmetry, at the bottom of the matrix there will also be 20 lines with exclusively composite numbers.

Multidimensional matrices and hyper-realistic fractals?

But what are these works? 2x3 is a rectangle with an area of ​​6. 2x3x5 is a parallelepiped with a volume of 30. And then? 2x3x5x7 - hyper-parallelepiped in 4 dimensions, with a hyper volume of 210? And then? 5 measurements, 6, ... infinity?

Just think that you could imagine a multidimensional world in which simple numbers cast their shadows in all dimensions ...

We can imagine four or more dimensions, projections of them onto a plane or into three-dimensional space, for example, spreading out a matrix, as if rolling a multidimensional hypercube from a face to the face and looking at the prints on paper (as well as getting section prints).

Here is the starting line:



But its sweep from two sides:



It is very fortunate that in the entire right hyperplane we have exclusively composite numbers. We can not even travel to it. You can look at another scan, a look from above, but then we will go in a more interesting direction.



Let us now try to expand the image into the fourth dimension, in the direction we are interested in, where we can find prime numbers:



Here, the brown color indicates the numbers of the form mn, which are composed of products of numbers from 11 to 19 (the nearest integer, less than 210/11). The peculiarity of these numbers is that, while they themselves are not prime numbers, they do not “cast shadows” into the next dimension.

As we see, the middle sweep layer again becomes trivial - here and further there are no primes. But the outer edges of the hyperpallelapiped can be considered further. Each column is decomposed into a 7x11 matrix, we get 5 such matrices for each of the three 3x5 matrix layers (a scan of one column and a matrix fragment for the second column are shown here):



We will not go further into measurements on the example of a sweep; within the framework of this article it would be unwise. At the end of the article you can look at a few more illustrations. I hope this study has a little awakened your imagination, and the journey into the world of complicated and simple numbers you liked and seemed useful.

Conclusion

In addition, the author wants to note that he continues the study of this method. For example, questions about the appearance in third-party matrices of third, fourth, and further degrees of numbers that add all new prime numbers in deep and three-dimensional projections, both casting shadows on the next dimensions and remaining “dotted” intersperses.

But perhaps the greatest interest is the possibility of refining the estimate of the probability of finding primes farther and farther away. If we consider the matrix, then we see how the probability falls, starting with 4/6, further to 7/24 (or 11/30 averaged), then 36/180 (or 47/210), etc.

In addition, the author has a factorization algorithm, the optimization of which in a multidimensional matrix can speed it up noticeably (but this does not cease to have an exponential degree of complexity depending on the number of digits of the decomposable number).

The algorithm itself is very basic.

We take two consecutive odd numbers, p and q, such that pq is close to X (rounding the root from X to larger and smaller odd numbers is used, provided that X is not a square). We first eliminate the parity of X (divide by 2 until the result is even), getting the factor 2 ^ K. Further, in the cycle, we check the difference between X and pq. If it is zero, the result is obtained. If it is greater than zero, we decrease q by 2. If it is less than zero, increase p by 2q. The cycle uses only addition, so the algorithm is quite fast (it depends only on the implementation of functions working with BigInteger).

However, the author has a hypothesis that the conversion step can be significantly increased, without losing in accuracy, if you use the multiplicity base. Each number X is between two consecutive P (i) and P (i + 1), where P (i) is the product of the first i prime numbers, so you can determine to which of the edges the number X is closer and which range of freedom y p and q in each of the projections) and thus a rectangle formed from p and q from one plane to expand into the section of the hyper-parallelepiped.

PS And what is the secret society of weavers, the reader will ask, who was attracted by the original title? Perhaps the reader remembers the film “Wanted”. This year they even promise to continue ... In this film, the loom makes predictions, putting the threads and knots ... Look at how simple threads make it look like ...

In the matrix 30x7:



And a piece of matrix 210x11:



But the knots of this machine are controlled by such matrix punch cards. 2x3 matrix sweep:



And more, 6x5 matrices: