0
$\begingroup$

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)$?

  • 0
    This is from $A$mortized $A$nalysis. $A$mortized $A$nalysis considers the cost for each step as the average of overall cost.2012-10-13

1 Answers 1

0

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

  • 0
    @GerryMyerson: you are right. Big change.2012-10-13