2015-08-21

# Problem 072: Counting fractions

Description:

Consider the fraction, `n/d`, where `n` and `d` are positive integers. If `n<d` and `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`?

Solution:
v00000     // Project Euler - Problem 72
XX     |AAAAAAAAAAAAAAAAAAA|
OOOO

# ... #
. . . .
.  .  .
. . . .
# ... #

>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<
>42g11g`#v_32g12g42g1--+12p>21g1-22g`22g9+1g:10g%\10g/3+g42g*11g`!*|>9+1g:10g%\10g/3+g*11g`!*|
>                 ^vg01:g1+9g22p24/g+3/g01\%g01:g1+9g22g24<^g22g24`g1+9g22g05<v22" "<
>%\10g/3+g22g0`22g9+1g22g8+1g-!*!-32g\/32p22g9+1g1+22g9+1p^g
>*!-32g\/32p22g9+1g1+22g9+1p        #@ #. #g #2 #1 #<               ^9
^!-g1+8g22g1+9g22`0g22p24/\g24:g+3/g01\%g01:g1+9g22_^#!`p22:-1g220p1+<
This program is too big to display/execute here, click [download] to get the full program.

Explanation:

First we need the number of proper reduced fractions for a denominator `d`. This is the amount of numbers `d<n` with `gcd(d,n) == 1`. Coincidentally this is again Eulers Phi-Function.

Now we need to find the sum over all phi values from `1` to `1 000 000`.

First we get all the prime numbers from `2` to `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 `x`.
• 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 Solution: 303963552391 Solved at: 2015-08-21

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript