Deterministic number factorization method based on mod 6 and mod 4
ABOUT! How many wonderful discoveries to us
Prepares the enlightenment spirit,
And experience, the son of difficult mistakes,
And genius, paradoxes friend,
And the case, God is the inventor ...
A.S. Pushkin
I hope to present a solution to the problem of factorization of numbers based on the use of mod 6 and mod 4, which made it possible to find patterns in the translation of quadratic dependencies into linear ones.
')
Based on the found pattern, a technique was written which, in the author’s opinion, when writing a program, opens up the possibility of significantly reducing the time spent on factorization of numbers when using non-probabilistic deterministic methods of mathematics.
According to this method, a program was written by self-taught programmer Sergei Aleksey Belykh, which showed its effectiveness. Unfortunately, it is not adapted to large numbers. The technique is written as an algorithm for drawing up the program, with explanations. The algorithm is presented in tabular form.
Based on the correlation dependence between the coordinates of a number in modes 6 and
mod 4, provided and the correlation dependence between the numbers of the number of data modules: N6; N4.
Recall that all composite numbers are located in 4 quadrants, both when using the coordinate system of modes 6, and when using the coordinate system of modes 4.
Each table is made up of four of the 16 possible options. Why out of 16?
Each quadrant contains compound numbers characterized by 4th design variants.
The design options depend on the parity of the coordinates, and on the ratio of the coordinate values of different parity.
For more explanations on the method follow the cat.
Referring to the table containing the numbers of the first number series, the numbers of which take the form: N = 6 * xy + x + y:
Thus we can fill any cells of the table. So, the number L 1 , the number of which N 1 is in table 1 (A), can be represented as:
L 1 = 6 (6xy + x + y) + 1,
where N 1 = 6 xy + (x + y).
In this case, both coordinates of the number of this table are positive, but they can be both even and odd. We pay attention to this, since even the coordinates, as well as the sign in front of them, affect the algorithm for calculating correlation dependencies between the coordinates of the coordinate system composed of mod 6 and the coordinates of the coordinate system composed of mod 4. And as a consequence of this, the calculation of the correlation dependencies between the numbers of numbers calculated by these modules. This is the main signs that cause differences in the factorization of the options under consideration.
So, the row numbers of a table are coordinates, the sign of which depends on the number of the table in question, as well as the column numbers. The difference between the numbers of adjacent numbers in the rows is constant. The difference between increments in rows is also. For tables compiled by mod 6, this value is 6. For tables compiled by mod 4, this value is 4.
If during the compilation of table 1 (A) the values of the first quantities for calculation are: 1.2, 3.4, 5.6 ..., while compiling the table for the numbers of the first auxiliary number series, the number of which is expressed as: N sub> 3 = 6xy- xy: -1, -2, -3, -4, -5, -6 ...
For the numbers of the second auxiliary series we get:
By analogy, the tables for the second numerical auxiliary series mod 4 are also calculated.
We proceed to the consideration of a specific example.
The numbers of the number, calculated by the modules used, may belong to the same quadrant with the used coordinate system, as well as to the various quadrants. But at the same time, they are always in strict correlation dependence between themselves.
Also in the strict correlation is the product of the coordinates, their sum, and their difference, calculated according to the modules.
Let us consider the regularities of the technique on the example of L = 10525. Determine which auxiliary number series belongs to this number. The condition determining whether a number belongs to the first or second numerical auxiliary series is belonging to the (+1) class of residues of a given number mod 6, or k (-1) residue class mod 6.
N 6 = (10525-1) / 6 = 1754;
The number belongs to the first auxiliary class of numbers, meaning can belong to either the first (A) or third (C) tables.
The next step is to determine: what parity can have the coordinates of the considered number? Since the number of the number is even, then in this variant both coordinates can have the same parity. We assume that both coordinates are even. In this embodiment, the conversion factor for the value (x + y) (correction value) calculated modulo 6 into the value of correction value calculated modulo 4 is 3/2 (k 6 ).
This coefficient is memorized to compare the numerical series of correction values calculated modulo 6 and mod 4.
Based on the number of the mod 6, a numerical series of correction values mod 6 is calculated, with an interval equal to 6. The first value of a number series is the class of residues, to which the number of the considered number mod 6 belongs:
1754: 6 = 292 * 6 + 2.
Based on the obtained balance, taking into account the sign, we compile a numerical series of correction values mod 6, with an interval of 6:
Now we determine the number of the number mod 4 (similar to the definition of the number number mod 6):
N 4 = (10525-1) / 4 = 2631;
Based on the number of the mod 4, we calculate a numerical series of correction values mod 4 with an interval of 4.
The first value of a number series is the class of deductions to which the number of the considered number mod 4 belongs: (When translating a correction value, represented by a sum of even coordinates, the correction value obtained as a result of the translation retains the sign before the correction value).
2631: 4 = 657 * 4 + 3.
Based on the obtained balance, taking into account the sign, we compile a numerical series of modulo correction values with an interval of 4:
Based on the correlation coefficient 1 / k 6 , we translate the values of the numerical series of correction values calculated mod 4 into correction values mod 6:
Based on the comparison of the numerical series (1) and (2), we build a numerical series of correction values calculated mod 6, with an interval of 24:
Now, we have all the necessary data to build a numerical series Discriminant, based on a numerical series of correction values calculated in absolute value, already 24. And, if we guessed the option, and the considered number is not simple, using one of the values of the obtained numerical series of correction values and, the Discriminant corresponding to them, necessarily, will provide definition of integer coordinates of the considered number.
Indeed, based on the number of a number and a specific correction value, we can determine the expected product of the coordinates further using the Viet formula:
D = (x + y) ^ 2 / (2 ^ 2) -4 * xy;
As a result, we get:
The analysis of the patterns led to the results, for consideration of which we use the consideration of the data in Table 10-1.
Consider these tables by looking at both the columns and rows, and the results in the cells.
The first, second, and third columns contain the modified, step-by-step, correction values (a i ) used to calculate the particular Discriminant for the first, second, and third columns.
The adjustment for the first column is carried out step by step, starting with the first correction value by an amount equal to -4;
For the second column, the size of the adjustment step is increased by 24. By analogy, and for the third column. The fourth, fifth and sixth columns are calculated by the formula:
D i - [(a i ) / 2] 2 (B i )
For each line considered.
The seventh column is the difference (P) between the two calculated, taking into account the correction of correction values, the neighboring values for a particular row.
The eighth column is the quotient from dividing the first calculated corrected value of the Discriminant by the difference (P), by a specific line.
At the same time, the integer quotient obtained in the calculations, allows us to determine both the correction value equal to the sum of the coordinates, and the value y corresponding to the considered number. In the given example, 2 -3 * 24 = - y; 2 - (-3 * 24) = 74 = (x + y).
Do not think that I will give all the answers. We agree that the answer, at the moment, is the existing patterns. Without additional calculations, the true answer is difficult. For calculations, you need a program that allows you to make a change to answer emerging questions.
Based on the use of auxiliary number series in mod 6 and in mod 4. From the natural series of numbers, composite numbers have been singled out and divided into 16 groups (variants). By comparing parallel calculations, it was possible to determine: whether the number in question belongs to the estimated group of composite numbers (the proposed option).
When analyzing a number to determine if it is simple or not, the maximum number of calculations is 4th. The calculation option is discussed below. For each group of numbers, calculation algorithms are formed that formalize the analysis of numbers. To find the factors of the considered number, an alternative method has been developed for solving a quadratic equation with two unknowns. The method is based on the found regularities of converting quadratic dependencies into linear ones, which, in the author's opinion, significantly reduces the time spent on the calculation.
An alternative method for solving a quadratic equation is that, unlike the traditional method, where a solution is sought by selecting a discriminant and sequentially extracting the square roots, in the proposed method, the solution is sought by means of an integer commensurability of the corrected discriminants (D i ) and differences between them (D (i + 1) -D i ), by finding the integer quotient when dividing the first value by the second.
This approach allows the use, in the analysis of a significant number of calculations, of initial, insignificant values. For each of the calculation options, a program was compiled using the capabilities of Excel tables. According to the author, the methodology after writing the program will allow finding new regularities in the theory of numbers, which should affect, additionally, the reduction of time spent on factorization of numbers.
The problem of the actual expansion of a given number into prime factors is one of the most difficult tasks of mathematics. In the third century BC Erastofen proposed a method for finding all prime numbers lower than a given limit of A. After some improvement in the early 20th century by Brun, this method is still the only way to solve this problem without using computing devices. Other attempts to find the distribution laws of prime numbers did not yield significant results.
The proposed work is a statement of the solution to this problem, based on the laws of distribution of composite numbers.
The job is to search for signs of the difference between prime and non-simple numbers, and to use these signs to determine: whether the number is considered simple or not.
The solution of this problem is reduced by us to the solution of a quadratic equation with the 2 nd unknown. Usually, such equations are solved by selecting one of the unknowns, in our case, k, but this method, despite the fact that we have increased the increment step to 24, is rather laborious for large numbers.
Difficulty and complexity without the use of software and PC.
The ability to use PC and software, regardless of the number of characters in the number in question. In the present paper, we have created, in our opinion, a good laboratory base suitable for solving various problems from the field of number theory, for example, expressing a cube of an integer as the sum of the first and second degree terms. We know that when multiplying numbers with a significant number of digits through a group of PCs, discharges may disappear. The developed method does not require the use of a PC group, since numbers with a small number of digits are used for calculations. The only lengthy computation in which the need remains is the division of a number.
Problems with writing a program for the method under consideration led the author to the opinion that it would not be bad to try to explain in a shorter description of the principles embodied in the method. After all, this attempt will probably interest not only programmers, but also mathematicians who are not familiar with the pattern found.
Therefore, the attempt of such a presentation is based on the fact that the consideration of one of the variants of the methodology should provide an explanation of the entire work, and also of the found pattern, which can be useful also for non-programmers. When understanding the meaning of work, all parts of the methodology are comparable for understanding.
The main task of the proposed work is to determine whether a given number is L, or it is a product of at least 2 simple factors not equal to 1. In the following, the word "number" is always an integer, non-negative number, unless otherwise specified the opposite. At the first stage, we applied the modulo comparison method. *
Any number L can be represented in the form:
L = m N + r,
Where:
m is the specified module;
N - we called the number number;
r is the remainder (can be positive, negative and equal to 0), r is in the range from - (m - 1) to (m - 1) (For m = 6, from - 5 to + 5).
We choose m = 6. This gives us the opportunity to exclude from the infinite series of numbers to be analyzed the numbers in which there are 2, 3 and 6 factors, since the presence of these factors in the number is easily recognizable. All numbers that are subject to analysis, we are called hard to recognize.
Regarding module 6, all natural numbers are divided into 6 classes, depending on the remainder:
1) r = 0. L = 6 N (that is, all the numbers of this class constitute the module M itself)
2) r = 1; L = 6 N + 1, which is equivalent to r = -5; L = 6N - 5.
3) r = 2; L = 6 N + 2, which is equivalent to r = -4; L = 6N - 4.
4) r = 3; L = 6 N + 3, which is equivalent to r = -3; L = 6N - 3.
5) r = 4; L = 6 N + 4, which is equivalent to r = -2; L = 6N - 2.
6) r = 5; L = 6 N + 5, which is equivalent to r = -1; L = 6N - 1.
- * A module M is a system of all numbers that are multiples of a given number m. The number m is the smallest number of a given module M. If the numbers a and b, when divided by m, give the same residuals, then they are called comparable modulo m. This is written like this:
a Ξ b. (mod m)
This relationship between a and b is called a comparison modulo m. Every number is comparable modulo m with its remainder from dividing this number by m. For example: if a when dividing by m gives the remainder 1, then:
a Ξ 1; (mod m)
if it is necessary to add 1 to a so that the sum is divided by m, then
a Ξ -1; (mod m)
In this case, -1 is called the “negative remainder”. The numbers of two classes are of interest to us:
L (+1) = 6N + 1; L (+1) Ξ 1 (mod 6) [1],
we called them branch numbers (+1); and
L (-1) = 6N - 1; L (-1) Ξ -1 (mod 6) [2] ,.
we called them branch numbers (- 1).
These numbers are odd, not divisible by either 3 or 6; that is, it is difficult to recognize numbers. By analogy, the number is considered when using mod 4.
To systematize all the difficult numbers of the natural number series, 4 tables are compiled. For compactness in tables, we introduce not the L numbers themselves, but their N numbers. If necessary, knowing N, we can calculate L by the formulas [1], [2]. And vice versa: using the given L we can calculate its number N. All tables are made up by the principle of the tables of Pythagoras.
Consider the characteristics common to all tables. In the zero row of each table we number the columns: 1, 2, 3, 4, ... In the column of each table we number the rows: 1, 2, 3, 4 ...
Sample table:
The zero row and column of each table we take for the coordinate axis, denoting them y and x. This statement is based on the fact that all compound numbers are arranged in four tables (quadrants of a given coordinate system). The row and column numbers located on the axes of coordinates are the coordinates of the numbers of the considered number series with the corresponding sign (the coordinates of the numbers N are also the coordinates of the numbers L).
Take in any cell of the table the number N i of the number L i . The coordinates of the number N i (and the number L i ) are x i , y i . The number L i is the product of X i and Y i . We write this in a formalized form:
L i = X i Y i , where X i = 6 x i ± 1; I = 6 i ± 1 [3]
L i = 6 N i ± 1.
N i i listed in the table (see sample table).
* In the table there are cells for which x = y. These cells make up the main downward diagonal of each table. It originates from x = y = 1 and lasts to infinity.
Prepares the enlightenment spirit,
And experience, the son of difficult mistakes,
And genius, paradoxes friend,
And the case, God is the inventor ...
A.S. Pushkin
Instead of intro
I hope to present a solution to the problem of factorization of numbers based on the use of mod 6 and mod 4, which made it possible to find patterns in the translation of quadratic dependencies into linear ones.
')
Based on the found pattern, a technique was written which, in the author’s opinion, when writing a program, opens up the possibility of significantly reducing the time spent on factorization of numbers when using non-probabilistic deterministic methods of mathematics.
According to this method, a program was written by self-taught programmer Sergei Aleksey Belykh, which showed its effectiveness. Unfortunately, it is not adapted to large numbers. The technique is written as an algorithm for drawing up the program, with explanations. The algorithm is presented in tabular form.
Based on the correlation dependence between the coordinates of a number in modes 6 and
mod 4, provided and the correlation dependence between the numbers of the number of data modules: N6; N4.
Recall that all composite numbers are located in 4 quadrants, both when using the coordinate system of modes 6, and when using the coordinate system of modes 4.
Each table is made up of four of the 16 possible options. Why out of 16?
Each quadrant contains compound numbers characterized by 4th design variants.
The design options depend on the parity of the coordinates, and on the ratio of the coordinate values of different parity.
For more explanations on the method follow the cat.
Referring to the table containing the numbers of the first number series, the numbers of which take the form: N = 6 * xy + x + y:
Table 1 (A)
| y \ x | one | 2 | 3 | four |
|---|---|---|---|---|
| one | eight | 15 | 22 | 29 |
| 2 | 15 | 22 | 41 | 54 |
| 3 | 22 | 41 | 54 | 79 |
| four | 29 | 54 | 79 | 104 |
Thus we can fill any cells of the table. So, the number L 1 , the number of which N 1 is in table 1 (A), can be represented as:
L 1 = 6 (6xy + x + y) + 1,
where N 1 = 6 xy + (x + y).
In this case, both coordinates of the number of this table are positive, but they can be both even and odd. We pay attention to this, since even the coordinates, as well as the sign in front of them, affect the algorithm for calculating correlation dependencies between the coordinates of the coordinate system composed of mod 6 and the coordinates of the coordinate system composed of mod 4. And as a consequence of this, the calculation of the correlation dependencies between the numbers of numbers calculated by these modules. This is the main signs that cause differences in the factorization of the options under consideration.
So, the row numbers of a table are coordinates, the sign of which depends on the number of the table in question, as well as the column numbers. The difference between the numbers of adjacent numbers in the rows is constant. The difference between increments in rows is also. For tables compiled by mod 6, this value is 6. For tables compiled by mod 4, this value is 4.
If during the compilation of table 1 (A) the values of the first quantities for calculation are: 1.2, 3.4, 5.6 ..., while compiling the table for the numbers of the first auxiliary number series, the number of which is expressed as: N sub> 3 = 6xy- xy: -1, -2, -3, -4, -5, -6 ...
Table 3 (C)
| y \ x | one | 2 | 3 | four |
|---|---|---|---|---|
| -one | four | 9 | 14 | nineteen |
| -2 | 9 | 20 | 31 | 42 |
| -3 | 14 | 31 | 48 | 65 |
| -four | nineteen | 42 | 65 | 88 |
For the numbers of the second auxiliary series we get:
Table 2 (B)
| y \ x | one | 2 | 3 | four |
|---|---|---|---|---|
| one | 6 | eleven | sixteen | 21 |
| 2 | 13 | 24 | 35 | 46 |
| 3 | 20 | 37 | 54 | 71 |
| four | 27 | 50 | 73 | 96 |
Table 4 (D)
| y \ x | one | 2 | 3 | four |
|---|---|---|---|---|
| -one | 6 | 13 | 20 | 27 |
| -2 | eleven | 24 | 37 | 50 |
| -3 | sixteen | 35 | 54 | 73 |
| -four | 21 | 46 | 71 | 96 |
By analogy, the tables for the second numerical auxiliary series mod 4 are also calculated.
We proceed to the consideration of a specific example.
The numbers of the number, calculated by the modules used, may belong to the same quadrant with the used coordinate system, as well as to the various quadrants. But at the same time, they are always in strict correlation dependence between themselves.
Also in the strict correlation is the product of the coordinates, their sum, and their difference, calculated according to the modules.
Let us consider the regularities of the technique on the example of L = 10525. Determine which auxiliary number series belongs to this number. The condition determining whether a number belongs to the first or second numerical auxiliary series is belonging to the (+1) class of residues of a given number mod 6, or k (-1) residue class mod 6.
N 6 = (10525-1) / 6 = 1754;
The number belongs to the first auxiliary class of numbers, meaning can belong to either the first (A) or third (C) tables.
The next step is to determine: what parity can have the coordinates of the considered number? Since the number of the number is even, then in this variant both coordinates can have the same parity. We assume that both coordinates are even. In this embodiment, the conversion factor for the value (x + y) (correction value) calculated modulo 6 into the value of correction value calculated modulo 4 is 3/2 (k 6 ).
This coefficient is memorized to compare the numerical series of correction values calculated modulo 6 and mod 4.
Based on the number of the mod 6, a numerical series of correction values mod 6 is calculated, with an interval equal to 6. The first value of a number series is the class of residues, to which the number of the considered number mod 6 belongs:
1754: 6 = 292 * 6 + 2.
Based on the obtained balance, taking into account the sign, we compile a numerical series of correction values mod 6, with an interval of 6:
2 8 14 20 26 32 38 44 … (1)
Now we determine the number of the number mod 4 (similar to the definition of the number number mod 6):
N 4 = (10525-1) / 4 = 2631;
Based on the number of the mod 4, we calculate a numerical series of correction values mod 4 with an interval of 4.
The first value of a number series is the class of deductions to which the number of the considered number mod 4 belongs: (When translating a correction value, represented by a sum of even coordinates, the correction value obtained as a result of the translation retains the sign before the correction value).
2631: 4 = 657 * 4 + 3.
Based on the obtained balance, taking into account the sign, we compile a numerical series of modulo correction values with an interval of 4:
3 7 11 15 19 23 27 31 35 39…
Based on the correlation coefficient 1 / k 6 , we translate the values of the numerical series of correction values calculated mod 4 into correction values mod 6:
2 4,666 7,333 10 12,666 15,333 18 20,666 26 … (2)
Based on the comparison of the numerical series (1) and (2), we build a numerical series of correction values calculated mod 6, with an interval of 24:
2 26 50 74 98 …
Now, we have all the necessary data to build a numerical series Discriminant, based on a numerical series of correction values calculated in absolute value, already 24. And, if we guessed the option, and the considered number is not simple, using one of the values of the obtained numerical series of correction values and, the Discriminant corresponding to them, necessarily, will provide definition of integer coordinates of the considered number.
Indeed, based on the number of a number and a specific correction value, we can determine the expected product of the coordinates further using the Viet formula:
D = (x + y) ^ 2 / (2 ^ 2) -4 * xy;
As a result, we get:
-291 -119 341 1089 2125 3449 5061 6961
The analysis of the patterns led to the results, for consideration of which we use the consideration of the data in Table 10-1.
Consider these tables by looking at both the columns and rows, and the results in the cells.
The first, second, and third columns contain the modified, step-by-step, correction values (a i ) used to calculate the particular Discriminant for the first, second, and third columns.
The adjustment for the first column is carried out step by step, starting with the first correction value by an amount equal to -4;
For the second column, the size of the adjustment step is increased by 24. By analogy, and for the third column. The fourth, fifth and sixth columns are calculated by the formula:
D i - [(a i ) / 2] 2 (B i )
For each line considered.
The seventh column is the difference (P) between the two calculated, taking into account the correction of correction values, the neighboring values for a particular row.
The eighth column is the quotient from dividing the first calculated corrected value of the Discriminant by the difference (P), by a specific line.
At the same time, the integer quotient obtained in the calculations, allows us to determine both the correction value equal to the sum of the coordinates, and the value y corresponding to the considered number. In the given example, 2 -3 * 24 = - y; 2 - (-3 * 24) = 74 = (x + y).
Do not think that I will give all the answers. We agree that the answer, at the moment, is the existing patterns. Without additional calculations, the true answer is difficult. For calculations, you need a program that allows you to make a change to answer emerging questions.
Table 10-1
| y \ x | one | 2 | 3 | four | five | 6 | 7 | eight |
|---|---|---|---|---|---|---|---|---|
| one | 2 | 26 | 50 | -292 | -288 | -284 | four | -73 |
| 2 | 22 | 46 | -292 | -240 | -188 | 52 | 52 | -5,615 |
| 3 | -6 | 18 | 42 | -300 | -200 | -100 | 100 | 3 |
| four | -ten | 14 | 38 | -316 | -168 | -20 | 148 | -2,135 |
Annotation to the method
Based on the use of auxiliary number series in mod 6 and in mod 4. From the natural series of numbers, composite numbers have been singled out and divided into 16 groups (variants). By comparing parallel calculations, it was possible to determine: whether the number in question belongs to the estimated group of composite numbers (the proposed option).
When analyzing a number to determine if it is simple or not, the maximum number of calculations is 4th. The calculation option is discussed below. For each group of numbers, calculation algorithms are formed that formalize the analysis of numbers. To find the factors of the considered number, an alternative method has been developed for solving a quadratic equation with two unknowns. The method is based on the found regularities of converting quadratic dependencies into linear ones, which, in the author's opinion, significantly reduces the time spent on the calculation.
An alternative method for solving a quadratic equation is that, unlike the traditional method, where a solution is sought by selecting a discriminant and sequentially extracting the square roots, in the proposed method, the solution is sought by means of an integer commensurability of the corrected discriminants (D i ) and differences between them (D (i + 1) -D i ), by finding the integer quotient when dividing the first value by the second.
This approach allows the use, in the analysis of a significant number of calculations, of initial, insignificant values. For each of the calculation options, a program was compiled using the capabilities of Excel tables. According to the author, the methodology after writing the program will allow finding new regularities in the theory of numbers, which should affect, additionally, the reduction of time spent on factorization of numbers.
Question state (introduction to the method)
The problem of the actual expansion of a given number into prime factors is one of the most difficult tasks of mathematics. In the third century BC Erastofen proposed a method for finding all prime numbers lower than a given limit of A. After some improvement in the early 20th century by Brun, this method is still the only way to solve this problem without using computing devices. Other attempts to find the distribution laws of prime numbers did not yield significant results.
The proposed work is a statement of the solution to this problem, based on the laws of distribution of composite numbers.
The job is to search for signs of the difference between prime and non-simple numbers, and to use these signs to determine: whether the number is considered simple or not.
The solution of this problem is reduced by us to the solution of a quadratic equation with the 2 nd unknown. Usually, such equations are solved by selecting one of the unknowns, in our case, k, but this method, despite the fact that we have increased the increment step to 24, is rather laborious for large numbers.
Lack of method
Difficulty and complexity without the use of software and PC.
Virtue of the method
The ability to use PC and software, regardless of the number of characters in the number in question. In the present paper, we have created, in our opinion, a good laboratory base suitable for solving various problems from the field of number theory, for example, expressing a cube of an integer as the sum of the first and second degree terms. We know that when multiplying numbers with a significant number of digits through a group of PCs, discharges may disappear. The developed method does not require the use of a PC group, since numbers with a small number of digits are used for calculations. The only lengthy computation in which the need remains is the division of a number.
Problems with writing a program for the method under consideration led the author to the opinion that it would not be bad to try to explain in a shorter description of the principles embodied in the method. After all, this attempt will probably interest not only programmers, but also mathematicians who are not familiar with the pattern found.
Therefore, the attempt of such a presentation is based on the fact that the consideration of one of the variants of the methodology should provide an explanation of the entire work, and also of the found pattern, which can be useful also for non-programmers. When understanding the meaning of work, all parts of the methodology are comparable for understanding.
The purpose of writing techniques
The main task of the proposed work is to determine whether a given number is L, or it is a product of at least 2 simple factors not equal to 1. In the following, the word "number" is always an integer, non-negative number, unless otherwise specified the opposite. At the first stage, we applied the modulo comparison method. *
Any number L can be represented in the form:
L = m N + r,
Where:
m is the specified module;
N - we called the number number;
r is the remainder (can be positive, negative and equal to 0), r is in the range from - (m - 1) to (m - 1) (For m = 6, from - 5 to + 5).
We choose m = 6. This gives us the opportunity to exclude from the infinite series of numbers to be analyzed the numbers in which there are 2, 3 and 6 factors, since the presence of these factors in the number is easily recognizable. All numbers that are subject to analysis, we are called hard to recognize.
Regarding module 6, all natural numbers are divided into 6 classes, depending on the remainder:
1) r = 0. L = 6 N (that is, all the numbers of this class constitute the module M itself)
2) r = 1; L = 6 N + 1, which is equivalent to r = -5; L = 6N - 5.
3) r = 2; L = 6 N + 2, which is equivalent to r = -4; L = 6N - 4.
4) r = 3; L = 6 N + 3, which is equivalent to r = -3; L = 6N - 3.
5) r = 4; L = 6 N + 4, which is equivalent to r = -2; L = 6N - 2.
6) r = 5; L = 6 N + 5, which is equivalent to r = -1; L = 6N - 1.
- * A module M is a system of all numbers that are multiples of a given number m. The number m is the smallest number of a given module M. If the numbers a and b, when divided by m, give the same residuals, then they are called comparable modulo m. This is written like this:
a Ξ b. (mod m)
This relationship between a and b is called a comparison modulo m. Every number is comparable modulo m with its remainder from dividing this number by m. For example: if a when dividing by m gives the remainder 1, then:
a Ξ 1; (mod m)
if it is necessary to add 1 to a so that the sum is divided by m, then
a Ξ -1; (mod m)
In this case, -1 is called the “negative remainder”. The numbers of two classes are of interest to us:
L (+1) = 6N + 1; L (+1) Ξ 1 (mod 6) [1],
we called them branch numbers (+1); and
L (-1) = 6N - 1; L (-1) Ξ -1 (mod 6) [2] ,.
we called them branch numbers (- 1).
These numbers are odd, not divisible by either 3 or 6; that is, it is difficult to recognize numbers. By analogy, the number is considered when using mod 4.
Compilation of tables, including the numbers of all non-prime numbers of the 1st auxiliary number series
To systematize all the difficult numbers of the natural number series, 4 tables are compiled. For compactness in tables, we introduce not the L numbers themselves, but their N numbers. If necessary, knowing N, we can calculate L by the formulas [1], [2]. And vice versa: using the given L we can calculate its number N. All tables are made up by the principle of the tables of Pythagoras.
Consider the characteristics common to all tables. In the zero row of each table we number the columns: 1, 2, 3, 4, ... In the column of each table we number the rows: 1, 2, 3, 4 ...
Sample table:
| y \ x | one | 2 | 3 | four | y i | |
|---|---|---|---|---|---|---|
| one | x | |||||
| 2 | x | |||||
| 3 | x | |||||
| four | x | |||||
| ... | x | |||||
| x i | N i |
The zero row and column of each table we take for the coordinate axis, denoting them y and x. This statement is based on the fact that all compound numbers are arranged in four tables (quadrants of a given coordinate system). The row and column numbers located on the axes of coordinates are the coordinates of the numbers of the considered number series with the corresponding sign (the coordinates of the numbers N are also the coordinates of the numbers L).
Take in any cell of the table the number N i of the number L i . The coordinates of the number N i (and the number L i ) are x i , y i . The number L i is the product of X i and Y i . We write this in a formalized form:
L i = X i Y i , where X i = 6 x i ± 1; I = 6 i ± 1 [3]
L i = 6 N i ± 1.
N i i listed in the table (see sample table).
* In the table there are cells for which x = y. These cells make up the main downward diagonal of each table. It originates from x = y = 1 and lasts to infinity.
Source: https://habr.com/ru/post/301094/
All Articles