Consider the fraction, n/d, where n and d are positive integers. If nd 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?
%pow %power_set %echo %prime_list %prime_iterator %factor %product %phi % % All we need to do is compute phi(n) for 1 < n <= 1000000 % % Here we use the multiplicative property as a shortcut, by % walking through the prime-factorization tree % p72()-> A=prime_list(), A ! {all_below,1000000,self()}, Primes=receive {primes_below,1000000,X}->X end, Ans=p72(help,1,1,Primes,[],0), io:format("~w~n",[Ans]). p72(N,_,_,_) when N > 1000000->0; p72(N,Phi,Primes,Used)-> [First|Others]=Primes, Phi+p72(N*First,phi(N*First,Used),Primes,Used)+p72(help,N,Phi,Others,Used,0). p72(help,_,_,[],_,Total)->Total; p72(help,N,Phi,Primes,Used,Total)-> [First|Others]=Primes, Next=p72(N*First,Phi*(First-1),Primes,[First|Used]), if Next == 0-> Total; true-> p72(help,N,Phi,Others,Used,Total+Next) end.