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.
Post a Comment