Prime Pair Connection

# -*- coding: utf-8 -*-
from primefac import primes
from math import log

'''
Prime pair connection
Project Euler: Problem 134

Consider the consecutive primes p1 = 19 and p2 = 23. It can be verified that 1219 is the smallest number such that the last digits are formed by p1 whilst also being divisible by p2.

In fact, with the exception of p1 = 3 and p2 = 5, for every pair of consecutive primes, p2 > p1, there exist values of n for which the last digits are formed by p1 and n is divisible by p2. Let S be the smallest of these values of n.

Find ∑ S for every pair of consecutive primes with 5 ≤ p1 ≤ 1000000.

'''

def sum_prime_pair(limit):
    twin = twin_primes(limit)
    twin.remove((3, 5))
    total = 0
    for pair in twin:
        total += p1_div_p2(pair)
    return total


def twin_primes(limit):
    prime_list = primes(limit)
    twin_lst = []
    p1 = prime_list.pop(0)
    for p2 in prime_list:
        if p1 + 2 == p2:
            twin_lst.append((p1, p2))
        p1 = p2
    return twin_lst


def p1_div_p2(twin_primes):
    p, q = twin_primes
    k = 10**int(log(p, 10)+1)
    m = 2*pow(k, p, q) % q
    return p + k*m


if __name__ == '__main__':
    print sum_prime_pair(10**6)