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:
This post was last edited on November 14, 2010.
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.
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.)
Post a Comment