Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

a) define f(k) as the largest power of 2 that divides k. For example, f(25) = 1, f(42) = 2, f(144) = 16. What is ${1 \over k}\sum_1^k f(k)$?

b) define f(k) as the square of largest power of 2 that divides k. For example, f(25) = 1, f(42) = 4, f(144) = 256 What is ${1 \over k}\sum_1^k f(k)$?

c) define f(k) as the number of divisors of k. For example, f(25) = 3 (1,5,25), f(42) = 9 (1,2,3,6,7,12,14,21,42) What is ${1 \over k}\sum_1^k f(k)$?

share|improve this question
    
Better not to reuse $k$ in ${1 \over k}\sum_1^k f(k)$. It is well-defined which are dummy and which are not, but it is harder to read. –  Ross Millikan Oct 13 '12 at 3:22
    
12 doesn't divide 42. –  Gerry Myerson Oct 13 '12 at 3:31
    
Amortized analysis? Really? –  Gerry Myerson Oct 13 '12 at 3:37
    
@GerryMyerson I agree I thought this was from financial problem. –  AD. Oct 13 '12 at 4:55
    
This is from Amortized Analysis. Amortized Analysis considers the cost for each step as the average of overall cost. –  CaptainObvious Oct 13 '12 at 5:44

1 Answer 1

For a, half the numbers are odd, so $f(k)$ is $1$, one quarter have a single factor of $2$ so f(k) is $2$, one eighth have two factors and so on. If we let the upper limit be a power of $2$, ${1 \over {2^m}}\sum_{k=1}^{2^m} f(k)=\frac 1{2^m} (\frac {2^m}2\cdot 1+\frac {2^m}4\cdot 2 + \frac {2^m}8\cdot 4 + \frac {2^m}{16}\cdot 8 \cdots )=\sum _{k=1}^{m} \frac 12=\frac m2.$ This will go to $\infty$ as $m \to \infty .$ A similar argument holds for b. For c you need to think about the prime number theorem

share|improve this answer
    
The average value of the number-of-divisors function is much much much easier than the prime number theorem. –  Gerry Myerson Oct 13 '12 at 3:32
    
For a), you aren't using OP's definition. If $2^r$ exactly divides $k$, then $f(k)$ is $2^r$, not $r$. –  Gerry Myerson Oct 13 '12 at 3:34
    
@GerryMyerson: you are right. Big change. –  Ross Millikan Oct 13 '12 at 3:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.