Counting fractions

Fork me on GitHub

Problem 072: Counting fractions


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?

v00000     // Project Euler - Problem 72

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

>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
This program is too big to display/execute here, click [download] to get the full program.


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