Home > Project Euler, python > Problem euler #49

Problem euler #49

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms
increases by 3330, is unusual in two ways: (i) each of the three terms
are prime, and, (ii) each of the 4-digit numbers are permutations of one
another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes,
exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this
sequence?

Analisi:

Per prima cosa ho creato una lista di primi di 4 cifre, partendo da 1009.
Seconda cosa ho creato un dizionario con le permutazioni di ogni primo.
Poi ciclando sulle chiavi del dizionario, ho estratto i valori:
chiave, valore_1, valore_2 per i quali la differenza è sempre la
stessa.
In pratica ogni valore di una chiave viene sottratto con tutti gli
altri valori della stessa chiave. Ogni differenza, viene aggiunta ad
una lista di appoggio solo se assente dalla lista stessa.
Se la differenza è già in lista, allora ho trovato la terzina.

python:

import time
from itertools import permutations as perm 
ts = time.time()

def is_prime(num):
    if num <= 1: return False
    elif num == 2: return True
    elif num % 2 == 0: return False
    else:
        d = 3
        r = int(num**0.5)
        while d <= r:
            if num % d == 0: return False
            d += 2
        return True
    
def prime_perm(n):
        '''List of n-permutations, n excleded'''
        return [int(''.join(i)) for i in perm(str(n)) if is_prime(int(''.join(i)))][1:]

def is_magic(d):
    for key in d:
        diffs = []
        for n in d[key]:
            for m in d[key]:
                if n<m: # equal digit numbers excluded
                    if not abs(n-m) in diffs:
                        diffs.append(abs(n-m))
                    elif m - n == n - key:
                        return '{}{}{}'.format(key, n, m)
            
primes = [x for x in xrange(1009, 10000, 2) if is_prime(x)]
dp = {p: sorted(set(prime_perm(p))) for p in primes}
dp.pop(1487) # example in problem test

res = is_magic(dp)
print "problem euler 49: {} \nelapsed time: {}sec".format(res, time.time() - ts)
Categorie:Project Euler, python
  1. settembre 4, 2014 alle 11:42 pm

    Superb site you have here but I was curious about if you
    knew of any user discussion forums that cover the same topics
    talked about in this article? I’d really love to
    be a part of group where I can get responses from other experienced
    individuals that share the same interest.
    If you have any suggestions, please let me know. Appreciate it!

  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: