The quotient triangle, the parabola-hyperbola sequence, the remainder triangle and perfect numbers

The quotient triangle
Consider a positive integer n. Then for all k=1,2,3...n do the floor operation T_q[n]= \left\lfloor \tfrac{n}{k}\right\rfloor. Say n=10, we get T_q[10]=10, 5, 3, 2, 2, 1, 1, 1, 1, 1, a sequence of quotients of the division n \div k. If we do this for all n=1, 2, 3, 4 ... we get the quotient triangular array T_q[n,k] whose top few elements are show below.

\begin{tabular}{|*{10}{r|}} \cline{1-1} 1\\ \cline{1-2} 2 & 1\\ \cline{1-3} 3 & 1 & 1\\ \cline{1-4} 4 & 2 & 1 & 1\\ \cline{1-5} 5 & 2 & 1 & 1 & 1\\ \cline{1-6} 6 & 3 & 2 & 1 & 1 & 1\\ \cline{1-7} 7 & 3 & 2 & 1 & 1 & 1 & 1\\ \cline{1-8} 8 & 4 & 2 & 2 & 1 & 1 & 1 & 1\\ \cline{1-9} 9 & 4 & 3 & 2 & 1 & 1 & 1 & 1 & 1\\ \cline{1-10} 10 & 5 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1\\ \cline{1-10} \end{tabular}

It is obvious that the first column T_q[n,1] is the sequence of n itself. The second column T_q[n,2] is the sequence of positive integers, each repeated twice; the third column T_q[n,3] is the sequence of positive integers, each repeated thrice; so on.

It we linearize this triangular array we get the sequence f_q= 1, 2, 1, 3, 1, 1, 4, 2, 1, 1.... Since each row of the triangular array adds n=1, 2, 3, 4... elements to the sequence, it grows as the sum of numbers from 1:n. We see that the successive maxima are attained at the following terms of f_q: 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56… We can plot f_q by placing the first term f_q[1] at 0, i.e., its x-coordinate will be 0, while its y-coordinate will be f_q[1]; for x=1, y=f_q[2] and so on. Based on the sum of integers 1:n we can show that the successive maxima attained by the sequence would be bounded in this plot by the parabola (Figure 1):

y=\dfrac{\sqrt{1+8x}-1}{2}+1

Quo_Rem_Fig1Figure 1

This sequence f_q also features cycles of decaying values (Figure 1) between successive maxima, starting from one maximum and going to 1 before jumping back to the next maximum and decaying again. Since the quotients are successively determined by n/1, n/2, n/3...3 = n\big/ n/3, 2 = n\big/ n/2, 1 = n\big/ 1/n, each cycle of the sequence of length n is a discrete form of the rectangular hyperbola (Figure 2):

y=\dfrac{n}{x}

Quo_Rem_Fig2Figure 2

Thus, we may term sequence f_q the parabola-hyperbola sequence. Since any n/2 < k \le n will produce quotient 1, the fraction of 1s in f_q will converge to f(1)=1-1/2=1/2; similarly, n/3 < k \le n/2 with produce quotient 2; hence, the fraction of 2s in f_q will converge to f(2)=1/2-1/3=1/6. Thus, generally f(k) \sim \tfrac{1}{k(k+1)}.

We then define a summatory sequence \varsigma[n] such that each term is the sum of the nth row of the quotient triangular array T_q:

\varsigma[n]=\displaystyle \sum_{k=1}^n T_q[n,k]

This sequence goes thus: 1, 3, 5, 8, 10, 14, 16, 20, 23, 27… and is shown graphically in figure 3.

Quo_Rem_Fig3Figure 3

Each term of this sequence is the sum of the terms in a given hyperbolic cycle (Figure 2) of sequence f_q (Figure 1). Thus, it can be approximated in continuous form by the area under the hyperbola corresponding to each cycle y=n/x. Hence, we can create a continuous approximation for \varsigma[n] by the integral function:

y=\displaystyle \int_1^x \dfrac{x dt}{t}=x\log(x)

This is shown by the red curve in Figure 3. We notice that this continuous approximation falls short of actual discrete \varsigma[n] sequence. This correction factor can be empirically determined using the method of least squares to be a linear term. Thus, with this correction the below function provides a good fit for the average behavior of \varsigma[n]:

y=x\log(x)+0.154 x

The empirical determination of this correction term prompted us to try to determine it from first principles. The function y=x\log(x) is a continuous approximation of the area in one cycle of the sequence f_q. But in reality our f_q cycles are approximately the discrete harmonic series as opposed to a smooth hyperbola. From Euler’s work we know that the difference between the discrete form and the continuous integral converges to that mysterious number Euler’s constant \gamma= 0.5772157... for a unit hyperbola. To make use of this we tried some experiments with the hyperbola and realized that the best way to capture the area of the cycle was to use the symmetry of the hyperbola y=n/x about the line y=x (Figure 2). Here, we can count all n/k in a cycle vertically till \sqrt{n} (see vertical line in Figure 2). The due to symmetry we can make the count again from the other end horizontally till \sqrt{n}. This way we would have completely covered all the discrete counts except that we would have counted the square \sqrt{n} \times \sqrt{n} twice. Hence, need to subtract n from our sum. We can get the two symmetric discrete sums now by the addition of \gamma to the integral of the continuous form. Thus, we can write the approximate area for a cycle and hence the function approximating \varsigma[n] as:

y=x(2\displaystyle \int_1^{\sqrt{x}} \dfrac{dt}{t}+\gamma)-(\sqrt{x})^2= 2x(\log(\sqrt{x})+\gamma)-x=2x(\dfrac{1}{2}\log(x)+\gamma)-x=x\log(x)+(2\gamma-1)x

Thus, we get our correction term to be 2\gamma-1=0.1544313.... It gave us great pleasure to have figured this out from scratch without any study of mathematical literature in this regard. We noticed that this already good fit can be made even better by addition of a further constant term c=5.479. We do not know if this is really a constant or is some subtle term currently beyond our reach. Thus, we may write the final function approximating summatory \varsigma[n] sequence as:

y=x\log(x)+(2\gamma -1)x+5.479

This function gives a mean difference of 6.8 \times 10^{-4} with \varsigma[n] for n=1:30000 (Figure 3: light blue dashed line). While this captures the average behavior of \varsigma[n], examination of the specific behavior of \varsigma[n] shows that it exhibits saltations that are greater than usual at certain values. To better understand this we created the difference sequence \Delta \varsigma[n] (Figure 4):

\Delta \varsigma[n]= \varsigma[n+1]-\varsigma[n]

Quo_Rem_Fig4Figure 4. We are yet to figure a curve to fit the successive maxima attained by \Delta \varsigma[n].

The sequence \Delta \varsigma[n] shows several interesting features which we consider in detail below:
1) The lowest value it ever attains is 2. A closer examination of the indices at which \Delta \varsigma[n]=2 reveals that they correspond to n+1 being a prime in the parent \varsigma[n] sequence. Thus, there are as many minima in \Delta \varsigma[n] as there are primes. This can be explained thus: Since, a prime is completely divisible only by k=1, n, these two values will generate quotients of 1 and n respectively to add to the quotient sum. The remaining quotients will be the same as previous number as none of the other k between 1 and n will perfectly divide the prime. Thus, the quotient sum will minimally differ from that of the previous number by 2.

2) Jumps above the median value of 6 (for this range; Figure 4: violet line) have propensity to increase with increasing n. Analysis of these jumps revealed that they have a significantly higher propensity to occur at n=6k-1. Figure 5 shows a box-plot of \Delta \varsigma[n], which indicates that the median value of this sequence for n=6k-1 is significantly higher than median value of the sequence for any other n as well as the median value of the overall sequence. This can be explained by considering the following n=6k-1 corresponds to n=6k in the parent \varsigma[n] sequence. A number of the form 6k will undergo complete divisions by at least 1, 2, 3, 6 out of the first 6 k. However, the number before it 6k-1 will not be divisible by 2, 3 or their multiples. Since it cannot undergo complete division by them, its quotients will be less than the corresponding ones of 6k by 1. Thus there will be a jump in \Delta \varsigma[n] corresponding to n=6k in \varsigma[n]. As e.g. consider 12:
\varsigma[10]= 10+5+3+2+2+1+1+1+1+1=27
\varsigma[11]= 11+5+3+2+2+1+1+1+1+1+1=29
\varsigma[12]= 12+6+4+3+2+2+1+1+1+1+1+1=35;
\varsigma[13]= 13+6+4+3+2+2+1+1+1+1+1+1+1=37
Thus, \varsigma[12] causes a spike in \Delta \varsigma[11]=6 due to completion of divisions by 2,3,4,6.

