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
pow(_,0)->1;
pow(1,_)->1;
pow(A,B)->pow(A,B,1).
pow(_,0,Res)->Res;
pow(Mult,B,Res) when B band 1 == 1 ->
	pow(Mult*Mult,B bsr 1, Res*Mult);
pow(Mult,B,Res)->pow(Mult*Mult,B bsr 1, Res).

+-%power_set
power_set(List)->
	power_set(List,1,[[]],pow(2,length(List))).
power_set(filter,_,0,Res)->Res;
power_set(filter,[H|T],N,Res)->
	case N band 1 of
		1->power_set(filter,T,N bsr 1,[H|Res]);
		0->power_set(filter,T,N bsr 1,Res)
	end;
power_set(_,N,Result,N)->Result;
power_set(List,C,Result,N)->
	power_set(List,C+1,[power_set(filter,List,C,[])|Result],N).

+-%echo
echo(Message,Sender)->Sender ! Message.

+-%prime_list
prime_list()->
	case whereis(primeList) of
		undefined->
			Pid=spawn(euler,prime_list,[initialize]),
			register(primeList, Pid),
			Pid;
		Exists->
			Exists
	end.
prime_list(initialize)->
	put(primes,array:from_list([2,3,5,7,11,13,17,19])),
	put(total,8),
	prime_list(idle);
prime_list(idle)->
	Size=get(total),
	receive
		{get,FromZero,Reply} when FromZero < Size ->
			Reply ! {prime,FromZero,array:get(FromZero,get(primes))};
		{get,FromZero,Reply} ->
			echo({get,FromZero,Reply},self()),
			prime_list(gen);
		{all_below,What,Reply} ->
			case array:get(Size-1,get(primes)) < What of 
				true->
					prime_list(gen),
					echo({all_below,What,Reply},self());
				false->
					Reply ! {primes_below,What,prime_list(below,What,0,[])}
			end;
		{is_prime,What,Reply}->
			Skirt=math:sqrt(What),
			Largest=array:get(Size-1,get(primes)),
			case Largest < What of
				true->
					case Largest < Skirt of 
						true->
							prime_list(gen),
							echo({is_prime,What,Reply},self());
						false->
							Reply ! {is_prime,What,prime_list(check_factors,0,What,Skirt)}
					end;
				false->
					Reply ! {is_prime,What,prime_list(binary_search,What,0,Size-1)}
				end
		end,
		prime_list(idle);
prime_list(gen)->
	Size=get(total),
	Start=array:get(Size-1,get(primes))+2,
	End=Start*10+1,
	Sqrt=math:sqrt(End),
	AsList=array:to_list(get(primes)),
	[2|Odds]=AsList,
	RelevantOdds=lists:takewhile(fun(N)->N =< Sqrt end,Odds),
	Newbs=prime_list(gen,Size,Start,End,RelevantOdds,ordsets:from_list(lists:seq(Start,End,2))),
	put(primes,array:from_list(lists:append(AsList,ordsets:to_list(Newbs)))),
	put(total,get(total)+ordsets:size(Newbs)).
prime_list(check_factors,NextIndex,N,Sqrt)->
	NextPrime=array:get(NextIndex,get(primes)),
	case NextPrime > Sqrt of
		true->true;
		false->
			case N rem NextPrime ==0 of
				true->false;
				false->
					prime_list(check_factors,NextIndex+1,N,Sqrt)
			end
		end;
prime_list(binary_search,What,Low,High) when High-Low < 2 ->
	H=array:get(High,get(primes)),
	L=array:get(Low,get(primes)),
	if
		H == What; L == What ->
			true;
		true->false
	end;
prime_list(binary_search,What,Low,High)->
	Mid=Low+((High-Low) div 2),
	Got=array:get(Mid,get(primes)),
	if
		What > Got->prime_list(binary_search,What,Mid+1,High);
		What < Got->prime_list(binary_search,What,Low,Mid-1);
		true->true
	end;

	
prime_list(below,What,Index,SoFar)->
	Next=array:get(Index,get(primes)),
	if
		Next >= What->
			lists:reverse(SoFar);
		true->
			prime_list(below,What,Index+1,[Next|SoFar])
	end.
prime_list(gen,_,_,_,[],Survivors)->Survivors;
prime_list(gen,Total,Lowest,Highest,[MyPrime|RestPrimes],Survivors)->
	prime_list(gen,Total,Lowest,Highest,RestPrimes,
		ordsets:subtract(Survivors,
			ordsets:from_list(
				lists:seq(Lowest-(Lowest rem MyPrime),Highest,MyPrime)))).

+-%prime_iterator
prime_iterator(Pid)->spawn(euler,prime_iterator,[idle,0,2,Pid,prime_list()]).
prime_iterator(idle,Index,Next,Parent,List)->
	receive
		next->
			Parent ! {prime, Next},
			List ! {get, Index+1,self()},
			prime_iterator(wait,Index+1,nothing,Parent,List)
	end;
prime_iterator(wait,Index,_,Parent,List)->
	receive
		{prime,Index,Next}->
			prime_iterator(idle,Index,Next,Parent,List)
	end.

+-%factor
factor(1)->[];
factor(N)->factor(N,prime_iterator(self()),0,math:sqrt(N)).
factor(1,_,_,_)->[];
factor(N,Iter,LastPrime,Sqrt) when LastPrime >= Sqrt->
	exit(Iter,kill),
	[N];
factor(N,Iter,_,Sqrt)->
	Iter ! next,
	Next=receive
		{prime,X}->X
	end,
	if
		N rem Next == 0 ->
			Small=N div Next,
			exit(Iter,kill),
			[Next|factor(Small,prime_iterator(self()),0,math:sqrt(Small))];
		true->
			factor(N,Iter,Next,Sqrt)
	end.

+-%product
product(List)->
	lists:foldl(fun(X,Prod)->X*Prod end, 1, List).

+-%phi
phi(1)->1;
phi(N)->
	phi(N,factor(N)).
phi(N,F)->
	P=power_set(ordsets:to_list(ordsets:from_list(F))),
	Sum=lists:map(fun([])->0;
			 (L)->
			 	pow(-1,(length(L) band 1)+1)*((N-1) div product(L)) end, P),
	N-1-lists:sum(Sum).

%
% 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.