October 2, 2014 at 18:09Two special number splitting models
Two special partitions of the natural number N can be used to construct the factorization algorithm. In previous posts, this was discussed and the author was asked questions. In the works on factorization, it was stipulated that with the approach under consideration, it is possible in principle to solve the problem of factorization of large numbers (FBCH) in a short time if there is a program that generates special partitions. In this work, the author reveals in more detail the specifics of the specialization of partitions. Since the majority of Habr community members are programmers, I suggest that those who show interest in the WFBH, solved in an acceptable time (not years, months, or even dozens of hours), try their hand and put their skills into the development of a special partition generator program. Break as follows from the text below is necessarythe f-invariant of the number N, a property independent of the bit depth of the number, or the number N itself. The table of all partitions of 13, of which only 4 are special, contains a factorization of any of the first three special partitions.
The problem of partitioning a natural number A
partition of a natural number N is 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, the numbers k i , i= 0 (1) t are called blocks (parts) of the partition. Partitions of numbers are ordered and disordered. There are partitions of numbers [1, 2] into odd and separately into even parts, partitions of numbers into identical and different parts, etc. For our purposes, we will use a graphical representation of partitions of numbers into different parts with restriction on the difference (∆ = 1) of one part of the partition from the other, for which we use the point graph of Ferrer.
In the problem of splitting the number N associated with the problem of factorization of numbers, we deal with two special cases of partitions not of the number N itself, but its φ-invariant, the number k p (N) / 2, i.e., half the number of the limit contour for N. In addition, we distinguish the partitions of the number k p(N) / 2, corresponding to integer and fractional numbers, as well as corresponding to left (Nl) and right (Nп) odd natural numbers. The graphical representation of the set of partitions of partitions of numbers k p (N) / 2 has the form of a trapezoid as part of a triangular dotted Ferrer diagram formed from its successive following lines. One of the bases of the trapezoid (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 partitions of a number from one to 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 partition of the number can differ from the neighboring ones by an amount greater than one. The extreme line (upper for Nl, lower for Np) is always split in half. You can read more about the terms in the partitions (Here) . If a line split in half contains an even number of points, then all parts of the partition of 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 are a fractional number. We also note some other features of these special partitions. These features are easily and clearly perceived when considering numerical examples, which in essence are the main content of the work.
First, for Nп (the right number), the representation of k п (N) / 2 by a partition is always formed only by different terms, and only half of its number is included in the sum from a smaller contour.
Secondly, for Nl (the left number), the representation of half the number of the limit contour (the number k p (N) / 2) by the partition is always formed by different parts if k p (N) / 2 is a fractional number.
Thirdly, for Nl, if k p (N) / 2 is an integer, then two terms in the sum can coincide, moreover, one term from such a pair is half the number of the larger contour in the sum. Let us explain these concepts with a numerical example.
Example 1. Given the left odd number Nl = 119, since 119 = 3 (mod4). The limit contour for this number has a length of 119 + 121 = 240. The number of the limit contour k p (119) = 240/8 = 30. The F-invariant for the number 119 is k p (119) / 2 = 30/2 = 15. The partition The f-invariant for the number N has the form 15 = 3 + 4 + 5 + 6/2 = 3 + 4 + 5 + 3. In the total, two identical terms equal to three were obtained. To make sure that the partition of the φ-invariant leads to the factorization of the number N = 119, we restore N by the partition, all of whose terms are the numbers of the contours. We multiply the terms by 8:
3 • 8 + 4 • 8 + 5 • 8 + 6 • 8 = 24 + 32 + 40 + 48.
The last (larger) term should give in the sum only its left half-loop 23 + 25 = 48, i.e. 23. So, we set the interval length for Nl = 119 (check) 24 + 32 + 40 + 23 = 119.
It remains to remember that the boundaries of the contours and half-circuits in the LFD are always squares and get their values at the extreme terms of the interval: a
smaller boundary Gm ( 3) for the circuit with number 3, Gm (3) = (2 • 3-1) 2 = 25 = 5 2 ;
the large boundary of the GB interval (6) for circuit number 6, GB = Hz (6) = (2 • 6) 2 = 144 = 12 2 - the right boundary of the left semicircle of the sixth circuit.
The final touch: N is the difference of the squares, i.e. the difference in the boundaries of the interval
N = 122 - 5 2 = (12 - 5) (12 + 5) = 7 • 17 = 119 and we obtain a factorization.
Natural odd numbers N (x1, xo) = 3t multiples of three are always formed by only three adjacent semicircles, two of which are a whole contour. For such numbers, the numbering model is quite simple. We find k - the number of the complete contour for the number N.
For odd left numbers,
k p (N) / 2 = (k + 1) / 2 + k => k p (N) = 3k + 1 => k = (k p ( N) - 1) / 3.
For odd right numbers,
k p (N) / 2 = (k –1) / 2 + k => k p (N) = 3k - 1 => k = (k p (N) + 1) / 3.
Example 2. Given the right odd number Nп = 129, since 129 = 1 (mod4). The limit contour for this number has a length of 127 + 129 = 256. The number of the limit contour is k p (129) = 256/8 = 32. The f-invariant for the number 129 is k p (129) / 2 = 32/2 = 16. Substitute found k = (32 + 1) / 3 = 11 in the formula. This is the number of the larger contour of the two half loops 43 + 45 = 88 = 11 • 8. To form the interval, we include in the sum of the half-circuits from the previous circuit with the number 11-1 = 10, i.e. M = 4k +1 = 41.
And finally, the sum of the semicircles 41+ 43 + 45 = 129. It remains to find the boundaries of the interval and factorize the number N = 129.
All terms in the sum of the partitions, except for one extreme term, always differ by unity, t i.e., these are numbers k i, following in the natural series one after the other k p (N) / 2 = ∑ t i = p k i ± k / 2,
where p is the index of the number of the integer initial (smaller) contour;
t is the index number of the integer 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 index), of which only half of the number is involved in the sum. The fact that the sum in the partition of the number k p (N) / 2 is formed by natural numbers increasing by 1 is crucial for the numbering model of the natural number.
All partitions of this type (all sums k p(N) / 2) turn out to be represented in the Ferrer triangular scatter diagram (graphical representation of the partition) and can be obtained from it.
We give 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 is the value of the graphical partition of the limiting half-loop k p (N) / 2) for the number 231 = 3 ∙ 77 = 7 ∙ 33 = 11 ∙ 21 into different parts (lines with dots) that differ from each other by one. The smaller divisor always shows how many half-circuits form the interval of N. The
interval model is the interval of the positions (lengths) of the contours / half-circuits, the sum of which is N.
So for N = 231, we have:
1st interval model 1 circuit + half-circuit 152 + 79 = 75 + 77 + 79 - three consecutive half-circuits that differ in length by two units.
The 2nd interval model of 3 circuits + half-circuits 56 + 64 + 72 + 39 = 27 + 29 + 31 + 33 + 35 + 37 +39 - seven consecutive half circuits that differ in length by two units.
3rd interval model of 5 loops + half loops
24 + 32 + 40 + 48 + 56 + 31 = 11 + 13 + 15 +17 +19 +21 + 23 + 25 + 27 + 29 +31
- eleven consecutive half loops that differ two units long.
The numbering model is a collection of circuit numbers and half-circuits that describe the number N, the sum of which is equal to the value of the f-invariant.
So for the number N = 231, the f-invariant is equal to k p(N) / 2 = k p (231) / 2 = 29.
k p (N) / 2 = k p (231) / 2 = 19 + 20/2 = 7 + 8 + 9 + 10/2 = 3 + 4 + 5 + 6 + 7 + 8/2.
Amounts in equality are three numbering models. The terms correspond to lines k of the diagram.
Both types of models are closely related and can be transformed one into another if necessary.
For odd positive integers N within the first thousand, on the basis of this diagram, they can be factorized into two factors. The first four columns of the table contain the characteristics of the interval model (circuit characteristics). The column to the right of the scatter chart is the outline number. The last two columns are the characteristics of the numbering model. The level is the nth bottom row of the table. Characteristic values in rows are shown in increments from the bottom row up. In the last column, the sum of the points from the previous rows are summed with half the number of points in the current row. In the penultimate column, the sums of points of complete 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 in the line. Obviously, if you fix a line from the sum that corresponds to a value equal to k p / 2 or the nearest larger one, but also containing half the top line, then to decide on the number of the bottom line in the total, it remains to determine only the number of the lower (smaller) contour or the corresponding line forming the sum of k p / 2. This value is determined by the difference between the sum of the points for the level of the fixed top row and the value of k p / 2. If such a difference is present in the column under consideration, then the line corresponding to it and the lines below it are not taken into account in the total.
Search for difference C2k+1 – kп /2 начинаем от значения С2k+1 > kп /2, а вычисленную разность сравниваем с k2/2, до тех пор, пока они не совпадут. При несовпадении увеличиваем значение k.
Пример 3. Для правого числа N(x1, xо) = 621 выполнить факторизацию, определить значение длины предельного контура чисел kп(Nп) = kп(621) = (621–1)/4 = (619 + 621)/8 = 155. Затем определяем значение kп(621)/2 = 77,5 и находим значение разности С2k+1 – kп /2, ближнюю к началу НРЧ. В столбце С2k+1table 1 we find at k = 12 a value of 78 that exceeds k p (621) / 2 = 77.5.
Then the desired difference is C 2 k + 1 - k p / 2 = 78 - 77.5 = 0.5. Check whether the found difference coincides with the value k 2 /2 for some value of k. Coincidence takes place 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 formed interval, is determined . The interval representing the number N = 621 starts with the middle square (even) point of the first circuit and reaches the 12th circuit inclusively. 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 - хоi2 . Knowing the numbers of the contours at the boundaries of the interval, we find its boundary points. The boundaries of the interval are:
• the left border at k = 1, Ch = (2k) 2 = (2 • 1) 2 = 4,
• the right border at k = 12 is Tn = (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 squares, the factorization of the number N = х1i 2 - хоi 2 = (25 + 2) is easily performed (25 - 2) = 27 • 23.
The scheme for solving the factorization problem considered in the example ensures the finding of other alternative pairs of boundaries. Search for the difference C 2k+1 – kп /2, совпадающей с k2 /2 приводит к получению такого совпадения при большем k = 19. Имеем равенство С2k+1 – kп /2 = 190 – 77,5 = 112,5 из которого находим меньшее, т.е. k = √2×112.5 = √225 = 15. Теперь можно приступить к поиску границ интервала и факторизации N.
Границами интервала будут:
• левая граница при k =15, Гл = (2k)2 = (2•15)2 = 900,
• правая при k = 19 есть Гп = (2k + 1)2 = (2•19 + 1)2 = 392 = 1521,
• N = Гп – Гл = х1i2 – хоi2 = 1521 – 900 = 621 и
• N = х1i 2 - хоi 2 = (39 + 30) (39 - 30) = 69 • 9.
Example 4 . (The division of the left number, where half of 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 limit contour Ln = 235 + 237 = 472, its number k p = L / 8 = 472/8 = 59, k p / 2 = 29.5, the values of the boundaries of the limit contour: right Гп = (2k p ) 2 = 118 2 , the left GL = (2k n –1) 2 = 117 2 they correspond to the trivial expansion of the number N = 235 ∙ 1.
Из нумерационной модели следует, что kп/2 = 29.5. Для N = 235 (см. пример ранее) kп(235)/2 = 29.5
Ближайшее значение в столбце k2/2 = 40.5 лежит в строке k = 9.
Ему соответствует разность k2/2 – kп/2 = 40.5 – 29.5 = 11, которая отсутствует в столбце «сумма».
Следующий уровень k = 11 и k2/2 = 60.5, ему соответствует разность k2/2 – kп/2 = 60.5 – 29.5 = 31, которая также отсутствует в столбце «сумма». Следующий уровень k = 13 и k2/2 = 84.5, ему соответствует разность
k2/2 – kп/ 2 = 84.5 - 29.5 = 55, which is present in the column “sum” in the row with the number k = 10.
From this it follows that all the lines starting from number 10 and below are not included in the sum of k p / 2. Therefore, k p / 2 = 29.5 = 11+ 12 + 13/2.
Factor the given number. The numbers of the contours that form the numbering model of the number are found: k = 11, 12, and 13. From k = 13, only the left half of this contour enters the formula.
We calculate the length of the contours L (11) = 8 • 11 = 88; L (12) = 8 • 12 = 96; L (13) = 8 • 13 = 104; the left half of the 13th contour is m (13) = 104/2 –1 = 51. The interval model is 88 + 96 + 51 = 43 + 45 + 47 + 49 + 51 = 235.
We define the boundaries of the interval model:
• Гп (13) = (2 • 13) 2 = 262 = 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 division of the right number, where half of the number (not an integer) in the amount is taken from the smaller contour ).
Let N = 357. This is the right number N = 357 ≡ 1 (mod4). The length of the limiting contour is Ln = 357 + 355 = 712, its number is k p = L / 8 = 712/8 = 89, k p / 2 = 44.5, the boundaries limit contour:
• left Gl = (2k p –1) 2 = 177 2 ,
• the average Hz = (2k n ) 2 = 178 2 ,
• the right Γn = (2k n + 1) 2 = 179 2 they correspond to the trivial expansion of the number N = 357 ∙ 1.
a) x1 = 19; ho = 2; N = Гп (2 ∙ 58) - Гл (58 ∙ 2 - 1) = х1i 2 - хоi 2 = 19 2 - 2 2 = 361 - 4 = (19 + 2) ∙ (19 - 2) = 21 ∙ 17 = 357, k n / 2 = ½ + 2 + 3 + 4 +5 + 6 + 7 + 8 + 9 = 44.5
b) x1 = 61; ho = 58; N = Гп (2 ∙ 58) - Гл (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 series of numbers between odd squares is a multiple of 8. The residue of an odd square in mod 8 is 1. The difference in the values 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 is the number n = 3t, since the extreme numbers are prime by hypothesis.
• LF1 2 = (2n - 1) 2 = 4n 2 - 4n + 1 = 1 + 4n (n - 1) = 1 + 8 C p 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 n 2 ) = 4n (n + 1 - n + 1) = 8n = 8 · 3t = 24t.
If the number N is a multiple of 3, it in the interval model is formed by three semicircuits standing side by side. In other words, if the number is right, then the semicircle is from the smaller contour. For N = 357 = 119 • 3, k n / 2 = 44.5. The value of the number of half-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 is 30. Indeed, 29/2 +30 = 44.5 = k p / 2. If the number N is a multiple of 5 (formed by five half-loops), then the number (k p / 2 - 6) / 5.
Example 6 . ( Relationship between the characteristics of the interval and numbering models of a multiple of three )
For the left number N (x1, xо) = 183 and the right number N (x1, xо) = 189, factorize, determine the number and length of the limit contour of the numbers k p (Nl) = k p (183) = (183 + 185) / 8 = 46, and k p (Nп) = k p (189) = (187 + 189) / 8 = 47. Next, we compose the equation for the number of the limiting half-loop in the numbering model kn (183) / 2 = (k + 1) / 2 + k, whence k n = 3k + 1 and k = (k n - 1) / 3 = 45/3 = 15.
• Large boundary of the interval for N = 183 right even Hz (16) = (2 · 16) 2 = 32 2 = 1024
• smaller left border Гл (15) = (2 • 15 - 1) 2 = 29 2 = 841.
Factorization of the number N = 183 = 32 2 - 29 2 = (32 + 29) (32 - 29) = 61 • 3.
The relationship of the right-hand numbers of the form Nп (x1, хо) = 3t with the sum of the numbers of the contours of the interval model is as follows:
half of the number of the contour plus the number of the next contour of the interval are equal to half the number of the limiting contour k p (Nп) / 2 of the number under investigation.
For the right number N (x1, xo) = 189, the value of the limiting semiconductor k p (189) / 2 = (k – 1) / 2 + k,
whence k p = 47 = 3k - 1 and k = (k p + 1) / 3 = 48/3 = 16. The smaller boundary of the interval for N = 189 the left even lies in the 15 Hz circuit (15) = (2 • 15) 2 = 30 2 = 900 and Гп (16) = (2 • 16 + 1 ) 2 = 33 2 = 1089.
Factorization of the number N = 189 = (33 + 30) (33 - 30) = 63 • 3
Similar calculations can be performed for numbers of left and right multiples of 5, 7, 9, etc.
List of references
[1] Hall M. Combinatorics. -M .: Mir, 1970 .-- 424 p.
[2] Andrews G. Partition Theory. -M .: Science GRFML, 1982. - 256 s.
The problem of partitioning a natural number A
partition of a natural number N is 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, the numbers k i , i= 0 (1) t are called blocks (parts) of the partition. Partitions of numbers are ordered and disordered. There are partitions of numbers [1, 2] into odd and separately into even parts, partitions of numbers into identical and different parts, etc. For our purposes, we will use a graphical representation of partitions of numbers into different parts with restriction on the difference (∆ = 1) of one part of the partition from the other, for which we use the point graph of Ferrer.
In the problem of splitting the number N associated with the problem of factorization of numbers, we deal with two special cases of partitions not of the number N itself, but its φ-invariant, the number k p (N) / 2, i.e., half the number of the limit contour for N. In addition, we distinguish the partitions of the number k p(N) / 2, corresponding to integer and fractional numbers, as well as corresponding to left (Nl) and right (Nп) odd natural numbers. The graphical representation of the set of partitions of partitions of numbers k p (N) / 2 has the form of a trapezoid as part of a triangular dotted Ferrer diagram formed from its successive following lines. One of the bases of the trapezoid (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 partitions of a number from one to 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 partition of the number can differ from the neighboring ones by an amount greater than one. The extreme line (upper for Nl, lower for Np) is always split in half. You can read more about the terms in the partitions (Here) . If a line split in half contains an even number of points, then all parts of the partition of 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 are a fractional number. We also note some other features of these special partitions. These features are easily and clearly perceived when considering numerical examples, which in essence are the main content of the work.
First, for Nп (the right number), the representation of k п (N) / 2 by a partition is always formed only by different terms, and only half of its number is included in the sum from a smaller contour.
Secondly, for Nl (the left number), the representation of half the number of the limit contour (the number k p (N) / 2) by the partition is always formed by different parts if k p (N) / 2 is a fractional number.
Thirdly, for Nl, if k p (N) / 2 is an integer, then two terms in the sum can coincide, moreover, one term from such a pair is half the number of the larger contour in the sum. Let us explain these concepts with a numerical example.
Example 1. Given the left odd number Nl = 119, since 119 = 3 (mod4). The limit contour for this number has a length of 119 + 121 = 240. The number of the limit contour k p (119) = 240/8 = 30. The F-invariant for the number 119 is k p (119) / 2 = 30/2 = 15. The partition The f-invariant for the number N has the form 15 = 3 + 4 + 5 + 6/2 = 3 + 4 + 5 + 3. In the total, two identical terms equal to three were obtained. To make sure that the partition of the φ-invariant leads to the factorization of the number N = 119, we restore N by the partition, all of whose terms are the numbers of the contours. We multiply the terms by 8:
3 • 8 + 4 • 8 + 5 • 8 + 6 • 8 = 24 + 32 + 40 + 48.
The last (larger) term should give in the sum only its left half-loop 23 + 25 = 48, i.e. 23. So, we set the interval length for Nl = 119 (check) 24 + 32 + 40 + 23 = 119.
It remains to remember that the boundaries of the contours and half-circuits in the LFD are always squares and get their values at the extreme terms of the interval: a
smaller boundary Gm ( 3) for the circuit with number 3, Gm (3) = (2 • 3-1) 2 = 25 = 5 2 ;
the large boundary of the GB interval (6) for circuit number 6, GB = Hz (6) = (2 • 6) 2 = 144 = 12 2 - the right boundary of the left semicircle of the sixth circuit.
The final touch: N is the difference of the squares, i.e. the difference in the boundaries of the interval
N = 122 - 5 2 = (12 - 5) (12 + 5) = 7 • 17 = 119 and we obtain a factorization.
Natural odd numbers N (x1, xo) = 3t multiples of three are always formed by only three adjacent semicircles, two of which are a whole contour. For such numbers, the numbering model is quite simple. We find k - the number of the complete contour for the number N.
For odd left numbers,
k p (N) / 2 = (k + 1) / 2 + k => k p (N) = 3k + 1 => k = (k p ( N) - 1) / 3.
For odd right numbers,
k p (N) / 2 = (k –1) / 2 + k => k p (N) = 3k - 1 => k = (k p (N) + 1) / 3.
Example 2. Given the right odd number Nп = 129, since 129 = 1 (mod4). The limit contour for this number has a length of 127 + 129 = 256. The number of the limit contour is k p (129) = 256/8 = 32. The f-invariant for the number 129 is k p (129) / 2 = 32/2 = 16. Substitute found k = (32 + 1) / 3 = 11 in the formula. This is the number of the larger contour of the two half loops 43 + 45 = 88 = 11 • 8. To form the interval, we include in the sum of the half-circuits from the previous circuit with the number 11-1 = 10, i.e. M = 4k +1 = 41.
And finally, the sum of the semicircles 41+ 43 + 45 = 129. It remains to find the boundaries of the interval and factorize the number N = 129.
All terms in the sum of the partitions, except for one extreme term, always differ by unity, t i.e., these are numbers k i, following in the natural series one after the other k p (N) / 2 = ∑ t i = p k i ± k / 2,
where p is the index of the number of the integer initial (smaller) contour;
t is the index number of the integer 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 index), of which only half of the number is involved in the sum. The fact that the sum in the partition of the number k p (N) / 2 is formed by natural numbers increasing by 1 is crucial for the numbering model of the natural number.
All partitions of this type (all sums k p(N) / 2) turn out to be represented in the Ferrer triangular scatter diagram (graphical representation of the partition) and can be obtained from it.
We give 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 is the value of the graphical partition of the limiting half-loop k p (N) / 2) for the number 231 = 3 ∙ 77 = 7 ∙ 33 = 11 ∙ 21 into different parts (lines with dots) that differ from each other by one. The smaller divisor always shows how many half-circuits form the interval of N. The
interval model is the interval of the positions (lengths) of the contours / half-circuits, the sum of which is N.
So for N = 231, we have:
1st interval model 1 circuit + half-circuit 152 + 79 = 75 + 77 + 79 - three consecutive half-circuits that differ in length by two units.
The 2nd interval model of 3 circuits + half-circuits 56 + 64 + 72 + 39 = 27 + 29 + 31 + 33 + 35 + 37 +39 - seven consecutive half circuits that differ in length by two units.
3rd interval model of 5 loops + half loops
24 + 32 + 40 + 48 + 56 + 31 = 11 + 13 + 15 +17 +19 +21 + 23 + 25 + 27 + 29 +31
- eleven consecutive half loops that differ two units long.
The numbering model is a collection of circuit numbers and half-circuits that describe the number N, the sum of which is equal to the value of the f-invariant.
So for the number N = 231, the f-invariant is equal to k p(N) / 2 = k p (231) / 2 = 29.
k p (N) / 2 = k p (231) / 2 = 19 + 20/2 = 7 + 8 + 9 + 10/2 = 3 + 4 + 5 + 6 + 7 + 8/2.
Amounts in equality are three numbering models. The terms correspond to lines k of the diagram.
Both types of models are closely related and can be transformed one into another if necessary.
For odd positive integers N within the first thousand, on the basis of this diagram, they can be factorized into two factors. The first four columns of the table contain the characteristics of the interval model (circuit characteristics). The column to the right of the scatter chart is the outline number. The last two columns are the characteristics of the numbering model. The level is the nth bottom row of the table. Characteristic values in rows are shown in increments from the bottom row up. In the last column, the sum of the points from the previous rows are summed with half the number of points in the current row. In the penultimate column, the sums of points of complete 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 in the line. Obviously, if you fix a line from the sum that corresponds to a value equal to k p / 2 or the nearest larger one, but also containing half the top line, then to decide on the number of the bottom line in the total, it remains to determine only the number of the lower (smaller) contour or the corresponding line forming the sum of k p / 2. This value is determined by the difference between the sum of the points for the level of the fixed top row and the value of k p / 2. If such a difference is present in the column under consideration, then the line corresponding to it and the lines below it are not taken into account in the total.
Search for difference C2k+1 – kп /2 начинаем от значения С2k+1 > kп /2, а вычисленную разность сравниваем с k2/2, до тех пор, пока они не совпадут. При несовпадении увеличиваем значение k.
Пример 3. Для правого числа N(x1, xо) = 621 выполнить факторизацию, определить значение длины предельного контура чисел kп(Nп) = kп(621) = (621–1)/4 = (619 + 621)/8 = 155. Затем определяем значение kп(621)/2 = 77,5 и находим значение разности С2k+1 – kп /2, ближнюю к началу НРЧ. В столбце С2k+1table 1 we find at k = 12 a value of 78 that exceeds k p (621) / 2 = 77.5.
Then the desired difference is C 2 k + 1 - k p / 2 = 78 - 77.5 = 0.5. Check whether the found difference coincides with the value k 2 /2 for some value of k. Coincidence takes place 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 formed interval, is determined . The interval representing the number N = 621 starts with the middle square (even) point of the first circuit and reaches the 12th circuit inclusively. 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 - хоi2 . Knowing the numbers of the contours at the boundaries of the interval, we find its boundary points. The boundaries of the interval are:
• the left border at k = 1, Ch = (2k) 2 = (2 • 1) 2 = 4,
• the right border at k = 12 is Tn = (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 squares, the factorization of the number N = х1i 2 - хоi 2 = (25 + 2) is easily performed (25 - 2) = 27 • 23.
The scheme for solving the factorization problem considered in the example ensures the finding of other alternative pairs of boundaries. Search for the difference C 2k+1 – kп /2, совпадающей с k2 /2 приводит к получению такого совпадения при большем k = 19. Имеем равенство С2k+1 – kп /2 = 190 – 77,5 = 112,5 из которого находим меньшее, т.е. k = √2×112.5 = √225 = 15. Теперь можно приступить к поиску границ интервала и факторизации N.
Границами интервала будут:
• левая граница при k =15, Гл = (2k)2 = (2•15)2 = 900,
• правая при k = 19 есть Гп = (2k + 1)2 = (2•19 + 1)2 = 392 = 1521,
• N = Гп – Гл = х1i2 – хоi2 = 1521 – 900 = 621 и
• N = х1i 2 - хоi 2 = (39 + 30) (39 - 30) = 69 • 9.
Example 4 . (The division of the left number, where half of 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 limit contour Ln = 235 + 237 = 472, its number k p = L / 8 = 472/8 = 59, k p / 2 = 29.5, the values of the boundaries of the limit contour: right Гп = (2k p ) 2 = 118 2 , the left GL = (2k n –1) 2 = 117 2 they correspond to the trivial expansion of the number N = 235 ∙ 1.
Из нумерационной модели следует, что kп/2 = 29.5. Для N = 235 (см. пример ранее) kп(235)/2 = 29.5
Ближайшее значение в столбце k2/2 = 40.5 лежит в строке k = 9.
Ему соответствует разность k2/2 – kп/2 = 40.5 – 29.5 = 11, которая отсутствует в столбце «сумма».
Следующий уровень k = 11 и k2/2 = 60.5, ему соответствует разность k2/2 – kп/2 = 60.5 – 29.5 = 31, которая также отсутствует в столбце «сумма». Следующий уровень k = 13 и k2/2 = 84.5, ему соответствует разность
k2/2 – kп/ 2 = 84.5 - 29.5 = 55, which is present in the column “sum” in the row with the number k = 10.
From this it follows that all the lines starting from number 10 and below are not included in the sum of k p / 2. Therefore, k p / 2 = 29.5 = 11+ 12 + 13/2.
Factor the given number. The numbers of the contours that form the numbering model of the number are found: k = 11, 12, and 13. From k = 13, only the left half of this contour enters the formula.
We calculate the length of the contours L (11) = 8 • 11 = 88; L (12) = 8 • 12 = 96; L (13) = 8 • 13 = 104; the left half of the 13th contour is m (13) = 104/2 –1 = 51. The interval model is 88 + 96 + 51 = 43 + 45 + 47 + 49 + 51 = 235.
We define the boundaries of the interval model:
• Гп (13) = (2 • 13) 2 = 262 = 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 division of the right number, where half of the number (not an integer) in the amount is taken from the smaller contour ).
Let N = 357. This is the right number N = 357 ≡ 1 (mod4). The length of the limiting contour is Ln = 357 + 355 = 712, its number is k p = L / 8 = 712/8 = 89, k p / 2 = 44.5, the boundaries limit contour:
• left Gl = (2k p –1) 2 = 177 2 ,
• the average Hz = (2k n ) 2 = 178 2 ,
• the right Γn = (2k n + 1) 2 = 179 2 they correspond to the trivial expansion of the number N = 357 ∙ 1.
a) x1 = 19; ho = 2; N = Гп (2 ∙ 58) - Гл (58 ∙ 2 - 1) = х1i 2 - хоi 2 = 19 2 - 2 2 = 361 - 4 = (19 + 2) ∙ (19 - 2) = 21 ∙ 17 = 357, k n / 2 = ½ + 2 + 3 + 4 +5 + 6 + 7 + 8 + 9 = 44.5
b) x1 = 61; ho = 58; N = Гп (2 ∙ 58) - Гл (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 series of numbers between odd squares is a multiple of 8. The residue of an odd square in mod 8 is 1. The difference in the values 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 is the number n = 3t, since the extreme numbers are prime by hypothesis.
• LF1 2 = (2n - 1) 2 = 4n 2 - 4n + 1 = 1 + 4n (n - 1) = 1 + 8 C p 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 n 2 ) = 4n (n + 1 - n + 1) = 8n = 8 · 3t = 24t.
If the number N is a multiple of 3, it in the interval model is formed by three semicircuits standing side by side. In other words, if the number is right, then the semicircle is from the smaller contour. For N = 357 = 119 • 3, k n / 2 = 44.5. The value of the number of half-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 is 30. Indeed, 29/2 +30 = 44.5 = k p / 2. If the number N is a multiple of 5 (formed by five half-loops), then the number (k p / 2 - 6) / 5.
Example 6 . ( Relationship between the characteristics of the interval and numbering models of a multiple of three )
For the left number N (x1, xо) = 183 and the right number N (x1, xо) = 189, factorize, determine the number and length of the limit contour of the numbers k p (Nl) = k p (183) = (183 + 185) / 8 = 46, and k p (Nп) = k p (189) = (187 + 189) / 8 = 47. Next, we compose the equation for the number of the limiting half-loop in the numbering model kn (183) / 2 = (k + 1) / 2 + k, whence k n = 3k + 1 and k = (k n - 1) / 3 = 45/3 = 15.
• Large boundary of the interval for N = 183 right even Hz (16) = (2 · 16) 2 = 32 2 = 1024
• smaller left border Гл (15) = (2 • 15 - 1) 2 = 29 2 = 841.
Factorization of the number N = 183 = 32 2 - 29 2 = (32 + 29) (32 - 29) = 61 • 3.
The relationship of the right-hand numbers of the form Nп (x1, хо) = 3t with the sum of the numbers of the contours of the interval model is as follows:
half of the number of the contour plus the number of the next contour of the interval are equal to half the number of the limiting contour k p (Nп) / 2 of the number under investigation.
For the right number N (x1, xo) = 189, the value of the limiting semiconductor k p (189) / 2 = (k – 1) / 2 + k,
whence k p = 47 = 3k - 1 and k = (k p + 1) / 3 = 48/3 = 16. The smaller boundary of the interval for N = 189 the left even lies in the 15 Hz circuit (15) = (2 • 15) 2 = 30 2 = 900 and Гп (16) = (2 • 16 + 1 ) 2 = 33 2 = 1089.
Factorization of the number N = 189 = (33 + 30) (33 - 30) = 63 • 3
Similar calculations can be performed for numbers of left and right multiples of 5, 7, 9, etc.
List of references
[1] Hall M. Combinatorics. -M .: Mir, 1970 .-- 424 p.
[2] Andrews G. Partition Theory. -M .: Science GRFML, 1982. - 256 s.