Quo_Rem_Fig5Figure 5.

3) Notably, the successive record values of \Delta\varsigma[n] for n<30000 are attained at: 1, 3, 5, 11, 23, 35, 47, 59, 119, 179, 239, 359, 719, 839, 1259, 1679, 2519, 5039, 7559, 10079, 15119, 20159, 25199, 27719 (Figure 4). These values of n correspond to 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560, 10080, 15120, 20160, 25200, 27720 in \varsigma[n]. Remarkably, these latter numbers are the highly composite numbers first defined by Ramanujan in 1915 CE. They are numbers with more divisors than any integer smaller than them. We can see why these highly composite numbers spawn maxima in \Delta\varsigma[n] — they will be maximally completely divided and thus yield the largest quotient sum for any number up to them. Thus, \Delta\varsigma[n] presents them as antipodes to the primes. Further, Ramanujan defined a second more inclusive set of numbers, the largely composite numbers, which are numbers with more or the same number of divisors than any integer smaller than them. This more inclusive set spawns high-points in \Delta\varsigma[n], which are not maxima but still stand out (Figure 4).

As an aside one may note that the above n at which the \Delta\varsigma[n] maxima occur are often primes: 15 out of the 24. Most of these are also in particular Sophie Germain or safe primes (primes of form where if p is a prime and 2p+1 is also a prime. Then the former is Sophie Germain prime and the latter a safe prime).

4) The successive record values of \Delta\varsigma[n] are: 2, 3, 4, 6, 8, 9, 10, 12, 16, 18, 20, 24, 30, 32, 36, 40, 48, 60, 64, 72, 80, 84, 90, 96… It turns out this sequence (another recorded by Ramanujan) is the number of divisors of the corresponding highly composite numbers which spawn the \Delta\varsigma[n] maximum. Thus, the successive maximum values of \Delta\varsigma[n] are attained at n one less than a highly composite number and is equal to the number of divisors of the HCN.

5) From the the above discussion of the specific cases of the maxima and minima it should be apparent that:

\Delta\varsigma[n]=\tau[n] where \tau[n] is the number of divisors including 1 and n itself for n \ge 2.

The remainder triangle
The above triangular array T_q can be converted to a second triangular array by the below transformation:

T_r[n,k]=n-k \cdot T_q[n,k]

This T_r turns out to be the triangular array of remainders. This can be alternatively obtained thus: Consider a positive integer n. Then for all k=1,2,3...n, T_r[n] \equiv n \mod k. Say n=10, we get T_r[10]=0, 0, 1, 2, 0, 4, 3, 2, 1, 0, a sequence of remainders of the division n \div k. If we do this for all n=1, 2, 3, 4 ... we get the remainder triangular array T_r[n,k], which is the same as the array obtained by the above-stated transformation of T_q[n,k]. Shown below are its initial terms.

\begin{tabular}{|*{10}{r|}} \cline{1-1} 0 \\ \cline{1-2} 0 & 0 \\ \cline{1-3} 0 & 1 & 0 \\ \cline{1-4} 0 & 0 & 1 & 0 \\ \cline{1-5} 0 & 1 & 2 & 1 & 0 \\ \cline{1-6} 0 & 0 & 0 & 2 & 1 & 0 \\ \cline{1-7} 0 & 1 & 1 & 3 & 2 & 1 & 0 \\ \cline{1-8} 0 & 0 & 2 & 0 & 3 & 2 & 1 & 0 \\ \cline{1-9} 0 & 1 & 0 & 1 & 4 & 3 & 2 & 1 & 0 \\ \cline{1-10} 0 & 0 & 1 & 2 & 0 & 4 & 3 & 2 & 1 & 0 \\ \cline{1-10} \end{tabular}

