Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

+-%run_procs
run_procs(wait,0,_,Val)->Val;
run_procs(wait,Running,AccFun,Val)->
	NextVal=receive Anything->Anything end,
	run_procs(wait,Running-1,AccFun,AccFun(Val,NextVal));
run_procs(HowMany,ArgFun,AccumulatorFun,InitialAccVal)->
	run_procs(1,HowMany+1,ArgFun,AccumulatorFun,InitialAccVal).
run_procs(Limit,Limit,_,AccFun,Val)->run_procs(wait,Limit-1,AccFun,Val);
run_procs(I,Limit,ArgFun,AccFun,Val)->
	[Mod,Fun,Args]=ArgFun(I),
	spawn(Mod,Fun,Args),
	run_procs(I+1,Limit,ArgFun,AccFun,Val).

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

+-%cartesian_product
cartesian_product([])->[];
cartesian_product([OneList])->lists:map(fun(X)->[X] end,OneList);
cartesian_product([FirstList|RestLists])->
	Others=cartesian_product(RestLists),
	lists:append(lists:map(fun(Item)-> lists:map(fun(Rest)->[Item|Rest] end, Others) end,FirstList)).

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

+-%divisors
divisors(0)->[];
divisors(1)->[1];
divisors(N)->divisors(with_factors,N,factor(N)).
divisors(with_factors,N,Factors)->
	lists:map(fun(A)->product(A) end,cartesian_product(divisors(Factors,[]))).
divisors([],Classes)->Classes;
divisors([P|RP],Classes)->
	{Taken,Dropped}=lists:splitwith(fun(X)->X==P end, RP),
	All=[P|Taken],
	lists:sort(
		divisors(
			Dropped,
				[lists:map(fun(X)->pow(P,X) end,
					lists:seq(0,length(All)))|Classes])).

p21()->
	Ans=run_procs(9998,fun(I)->[euler,p21,[I+1,self()]] end,
			   fun(F,{positive,A,B})->F+A+B;
			      (F,negative)->F end,
			   0),
	io:format("~w~n",[Ans]).

p21(Test,Parent)->
	P=lists:sum(divisors(Test))-Test,
	if
		P > Test ->
			C=lists:sum(divisors(P))-P,
			if
				C==Test->
					Parent ! {positive,C,P};
				true-> Parent ! negative
			end;
		true -> Parent ! negative
	end.

+-#cartesian_product
def cartesian_product(*a)
	return [] if a.length==0
	return a[0].map{|h|[h]} if a.length==1
	a.map!{|b| b.to_a}
	b=cartesian_product(*(a[1..-1]))
	a=a[0]
	res=[]
	if block_given?
		a.each do |aitem|
			res=res+b.select{|i|yield(aitem,*i)}.map{|i|[aitem]+i}
		end
	else
		a.each do |aitem|
			b.each{|bitem| res.push([aitem]+bitem)}
		end
	end
	res
end

+-#PrimeList
class PrimeList
  @@primes=[2,3,5,7,11,13,17,19]

  def initialize
    @next=-1
  end

  def last
    return 0 if @next==-1
    PrimeList.get(@next)
  end

  def getNext
    PrimeList.get(@next+=1)
  end

  def [](i)
    PrimeList.get(i)
  end

  def PrimeList.isPrime?(n)
    if(@@primes[-1] >= n)
      return true if @@primes.index n
      return false
    end
    p=PrimeList.new
    sq=Math.sqrt(n)
    while(p.last<=sq)
      return false if n % (p.getNext)==0
    end
    true
  end

  def PrimeList.get(i)
    PrimeList.gen while @@primes.length<=i
    @@primes[i]
  end

  def PrimeList.getPrimeNear(n)
    PrimeList.gen until n<@@primes[-1]
    @@primes[PrimeList.primeIndexNear(n)]
  end  

  private

  def PrimeList.primeIndexNear(n)
    return 0 if n<@@primes[0]
    return [-1] if n>@@primes[-1]
    PrimeList.getIndexNear(@@primes,n)
  end

  def PrimeList.getIndexNear(list,n)
    return 0 if list.length==1
    if(list.length==2)
      avg=(list[0]+list[1])/2.0
      return 1 if n>avg
      return 0
    end
    splitAfter=list.size/2
    return PrimeList.getIndexNear(list[0..splitAfter],n) if n<list[splitAfter]
    return splitAfter+1+PrimeList.getIndexNear(list[(splitAfter+1)..-1],n) if n>list[splitAfter+1]
    avg=(list[splitAfter]+list[splitAfter+1])/2
    return splitAfter+1 if n>avg
    splitAfter
  end

  def PrimeList.gen
    add=@@primes[-1]
    cands=Set.new(1..(5*add)){|i|2*i+add}
    theBegin=add+2
    theEnd=11*add
    highest=Math.sqrt(theEnd).to_i
    upTo=PrimeList.primeIndexNear(highest)
    upTo-=1 if @@primes[upTo]>highest
    @@primes[1..upTo].each do |mult|
      ((theBegin-theBegin%mult)..(theEnd-theEnd%mult + mult)).step(mult){|i|cands.delete i}
    end
    @@primes=@@primes+cands.to_a.sort
  end
end

+-#factors
def factors(n)
  return [] if n<2
  p=PrimeList.new
  sq=Math.sqrt(n)
  while(p.last<=sq)
    if n % (p.getNext)==0
      return [p.last]+factors(n/p.last)
    end
  end
  return [n]    
end

+-#divisors
def divisors(n)
  fax=factors(n)
  distinct_primes={}
  while fax.length >0
    n=fax.pop
    i=1
    while(fax.length>0 and fax.last==n)
      i+=1
      fax.pop
    end
    distinct_primes[n]=i
  end
  product_of=[]
  distinct_primes.keys.each do |k|
    t=[1]
    i=distinct_primes[k]
    i.times{t.push(t.last*k)}
    product_of.push t
  end
  cartesian_product(*product_of).map{|j|j.inject{|u,v|u*v}}.to_set
end

+-#Enumerable
module Enumerable
  def sum
    self.inject{|u,v|u+v}
  end
  def product
    self.inject{|u,v|u*v}
  end
  def count(ob)
    self.select{|i|i==ob}.length
  end
  def take_while
    return [] unless yield(self.first)
    if(self.class==Range)
      evalPoint=self.first
      evalPoint=evalPoint.succ while yield(evalPoint.succ) and not evalPoint==self.last
      return self.first..evalPoint
    else
      s=self.to_a
      upTo=1
      upTo+=1 while yield(s[upTo]) and upTo<self.length
      return self[0...upTo]
    end
  end
end

def p21amicable?(a)
  c=divisors(a).delete(a).sum
  (not a==c) and a==divisors(c).delete(c).sum
end

def p21
  puts (2...10000).select{|i|p21amicable? i}.sum
end