A perfect number is a positive integer equal to the sum of its proper divisors, all divisors less than itself. The first three examples are as follows.

6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248

Even and odd perfect numbers

Every known perfect number is even. No one has proved that odd perfect numbers don’t exist, but people keep proving properties than an odd perfect number must have, and maybe some day this list of properties will contain a contradiction, proving that such numbers don’t exist. For example, an odd perfect number, if it exists, must have over 1,500 digits.

Mersenne primes

A Mersenne prime is a prime number of the form 2^p− 1. Euclid proved that if M is a Mersenne prime, then M(M + 1)/2 is an even perfect number [1]. Leonhard Euler proved the converse of Euclid’s theorem two millennia later: all even perfect numbers have the form M(M + 1)/2 where M is a Mersenne prime.

There are currently 52 known Mersenne primes. The number of Mersenne primes is conjectured to be infinite, and the Mersenne primes discovered so far have roughly fit the projected distribution of such primes, so there is reason to suspect that there are infinitely many perfect numbers. There are at least 52.

Triangular numbers

By Euler’s theorem, all even perfect numbers have the form M(M + 1)/2 , and so all even perfect numbers are triangular numbers.

P = 1 + 2 + 3 + … + M

Binary numbers

Even perfect numbers have the form 2^p−1(2^p − 1), and so this means all perfect numbers when written in binary consist of p ones followed by p − 1 zeros.

For example,

496 = 31 × 32 / 2 = 2⁴(2⁵ − 1)

and 496 = 111110000_two, five ones followed by four zeros.

Related posts

• Tetrahedral numbers
• Pentagonal numbers
• Five things about Mersenne primes

[1] Euclid didn’t use the term “Mersenne prime” because he lived 17 centuries before Marin Mersenne, but he did prove that if 2^p − 1 is prime, then 2^p−1(2^p − 1) is perfect.

I ran across the following theorem in Ross Honsberger’s book Mathematical Morsels:

Every odd square ends in 1 in base 8, and if you cut off the 1 you have a triangular number.

A number is an odd square if and only if it is the square of an odd number, so odd squares have the form (2n + 1)².

Both parts of the theorem above follow from the calculation

( (2n + 1)² − 1 ) / 8 = n(n + 1) / 2.

In fact, we can strengthen the theorem. Not only does writing the nth odd square in base 8 and chopping off the final digit give some triangular number, it gives the nth triangular number.

Let d(n) be the number of divisors of an integer n. For example, d(12) = 6 because 12 is divisible by 1, 2, 3, 4, 6, and 12.

The function d varies erratically as the following plot shows.

But if you take the running average of d

f(n) = (d(1) + d(2) + d(3) + … + d(n)) / n

then this function is remarkably smoother.

Not only that, the function f(n) is asymptotically equal to log(n).

Computing

Incidentally, directly computing f(n) for n = 1, 2, 3, …, N would be inefficient because most of the work in computing f(m) would be duplicated in computing f(m + 1). The inefficiency isn’t noticeable for small N but matters more as N increases. It would be more efficient to iteratively compute f(n) by

f(n + 1) = (n f(n) + d(n + 1)) / (n + 1).

Asymptotics and citations

Several people have asked for a reference for the results above. I didn’t know of one when I wrote the post, but thanks to reader input I now know that the result is due to Dirichlet. He proved that

f(n) = log(n) + 2γ − 1 + o(1).

Here γ is the Euler-Mascheroni constant.

You can find Dirichlet’s 1849 paper (in German) here. You can also find the result in Tom Apostol’s book Introduction to Analytic Number Theory.

Related posts

• The smallest number with a given number of divisors
• Accurately computing running variance

Lucas numbers [1] are sometimes called the companions to the Fibonacci numbers. This sequence of numbers satisfies the same recurrence relation as the Fibonacci numbers,

L_n+2 = L_n + L_n+1

but with different initial conditions: L₀ = 2 and L₁ = 1.

Lucas numbers are analogous to Fibonacci numbers in many ways, but are also in some ways complementary. Many sources refer to Lucas numbers as the complement to the Fibonacci numbers, I have not seen a source that explains why they are not simply a complement to the Fibonacci numbers. That is, I have not seen anyone explain why Édouard Lucas chose the particular initial conditions that he did.

Any initial conditions linearly independent from the Fibonacci conditions would produce a sequence complementary to the Fibonacci numbers. Just as a second order linear differential equation has two linearly independent solutions, so a second order linear difference equation has two linearly independent solutions.

Fibonacci and Lucas numbers are analogous to sines and cosines because the former form a basis for solutions to a difference equation and the latter form a basis for solutions to a differential equation. The analogy goes deeper than that [2], but that’s a topic for another post.

As with Fibonacci numbers, the ratio of consecutive Lucas numbers converges to the golden ratio. An interesting property of the Lucas numbers, one with no Fibonacci analogy, is that if n is prime, then

L_n ≡ 1 mod n.

For example, the 7th Lucas number is 29, which is congruent to 1 mod 7. Maybe this property had something to do with how Lucas chose his starting values, or maybe he chose the starting values and discovered this later. If you know the history hear, please let me know.

