Suggerimenti per Project Euler Problema # 78

Question

Questo è il problema in questione: Problem #78

Questo mi sta facendo impazzire. Ho lavorato su questo per un paio d'ore e sono stato in grado di ridurre la complessità di trovare il numero di modi per impilare le monete n su O(n/2), ma anche con quei miglioramenti e a partire da un n per il quale p(n) è vicino a un milione, non riesco ancora a raggiungere la risposta in meno di un minuto. Assolutamente no.

Ci sono suggerimenti che potrebbero aiutarmi con questo?

Ricordare che non voglio una soluzione completa e non dovrebbero esserci soluzioni funzionali pubblicate qui, in modo da non rovinare il problema ad altre persone. Questo è il motivo per cui non ho incluso alcun codice.

Answer 1

Wikipedia può aiutarti qui. Suppongo che la soluzione che hai già sia una ricorsione come quella nella sezione "funzione intermedia". Questo può essere usato per trovare la soluzione al problema di Eulero, ma non è veloce.

Un modo molto migliore è utilizzare la ricorsione basata su pentagonal number theorem nella sezione successiva. La dimostrazione di questo teorema non è semplice, quindi non penso che gli autori del problema si aspettino che tu ti presenti il ​​teorema da solo. Piuttosto è uno dei problemi, dove si aspettano ricerche di letteratura.

Answer 2

qui alcuni suggerimenti:

1. divisibilità per un milione non è la stessa cosa come solo essere più grande di un milione. 1 milione = 1.000.000 = 10^6 = 2^6 * 5^6.

2. Quindi la domanda è di trovare il n più basso in modo che i fattori di p (n) contengano sei 2 e sei 5.

Answer 3

Hai già avuto problemi 31 o 76? Formano un insieme piacevole che è una generalizzazione dello stesso problema di base ogni volta. Fare le domande più semplici può darti un'idea di una soluzione per 78.

Answer 4

Questo problema è davvero chiedere di trovare il primo termine nella sequenza di partizioni intere che è divisibile per 1.000.000.

Una partizione di un numero intero, n, è un modo per descrivere in quanti modi la somma di numeri interi positivi, ≤ n, può essere sommata per uguagliare n, indipendentemente dall'ordine. La funzione p (n) è utilizzata per indicare il numero di partizioni per n. Di seguito mostriamo le nostre 5 "monete" come addendi per valutare 7 partizioni, cioè p (5) = 7.

5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1

Usiamo una funzione di generazione per creare la serie finché non troviamo il necessario n. La funzione di generazione richiede al massimo 500 cosiddetti numeri pentagonali generalizzati, dati da n (3n - 1)/2 con 0, ± 1, ± 2, ± 3 ..., i primi dei quali sono 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, ... (Sloane A001318).

Abbiamo la seguente funzione generatrice che usa nostre numero pentagonale come esponenti:

1 - q - q^2 + q^5 + q^7 - q^12 - q^15 + q^22 + q^26 + ...

il mio blog su blog.dreamshire.com ha un programma perl che risolve questo in meno di 10 secondi.