Progetto Euler numero 338

Question

Sono bloccato su Project Euler problem 338. Ecco cosa ho fatto finora ...

Indichiamo un rettangolo con larghezza e altezza x e rispettivamente (x,y). Per formare nuovi rettangoli, puoi considerare di tagliare una specie di scala lungo la diagonale (come mostrato nella descrizione del problema) con i passaggi di d. Ma per formare un nuovo rettangolo deve contenere: d|x e (d-1)|y o (d+1)|y. Il nuovo rettangolo diventa quindi (x/d*(d-1), y/(d-1)*d) o (x/d*(d+1), y/(d+1)*d). Ovviamente la nuova area dei rettangoli è la stessa del vecchio rettangolo.

Questo è stato sufficiente per confermare che G(10)=55 e G(1000)=971745 da loop attraverso tutti d pertinenti e l'aggiunta di tutti i nuovi rettangoli per un set facendo attenzione a contare (x,y) e (y,x) solo una volta.

Il problema principale con questo metodo è che è possibile creare un nuovo rettangolo in due modi diversi. Ad esempio, (9,8) può essere convertito in (6,12) e (12,6) con d=3 e d-1 o d+1 dividendo . Oppure un altro esempio di (4,4) si trasforma in entrambi (2,8) e (8,2) con d=2 e d=1 rispettivamente.

Sono stato quindi fortunato a leggere this blog post. Rimuove la necessità di controllare i duplicati cercando invece uno dei lati.

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) richiederebbe troppo tempo per risolvere indipendentemente dalla velocità F è però. Penso che sia necessario o utilizzare per un qualche tipo di algoritmo di setacciatura dove il ciclo di tutti x contare quante (w, h) soddisfare h < = w < = 10 , x | (w * h) , x! = h e (wx) | w o (xh) | x.

Penso che un algoritmo O (n ^2/3) sia possibile ... ma sono bloccato qui!

---

Edit: Non ho accesso al forum dal momento che sono in grado di risolverlo. Ecco perché sto chiedendo aiuto. Ho completato la maggior parte delle altre domande e voglio affrontare questa domanda ora!

Modifica 2: Penso che considerare le aree in base ai fattori primi sia un vicolo cieco. Questo perché ci sono 10 aree diverse. I rettangoli con aree principali hanno 0 soluzioni, i rettangoli con aree semiprime hanno 1 soluzione se uno dei primi è 2 altrimenti hanno 0 soluzioni. Ma contare da sole tutte le soluzioni semiprime richiederebbe troppo tempo poiché dovremmo contare tutti i numeri primi p tali che 2 * p che non è fattibile.

Edit 3: ho messo a nudo giù il codice:

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 

Non credo che rompere il codice di forza bruta verso il basso funzionerà però. Ricorda che è sufficiente contare le soluzioni (x, w, h) su ciascuno di questi tre sottoproblemi. L'ultimo esempio somma avrebbe i vincoli 0 < x < N, 0 < h < N + 1, x = H, max (h, x/h) < w < N + 1, x |! Wh e XH | h.

Penso che dovremmo partire dal presupposto che un primo p divide x, w, h o anche x-h e quindi vedere cosa possiamo dedurre riguardo alle altre variabili. Se ciò funziona bene, si consideri p ^k per k arbitrari.

Answer 1

Non ho ancora una soluzione, ma qualcosa di interessante per Python. Mi sono reso conto che Python può essere usato come uno strumento utile per la notazione degli algoritmi! Fondamentalmente ho scritto un programma simile al tuo e ho iniziato a trasformare il programma logicamente, lasciando i risultati invariati. Sono venuto con

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)) 

forza Ovviamente bruta o anche un semplice ciclo su 10^12 non è fattibile, ma forse con questo algoritmo si può trovare un'espressione in forma chiusa ad un certo punto. Se non fosse per il carattere impostato di num, sarebbe fattibile. Forse si può trovare il doppio punto in questo modo.

Questo potrebbe essere un vicolo cieco, ma ancora è abbastanza freddo che Python può essere usato per la notazione e lavorare con gli algoritmi :)

Ogni progresso dalla tua parte?