24 de julio de 2012

Project Euler 21

  1. #!/usr/bin/env python
  2. from math import sqrt
  3. #This is a very slow solution
  4. def factor(n):#proper
  5.     cota=int(sqrt(n))+1
  6.     exp=0
  7.     result={}
  8.     for i in range(3,n+1,2):
  9.         while n%i==0:
  10.             n/=i
  11.             exp+=1
  12.         if exp>0:
  13.             result[i]=exp
  14.             exp=0
  15.     if n in result:
  16.         while n%2==0:
  17.             result[2]+=1
  18.             n/=2
  19.     else:
  20.         if n%2==0:
  21.             n/=2
  22.             result[2]=1
  23.         while n%2==0:
  24.             n/=2
  25.             result[2]+=1
  26.     return result
  27. #based on this goo.gl/v0Rks
  28. #and this goo.gl/ybxze
  29. def sigmaS(p,a):# n={primefactor:exp,...}
  30.     return (p**(a+1)-1)/(p-1)
  31. def s(n):
  32.     r=1
  33.     ht=factor(n)
  34.     for p in ht:
  35.         r*=sigmaS(p,ht[p])
  36.     return r-n
  37. #
  38. #d(n) & n cannot be amicable pairs
  39. #i spent a lot of time because of this
  40. #
  41. #d(n) & n no pueden ser num. "amigos"
  42. #desperdicié mucho tiempo por esa
  43. #condición.
  44. def isamicable(a):
  45.     b=s(a)
  46.     if a==b:
  47.         return False
  48.     if a==s(b):
  49.         return True
  50. print sum(filter(isamicable,range(3,10000)))

    I should've used some kind of memoization to make it faster, but i'm lazy.

    Debí usar algo de memoization para hacerlo mas rápido, pero soy perezoso.


    Update & spoiler:
    This is a big spoiler, it is based on "extra" info given when you solve the problem. The result is "instantaneous"


    Esta solución es spoiler, basado en la información extra dada cuando resuelves un problema en Project Euler. El resultado es "instantáneo"



    1. #!/usr/bin/env python
    2. #based on goo.gl/v0Rks
    3. def sumdiv(n):
    4.     s=1
    5.     p=2
    6.     while p*p<=n and n>1:
    7.         if n%p==0:
    8.             j=p*p
    9.             n/=p
    10.             while n%p==0:
    11.                 j*=p
    12.                 n/=p
    13.             s*=(j-1)
    14.             s/=(p-1)
    15.         if p==2:
    16.             p=3
    17.         else:
    18.             p+=2
    19.     if n>1:
    20.         s*=(n+1)
    21.     return s
    22.  
    23. def sumpropdiv(n):
    24.     return sumdiv(n)-n
    25.  
    26. s=0
    27. for a in range(2,10000):
    28.     b=sumpropdiv(a)
    29.     if b>and sumpropdiv(b)==a:
    30.         s+=a+b
    31. print s