Optimizar sumas no abundantes algoritmo

Question

estoy tratando de resolver this Project Euler question:

Un número perfecto es un número para el que la suma de sus divisores propios es exactamente igual al número. Por ejemplo, la suma de los divisores adecuados de de 28 sería 1 + 2 + 4 + 7 + 14 = 28, lo que significa que 28 es un número perfecto.

Un número n se llama deficiente si la suma de sus divisores propios es menor que ny se llama abundante si esta suma excede n.

Como 12 es el número abundante más pequeño, 1 + 2 + 3 + 4 + 6 = 16, la número más pequeño que se puede escribir como la suma de dos números abundantes es de 24. Por análisis matemático, puede ser se muestra que todos los enteros mayor que 28123 se pueden escribir como la suma de dos números abundantes. Sin embargo, este límite superior no puede reducirse más mediante el análisis aunque se sabe que el mayor número que no puede ser expresado como la suma de dos números abundantes es menor que este límite.

Encuentra la suma de todos los enteros positivos que no pueden escribirse como la suma de dos números abundantes.

Mi solución:

#returns a list of the divisors of a given number 
def Divs(Number): 
    Divisors = [] 

    for i in range(2 , int(Number**0.5) + 1): 
     if Number % i == 0: 
      Divisors.append(i) 

    for q in range(len(Divisors)): 
     if Divisors[q] != (Number/Divisors[q]): 
      Divisors.append(Number/Divisors[q]) 

    Divisors.insert(0,1) 
    return Divisors 

#returns a list of abundant numbers up to and including the limit 
def AbList(limit): 
    Abundant = [] 

    for i in range(11,limit + 1): 
     if sum(Divs(i)) > i: 
      Abundant.append(i) 

    return Abundant 

#Finds the sum of all positive integers that cannot be written as the 
#sum of two abundant numbers... 
def AbSum(limit): 
    Abundant = AbList(limit) 
    NoAbSum = 0 
    for i in range(1 , limit): 
     AbSum = 0 
     x = 0 
     for x in Abundant: 
      if i - x in Abundant[:i]: 
       AbSum = 1 
       break 
     if AbSum == 0: 
      NoAbSum += i 
    return NoAbSum 

Esto llevó a mi procesador de 3,4 GHz aproximadamente 15 minutos para resolver y estoy en busca de una mejor manera. No me preocupan las primeras dos funciones porque juntas tardan menos de un segundo en ejecutarse. La tercera función es el kicker aquí. Corre a través del rango de números hasta el límite (en este caso, 20000 y algo), y cada vez, recorre la lista de números abundantes, restando cada uno del número actual, luego verificando esa respuesta contra la lista de abundantes números. Si hay una coincidencia, el bucle se rompe e intenta nuevamente con el siguiente número, todo el camino hasta el límite.

Sé que tiene que haber una mejor manera de hacerlo, pero soy algo nuevo en la programación. ¿Cómo puedo acelerar este algoritmo?

Answer 1

Está probando cada número entre 1 y el límite (digamos 30000) contra cada número abundante, por lo que está realizando aproximadamente 30000 * 7428 iteraciones; y está comprobando si el resultado está en una lista, que es una operación muy lenta: ¡comprueba cada elemento de la lista hasta que encuentra una coincidencia!

En su lugar, debe generar cada número que es una suma de dos números abundantes.A lo sumo, eso requeriría 7428 * 7428 iteraciones, menos si se ejecuta correctamente (sugerencia: evite verificar tanto a + b como b + a asegurando que b sea siempre> = a; y como sugirió otra persona, asegúrese de detener cuando las sumas son demasiado grandes). Marque esos números de una lista de números debajo de limit y sume los números restantes.

En otras palabras:

[... 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 ...] 

convierte

[... 31, 0, 33, 34, 35, 0, 37, 0, 39, 0, 41, 0, 43 ...] 

---

Editar: Después de jugar con las implementaciones de unos minutos, puedo decir con confianza que if i - x in Abundant[:i]: es el problema. La primera solución pitón publicado al foro p23 del Proyecto Euler es esencialmente una aplicación inteligente de su algoritmo, siendo la única diferencia importante que utiliza un conjunto de abundantes números en lugar de una lista. Resuelve el problema en un procesador Atom en 15 segundos; cuando lo cambié para usar una lista, después de quince minutos, todavía no había resuelto el problema.

Moraleja de la historia: x in list es lento.

Aún así, la generación de las sumas directamente es más rápido que restar y de cheques. :)

Answer 2

Una cosa que ayudaría es a salir de su circuito interno una vez que los números abundantes sean mayores que el que está probando.

Asimismo, no entiendo poco de su código:

for q in range(len(Divisors)): 
    if Divisors[q] != (Number/Divisors[q]): 
     Divisors.append(Number/Divisors[q]) 

Una vez que haya verificado que el módulo es 0, es un divisor. No sé por qué estás haciendo una verificación de identidad esencialmente.

Answer 3

Su código parece que podría beneficiarse del mapa, filtro o lista de comprensión a favor de aquellos para bucles.

Answer 4

for x in Abundant: 
     if i - x in Abundant[:i]: 
      AbSum = 1 
      break 

Tenga en cuenta que la expresión in aquí toma tiempo O (i), y por lo tanto el bucle es O (N $ ² $). Puede mejorar esto en O (n) si usa un set en lugar de un list.

Answer 5

Se puede utilizar un simple truco matemático: La suma de todos los números que no se puede escribir como una suma de dos números abundante es la suma de todos los números menos los números que puede escribirse como suma de dos números abundantes:

solution = sum(range(limit)) - sum(all_two_sums(abundant_numbers)) 

(sum(range(limit)) también se puede simplificar con las matemáticas, pero es posible que no se encuentre a menos que estés Gauss ;-))

ya tiene una lista de números abundantes, por lo que es relativamente fácil para crear el conjunto de números que puede escribirse como la suma de dos números abundantes y donde la suma es menor que el límite. Solo asegúrate de no tener números duplicados, Python set hace eso. inicio

Answer 6

Vamos buscando un poco, y averiguar el número más grande no puede expresar como la suma de dos números abundantes en realidad es 20161. Entonces, podemos resolver el problema con un simple análisis de miembro determinada. Además, funciona bastante rápido. :-)

#!/usr/bin/env python 
# -*- coding: utf-8 -*- 
from math import sqrt 

def d(n): 
    sum = 1 
    t = sqrt(n) 
    # only proper divisors; start from 2. 
    for i in range(2, int(t)+1): 
     if n % i == 0: 
      sum += i + n/i 
    # don't count the square root twice! 
    if t == int(t): 
     sum -= t 
    return sum 

limit = 20162 
sum = 0 
# it's a set, after all. sets are faster than lists for our needs. 
abn = set() 
for n in range(1, limit): 
    if d(n) > n: 
     abn.add(n) 
    # if the difference of the number we're examining and every number in the set 
    # is in the set, then the number is the sum of two abundant numbers. 
    # otherwise, we must add it to our sum in question. 
    if not any((n-a in abn) for a in abn): 
     sum += n 

Se ejecuta en 0.6463340939061518 segundos en promedio en un sistema i5, con base en timeit.