Two special models for splitting numbers
Two special partitions of the natural number N can be used in the construction of the factorization algorithm. In previous posts, this was discussed and the author was asked questions. In the works on factorization, it was stipulated that the approach under consideration gives a fundamental opportunity to solve the problem of factoring large numbers (SFCH) in a short time with a program that generates special partitions. In this paper, the author reveals in more detail the specifics of the specialty of partitions. Since the members of the Habra community are mostly programmers, I suggest that anyone who shows an interest in ZFBCH, solved in a reasonable time (not for years, not months, or even dozens of hours), try their hand and apply skills to develop a partitioning program. As follows from the text below, it is necessary to have a f-invariant of the number N, a property that does not depend on the digit capacity of the number, or the number N itself. The comments show a table of all partitions of the number 13, of which only 4 are special, any of the first three special splits.
The problem of splitting a natural number
A partition of a natural number N is called a finite non-increasing sequence of natural numbers k0, k1, k2, k3, ..., kt less than N, for which the sum k0 + k1 + k2 + k3 +, ..., + kt = N, numbers k i , i = 0 (1) t, are called partitioning blocks (parts). Number splits are ordered and unordered. There are splits of numbers [1, 2] into odd and separately into even parts, splits of numbers into identical and different parts, etc. For our purposes, we will use a graphical representation of the division of numbers into different parts with the restriction on the difference (β = 1) of one part of the partition from another, for which we use the Ferrer point graph.
In the problem of splitting the number N, which is associated with the problem of factoring numbers, they deal with two special cases of partitions not of the number N itself, but of its Ο-invariant, the number kn (N) / 2, that is, half of the number of the limit contour for N. In addition, we will distinguish the partitions of the number kn (N) / 2, the corresponding integer and fractional numbers, and the corresponding left (Nl) and right (Nn) odd natural numbers. A graphical representation of the set of partitions of the partitions of the numbers kn (N) / 2 has the form of a trapezium as an integral part of the triangular Ferrere dotted diagram formed from its successive following lines. One of the bases of the trapezium (upper or lower) always includes only half of its points. The main specialization of the two types of partitions considered here is that the difference between the parts of the number splitting one from the other is only one β = 1, and only the extreme parts (lines that are the bases of the trapezoid of the graphical representation) of the number splitting may differ from the neighboring ones by an amount greater than unit. The last line (top - for Nl, bottom - for Np) is always split in half. You can also read about the terms in the partitions (here) . If the line to be split in half contains an even number of points, then all parts of the partition of the number N are integers, if the number of points in such a line is odd, then the extreme part of the partition and k n (N) / 2 itself is a fractional number. We also note some other features of these special partitions. These features are easily and visually perceived when considering numerical examples, which in essence are the main content of the work.
First, for Nn (the right number), the kn (N) / 2 representation of a partition is always formed only by different terms, and only half of its number is included in the sum from the smaller contour.
Secondly, for NL (left number), the representation of half the number of the limit contour (the numbers kn (N) / 2) by splitting is always formed by different parts, if kn (N) / 2 is a fractional number.
Thirdly, for Nl, if kn (N) / 2 is an integer, then the two terms in the sum may coincide, and one term from such a pair is half the number of the larger contour in the sum. Let us explain these concepts by a numerical example.
')
Example 1 An odd left number Nl = 119 is specified, since 119 = 3 (mod4). The limit contour for this number has a length of 119 + 121 = 240. The number of the limit contour is kn (119) = 240/8 = 30. The F-invariant for the number 119 is equal to kn (119) / 2 = 30/2 = 15. Splitting The Ο-invariant for the number N has the form 15 = 3 + 4 + 5 + 6/2 = 3 + 4 + 5 + 3. In the total, we got two identical terms equal to three. To make sure that the splitting of the f-invariant leads to the factorization of the number N = 119, we reconstruct N by the splitting, all the terms of which are the numbers of the contours. Multiply the terms by 8:
3 β’ 8 + 4 β’ 8 + 5 β’ 8 + 6 β’ 8 = 24 + 32 + 40 + 48.
The last (larger) addend must give only its left semi-contour 23 + 25 = 48 in sum, i.e. 23. So, set the length of the interval for Nl = 119 (check) 24 + 32 + 40 + 23 = 119.
It remains to recall that the boundaries of contours and half-contours in the NPS are always squares and get their values ββat the extreme components of the interval:
smaller border GM (3) for the circuit with the number 3, GM (3) = (2 β’ 3-1) 2 = 25 = 5 2 ;
a large boundary of the interval GB (6) for the contour with the number 6, GB = Hz (6) = (2 β’ 6) 2 = 144 = 12 2 - the right border of the left semi-contour of the sixth contour.
The final touch: N is the difference of squares, i.e. interval difference
N = 12 2 - 5 2 = (12 - 5) (12 + 5) = 7 β’ 17 = 119 and we get the factorization.
Natural odd numbers N (x1, x) = 3t multiples of three are always formed by only three adjacent semi-circuits, two of which are the whole contour. For such numbers, the numbering model is quite simple. Find k - the number of the full contour for the number N.
For left odd numbers
kn (N) / 2 = (k + 1) / 2 + k => kn (N) = 3k + 1 => k = (kn (N) - 1) / 3.
For right odd numbers
kn (N) / 2 = (k β1) / 2 + k => kn (N) = 3k - 1 => k = (kn (N) + 1) / 3.
Example 2 Given the right odd number N = 129, since 129 = 1 (mod4). The limit contour for this number is 127 + 129 = 256. The number of the limit contour is kn (129) = 256/8 = 32. The F-invariant for the number 129 is equal to kn (129) / 2 = 32/2 = 16. We substitute in the formula, the found values ββare k = (32 + 1) / 3 = 11. This is the number of the larger contour of the two semi-contours 43 + 45 = 88 = 11 β’ 8. To form the interval, we include in the sum a semi-contour from the previous contour with the number 11-1 = 10, i.e. M = 4k +1 = 41.
And finally, the sum of the semi-contours 41+ 43 + 45 = 129. It remains to find the limits of the interval and factorize the number N = 129.
All terms in the sum of partitions, except for one extreme term, always differ by one, i.e. these are the numbers k i , following in the natural series one after another k (N) / 2 = β t i = p k i Β± k / 2,
where p is the index of the integer number of the initial (smaller) contour;
t is the index of the integer number of the final (larger) contour;
Β± - the sign in the sum is determined by the form (left k> k t , right k <k p ) of the number N;
k is the number of the extreme contour (without an index), from which only half of the number takes part in the total. The fact that the sum in the division of the number kn (N) / 2 is formed by natural numbers increasing by 1 is crucial for the numerical model of a natural number.
All partitions of this type (all sums kn (N) / 2) are represented in the triangular dot Ferrer diagram (a graphical representation of the partition) and can be obtained from it.
We present table 1 with such a diagram, accompanying it with additional information about the interval and numbering models of the number N.
Table 1 - Characteristics of the interval and numbering models of the number N
In the middle part of the table, the value of the graphical splitting of the limiting semicontour k n (N) / 2) for the number 231 = 3 β 77 = 7 β 33 = 11 β 21 into different parts (rows with dots) that differ from one another is placed. The smaller divider always shows how many half-contours form the interval of the number N.
The interval model is the interval of the positions (lengths) of contours / semi-contours, the sum of which is equal to N.
So for N = 231, we have:
1st interval model 1 contour + semi-contour 152 + 79 = 75 + 77 + 79 - three consecutive semi-contour, which differ in length by two units.
2nd interval model 3 contours + semi-contour 56 + 64 + 72 + 39 = 27 + 29 + 31 + 33 + 35 + 37 +39 - seven consecutive next contours, which differ in the length of two units.
3rd interval model of 5 contours + semi-contour
24 + 32 + 40 + 48 + 56 + 31 = 11 + 13 + 15 +17 +19 +21 + 23 + 25 + 27 + 29 +31
- eleven consecutive semi-circuits that differ in length of two units.
The numbering model is a set of numbers of contours and semi-contour, which describe the number N, the sum of which is equal to the value of the Ξ¦-invariant.
So for the number N = 231, the f-invariant is equal to kn (N) / 2 = kn (231) / 2 = 29.
kn (N) / 2 = kn (231) / 2 = 19 + 20/2 = 7 + 8 + 9 + 10/2 = 3 + 4 + 5 + 6 + 7 + 8/2.
Equality sums are three numbering models. The terms correspond to the lines of the k diagram.
Both types of models are closely related and can be transformed one into another if necessary.
For odd natural numbers N within the first thousand, on the basis of this diagram, factoring them into two factors can be carried out. The first four columns of the table contain the characteristics of the interval model (characteristics of the contours). The column to the right of the scatter plot is the contour number. The last two columns are the characteristics of the numbering model. The level is called the nth row of the table below. The values ββof the characteristics in the rows are given with the increase from the bottom line up. In the last column, the sums of points from the preceding lines are summarized with half the number of points of the current line. In the last but one column of the sum of points of full rows
For left NL numbers, such sums k p / 2, corresponding to intervals of length NL, always contain a certain number of points and lines from a triangle and in the upper part only half the number of points of a line. Obviously, if we fix a line from the sum to which a value equal to k p / 2 corresponds or the nearest greater, but also containing half of the top line, then for deciding on the number of the bottom line in the sum, it remains to determine only the number of the lower (smaller) contour or the corresponding line forming sum k p / 2. This value is determined by the difference between the sum of points for the level of the fixed upper line and the value of k p / 2. If such a difference is present in the column in question, then the line corresponding to it and the lines below it are not taken into account in the sum.
The search for the difference C 2 k + 1 - k p / 2 starts from the value C 2 k + 1 > k p / 2, and compare the calculated difference with k 2/2, until they coincide. If there is a mismatch, increase the value of k.
Example 3 For the right number N (x1, x) = 621, perform factorization, determine the value of the length of the limit contour of the numbers kn (Nn) = kn (621) = (621β1) / 4 = (619 + 621) / 8 = 155. Then we determine the value of k p (621) / 2 = 77.5 and find the value of the difference C 2 k + 1 - k p / 2, closest to the beginning of the NPS. In the column C 2 k + 1 of table 1 we find, for k = 12, the value 78, which exceeds k n (621) / 2 = 77.5.
Then the desired difference C 2 k + 1 - k p / 2 = 78 - 77.5 = 0.5. We check whether the found difference coincides with the value of k 2/2 for a certain value of k. The match occurs with a value of 0.5 in the bottom row of the table.
From this, the number of the smaller contour k p 2/2 = 0.5 => k = 1 of the interval being formed is determined. The interval, representing the number N = 621, begins with a point of the mean square (even) of the first contour and reaches the 12th contour, inclusive. It is known that through the values ββof the boundaries, the length of the interval for the number N is represented by the expression N = - = 1i 2 - i 2 . Knowing the numbers of contours on the boundaries of the interval, we find its boundary points. The boundaries of the interval will be:
β’ left border with k = 1, Ch = (2k) 2 = (2 β’ 1) 2 = 4,
β’ the right one with k = 12 is = (2k + 1) 2 = (2 β’ 12 + 1) 2 = 625.
Then N = - = 1i 2 - i 2 = 625 - 4 = 621. On the other hand, in the presence of square boundaries, the factorization of the number N = x1i 2 - i 2 = (25 + 2) (25 - 2) = 27 β’ 23.
The scheme of solving the factorization problem considered in the example ensures the finding of other alternative pairs of boundaries. The search for the difference C 2 k + 1 - k p / 2, which coincides with k 2/2 results in such a coincidence with larger k = 19. We have the equality C 2 k + 1 - k p / 2 = 190 - 77.5 = 112 , 5 of which we find the least, i.e. k = β2 Γ 112.5 = β225 = 15. Now you can start searching for the boundaries of the interval and factorization N.
The boundaries of the interval will be:
β’ left border at k = 15, Gl = (2k) 2 = (2 β’ 15) 2 = 900,
β’ the right one with k = 19 is = (2k + 1) 2 = (2 β’ 19 + 1) = 392 = 1521,
β’ N = - Gl = 1i 2 - i 2 = 1521 - 900 = 621 and
β’ N = 1i 2 - i 2 = (39 + 30) (39 - 30) = 69 β’ 9.
Example 4 ( Splitting the left number, where half the number (not an integer) in the sum is taken from the larger contour ).
Let the number N = 235 be given, the number N = 235 β‘ 3 (mod4) left.
The length of the limiting contour is Ln = 235 + 237 = 472, its number is kn = L / 8 = 472/8 = 59, kn / 2 = 29.5, the values ββof the limits of the limiting contour: right Hn = (2kn) 2 = 1182, left Ch = (2k n β1) 2 = 117 2; they correspond to the trivial decomposition of the number N = 235 1.
From the numbering model, it follows that k p / 2 = 29.5. For N = 235 (see example earlier) k n (235) / 2 = 29.5
The nearest value in the column k 2/2 = 40.5 lies in the line k = 9.
It corresponds to the difference k 2/2 - k p / 2 = 40.5 - 29.5 = 11, which is absent in the column βsumβ.
The next level is k = 11 and k 2/2 = 60.5, it corresponds to the difference k 2/2 - k p / 2 = 60.5 - 29.5 = 31, which is also absent in the βsumβ column. The next level is k = 13 and k 2/2 = 84.5, it corresponds to the difference
k 2/2 - k p / 2 = 84.5 - 29.5 = 55, which is present in the column "sum" in the row with the number k = 10.
Hence the conclusion that all lines, starting with the number 10 and below, are not included in the sum k p / 2. Therefore, k p / 2 = 29.5 = 11 + 12 + 13/2.
Perform factorization of a given number. The numbers of contours that form the numbering model of a number are found: k = 11, 12, and 13. From k = 13, only the left half of this contour is included in the formula.
We calculate the lengths of the contours L (11) = 8 β’ 11 = 88; L (12) = 8 β’ 12 = 96; L (13) = 8 β’ 13 = 104; the left half of the 13th circuit m (13) = 104/2 β1 = 51. The interval model 88 + 96 + 51 = 43 + 45 + 47 + 49 + 51 = 235.
Define the boundaries of the interval model:
β’ (13) = (2 β’ 13) 2 = 26 2 = 676;
β’ Ch (11) = (2 β’ 11β1) 2 = 21 2 = 441.
Now the number N = 235 can be factorized.
N (x1, x) = 235 = (x1 + x) (x1 - x) = (26 + 21) (26β21) = 47 β’ 5 = 235.
Example 5 (The splitting of the right number, where half of the number (not an integer) in the sum is taken from the smaller contour ).
Let N = 357 This is the right number N = 357 β‘ 1 (mod4). The length of the limit contour is Ln = 357 + 355 = 712, its number is k = L / 8 = 712/8 = 89, k / 2 = 44.5, borders limit contour:
β’ Left Ch = (2k n β1) 2 = 177 2 ,
β’ average Hz = (2k n ) 2 = 178 2 ,
β’ right = (2k + 1) 2 = 179 2 they correspond to the trivial decomposition of the number N = 357 1.
a) x1 = 19; ho = 2; N = (2 β 58) - Ch (58 β 2 - 1) = 1i 2 - ii = 19 2 - 2 2 = 361 - 4 = (19 + 2) (19 - 2) = 21 β 17 = 357, k p / 2 = Β½ + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 44.5
b) x1 = 61; ho = 58; N = (2 β 58) - Ch (58 β 2 - 1) = 1i 2 - i 2 = 61 2 - 58 2 = 3721 - 3364 = (61 + 58) (61 - 58) = 119 3 = 357; k p / 2 = 29/2 + 30 = 44.5.
The length of an arbitrary contour and the interval of the natural number series between odd squares is a multiple of 8. The odd square deduction modulo 8 is 1. The difference of the squares of odd primes β₯ 5 is always a multiple of 24 (7 2 - 5 2 = 24). This can be shown as follows. Consider the squares of two odd primes, and then find their difference. Of the three adjacent numbers 2n - 1, 2n, 2n + 1, one is always a multiple of three. In our case, this number is n = 3t, since the extreme numbers are simple by condition.
β’ 1 2 = (2n - 1) 2 = 4n 2 - 4n + 1 = 1 + 4n (n - 1) = 1 + 8 C n 2 ,
β’ 2 2 = (2n + 1) 2 = 4n 2 + 4n + 1 = 1 + 4n (n + 1) = 1 + 8 2 n + 1 ,
β’ 2 2 - 1 2 = 8 ( 2 n + 1 - C 2 ) = 4n (n + 1 - n + 1) = 8n = 8 Β· 3t = 24t.
If the number N is a multiple of 3, it is formed in the interval model by three semi-circuits standing side by side. In other words, if the number is right, then the semi-contour from the smaller contour. For N = 357 = 119 β’ 3, k p / 2 = 44.5. The value of the number of the semi-circuit is determined by the formula (k p / 2 β1) / 3 = (44/5 - 1) / 3 = 14.5. Therefore, the number of the smaller contour is 14.5 β’ 2 = 29, and the number of the next 30. Indeed, 29/2 +30 = 44.5 = k p / 2. If the number N is a multiple of 5 (formed by five half-contours), then the number (k p / 2 - 6) / 5.
Example 6 ( Interrelation of characteristics of interval and numbering models of a multiple of three )
For the left number N (x1, xo) = 183 and the right number N (x1, xo) = 189, perform factorization, determine the number and length of the limit contour of the numbers kn (Nl) = kn (183) = (183 + 185) / 8 = 46, and k p (N) = k p (189) = (187 + 189) / 8 = 47. Next, we make the equation for the number of the limiting semicontour in the numerical model k p (183) / 2 = (k + 1) / 2 + k, whence kn = 3k + 1 and k = (kn - 1) / 3 = 45/3 = 15.
β’ Large interval boundary for N = 183 right even Hz (16) = (2 Β· 16) 2 = 32 2 = 1024
β’ the smaller left border of Ch (15) = (2 β’ 15 - 1) 2 = 29 2 = 841.
The factorization of the number N = 183 = 32 2 - 29 2 = (32 + 29) (32 - 29) = 61 β’ 3.
The connection of right numbers of the form N (x1, x) = 3t with the sum of the contour numbers of the interval model is as follows:
the half of the contour number plus the number of the next contour of the interval is equal to the half of the number of the limit contour kn (Np) / 2 of the investigated number.
For the right number N (x1, x) = 189, the value of the limiting semicontour k n (189) / 2 = (k β 1) / 2 + k,
whence kn = 47 = 3k - 1 and k = (kn + 1) / 3 = 48/3 = 16. Smaller border of the interval for N = 189 left even even lies in 15 contour Hz (15) = (2 β’ 15) 2 = 30 2 = 900 and (16) = (2 β’ 16 + 1) 2 = 33 2 = 1089.
The factorization of the number N = 189 = (33 + 30) (33 - 30) = 63 β’ 3
Similar calculations can be performed for left and right multiples of 5, 7, 9, etc.
List of used sources
[1] Hall M. Combinatorics. -M .: Mir, 1970. - 424 p.
[2] Andrews G. Theory of partitions. - M .: Science GRFML, 1982. - 256 s.
The problem of splitting a natural number
A partition of a natural number N is called a finite non-increasing sequence of natural numbers k0, k1, k2, k3, ..., kt less than N, for which the sum k0 + k1 + k2 + k3 +, ..., + kt = N, numbers k i , i = 0 (1) t, are called partitioning blocks (parts). Number splits are ordered and unordered. There are splits of numbers [1, 2] into odd and separately into even parts, splits of numbers into identical and different parts, etc. For our purposes, we will use a graphical representation of the division of numbers into different parts with the restriction on the difference (β = 1) of one part of the partition from another, for which we use the Ferrer point graph.
In the problem of splitting the number N, which is associated with the problem of factoring numbers, they deal with two special cases of partitions not of the number N itself, but of its Ο-invariant, the number kn (N) / 2, that is, half of the number of the limit contour for N. In addition, we will distinguish the partitions of the number kn (N) / 2, the corresponding integer and fractional numbers, and the corresponding left (Nl) and right (Nn) odd natural numbers. A graphical representation of the set of partitions of the partitions of the numbers kn (N) / 2 has the form of a trapezium as an integral part of the triangular Ferrere dotted diagram formed from its successive following lines. One of the bases of the trapezium (upper or lower) always includes only half of its points. The main specialization of the two types of partitions considered here is that the difference between the parts of the number splitting one from the other is only one β = 1, and only the extreme parts (lines that are the bases of the trapezoid of the graphical representation) of the number splitting may differ from the neighboring ones by an amount greater than unit. The last line (top - for Nl, bottom - for Np) is always split in half. You can also read about the terms in the partitions (here) . If the line to be split in half contains an even number of points, then all parts of the partition of the number N are integers, if the number of points in such a line is odd, then the extreme part of the partition and k n (N) / 2 itself is a fractional number. We also note some other features of these special partitions. These features are easily and visually perceived when considering numerical examples, which in essence are the main content of the work.
First, for Nn (the right number), the kn (N) / 2 representation of a partition is always formed only by different terms, and only half of its number is included in the sum from the smaller contour.
Secondly, for NL (left number), the representation of half the number of the limit contour (the numbers kn (N) / 2) by splitting is always formed by different parts, if kn (N) / 2 is a fractional number.
Thirdly, for Nl, if kn (N) / 2 is an integer, then the two terms in the sum may coincide, and one term from such a pair is half the number of the larger contour in the sum. Let us explain these concepts by a numerical example.
')
Example 1 An odd left number Nl = 119 is specified, since 119 = 3 (mod4). The limit contour for this number has a length of 119 + 121 = 240. The number of the limit contour is kn (119) = 240/8 = 30. The F-invariant for the number 119 is equal to kn (119) / 2 = 30/2 = 15. Splitting The Ο-invariant for the number N has the form 15 = 3 + 4 + 5 + 6/2 = 3 + 4 + 5 + 3. In the total, we got two identical terms equal to three. To make sure that the splitting of the f-invariant leads to the factorization of the number N = 119, we reconstruct N by the splitting, all the terms of which are the numbers of the contours. Multiply the terms by 8:
3 β’ 8 + 4 β’ 8 + 5 β’ 8 + 6 β’ 8 = 24 + 32 + 40 + 48.
The last (larger) addend must give only its left semi-contour 23 + 25 = 48 in sum, i.e. 23. So, set the length of the interval for Nl = 119 (check) 24 + 32 + 40 + 23 = 119.
It remains to recall that the boundaries of contours and half-contours in the NPS are always squares and get their values ββat the extreme components of the interval:
smaller border GM (3) for the circuit with the number 3, GM (3) = (2 β’ 3-1) 2 = 25 = 5 2 ;
a large boundary of the interval GB (6) for the contour with the number 6, GB = Hz (6) = (2 β’ 6) 2 = 144 = 12 2 - the right border of the left semi-contour of the sixth contour.
The final touch: N is the difference of squares, i.e. interval difference
N = 12 2 - 5 2 = (12 - 5) (12 + 5) = 7 β’ 17 = 119 and we get the factorization.
Natural odd numbers N (x1, x) = 3t multiples of three are always formed by only three adjacent semi-circuits, two of which are the whole contour. For such numbers, the numbering model is quite simple. Find k - the number of the full contour for the number N.
For left odd numbers
kn (N) / 2 = (k + 1) / 2 + k => kn (N) = 3k + 1 => k = (kn (N) - 1) / 3.
For right odd numbers
kn (N) / 2 = (k β1) / 2 + k => kn (N) = 3k - 1 => k = (kn (N) + 1) / 3.
Example 2 Given the right odd number N = 129, since 129 = 1 (mod4). The limit contour for this number is 127 + 129 = 256. The number of the limit contour is kn (129) = 256/8 = 32. The F-invariant for the number 129 is equal to kn (129) / 2 = 32/2 = 16. We substitute in the formula, the found values ββare k = (32 + 1) / 3 = 11. This is the number of the larger contour of the two semi-contours 43 + 45 = 88 = 11 β’ 8. To form the interval, we include in the sum a semi-contour from the previous contour with the number 11-1 = 10, i.e. M = 4k +1 = 41.
And finally, the sum of the semi-contours 41+ 43 + 45 = 129. It remains to find the limits of the interval and factorize the number N = 129.
All terms in the sum of partitions, except for one extreme term, always differ by one, i.e. these are the numbers k i , following in the natural series one after another k (N) / 2 = β t i = p k i Β± k / 2,
where p is the index of the integer number of the initial (smaller) contour;
t is the index of the integer number of the final (larger) contour;
Β± - the sign in the sum is determined by the form (left k> k t , right k <k p ) of the number N;
k is the number of the extreme contour (without an index), from which only half of the number takes part in the total. The fact that the sum in the division of the number kn (N) / 2 is formed by natural numbers increasing by 1 is crucial for the numerical model of a natural number.
All partitions of this type (all sums kn (N) / 2) are represented in the triangular dot Ferrer diagram (a graphical representation of the partition) and can be obtained from it.
We present table 1 with such a diagram, accompanying it with additional information about the interval and numbering models of the number N.
Table 1 - Characteristics of the interval and numbering models of the number N
In the middle part of the table, the value of the graphical splitting of the limiting semicontour k n (N) / 2) for the number 231 = 3 β 77 = 7 β 33 = 11 β 21 into different parts (rows with dots) that differ from one another is placed. The smaller divider always shows how many half-contours form the interval of the number N.
The interval model is the interval of the positions (lengths) of contours / semi-contours, the sum of which is equal to N.
So for N = 231, we have:
1st interval model 1 contour + semi-contour 152 + 79 = 75 + 77 + 79 - three consecutive semi-contour, which differ in length by two units.
2nd interval model 3 contours + semi-contour 56 + 64 + 72 + 39 = 27 + 29 + 31 + 33 + 35 + 37 +39 - seven consecutive next contours, which differ in the length of two units.
3rd interval model of 5 contours + semi-contour
24 + 32 + 40 + 48 + 56 + 31 = 11 + 13 + 15 +17 +19 +21 + 23 + 25 + 27 + 29 +31
- eleven consecutive semi-circuits that differ in length of two units.
The numbering model is a set of numbers of contours and semi-contour, which describe the number N, the sum of which is equal to the value of the Ξ¦-invariant.
So for the number N = 231, the f-invariant is equal to kn (N) / 2 = kn (231) / 2 = 29.
kn (N) / 2 = kn (231) / 2 = 19 + 20/2 = 7 + 8 + 9 + 10/2 = 3 + 4 + 5 + 6 + 7 + 8/2.
Equality sums are three numbering models. The terms correspond to the lines of the k diagram.
Both types of models are closely related and can be transformed one into another if necessary.
For odd natural numbers N within the first thousand, on the basis of this diagram, factoring them into two factors can be carried out. The first four columns of the table contain the characteristics of the interval model (characteristics of the contours). The column to the right of the scatter plot is the contour number. The last two columns are the characteristics of the numbering model. The level is called the nth row of the table below. The values ββof the characteristics in the rows are given with the increase from the bottom line up. In the last column, the sums of points from the preceding lines are summarized with half the number of points of the current line. In the last but one column of the sum of points of full rows
For left NL numbers, such sums k p / 2, corresponding to intervals of length NL, always contain a certain number of points and lines from a triangle and in the upper part only half the number of points of a line. Obviously, if we fix a line from the sum to which a value equal to k p / 2 corresponds or the nearest greater, but also containing half of the top line, then for deciding on the number of the bottom line in the sum, it remains to determine only the number of the lower (smaller) contour or the corresponding line forming sum k p / 2. This value is determined by the difference between the sum of points for the level of the fixed upper line and the value of k p / 2. If such a difference is present in the column in question, then the line corresponding to it and the lines below it are not taken into account in the sum.
The search for the difference C 2 k + 1 - k p / 2 starts from the value C 2 k + 1 > k p / 2, and compare the calculated difference with k 2/2, until they coincide. If there is a mismatch, increase the value of k.
Example 3 For the right number N (x1, x) = 621, perform factorization, determine the value of the length of the limit contour of the numbers kn (Nn) = kn (621) = (621β1) / 4 = (619 + 621) / 8 = 155. Then we determine the value of k p (621) / 2 = 77.5 and find the value of the difference C 2 k + 1 - k p / 2, closest to the beginning of the NPS. In the column C 2 k + 1 of table 1 we find, for k = 12, the value 78, which exceeds k n (621) / 2 = 77.5.
Then the desired difference C 2 k + 1 - k p / 2 = 78 - 77.5 = 0.5. We check whether the found difference coincides with the value of k 2/2 for a certain value of k. The match occurs with a value of 0.5 in the bottom row of the table.
From this, the number of the smaller contour k p 2/2 = 0.5 => k = 1 of the interval being formed is determined. The interval, representing the number N = 621, begins with a point of the mean square (even) of the first contour and reaches the 12th contour, inclusive. It is known that through the values ββof the boundaries, the length of the interval for the number N is represented by the expression N = - = 1i 2 - i 2 . Knowing the numbers of contours on the boundaries of the interval, we find its boundary points. The boundaries of the interval will be:
β’ left border with k = 1, Ch = (2k) 2 = (2 β’ 1) 2 = 4,
β’ the right one with k = 12 is = (2k + 1) 2 = (2 β’ 12 + 1) 2 = 625.
Then N = - = 1i 2 - i 2 = 625 - 4 = 621. On the other hand, in the presence of square boundaries, the factorization of the number N = x1i 2 - i 2 = (25 + 2) (25 - 2) = 27 β’ 23.
The scheme of solving the factorization problem considered in the example ensures the finding of other alternative pairs of boundaries. The search for the difference C 2 k + 1 - k p / 2, which coincides with k 2/2 results in such a coincidence with larger k = 19. We have the equality C 2 k + 1 - k p / 2 = 190 - 77.5 = 112 , 5 of which we find the least, i.e. k = β2 Γ 112.5 = β225 = 15. Now you can start searching for the boundaries of the interval and factorization N.
The boundaries of the interval will be:
β’ left border at k = 15, Gl = (2k) 2 = (2 β’ 15) 2 = 900,
β’ the right one with k = 19 is = (2k + 1) 2 = (2 β’ 19 + 1) = 392 = 1521,
β’ N = - Gl = 1i 2 - i 2 = 1521 - 900 = 621 and
β’ N = 1i 2 - i 2 = (39 + 30) (39 - 30) = 69 β’ 9.
Example 4 ( Splitting the left number, where half the number (not an integer) in the sum is taken from the larger contour ).
Let the number N = 235 be given, the number N = 235 β‘ 3 (mod4) left.
The length of the limiting contour is Ln = 235 + 237 = 472, its number is kn = L / 8 = 472/8 = 59, kn / 2 = 29.5, the values ββof the limits of the limiting contour: right Hn = (2kn) 2 = 1182, left Ch = (2k n β1) 2 = 117 2; they correspond to the trivial decomposition of the number N = 235 1.
From the numbering model, it follows that k p / 2 = 29.5. For N = 235 (see example earlier) k n (235) / 2 = 29.5
The nearest value in the column k 2/2 = 40.5 lies in the line k = 9.
It corresponds to the difference k 2/2 - k p / 2 = 40.5 - 29.5 = 11, which is absent in the column βsumβ.
The next level is k = 11 and k 2/2 = 60.5, it corresponds to the difference k 2/2 - k p / 2 = 60.5 - 29.5 = 31, which is also absent in the βsumβ column. The next level is k = 13 and k 2/2 = 84.5, it corresponds to the difference
k 2/2 - k p / 2 = 84.5 - 29.5 = 55, which is present in the column "sum" in the row with the number k = 10.
Hence the conclusion that all lines, starting with the number 10 and below, are not included in the sum k p / 2. Therefore, k p / 2 = 29.5 = 11 + 12 + 13/2.
Perform factorization of a given number. The numbers of contours that form the numbering model of a number are found: k = 11, 12, and 13. From k = 13, only the left half of this contour is included in the formula.
We calculate the lengths of the contours L (11) = 8 β’ 11 = 88; L (12) = 8 β’ 12 = 96; L (13) = 8 β’ 13 = 104; the left half of the 13th circuit m (13) = 104/2 β1 = 51. The interval model 88 + 96 + 51 = 43 + 45 + 47 + 49 + 51 = 235.
Define the boundaries of the interval model:
β’ (13) = (2 β’ 13) 2 = 26 2 = 676;
β’ Ch (11) = (2 β’ 11β1) 2 = 21 2 = 441.
Now the number N = 235 can be factorized.
N (x1, x) = 235 = (x1 + x) (x1 - x) = (26 + 21) (26β21) = 47 β’ 5 = 235.
Example 5 (The splitting of the right number, where half of the number (not an integer) in the sum is taken from the smaller contour ).
Let N = 357 This is the right number N = 357 β‘ 1 (mod4). The length of the limit contour is Ln = 357 + 355 = 712, its number is k = L / 8 = 712/8 = 89, k / 2 = 44.5, borders limit contour:
β’ Left Ch = (2k n β1) 2 = 177 2 ,
β’ average Hz = (2k n ) 2 = 178 2 ,
β’ right = (2k + 1) 2 = 179 2 they correspond to the trivial decomposition of the number N = 357 1.
a) x1 = 19; ho = 2; N = (2 β 58) - Ch (58 β 2 - 1) = 1i 2 - ii = 19 2 - 2 2 = 361 - 4 = (19 + 2) (19 - 2) = 21 β 17 = 357, k p / 2 = Β½ + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 44.5
b) x1 = 61; ho = 58; N = (2 β 58) - Ch (58 β 2 - 1) = 1i 2 - i 2 = 61 2 - 58 2 = 3721 - 3364 = (61 + 58) (61 - 58) = 119 3 = 357; k p / 2 = 29/2 + 30 = 44.5.
The length of an arbitrary contour and the interval of the natural number series between odd squares is a multiple of 8. The odd square deduction modulo 8 is 1. The difference of the squares of odd primes β₯ 5 is always a multiple of 24 (7 2 - 5 2 = 24). This can be shown as follows. Consider the squares of two odd primes, and then find their difference. Of the three adjacent numbers 2n - 1, 2n, 2n + 1, one is always a multiple of three. In our case, this number is n = 3t, since the extreme numbers are simple by condition.
β’ 1 2 = (2n - 1) 2 = 4n 2 - 4n + 1 = 1 + 4n (n - 1) = 1 + 8 C n 2 ,
β’ 2 2 = (2n + 1) 2 = 4n 2 + 4n + 1 = 1 + 4n (n + 1) = 1 + 8 2 n + 1 ,
β’ 2 2 - 1 2 = 8 ( 2 n + 1 - C 2 ) = 4n (n + 1 - n + 1) = 8n = 8 Β· 3t = 24t.
If the number N is a multiple of 3, it is formed in the interval model by three semi-circuits standing side by side. In other words, if the number is right, then the semi-contour from the smaller contour. For N = 357 = 119 β’ 3, k p / 2 = 44.5. The value of the number of the semi-circuit is determined by the formula (k p / 2 β1) / 3 = (44/5 - 1) / 3 = 14.5. Therefore, the number of the smaller contour is 14.5 β’ 2 = 29, and the number of the next 30. Indeed, 29/2 +30 = 44.5 = k p / 2. If the number N is a multiple of 5 (formed by five half-contours), then the number (k p / 2 - 6) / 5.
Example 6 ( Interrelation of characteristics of interval and numbering models of a multiple of three )
For the left number N (x1, xo) = 183 and the right number N (x1, xo) = 189, perform factorization, determine the number and length of the limit contour of the numbers kn (Nl) = kn (183) = (183 + 185) / 8 = 46, and k p (N) = k p (189) = (187 + 189) / 8 = 47. Next, we make the equation for the number of the limiting semicontour in the numerical model k p (183) / 2 = (k + 1) / 2 + k, whence kn = 3k + 1 and k = (kn - 1) / 3 = 45/3 = 15.
β’ Large interval boundary for N = 183 right even Hz (16) = (2 Β· 16) 2 = 32 2 = 1024
β’ the smaller left border of Ch (15) = (2 β’ 15 - 1) 2 = 29 2 = 841.
The factorization of the number N = 183 = 32 2 - 29 2 = (32 + 29) (32 - 29) = 61 β’ 3.
The connection of right numbers of the form N (x1, x) = 3t with the sum of the contour numbers of the interval model is as follows:
the half of the contour number plus the number of the next contour of the interval is equal to the half of the number of the limit contour kn (Np) / 2 of the investigated number.
For the right number N (x1, x) = 189, the value of the limiting semicontour k n (189) / 2 = (k β 1) / 2 + k,
whence kn = 47 = 3k - 1 and k = (kn + 1) / 3 = 48/3 = 16. Smaller border of the interval for N = 189 left even even lies in 15 contour Hz (15) = (2 β’ 15) 2 = 30 2 = 900 and (16) = (2 β’ 16 + 1) 2 = 33 2 = 1089.
The factorization of the number N = 189 = (33 + 30) (33 - 30) = 63 β’ 3
Similar calculations can be performed for left and right multiples of 5, 7, 9, etc.
List of used sources
[1] Hall M. Combinatorics. -M .: Mir, 1970. - 424 p.
[2] Andrews G. Theory of partitions. - M .: Science GRFML, 1982. - 256 s.
Source: https://habr.com/ru/post/239009/
All Articles