Search This Blog

5.11.10

A Recurrence Relation for the Abundancy Index

C. A Recurrence Relation for the Abundancy Index

Fix a prime p, and let k be a positive integer.

Write Sigma(p^k) = 1 + p + p^2 + ... + p^(k - 1) + p^k as:

Sigma(p^k) = (1 + p + p^2 + ... + p^(k - 1)) + p^k

Thus: Sigma(p^k) = Sigma(p^(k - 1)) + p^k

Consequently, F(p, k) = Sigma(p^k) satisfies the recurrence relation:

(!) F(k) = F(k - 1) + g(k)      (note: F(k) = F(p, k) -- we omit p because it is fixed)

where g(k) is the exponential function g(k) = p^k (where p is held constant).

The recurrence relation for F gives rise to an equivalent recurrence relation for f:

We have: Sigma(p^k) = Sigma(p^(k - 1)) + p^k

Divide through by (p^k): I(p^k) = (1/p)I(p^(k - 1)) + 1

Multiply through by (p): p*I(p^k) = I(p^(k - 1)) + p

Thus, the resulting recurrence relation for f(p, k) = I(p^k) is given by:

(@) p*f(k) = f(k - 1) + p (note: f(k) = f(p, k) -- we omit p because
                                       it is fixed)


Since I(1) = 1, for consistency in our recurrence equations, we can set:

f(0) = 1

With this initial seed, our recursion goes thus:

p*f(1) = f(0) + p = 1 + p
f(1) = (1 + p)/p = (1/p) + 1

p*f(2) = f(1) + p = (1 + p)/p + p = (1 + p + p^2)/p
f(2) = (1 + p + p^2)/p^2 = (1/p)^2 + (1/p) + 1

p*f(3) = f(2) + p = (1 + p + p^2)/p^2 + p
          = (1 + p + p^2 + p^3)/p^2
f(3) = (1 + p + p^2 + p^3)/p^3
      = (1/p)^3 + (1/p)^2 + (1/p) + 1
...
...
...

Thus, roughly we have:

f(p, k) = Big-OH((1/p)^k)

when p is fixed.

That is, the abundancy index is a (rational) NON-polynomial function of k for constant p.  [Please see comment #2.]

Indeed, we have the closed form:

I(p^k) = (p^(k + 1) - 1)/((p^k)(p - 1))

where of course you will be able to recognize the familiar formula:

Sigma(p^k) = (p^(k + 1) - 1)/(p - 1)

which is derived via finite geometric series.

3 comments:

Arnie Dris said...

This post was last edited on November 14, 2010.

Arnie Dris said...

That is, the abundancy index is a (rational) polynomial function of k for constant p.

--> This should have been:

--> That is, the abundancy index is a (rational) NON-polynomial function of k for constant p.

Arnie Dris said...

A related question is: Is the set of perfect numbers a "recursive" set?

If you look at the multiplicative forms of even and odd perfect numbers:

Even Perfect Number = (2^Q - 1)(2^[Q - 1])

Odd Perfect Number = (P^K)(M^2)

For the even case, we have the multiplicative form:

[(Mersenne prime)^1]*[SQUAREof(2^[(Q - 1)/2])]

where 2^Q - 1 == 3 (mod 4) is the Mersenne prime.

For the odd case, we have the multiplicative form:

[(Euler prime)^K]*[SQUAREof(M)]

where P == 1 (mod 4) is the Euler prime.

Ronald Sorli conjectured in 2003 that K = 1. (Sorli was trying to prove that omega(N) >= 9 for an odd perfect number N, where omega(x) is the number of distinct prime factors of x.)