Sunday, February 20, 2022

[epwwmanh] series that grow faster than harmonic

sum(1/n) grows as O(log n)

sum((log n)/n) grows as O((log n)^2)

sum((log n)^c/n) grows as O((log n)^(c+1))

sum(1) grows as O(exp(log n)) = O(n)

next, faster than any constant power of logarithm but slower than linear:

sum(1/(sqrt n)) grows as O(sqrt n)

sum(1/n^(1-delta)) grows as O(n^delta) for constant delta > 0.  more precisely, integral(1/x^(1-delta), x from 1 to n) = (n^delta - 1)/delta.  as delta gets smaller, the constant factor gets larger.

all of these derived by substituting integral for sum.

motivation is reward for a game: n units of work result in unbounded but less than linear reward, e.g. weapon multiplier.

one can play tricks by starting the series not at n=1, by taking steps not of size 1, or multiplying by a constant.

previously, growing slower than harmonic.  this would be very frustrating for a game (future post kybzoejv).

No comments :