Proyecto Euler Número 338

Question

Estoy atascado en el Proyecto Euler problem 338. Esto es lo que he hecho hasta ahora ...

Vamos a denotar un rectángulo con un ancho y altura x y y respectivamente (x,y). Para formar nuevos rectángulos, puede considerar cortar un tipo de escalera por la diagonal (como se muestra en la descripción del problema) con d pasos. Pero para formar un nuevo rectángulo, debe tener lo siguiente: d|x y (d-1)|y o (d+1)|y. El nuevo rectángulo se convierte en (x/d*(d-1), y/(d-1)*d) o (x/d*(d+1), y/(d+1)*d). Obviamente, el área de los nuevos rectángulos es la misma que la del rectángulo anterior.

Eso fue suficiente para confirmar que G(10)=55G(1000)=971745 y haciendo un bucle a través de todos relevante d y la adición de todos los nuevos rectángulos para un conjunto teniendo cuidado de contar (x,y) y (y,x) sólo una vez.

El problema principal con este método es que es posible crear un nuevo rectángulo de dos maneras diferentes. Por ejemplo, (9,8) puede transformarse en (6,12) y (12,6) con d=3 y d-1 o dividiendo y. O bien, otro ejemplo de (4,4) se transforma en (2,8) y (8,2) con d=2 y d=1, respectivamente.

Tuve la suerte de leer this blog post. Elimina la necesidad de buscar duplicados buscando en su lugar uno de los lados.

def F(w, h): 
    if w&1 and h&1: return 0 
    if w<h: w,h = h,w 

    r = 0 
    x = 1 
    while x**2 <= w*h: 
     if (w*h)%x!=0 or x==h: 
      x += 1 
      continue 

     if w%(w-x)==0 or x%(x-h)==0: 
      r += 1 

     x += 1 

    return r 

def G(N): 
    s = 0 
    for w in range(1, N+1): 
     for h in range(1, w+1): 
      s += F(w,h) 

    return s 

G (10) requeriría demasiado tiempo para resolver independientemente de la rapidez con F es sin embargo. Creo que es necesario, o utilizar algún tipo de algoritmo de tamizado en el que recorrer todos x contar cuántas (w, h) cumplir h < = w < = 10 , X | (w * h) , x! = h y (wx) | w o (xh) | x.

Creo que un algoritmo O (n ^2/3) debe ser posible ... ¡pero estoy atrapado aquí!

---

Editar: No tengo acceso al foro ya que soy incapaz de resolverlo. Es por eso que estoy pidiendo ayuda. He completado la mayoría de las otras preguntas y quiero abordar esta pregunta ahora!

Editar 2: Creo que considerar las áreas por factores primos es un callejón sin salida. Eso es porque hay 10 áreas diferentes. Los rectángulos con áreas principales tienen 0 soluciones, los rectángulos con áreas semiprime tienen 1 solución si uno de los números primos es 2, de lo contrario tienen 0 soluciones. Pero contar todas las soluciones semiprime solo llevaría demasiado tiempo, ya que necesitaríamos contar todos los primos p de forma tal que 2 * p que no es factible.

Datos 3: He simplificada del código:

def G(N): 
    s = 0 
    for x in range(1, N): 
     for h in range(1, N+1): 
      if x==h: continue 
      for w in range(max(h, x**2//h), N+1): 
       if (w*h)%x==0 and x%(w-x)==0 and x%(x-h)==0: 
        s -= 1 

    for x in range(1, N): 
     for h in range(1, N+1): 
      if x==h: continue 
      for w in range(max(h, x**2//h), N+1): 
       if (w*h)%x==0 and w%(w-x)==0: 
        s += 1 

    for x in range(1, N): 
     for h in range(1, N+1): 
      if x==h: continue 
      for w in range(max(h, x**2//h), N+1): 
       if (w*h)%x==0 and h%(x-h)==0: 
        s += 1 

    return s 

No creo que romper el código de fuerza bruta abajo funcionará sin embargo. Recuerde que es suficiente que solo cuente las soluciones (x, w, h) para cada uno de estos tres subproblemas. El último de estos suma tendría las limitaciones 0 < x < N, 0 < h < N + 1, X = H, max (H, X/h) < w < N + 1, x |! Wh y xh | h.

Creo que deberíamos comenzar con la suposición de que algunos primos p dividen x, w, h o incluso x-h y luego vemos lo que podemos deducir sobre las otras variables. Si eso funciona bien, tal vez considere p ^k para k arbitraria.

Answer 1

Todavía no tengo una solución, pero algo interesante para Python. ¡Me di cuenta de que Python se puede usar como una herramienta conveniente para la notación de algoritmos! Básicamente escribí un programa similar al tuyo y empecé a transformar el programa lógicamente, lo que no modificaba los resultados. Se me ocurrió

def order(x,y): 
    if x>=y: 
     return (x,y) 
    else: 
     return (y,x) 

N=1000 
num=set() 
for n in range(1, N+1): 
    for a in range(1,N//n+1): 
     for b in range(1,N//(n+1)+1): 
      if a==b: continue 
      num.add((order(a*n,b*(n+1)), order(b*n,a*(n+1)))) 

print(N, len(num)) 

fuerza Obviamente bruta o incluso un simple bucle de más de 10^12 no es factible, pero tal vez con este algoritmo se puede encontrar una forma cerrada en algún momento. Si no fuera por el carácter establecido de num, sería factible. Tal vez uno puede encontrar puntos duplicados de esta manera.

Esto podría ser un callejón sin salida, pero aún así es muy bueno que se puede usar Python para la notación y trabajar con algoritmos :)

Cualquier progreso de su lado?