The converse of the theorem above is false. That is, the condition

L_n ≡ 1 mod n

does not imply that n is prime. Composite numbers satisfying this condition are called Lucas pseudoprimes. The smallest Lucas pseudoprime is 705. The 705th Lucas number

2169133972532938006110694904080729167368737086736963884235248637362562310877666927155150078519441454973795318130267004238028943442676926535761270636

leaves a remainder of 1 when divided by 705.

If φ is the golden ratio, then L_n is the nearest integer to φⁿ for n ≥ 2. Perhaps this motivated Lucas’ definition.

Related posts

• Miles to kilometers
• Lucas-Lehmer test
• Various kinds of pseudoprimes

[1] The “s” in Lucas is silence because Monsieur Lucas was French.

[2] Barry Lewis, Trigonometry and Fibonacci Numbers, Math. Gazette, 91 (July 2007) pp. 216—226

As mentioned in the previous post, the ratio of consecutive Fibonacci numbers converges to the golden ratio. Is there a sequence whose ratios converge to the silver ratio the way ratios of Fibonacci numbers converge to the golden ratio?

(If you’re not familiar with the silver ratio, you can read more about it here.)

The Pell numbers P_n start out just like the Fibonacci numbers:

P₀ = 0
P₁ = 1.

But the recurrence relationship is slightly different:

P_n+2 = 2P_n+1 + P_n.

So the Pell numbers are 0, 1, 2, 5, 12, 29, ….

The ratios of consecutive Pell numbers converge to the silver ratio.

Metallic ratios

There are more analogs of the golden ratio, such as the bronze ratio and more that do not have names. In general the kth metallic ratio is the larger root of

x² − kx − 1 = 0.

The cases n = 1, 2, and 3 correspond to the gold, silver, and bronze ratios respectively.

The quadratic equation above is the characteristic equation of the recurrence relation

P_n+2 = kP_n+1 + P_n.

which suggests how we construct a sequence of integers such that consecutive ratios converge to the nth metallic constant.

So if we use k = 3 in the recurrence relation, we should get a sequence whose ratios converge to the bronze ratio. The results are

0, 1, 3, 10, 33, 109, 360, 1189, 3927, 12970, …

The following code will print the ratios.

    def bronze(n):
        if n == 0: return 0
        if n == 1: return 1
        return 3*bronze(n-1) + bronze(n-2)

    for n in range(2, 12):
        print( bronze(n)/bronze(n-1) )

Here’s the output.

    3.0
    3.3333333333333335
    3.3
    3.303030303030303
    3.302752293577982
    3.3027777777777776
    3.302775441547519
    3.3027756557168324
    3.302775636083269
    3.3027756378831383

The results are converging to the bronze ratio

(3 + √13)/2 = 3.302775637731995.

Plastic ratio

The plastic ratio is the real root of x³ − x − 1 = 0. Following the approach above, we can construct a sequence of integers whose consecutive ratios converge to the plastic ratio with the recurrence relation

S_n+3 = S_n+1 + S_n

Let’s try this out with a little code.

    def plastic(n):
        if n < 3: return n
        return plastic(n-2) + plastic(n-3)

    for n in range(10, 20):
        print( plastic(n)/plastic(n-1) )

This prints

    1.3
    1.3076923076923077
    1.3529411764705883
    1.3043478260869565
    1.3333333333333333
    1.325
    1.320754716981132
    1.3285714285714285
    1.3225806451612903

which shows the ratios are approaching the plastic constant 1.324717957244746.

Related posts

• Gold, Silver, and Bronze Ratios
• Imaginary gold, silver, and bronze
• Plastic powers

The number of kilometers in a mile is k = 1.609344 which is close to the golden ratio φ = 1.6180334.

The ratio of consecutive Fibonacci numbers converges to φ, and so you can approximately convert miles to kilometers by multiplying by a Fibonacci number and dividing by the previous Fibonacci number. For example, you could multiply by 8 and divide by 5, or you could multiply by 13 and divide by 8.

As you start going down the Fibonacci sequence, consecutive ratios get closer to k and closer to φ. But since the ratios converge to φ, at some point the ratios get closer to φ and further from k. That means there’s an optimal Fibonacci ratio for converting miles to kilometers.

I was curious what this optimal ratio is, and it turns out to be 21/13. There we have

|k − 21/13| = 0.0060406

and so the error in the approximation is 0.375%. The error is about a third smaller than using φ as the conversion factor.

The Lucas numbers satisfy the same recurrence relation as the Fibonacci numbers, but start with L₀ = 2 and L₁ = 1. The ratio of consecutive Lucas numbers also converges to φ, and so you could also use Lucas numbers to convert miles to kilometers.

There is an optimal Lucas ratio for converting miles to kilometers for the same reasons there is an optimal Fibonacci ratio. That ratio turns out to be 29/18, and

|k − 29/18| = 0.001767

which is about 4 times more accurate than the best Fibonacci ratio.