Home > Project Euler, python > Problem euler #43

Problem euler #43

The number, 1406357289, is a 0 to 9 pandigital number because it is made up
of each of the digits 0 to 9 in some order, but it also has a rather
interesting sub-string divisibility property.
Let d1 be the 1st digit, d2 be the 2nd digit, and so on.
In this way, we note the following:

    d2d3d4=406 is divisible by 2
    d3d4d5=063 is divisible by 3
    d4d5d6=635 is divisible by 5
    d5d6d7=357 is divisible by 7
    d6d7d8=572 is divisible by 11
    d7d8d9=728 is divisible by 13
    d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

Il mio approccio iniziale è stato quello di creare un generatore di pandigitali
(9×9! = 3’265’920) controllando per ogni permutazione, la divisibilità di ogni
terzina, per i numeri primi dati.
Questo porta il tempo di esecuzione a circa 20sec controllando solo l’ultima terzina
(% 17) e 19 sec controllandole tutte:

import time
import itertools as it

ts = time.time()


def pan_generator():
    for i in it.permutations(range(10)):
        r = ''
        for n in i:
            r += (str(n))
        if r[0] != '0' and int(r[-3:]) % 17 == 0:
            yield r

def is_magic(n):
    primes=[1,2,3,5,7,11,13]
    i = 1
    while i < len(primes):
        if int(n[i:3+i]) % primes[i] == 0:
            i += 1
        else:
            return False
    return True


res = sum([int(n) for n in pan_generator() if is_magic(n)])

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


>>> 
problem euler 43: 16695334890 
elapsed time: 21.8429999352sec

Il minuto limite è lontano, ma si può fare di meglio.
Google come sempre è arrivato in aiuto.
(ringrazio l’autore del sito DreamShire)

Nuova Analisi

Le possibilità di pandigitali a 10 cifre sono (0-9) 9×9! = 3’265’920
Controllare la divisibilità di ogni permutazione, di 3 cifre in 3 cifre con i primi,
porta il tempo di esecuzione a circa un minuto.
Bisogna semplificare il tutto.

1) Il numero non può cominciare per 0, altrimenti avremmo un intero di sole 9 cifre.

2) d4 deve essere divisibile per 2, quindi d4 deve appartenere al gruppo (0, 2, 4, 6, 8).

3) la terna d4d5d6 deve essere divisibile per 5, quindi d6 deve appartenere al gruppo (0, 5).

4) la terna d6d7d8 deve essere divisibile per 11. Se controlliamo il ‘punto 3’, d6 deve
appartenere al gruppo (0, 5). Se d6 fosse ‘0’, come multipli di 11, nella terzina, avrei numeri ripetuti
(011, 022, 033, …, 099), cosa vietata dallo stato di pandigitale.
Ne consegue che d6 deve per forza essere un ‘5’.
Il gruppo di numeri divisibile per 11, che cominciano per 5 sono (506, 517, 528, 539, 561, 572, 583, 594).

2-bis) Dal punto precedente il ‘punto 2’ va modificato inquanto ora d6 = 5.

5) la terna d7d8d9 deve essere divisibile per 13. Dal ‘punto 4’, sappiamo che le terne possono cominciare
per (06, 17, 28, 39, 61, 72, 83, 94), non possono contenere ‘5’ (proprietà esclusiva di d6), quindi, escludendo
numeri ripetuti il range di possibilità sarà: (286, 390, 728, 832).

6) la terna d8d9d10 deve essere divisibile per 17 e dal ‘punto 5’ sappiamo che deve cominciare per (28, 32, 86, 90),
non contenere ‘5’ (d6) e nessuna cifra ripetuta, quindi il range sarà (289, 867, 901).

Controllando le cifre d6-d10 sappiamo che:
d6 = 5
d7d8d9 = (286, 390, 728)
d8d9d10 = (289, 867, 901)

incrociando le ‘regole’ ne consegue che:
d6d7d8d9d10 = (52867, 53901, 57289)

7) la terna d5d6d7 deve essere divisibile per 7 e, dopo il ‘punto 6’, finire per (52, 53, 57).
Gli unici numeri con queste caratterisitche sono (357, 952)
Questo corregge il ‘punto 2’ eliminando dalle possibilità di d4, il 2 e l’8 (punto 6).
Quindi d4 potrà essere (0, 4, 6) non possiamo avere numeri ripetuti.
Considerando la terzina appartenente al gruppo (357, 952) limitiamo il campo d5-d10 a: (357289, 952867)

7-bis) Siccome i valori di d4 come detto sono (0, 4, 6), il gruppo d4d5d6d7d8d9d10 si estenderà a:
(0357289, 0952867, 4357289, 4952867, 6357289, 6952867)

8) la terzina d3d4d5 deve essere divisibile per 3, quindi dal gruppo al punto precedente abbiamo che
le terzine divisibili per 3 finiranno per (03, 09, 43, 49, 63, 69). Considerate le cifre mancanti
e la divisibilità per 3, rimaniamo con (30952867, 60357289, 06357289).

Ora mancano solo le cifre 1-4, cioè d1 e d2. Non ci sono particolari regole, quindi le combinazioni sono:
(1430952867, 1460357289, 1406357289, 4130952867, 4160357289, 4106357289)

Nuovo approccio.

Non devo più creare tutte le permutazioni e poi filtrarle, poichè il collo di bottiglia è proprio
nel completamento di tutte le permutazioni.
Decido da quale punto in poi far lavorare il pc (punto 7).
Diciamo che abbiamo capito che la parte finale dei numeri pandigitali sarà (357289, 952867).
Permutiamo solo sulle 4 cifre mancanti delle 2 possibilità:
1460 e 1340

python:

import time
import itertools as it

ts = time.time()

def is_magic(strnum):
    # testo i punti 7-bis e 8
    if int(strnum[1:4]) % 2 == 0 and int(strnum[2:5]) % 3 == 0:
        return True
    return False

def pan_generator(str, n=4):
    return (''.join(i) for i in it.permutations(str, n))

def get_sum(permutable, suffix):
    perm_sum = 0
    for sn in pan_generator(permutable):
        # testo il punto 7 ed elimino lo 'o' come prima cifra
        if is_magic(sn + suffix) and sn[0] != '0':
            perm_sum += int(sn + suffix)
    return perm_sum

res = get_sum('1340', '952867') + get_sum('1460', '357289')

print "problem euler 43: {} \nelapsed time: {}sec".format(res, time.time() - ts)
>>> 
problem euler 43: 16695334890 
elapsed time: 0.0sec

ah però!

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: