Home > Project Euler, python > Problem euler #44

Problem euler #44

Pentagonal numbers are generated by the formula, Pn=n(3n-1)/2.
The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P4 + P7 = 22 + 70 = 92 = P8.
However, their difference, 70 - 22 = 48, is not pentagonal.
Find the pair of pentagonal numbers, Pj and Pk, for which their sum
and difference is pentagonal and D = |Pk - Pj| is minimised; what is
the value of D?

Analisi:

Dal testo del problema, sappiamo che la formula per calcolare un numero
pentagonale è:

Pn=n(3n-1)/2

Da wikipedia ricaviamo la formula per sapere se un numero ‘n’, è
pentagonale:

sqrt(24*n + 1) + 1)/6

Queste 2 cose sono sufficienti per trovare il risultato in un tempo di
circa 2sec.
In sostanza creiamo una lista di numeri pentagonali, e cicliamo su
essa due volte, in modo da poter controllare tutte le somme e tutte le differenze
di due pentagonali. Quando avremo sia somma e differenza, pentagonali, avremo
trovato il risultato, nel nostro caso la minima differenza richiesta.
Senza dover maneggiare con gli assoluti (D = |Pk – Pj|) pongo come test
nel ciclo, che il primo pentagonale sia maggiore del secondo, così la differenza
sarà sempre un numero positivo ed inoltre non ciclerò sui doppioni (70,22 e 22,70).

python:

import time
import math

ts = time.time()

def is_pentagonal(n):
    res = (math.sqrt(24*n + 1) + 1)/6 # is n pentagonal formula
    return res % 1 == 0

def get_pentagonals():
    pents = [n*(3*n - 1)/2 for n in range(2, 2500)]
    for i in pents:
        for j in pents:
            if j > i and is_pentagonal(i+j) and is_pentagonal(j-i):
                return j-i

res = get_pentagonals()
print "problem euler 44: {} \nelapsed time: {}sec".format(res, time.time() - ts)

Categorie:Project Euler, python
  1. Non c'è ancora nessun commento.
  1. No trackbacks yet.

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: