Problem 072: Counting fractions
Consider the fraction,
d are positive integers.
HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for
d <= 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 21 elements in this set.
How many elements would be contained in the set of reduced proper fractions for
d <= 1,000,000?
# ... #
. . . .
. . .
. . . .
# ... #
>699**:10p3777***:20p*40p230p" ":03p13p"}}@"**11p192*+21p022pv >030p0>::10g%\10g/3+g"X"-#v_v
vp+3/g01\%g01:\"#":-1<g04 p242p231< v%g01:p03+1:g03 :<
> :| ^ <>\10g/3+pv
v $<0 _^#`g03g04<|-g04:+1 < <
>"X"30g:10g%\10g/3+p30g>30g+:40g\` #v_$>30g1+:30p:10g%\10g/3+g" "-|$
> v ^p+3/g01\%g01:\" ":< ^ <
v_^#!:p1+9\" ":-1<g12 p21/2-\*::g11p05g03<
>$091pv v p23*g23-1p24*<
v < <p23*g23p24*g24:g+3/g01\%g01:p1+9g22:g1+9p22+1:g22<^g24:g+3/g01\%g01:g1+9g22<
> ^vg01:g1+9g22p24/g+3/g01\%g01:g1+9g22g24<^g22g24`g1+9g22g05<v22" "<
>*!-32g\/32p22g9+1g1+22g9+1p #@ #. #g #2 #1 #< ^9
First we need the number of proper reduced fractions for a denominator
This is the amount of numbers
gcd(d,n) == 1.
Coincidentally this is again Eulers Phi-Function.
Now we need to find the sum over all phi values from
1 000 000.
First we get all the prime numbers from
limit/2 (with an Sieve of Eratosthenes).
Then we iterate through all possible prime combinations smaller than the limit (practically this is prime factorization).
While we do this we calculate on the side the phi value of these numbers (with the prime factorization this is trivial) and sum these values together.
For all values bigger than
LIMIT/2 where we haven't got a factorization we use
phi(p) = p-1.
Because these must be prime. (see Eulers totient function)
The rest is a bit of clever optimization, so this all does not take too long.
- First we assume every number is prime and calculate the sum of the phi function of all these primes. Then when we find a number (that is not a prime) we subtract the old (wrong) value from the result and add the new (correct) value.
- We abort our loops early when we run into a number
x > limit. Because every other factor will only increase
- The value of phi is always calculated from the last phi value. So we don't need to totally recalculate it in every step.
After looking a little bit around this is not *the fastest solution to this problem. But it's the one I found and I think it's reasonable fast.
|Interpreter steps:||339 636 085|
|Execution time (BefunExec):||50s (6.71 MHz)|
|Program size:||486 x 1047|