We observe that each column in T_r can be described thus: 1st, all 0s; 2nd a 2-term cycle sequence of 0,1; 3rd a 3-term cycle of sequence 0,1,2. In general terms the kth column is a k term cycle of form 0,1,2...k-1

If we linearize T_r we get the remainders sequence f_r, which goes 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 2, 1, 0, 0, 0, 0, 2, 1… As the linearization of a triangular array f_r also grows as \sum_{j=1}^n j, where n is the row number of T_r. The sequence is plotted in Figure 6 with the x-coordinate of the first term as 0 and y=coordinate as f_r[1].

Quo_Rem_Fig6Figure 6

It shows cycles of length n=1,2,3... Each pair of cycles shows the same maximum value. Examination of the sequence shows that successively greater maxima are all bounded by the parabola:

y=\dfrac{\sqrt{1+2x}-1}{2}

Just as we did with T_q, we can similarly define the summatory sequence \rho[n] (we are using this notation after we discovered post facto that \rho has been used for related remainder sequences in the mathematical literature, where each term is the sum of the numbers in a row of T_r. This sequence goes thus: 0, 0, 1, 1, 4, 3, 8, 8, 12, 13, 22, 17, 28, 31, 36, 36, 51, 47, 64, 61… It is plotted in Figure 7.

Quo_Rem_Fig7Figure 7

We determined that the sequence can be described by a continuous function, a parabola of the form y=a x^2 (shown as red line in Figure 7), where we empirically determined a \approx 0.177.

We next sought to obtain the exact value of the constant of the parabola a from first principles. For this consider the plot a single cycle of length n of sequence f_r (Figure 8). We observe that as n \to \infty it is a series of right triangles.

Quo_Rem_Fig8Figure 8

The largest of these triangles is an isosceles triangle with h=n/2, b=n/2. The next triangle has h=n/3, b=n/6, the next has h=n/4, b=n/12. Thus, the general expression for the heights and bases of these triangles is h=n\cdot\tfrac{1}{k+1}, b=n \cdot \tfrac{1}{k(k+1)} where k=1,2,3... and the area of the triangles would be A=n^2 \cdot \tfrac{1}{2k(k+1)^2}. Thus at limit the area under the triangles in a single cycle, which will be the value of the nth term of \rho[n] for large n, will be given by the sum (assuming n \to \infty):

y=n^2\displaystyle \sum_{k=1}^\infty \dfrac{1}{2k(k+1)^2}

We realized, much to our pleasure on discovering it, that this sum is convergent and remarkably can be expressed in terms of the Riemann \zeta function as:

\displaystyle \sum_{k=1}^\infty \dfrac{1}{2k(k+1)^2}= 1-\dfrac{\zeta(2)}{2}=1-\dfrac{\pi^2}{12} \approx 0.177532966

Thus we can express the parabola fitting the sequence \rho[n] precisely as:

y=\left(1-\dfrac{\pi^2}{12}\right)x^2

Thus, again we stumble upon one of those deep links we seen in mathematics, in this case between remainders of division and the number \pi. Now, to study the exact behavior of \rho[n] we define the difference sequence \Delta \rho[n]:

\Delta \rho[n] =\rho[n+1]-\rho[n]

This difference sequence is plotted in Figure 9.

Quo_Rem_Fig9Figure 9. The points corresponding to perfect numbers and powers of 2 are shown in red and blue respectively.

The \Delta \rho[n] sequence shows the following notable features:
1) \Delta \rho[n] takes positive values more often than negative values (3.03:1) in the first 30000 terms. This corresponds to the ratio of numbers with the sum of their divisors smaller than themselves being less than them by at least 2 (known as deficient numbers) to those whose sum of divisors smaller than them is equal or greater than them. This will become clear from the discussion that follows further down.

2) Successive maxima, i.e. the record value of the sequence up to certain n occur only at even values of n > 1. Closer examination revealed that the maxima are associated with n being a prime in the parent sequence \rho[n]; then \Delta \rho[n-1] will be a maximum. If we take a number 6k then the numbers 6k+2, 6k+4 will be even. 6k+3 will be divisible by 3. Thus, these will not be primes. That leaves 6k+1 and 6k+5; the latter is the same as 6k-1 for another k. Thus, 6k \pm 1 will not be divisible by 2 and 3 and could be prime \ge 5. Thus, all primes p \ge 5 can be expressed as 6k \pm 1. Hence, in the sequence \Delta \rho[n], p=6k+1 will correspond n=6k and p=6k-1 to n=6k-2. Thus, at n \ge 6, the successive \Delta \rho[n] maxima occur at n=6k or n=6k-2 corresponding to every n that related to a prime in the \rho[n] sequence. That \Delta \rho[n] successive maxima will occur at primes can be explained easily. A prime will not be divisible by any number other than 1 and itself so all other remainders will be non-zero. The number before it will have at least 2 or at least 2, 3 and 6 as divisors that will yield remainder 0. Thus, a prime will result in remainders adding to a larger number relative to the remainder sum of its prior number, thereby causing a maximum to attained. Thus, there will as many successive maxima in \Delta \rho[n] as primes.

3) \Delta \rho[n]=0 only when n=2^k-1, which corresponds to n=2^k in \rho[n].

4) Negative values of \Delta \rho[n] show a more complex behavior. They are seen where the n in \rho[n] is a number which might be perfect numbers, abundant numbers and highly abundant numbers. We discuss these in detail below.

5) The successive minima, i.e. record negative values assumed by \Delta \rho[n] for a given n are fewer than the successive maxima. While we see a succession of 3245 maxima, corresponding the same number of primes in the first 30000 terms of \Delta \rho[n], we only see a succession of 60 minima. We did some experimentation to discover where these minima occur. Let us define an arithmetic function as below for all n \ge 2:

s[n]=\left(\displaystyle \sum d_n[i]\right)-2n. Where d_n[i] is a divisor of n from d[i]=1...n

Whenever s[n] is greater than s[k] of all k integers lesser than it, then n is considered part of the sequence. It goes: 2, 6, 12, 24, 36, 48, 60, 72, 84, 96… and may be called “remainder anti-primes”. When n belongs to this sequence in \rho[n] it spawns a minimum at \Delta \rho[n-1]. Thus, for n\ge 5 the successive minima occur only at a n of the form 6k-1. Remainder anti-primes are a subset of a class of numbers, highly abundant numbers, defined by the mathematician S. Sivasankaranarayana Pillai. These are numbers whose divisors smaller than themselves sum up to a value, which is bigger than the sum of the divisors for each of the numbers smaller than that number. More generally, whenever n of \rho[n] is a highly abundant number it results in strongly negative values in \Delta \rho[n-1].

6) Definition of s[n] also helps us understand the value assumed by \Delta \rho[n]:

\Delta \rho[n-1]=-(s[n]+1)

Thus, for a prime p since the divisors are only 1, p, we have \Delta \rho[p-1]=-(p+1-2p+1)=p-2. Thus successive maxima in \Delta \rho[n] occur at n=p-1 and attain the value p-2. Thus, after 1 they are either of the form 6k-1 or 6k-3 and will always be odd. Further, this implies that the successive maxima are bounded by the line y=x (Figure 9). The successive minima usually take the form -6k \pm 1, -6k \pm 2, -6k \pm 3. The middle of these, the only even values of minima, are very rare: there being on 3 in the first 30000 terms, namely \Delta \rho[35, 71, 7199]=  -20, -52, -10990. The successive minima increase in magnitude with increasing n but can attain much greater magnitudes than the maxima in their vicinity. Their increase with n is not linear unlike the maxima as the s[n] for this specialized subset of highly abundant numbers grows rapidly. We empirically found a curve of the form y=-\tfrac{x\log(x)}{5.017} to approximately fit them (Figure 9).

7) When \Delta\rho[n]=-1 it corresponds to n+1, i.e. n in \rho[n] of 6, 28, 496, 8128 in our range of 1:30000. These numbers are known after the Pythagorean sage Nicomachus as perfect numbers because their divisors other than themselves add up exactly to them (one can see why this is so from the above, \Delta \rho[n-1]=-(s[n]+1)):
6=1+2+3
28=1+2+4+7+14
496=1+2+4+8+16+31+62+124+248
8128=1+2+4+8+16+32+64+127+254+508+1016+2032+4064
One notices that they have a curious form with respect to the powers of 2:
6=2^0+2^1+2^2-2^0
28=2^0+2^1+2^2+2^3-2^0+2^4+2^1
496=2^0+2^1+2^2+2^3+2^4+2^5-2^0+2^6-2^1+2^7-2^2+2^8-2^3
8128=2^0+2^1+2^2+2^3+2^4+2^5+2^6+2^7-2^0+2^8-2^1+2^9-2^2+2^{10}-2^3+2^{11}-2^4+2^{12}-2^5

More generally, if p is a prime and 2p-1 is also a prime (such primes are called Mersenne primes) then 2^{p-1}(2^p - 1) is a perfect number. The search for such perfect numbers goes on this date computationally and checking online while writing this article shows that to date 50 such numbers have been found. All known perfect numbers are of a form ending in 6 or 28. Yet it has not be formally proven that no odd perfect numbers exist or if there are an infinite number of perfect numbers!

8) Abundant numbers are those numbers whose divisors smaller than themselves add up to a number greater than themselves. e.g. d(12)=1,2,3,4,6; 12<16. When n is an abundant number in \rho[n] it results in a negative value of \Delta\rho[n-1]. The odd abundant numbers like 945, 1575, 2205 in \rho[n] result in the only even indices ( n-1) at which the sequence \Delta\rho[n] is negative.

9) \Delta \rho[n]=-2 is unknown to us. This would imply that the sum of the divisors of a number which are smaller than it can never be 1 more than the number. Similarly \Delta \rho[n]=2, appears to be unknown, i.e. corresponding to deficient numbers with a deficiency of 3. We do not know if these have been proven or disproven. \Delta \rho[n]=1 are also rare. We get only 3 such numbers from 1:30000 which correspond the below n of \rho[n] and observe that:
3=3\times 1; \; 1=3-2
10=1\times 2 \times 5; \; 1+2+5=10-2
136=1 \times 2 \times 4 \times 8 \times 17 \times 34 \times 68; \; 1 + 2 + 4 + 8 + 17 + 34 +68 =136-2
These are numbers whose sum of divisors smaller than them fall short of them by 2. Similarly, we have only 5 numbers resulting in \Delta\rho[n]=-3: 20, 104 464, 650, 1952. These are numbers whose sum of divisors smaller than them exceed them by 2.

Epilog
The \Delta\varsigma[n] and \Delta \rho[n] sequences (Figures 4 and 9) are striking in being simple means of illustrating the fundamental asymmetry in the number world between primes and their anti-numbers. \Delta\varsigma[n] reveals the highly composite numbers, and more weakly the largely composite numbers of Ramanujan as the antipodes of primes. \Delta \rho[n] suggests that the remainder anti-primes, a subset of the highly abundant numbers of Pillai, are the anti-numbers of primes. From the vantage point of these sequences the primes appear to define a more regular pattern in terms of minima and maxima respectively while these anti-numbers define more mysterious patterns.

There are some questions for which we do not have ready answers are (though they might have been answered/studied by mathematicians):
1) Can you give an exact form for the constant correction term used to recapitulating \varsigma(x)?
2) Can you derive a function that bounds the maxima of \Delta\varsigma[n]?
3) Can you derive the exact form of the bounding function of the minima of \Delta\rho[n]?

We carried out all this quite independently of the mathematical literature and were pleased to see the organic emergence of the two classes of anti-prime numbers including those previously discovered by Ramanujan. We showed an earlier variant of this material to a person with extraordinary mathematical talent. He brought to our attention a formal proof for the relationship between perfect numbers and the remainder sequence, which was given to him by a poorly known genius Suryanarayana from Vishakhapatnam who studied such issues extensively in the last century. However, such a proof might have been first published by the mathematician Lucas in the late 1800s. Searching the internet, we came across a simple presentation of that proof in an excellent paper by Spivey in the Mathematics Magazine in 2005. Hence, we are not providing that here. Otherwise our account here provides a summary of the main interesting results concerning these sequences we found as part of our investigation.

Advertisements
This entry was posted in Scientific ramblings and tagged , , , , , , , , . Bookmark the permalink.