what are they trying to say in this paragraph , I have read it 10 times, but not getting what they want to teach me here:
link is this. : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primeNumbers
and the para which is just before the euler totient theorem. am copying here also.
Or consider a scenario where you are asked to calculate a function Answer(x, y), with x and y both integers in the range [1, n], 1 ≤ n ≤ 50000. If you know Answer(x, y), then you can easily derive Answer(kx, k*y) for any integer k. In this situation you want to know how many values of Answer(x, y) you need to precalculate. The function Answer is not symmetric.
For example, if n = 4, you need to precalculate 11 values: Answer(1, 1), Answer(1, 2), Answer(2, 1), Answer(1, 3), Answer(2, 3), Answer(3, 2), Answer(3, 1), Answer(1, 4), Answer(3, 4), Answer(4, 3) and Answer(4, 1).
The solution here is to let res(i) be the minimum number of Answer(x, y) to precalculate, where x, y Î{1, …, i}. It is obvious that res(1) = 1, because if n = 1, it is enough to know Answer(1, 1). Let we know res(i). So for n = i + 1 we need to find Answer(1, i + 1), Answer(2, i + 1), … , Answer(i + 1, i + 1), Answer(i + 1, 1), Answer(i + 1, 2), … , Answer(i + 1, i).
The values Answer(j, i + 1) and Answer(i + 1, j), j Î{1, …, i + 1}, can be found from known values if GCD(j, i + 1) > 1, i.e. if the numbers j and i + 1 are not common primes. So we must know all the values Answer(j, i + 1) and Answer(i + 1, j) for which j and i + 1 are coprime. The number of such values equals to 2 * φ (i + 1), where φ is an Euler’s totient function. So we have a recursion to solve a problem:
res(1) = 1,
res(i + 1) = res(i) + 2 * j (i + 1), i > 1*
thanks if you can help me.