Ratio Mathematica Volume 40, 2021, pp. 87-111 On odd integers and their couples of divisors Giuseppe Buffoni* Abstract A composite odd integer can be expressed as the product of two odd integers. Possibly, this decomposition is not unique. From 2n + 1 = (2i + 1)(2j + 1) it follows that n = i + j + 2ij. This form of n characterizes the composite odd integers. It allows the formulation of simple algorithms to compute all the couples of divisors of odd integers and to identify the odd integers with the same number of couples of divisors (including the primes, with the number of non trivial divisors equal to zero). The distributions of odd integers ≤ 2n+1 vs. the number of their couples of divisors have been computed up to n ' 5 107, and the main features are illustrated. Keywords: divisor computation; odd integer distribution vs. divisor number. 2020 AMS subject classifications: 11Axx, 11Yxx. 1 1 Introduction: characterization of composite odd and prime numbers Let N be the set of positive integers and P the set of prime numbers with the exception of 2. Composite odd integers 2n + 1, n ∈ N, may be expressed as product of two odd integers, 2n + 1 = (2i + 1)(2j + 1), i,j ∈ N, (1) or of more than two odd integers, i.e. as product of two odd integers in different ways. The decomposition (1) implies that *CNR-IMATI “Enrico Magenes”, Via A. Corti 12, 20133 Milano, Italy; giuseppe.buffoni9av2@alice.it. 1Received on June 8th, 2021. Accepted on June 23rd, 2021. Published on June 30th, 2021. doi: 10.23755/rm.v40i1.618. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper is published under the CC-BY licence agreement. 87 G.Buffoni n = kij = i + j + 2ij, (2) which may also be rewritten in the form n = kij = i(j + 1) + (i + 1)j. (3) Either equation (2) or (3) specifies the structure of a composite odd integer 2n+ 1. Let K ⊂ N be the set of the integers kij ∀i,j ∈ N. Since any odd integer 2n + 1 greater than one is either a composite or a prime number, it follows that n ∈ K ⇐⇒ 2n + 1 ∈ N\P, or, equivalently, n ∈ N\K ⇐⇒ 2n + 1 ∈ P. Remark. More involved characterizations of prime numbers can be formu- lated. They are obtained starting from the observation that all prime numbers greater than c ∈ N, are of the form c#h + ι, where c# represents c primorial, h,ι ∈ N, and ι < c# is coprime to c#, i.e. gcd(ι,c#) = 1. As an example, let c = 4, c# = 6; thus, all prime numbers > 4 may be expressed as 6h + ι with ι = 1, 5. Since 6h + 5 = 6(h + 1) − 1, then all prime numbers may be expressed in the form 6h± 1, with the exception of 2 and 3. Let the odd integer 2n + 1 be written as 2n + 1 = 6h± 1, so that either n = 3h or n = 3h− 1. For composite integers n = kij, and consequently 3 should be a dvisor of either kij or kij + 1. The paper is organized as follows. In section 2 varios formulations of the relationship between n and the pair (i,j) are viewed. An algorithm to compute the divisors of an odd integer is described; it can also be used as a primality test. In sections 3 and 4 it is shown how odd integers with the same number of couples of divisors can be identified. Moreover, the distributions of odd integers ≤ 2n+ 1 vs. the number of their couples of divisors are computed up to n = 5 107 and illustrated. Some concluding remarks can be found in section 5. Details of calculations are reported in appendix. 2 The relationship between n and the pair (i,j) The functional relationship between a composite integer 2n+ 1 and the factors 2i + 1, 2j + 1 of its decompositions, or between n, i, j, can be written in different forms. The decomposition (1) is an inverse proportional relationship (hyperbolic relation) between 2i + 1 and 2j + 1. Here and in the following it is assumed that i ≤ j, so that 2i + 1 ≤ √ 2n + 1 ≤ 2j + 1 (equality holds iff i = j), or equivalently 88 On odd integers and their couples of divisors i ≤ In = 1 2 (−1 + √ 2n + 1) ≤ j. (4) The relation (1) has been written in the forms (2) and (3). These equations define the entries of the matrix K = {kij}, used for the computation of the distri- bution of odd integers vs. the number of their couples of divisors. Properties of K can be found in appendix 1. By making explicit the variable j, (2) can be written in the form of an homo- graphic function j = φn(i) = n− i 2i + 1 , 1 ≤ i ≤ In. (5) Thus, 2i + 1 is a divisor of both 2n + 1 and n − i. From (12) in appendix 1, it follows that 2i + 1 is also a divisor of n−kii. Equation (5) can be used to compute the couples of divisors of an integer 2n+1 by means of the following algorithm: given n, compute φn(i) for i = 1, 2, ..., [In], where [·] is the integer part of the real argument; if for some i = iq we obtain that jq = φn(iq) ∈ N, then 2iq + 1 ≤ √ 2n + 1 ≤ 2jq + 1 is a couple of divisors of 2n + 1. The order of the number of operations is √ n/2. The algorithm can also be used as a primality test: if the computed φn(i) /∈ N ∀i, then 2n + 1 is a prime. The functions y = φn(x), x+y, xy, y−x, of the real variable x, are monotone for 0 ≤ x ≤ In (figure 1). In, defined in (4), is the unique positive solution to the equation φn(x) = x, i.e. 2x2 + 2x−n = 0. The point x = In corresponds to the minimum of x + y, to the maximum of xy, and, obviously, to y −x = 0. By means of a change of variables, the relationship (1) can be put in the form 2n + 1 = (s + t)(s− t) = s2 − t2, with s = i + j + 1, t = j − i, (6) while (2) and (3), representing partitions of the integer n in two sections, can be put in linear forms n = s + 2t, with s = i + j, t = ij, (7) n = s + t, with s = i(j + 1), t = (i + 1)j. (8) Equation (6) shows the well known fact that composite odd integers can be written as a difference of two squares in different ways, while for a prime only holds the decomposition 2n + 1 = (n + 1)2 −n2. 89 G.Buffoni Figure 1: Top left y = φn(x), top right x + y, bottom left xy, bottom right y−x. Circle: point x = In on the x axis, and corresponding points on the curves. n = 50, In = 4.52. 90 On odd integers and their couples of divisors Given n,s ∈ N, it is possible to prove when s and t = n−s can be expressed as either in (7) or in (8). The details are reported in appendix 2: it is shown that i,j are solutions to second order equations, and they are integer satisfying either (7) or (8), iff the square root of a quadratic form in n and s is an integer, 3 Identification of odd integers ≤ 2n + 1 with the same number of couples of divisors Let 2m + 1 be a composite integer and let ψ(m) = number of couples of divisors of 2m + 1. Obviously, ψ(m) is also equal to the number of divisors of 2m + 1 ≤ √ 2m + 1. If ψ(m) = ν, then the entry m = kij, with i ≤ j, appears ν times in the matrix K = {kij}. Composite integers 2m + 1 with m ≤ n are identified by the pairs (i,j) such that 4 ≤ m = kij ≤ n. (9) By assuming i ≤ j, it follows that (9) holds for the pairs (i,j) ∈ Ω(4,n) = {i,j ∈ N : i = 1, 2, ..., [In]; j = i, i + 1, ..., [φn(i)]}. An estimation of the number of these pairs as n −→ +∞ is given by κ∗n ' n( 1 4 ln(n) + c). (10) with c = −0.4415. The details can be found at the end of appendix 1. In doing so we do not consider the couple (0,n), corresponding to the couple of trivial divisors (1, 2n + 1). The odd integers 2m+ 1, m ≤ n, with the same number of couples of divisors can be identified by means of the following algorithm: let ψ(m) = 0, m = 1, ...,n; compute kij, ∀(i,j) ∈ Ω(4,n); for kij = m let ψ(m) = ψ(m) + 1. When ψ(m) = 0, then the integer 2m + 1 is a prime. All the integers 2m + 1, with ν couples of divisors, are identified by the values of m for which ψ(m) = ν. 91 G.Buffoni Furthermore, let Πn(ν) = number of odd integers ≤ 2n + 1 with ν couples of divisors. Πn(0) is the number of primes ≤ 2n + 1, except 2. Πn(ν) is estimated as follows: for ν = 0 : Πn(0) = number of ψ(m) = 0, for ν > 0 : Πn(ν) = 1 ν ∑ ψ(m)=ν ψ(m). This approach, used to identify the prime numbers, is an equivalent formu- lation of the common implementation of the Eratostene’s sieve (see for example the C program source in (2), section 6.3). In this case ψ(m) could be a logical variable. The algorithm may be easily applied to the integers in a generic set [2a + 1, 2n + 1], with 4 < a < n, to identify either the odd integers in this interval with the same number of couples of divisors or the primes. The inequalities identifying these integers, a ≤ kij ≤ n, with i ≤ j, hold for the pairs (i,j) ∈ Ω(a,n) = {i,j ∈ N : i = 1, 2, ..., [In]; j = Ja(i),Ja(i)+1, ..., [φn(i, )]}, where: when i ≤ [Ia] : either Ja(i) = [φa(i)] + 1, φa(i) /∈ N, or Ja(i) = φa(i) ∈ N; when i > [Ia] : Ja(i) = i. The set of the points (i,j) ∈ Ω(a,n), with integer coordinates, is contained in a closed and convex set Ω∗(a,n) of a plane. See figure 2, where the boundaries of this set are plain defined. Some remarks on the case with large n and n − a << n can be found in appendix 3. 92 On odd integers and their couples of divisors Figure 2: Set Ω∗(a,n) in the plane (x,y). Continuous lines: y = φa(x) < y = φn(x); dotted line: y = x; asterisk: points (0,a), (0,n); circle: points (Ia, 0), (In, 0), and corresponding points on the curves. Different scales for x and y. 93 G.Buffoni 4 Distributions of odd numbers vs. the number of their couples of divisors The computation of the distributions Πn(ν) has been performed, by means of the algorithm described in the previous section, for n ≤ 5 107, i.e. for odd integers 2n + 1 ≤ 108 + 1 (see the tables 1, 2 for some values of n). n = 5 n = 50 n = 5 102 n = 5 103 n = 5 104 ν 0 4 25 167 1228 9591 1 1 20 207 1964 18259 2 5 52 382 2824 3 56 925 11380 4 5 50 308 5 12 264 3200 6 0 4 32 7 1 128 2785 8 22 265 9 9 188 10 0 3 11 24 826 12 1 13 18 14 27 15 195 16 0 17 66 18 0 19 13 20 0 21 0 22 1 23 18 tot. 4 1 30 20 224 276 1686 3314 13052 36948 Table 1: Distribution Πn(ν) of odd integers ≤ 2n + 1, with ν couples of divisors, for n = 5, 50, 5 102, 5 103, 5 104. Let ν∗n = maximum number of couples of divisors of odd integers ≤ 2n + 1. 94 On odd integers and their couples of divisors n = 5 105 n = 5 106 n = 5 105 n = 5 106 ν ν 0 78497 664578 1 168522 1555858 2 21711 174188 3 126518 1336044 4 2030 14919 5 32314 309137 6 236 1758 7 42022 542740 8 2228 17481 9 2171 21649 10 16 74 11 13521 172181 12 2 12 13 238 2343 14 295 2376 15 5733 105676 16 0 4 17 1403 17487 18 0 0 19 545 8847 20 24 268 21 0 15 22 11 60 23 1537 34648 24 6 57 25 0 0 26 50 705 27 17 566 28 0 0 29 67 1503 30 0 0 31 179 8098 32 0 0 33 0 0 34 0 7 35 88 3589 36 0 0 37 0 4 38 0 0 39 13 922 40 0 11 41 0 69 42 0 0 43 0 0 44 0 65 45 0 0 46 0 0 47 6 1693 48 0 49 7 50 0 51 0 52 0 53 118 54 0 55 16 56 0 57 0 58 0 59 86 60 0 61 0 62 1 63 91 64 0 65 0 66 0 67 0 68 0 69 0 70 0 71 46 72 0 73 0 .. .. .. .. 78 0 79 3 tot. 105106 876564 tot. 394894 4123436 Table 2: Distribution Πn(ν) of odd integers ≤ 2n + 1, with ν couples of divisors, for n = 5 105, 5 106. (Since ν∗n = 143 for n = 5 10 7, this case is not reported here). 95 G.Buffoni Thus, Πn(ν) = 0 for ν > ν∗n. It has been estimated (table 3, figure 3) that ν ∗ n increases as a power of n. The following approximation has been found by a fitting procedure ν∗n = µn λ, µ = e0.3992±0.1050, λ = 0.2586 ± 0.0083, 5 102 ≤ n ≤ 5 107. n 5 102 5 103 5 104 5 105 5 106 5 107 ν∗n 8 12 24 48 80 144 µ nλ 7.43 13.48 24.46 44.37 80.48 145.99 Table 3: Computed values of ν∗n and those produced by ν ∗ n = µn λ for some values of n. A visual inspection of the patterns of Πn(ν) (the scattered plots of ln(Πn(ν)) vs. ν are shown in the figures 4, 5) suggests that the odd integers with even and odd numbers of couples of divisors should belong to different populations. This view has to be considered only as a guess of the author, trying to interpret special features of Πn(ν). Anyhow, to avoid repetitions, we nickname these integers as ravens the odd integers with 2ν couples of divisors, cods the odd integers with 2ν + 1 couples of divisors. The primes, identified by ν = 0, are included in the ravens. We have that Πn(2ν) = number of ravens ≤ 2n + 1, Πn(2ν + 1) = number of cods ≤ 2n + 1. For n > 150, in general Πn(2ν) < Πn(2ν + 1). (11) Only for few values of ν this inequality is not satisfied in the computed distribu- tions (table 4). The number of ravens is less large than that of cods (see the last row in the tables 1, 2). 96 On odd integers and their couples of divisors Figure 3: ν∗n vs. ln(n). Circles: computed values, continuous line: approximation ν∗n = µ exp(λ ln(n)) for 2 10 2 ≤ n ≤ 5 107. n 5 102 5 103 5 104 5 105 5 106 5 107 8-9 8-9 8-9 20-21 20-21 24-25 20-21 24-25 24-25 26-27 44-45 32-33 44-45 74-75 80-81 N. couples 0 1 1 4 3 6 Table 4: Couples of ν for which inequality (11) is not satisfied. 97 G.Buffoni Figure 4: Distributions ln(Πn(ν) vs. ν for n = 5 102, 5 103 5 104, 5 105. Circle: ravens, asterisk: cods. 98 On odd integers and their couples of divisors Figure 5: Distribution ln(Πn(ν)) vs. ν for n = 5 106, n = 5 107. Circle: ravens, asterisk: cods. 99 G.Buffoni For ' 5 102 ≤ n ≤' 5 104 both the points Πn(2ν) and Πn(2ν + 1) show well distinct decreasing trends with ν (figure 4). However, points not belonging to the initial trends begin to appear for n ' 5 103. Indeed, new branches (generally decreasing with ν) grow for increasing n, beginning at ν values not detected in the previous branches (figure 5). A branch may be roughly defined as a sequence of points in the plane (ν, ln Π) which approximately lay on a straight line. For example, in the plot for n = 5 105 in figure 4, we can recognize two raven branches: the initial at the points ν = 0, 2, 4, 6, 8 and a second branch at ν = 8, 14, 20, 22, 24 (the point at ν = 8 is already present in the distribution for n = 5 103), and a single point at ν = 26. Moreover, four cod branches: the initial at the points ν = 1, 3, 7, 11, 15, 23, 31, 35, and then at ν = 5, 9, 13, at ν = 17, 19, 27, and at ν = 29, 39. The attribution of a point to a branch is sometimes uncertain. Indeed, the interpretation of the evo- lution of the distributions Πn(ν) with n in terms of growing branches is arbitrary. The straight lines in the plane (ν, ln Π) approximating the initial trends of both ravens and cods are estimated by a fitting procedure (table 5, figure 6). n α±σ β ±σ σ ravens 5 105 11.3131 ± 0.2663 −0.8846 ± 0.0377 0.3901 5 106 13.4700 ± 0.2292 −0.9257 ± 0.0324 0.3358 5 107 15.7156 ± 0.1925 −0.9823 ± 0.0272 0.2820 cods 5 105 12.2196 ± 0.1155 −0.2234 ± 0.0059 0.1971 5 106 14.3920 ± 0.1244 −0.1770 ± 0.0063 0.2122 5 107 16.4599 ± 0.2084 −0.1484 ± 0.0106 0.3557 Table 5: Initial branches of Πn(ν): coefficients of the linear relationship ln(Πn(ν)) = α+βν and their standard deviations σ. Last column: σ of ln(Πn(ν)). All the points (ν, ln(Πn(ν)) are contained in a bounded region of the plane (ν, ln Π) (figures 4, 5). This region is bounded from the bottom by the initial branch of ravens, starting from the number of primes ln(Πn(0)) and ending in ν ' 20, and then by the axis ln Π = 0. From the top by the initial branch of cods, starting from ln(Πn(1)) and ending in ν ' 40, and then by sparse decreasing cod points, belonging to different branches. The upper boundary can be approximated by a straight line with ' the same slope of the initial cod trend. A guess about the description of the evolution of Πn(ν) with n has been sug- 100 On odd integers and their couples of divisors Figure 6: Top: initial branch of cods at ν = 1, 3, 7, 11, 15, 23, 31, 35. Bottom: initial branch of ravens at ν = 0, 2, 4, 6, 10, 12. Triangle: n = 5 105; square: n = 5 106; circle: n = 5 107. Continuous line: linear approximation. 101 G.Buffoni gested by the most simple formula ((1), p. 8) approximating the number of primes ≤ 2n + 1: Πn(0) = 2n + 1 ln(2n + 1) . Taking into account that ln(ln(n)) ' 1.2334 + 0.0992 ln(n), 102 ≤ n ≤ 107, this relationship can be approximated by ln(Πn(0)) ' −0.5403 + 0.9008 ln(n). Fitting of ln(Πn(ν)) to the linear expression α + β ln(n) has been carried out for ν = 0, 1, 2, 3 (table 6, figure 7). The straight lines are ' parallel for the ravens ν = 0, 2, while the lines for the codes ν = 1, 3 show different slopes (the line for ν = 3 is not shown in figure 7 for clearness of the figure). It is worth here to remind that a logarithmic approximation of a quantity may lead to a rough estimation of the quantity. ν α±σ β ±σ σ 0 −0.4902 ± 0.0755 0.8993 ± 0.0068 0.0847 1 −0.7130 ± 0.0282 0.9714 ± 0.0025 0.0317 2 −1.7076 ± 0.0550 0.8944 ± 0.0049 0.0617 3 −2.3972 ± 0.1632 1.0721 ± 0.0140 0.1528 Table 6: ln(Πn(ν)) vs. ln(n): coefficients of the linear relationship ln(Πn(ν)) = α + β ln(n) and their standard deviations σ. Last column: σ of ln(Πn(ν)). Ten n−points, from n = 100 to n = 5 107 are used in fitting ln(Πn(ν)) for ν = 0, 1, 2. Since Πn(3) is very small for n = 100, this point is not included for ν = 3. The ”regularity” of some relationships between Πn(ν) (figure 8) may arouse some surprise. We have performed a survey on the ratios between Πn(ν) with ν = 0, 1, 2, 3. The trends of the ratios Πn(1)/Πn(0), Πn(3)/Πn(0), Πn(3)/Πn(1) (figure 8 top), increasing with n, seem to be reasonable. On the other hand, the trends of the ratios Πn(2)/Πn(ν), ν = 0, 1, 3, (figure 8 bottom), are disturbing. This might be due to the shortage of ravens with ν = 2 detected. Obviously, computations with n greater than n = 5 107, the maximum value here considered, should be carried out to confirm the results, and to try to explain the trends. A careful analysis to produce a thorough knowledge has to be hoped for. 102 On odd integers and their couples of divisors Figure 7: Distributions ln(Πn(ν)) vs. ln(n). Circle: Πn(0), asterisk: Πn(1), square: Πn(2). Continuous line: linear approximation. 5 Concluding remarks We have focused our attention on the computation of the couples of divisors of odd integers. Indeed, any even integer can be written in the form 2m (2n + 1), with m ≥ 1, n ≥ 0. Thus, it is characterized by the power of two, and possibly by an odd integer with its divisors. The following considerations hold for the computed distributions for n up to 5 107. For small n the following inequalities hold: Πn(0) > Πn(1) > Πn(2) > Πn(ν), ν > 2, n < 149. Πn(0) is the number of primes, Πn(1) is the number of cods either products of two primes or primes cubed, while Πn(2) is the number of ravens either products of primes by primes squared or primes to the fourth. The previous inequalities can be explained by the following reasonings: for small n, (1) the density of primes is high, and (2) the prime factors in the divisors of both cods and ravens should be small. As an example, the possible decompositions of cods ≤ 101 with ν = 1 are reported here: 103 G.Buffoni Figure 8: Ratios of distributions Πn(ν) vs. ln(n). Top: Πn(1)/Πn(0) aster- isk, Πn(3)/Πn(0) circle, Πn(3)/Πn(1) square. Bottom: Πn(2)/Πn(0) asterisk, Πn(2)/Πn(1) circle, Πn(2)/Πn(3) square. 104 On odd integers and their couples of divisors p1pi, i = 1, ..., 10; p2pi, i = 2, 3, ..., 7; p3pi, i = 3, 4, 5; p1p 2 1; where p1 = 3, p2 = 5, ... are the primes. Thus, for small n, few factors produce cod integers ≤ 2n + 1. For increasing n, the inequality Πn(1) > Πn(ν), ν 6= 1, hold. For n = 149 we have Πn(0) = Πn(1) (table 7. n Πn(0) Πn(1) Πn(2) 50 25 20 5 100 45 40 10 148 61 60 16 149 61 61 16 150 61 62 16 200 78 83 21 250 94 104 25 Table 7: The transition from Πn(0) > Πn(1) to Πn(0) < Πn(1). The distributions Πn(ν) have been obtained by identifying all the couples (2i+ 1, 2j + 1) of divisors of the integers 2m + 1 with m = kij ≤ n. For large n the number κ∗n of kij ≤ n is n(ln(n)/4 + c) (10). The number k∗a+1n of kij such that a + 1 ≤ kij ≤ n can be estimated by k∗a+1n = k ∗ n −k ∗ a = 1 4 (n ln(n) −a ln(a)) + c(n−a). Under the assumption n−a << a < n it follows that 1 < n a = 1 + ( n a − 1) << 2, so that 0 < n a − 1 << 1. Thus, k∗a+1n = k ∗ n−k ∗ a = (n−a)( 1 4 ln(n) + c) + 1 4 a ln( n a ) = (n−a)( 1 4 ln(n) + c + 1 4 ). Some explanations on the numerical computations are given. The algorithms described in sections 2 and 3 can be easily implemented in Fortran language. The algorithm (in section 2) for the computation of the couples of divisors of a given integer 2n + 1 does not require the storage of large dimension vectors. It has been successfully used to determine the couples of divisors of odd composite integers (and whether a number is prime or composite), up to input numbers of 105 G.Buffoni order 260 ' 1018. Note that quadruple precision for floating point operations is necessary for numbers of order 260. We do not have recourse to computer algebra systems, with numbers of variable length (3; 4). The algorithm (in section 3) for the computaion of the distributions Πn(ν) requires the storage of an INTEGER*8 vector; the computation has been carried out up to the limit of the storage carrying capacity of the available computer (about a vector of 6 107 of INTEGERS*8 entries). The computation of the primes in a given interval [2a+ 1, 2n+ 1] has been performed either with small n−a ∈ [5, 50] and a up to 1018, or with large n−a ∈ [102, 4 107] and a up to 109. Acknowledgments I am very grateful to Fabrizio Luccio (Un. Pisa) and Alessandro Zaccagnini (Un. Parma) for reading an old version of the work, and for their precise criticism, and to Andrea Cappelletti (ENEA Pisa) and Sara Pasquali (CNR IMATI Milano) for their prompt replies to my requests. References [1] T. M. Apostol, Introduction to analytic number theory. Springer-Verlag, Berlin, 1976. [2] A. Languasco and A. Zaccagnini, Introduzione alla crittografia. U. Hoepli Editore, Milano, 2004. [3] PARI/GP computer algebra system develoiped by H. Cohen et al., 1985. Available from: http://pari.math.u.bordeaux.fr/ [4] The GNU MP Bignum Library. Available from: http:77gmplib.org/ Appendix 1. The matrix K = {kij} Obviously, the symmetry property holds for the elements kij of K: kij = kji,∀ i,j ∈ N. Thus, they can be represented by means of a symmetric matrix. (see the table 8). Since some composite odd numbers 2n + 1 may be expressed as product of two odd numbers in different ways, it follows that 2n + 1 = (2i1 + 1)(2j1 + 1) = (2i2 + 1)(2j2 + 1) =⇒ ki1j1 = ki2j2, 106 On odd integers and their couples of divisors as it can be observed in the matrix K (table 8). The number of couples (i,j) such that n = kij, if they exist, is the number of decompositions of 2n + 1 in two factors. −↓ i j → 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 2 12 17 22 27 32 37 42 47 52 57 62 67 72 77 3 24 31 38 45 52 59 66 73 80 87 94 101 108 4 40 49 58 67 76 85 94 103 112 121 130 139 5 60 71 82 93 104 115 126 137 148 159 170 6 84 97 110 123 136 149 162 175 188 201 7 112 127 142 157 172 187 202 217 232 8 144 161 178 195 212 229 246 263 9 180 199 218 237 256 275 294 10 220 241 262 283 304 325 11 264 287 310 333 356 12 312 337 362 387 13 364 391 418 14 420 449 15 480 Table 8: Matrix K = {kij} for 1 ≤ i ≤ j ≤ 15. i=row and j=column index. Besides the symmetry identity, the elements kij satisfy other combinatorial properties, obtained from the equation (2n + 1)(2kij + 1) = 2knkij + 1. The identities kpkqr = kqkrp = krkpq, p,q,r ∈ N follow from the product of three odd numbers (2p + 1)(2q + 1)(2r + 1), while the identities kkpqkrs = kkprkqs = ... = kpkqkrs = kqkpkrs = ..., p,q,r,s ∈ N follow from the product of four odd numbers (2p + 1)(2q + 1)(2r + 1)(2s + 1). Obviously, more involved identities are obtained from products of more than four odd numbers. The quantities kij − i = (2i + 1)j and kij − j = i(2j + 1) are divisible by 2i + 1, j and by i, 2j + 1, respectively. Moreover, kij can be written in the form 107 G.Buffoni kij = kii+(2i+1)(j−i), i = 1, 2, ..., j = i, i+1, ... with kii = 2i2 +2i, (12) which leads to the following recurrence formula for the computation (by means of additions) of the entries of the i− th row, with i ≤ j, of the matrix K: kij = ki (j−1) + 2i + 1, j = i + 1, i + 2, ... Now we estimate κ∗n = number of pairs (i,j) with 1 ≤ i ≤ j such that 4 ≤ kij ≤ n. It is given by κ∗n = In∑ i=1 [qn(i)]. where qn(i) = φn(i) − i + 1 = 1 2 ( 2n + 1 2i + 1 − (2i− 1)), and here In denotes the integer part of the quantity defined in (4). qn(i) are de- creasing with i, and qn(In) = 1 ≤ qn(i) ≤ qn(1) = n− 1 3 . By direct calculation we have that Qn = In∑ i=1 qn(i) = = (n + 1 2 ) In∑ i=1 1 2i + 1 − 1 2 I2n = (n + 1 2 ) In∑ i=1 1 2i + 1 − 1 4 (1 + n− √ 2n + 1). Taking into account the logarthmic growth of the harmonic series, we have for n large enough In∑ i=1 1 2i + 1 ' ln( 2In + 1√ In ) + γ 2 − 1, where γ ' 0.5772 is the Euler-Mascheroni constant. It follows that 108 On odd integers and their couples of divisors Qn n −→ ln(2 √ In + 1 √ In ) + γ 2 − 5 4 ' 1 4 ln(n) + c as n −→ +∞, with c = 0.5(1.5 ln(2) + γ − 2.5) = −0.4415. Since the following inequalities Qn − In ≤ k∗n ≤ Qn. hold, and In/n −→ 0 as n −→ +∞, for the increasing function κ∗n/n we have that κ∗n n −→ 1 4 ln(n) + c as n −→ +∞. A linear fit of κ∗n/n vs. ln(n), for 10 ≤ n ≤ 1017.5, produces the line κ∗n/n ' (−0.4017 ± 0.0102) + (0.2486 ± 0.0004) ln(n). Appendix 2. The partitions n = s + 2t and n = s + t Equation (2) represents a partition of the integer n in two sections s = i + j and n−s = 2ij, with 2s ≤ n (2s = n iff i = j = 1). (13) Since i ∈ [1,In] and j = φn(i), the bounds for s in the partition (13) are given by In + φn(In) = 2In and 1 + φn(1) (see figure 1, plot of x + y). Therefore, the set of admissible values for s is Ω1 = [2In, n + 2 3 ]. (14) From (13) it follows that i and j are the positive integer solutions,if they exist, to the equation x2 −sx + n−s 2 = 0. (15) The solutions to (15) are x± = 1 2 (s± √ ∆, with ∆ = s2 + 2s− 2n. (16) Since ∆ and s have the same parity, positive integer solutions exist iff 109 G.Buffoni ∃s ∈ Ω1 : √ ∆ ∈ N. Equation (3) represents another partition of the integer n in two sections s = i(j+1) and n−s = (i+1)j, with 2s ≤ n (2s = n iff i = j). (17) The set of admissible values for s is Ω2 = [ n + 2 3 , n 2 ]. (18) From (17) it follows that i is solution to the following equation i2 + (n− 2s + 1)i−s = 0, and j = i + n− 2s. The results are given by i = 1 2 [−1 − (n− 2s) + √ ∆], j = 1 2 [−1 + (n− 2s) + √ ∆], where ∆ = 2n + 1 + (n− 2s)2. Since ∆ and s have the same parity, positive integer solutions to the system (17) exist iff ∃s ∈ Ω2 : √ ∆ ∈ N. We can summarize the reasonings on the partitions of n in the following im- plications: n ∈ K, ∆ = s2 + 2s− 2n ⇐⇒∃s ∈ Ω1 : √ ∆ ∈ N, n ∈ K, ∆ = 4s2 − 4ns + 2n + 1 ⇐⇒∃s ∈ Ω2 : √ ∆ ∈ N. 110 On odd integers and their couples of divisors Appendix 3. Remarks on the sets Ω(a,n) and Ω∗(a,n) Here we consider the case n−a << Ia = min(a,n,Ia,In). (19) For example, this situation happens when we are looking for very few primes in [2a + 1, 2n + 1] with large a. In virtue of the prime distribution ((1), p. 8) we should choose n−a ' ι 2 ln(2a + 1), with 1 ≤ ι ≤ 10. The difference between the top and bottom boundary lines of Ω∗(a,n) (figure 2) is φn(i) −φa(i) = n−a 2i + 1 . It is decreasing with i, and φn(i) −φa(i) < 1 for i ≥ [I0], I0 = n−a− 1 2 + 1 < Ia. (20) When (20) holds, at most only one integer is in [φa(i),φn(i)]. It follows that for i ≥ [I0] the points of Ω∗(a,n) with integer coordinates are the points (i,j) with j = [φa(i) + 1] = [φn(i)]. Furthermore, since Ia < 2 √ n + a, from (19) we have that also n − a < 2 √ n + a, which implies In−Ia < 1. Thus, the boundary of Ω∗(a,n) between the points (Ia,Ia) and (In,In) (figure 2) does not contain points with integer coordi- nates. In the limit case a = n, the set Ω∗(a,n) (figure 2) reduces to the curve y = φn(x) for 0 ≤ x ≤ In, and Ω(n,n) is then defined by (i,j) ∈ Ω(n,n) = {i = 1, 2, ..., [In] : φn(i) ∈ N, j = φn(i)}. The algorithm described in section 2 identifies the points of the set Ω(n,n). 111