<jupyter_start><jupyter_text>Pandigital prime Problem 41We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.What is the largest n-digit pandigital prime that exists?<jupyter_code>from euler import Seq, timer, is_prime
from itertools import permutations

def p041():
    k = 9
    results = []
    while results == []:
        results = (permutations(range(1, k+1) >> Seq.map(str))
                   >> Seq.map(lambda x: int("".join(x)))
                   >> Seq.filter(is_prime)
                   >> Seq.toList)
        k-=1    
    return max(results)

timer(p041)<jupyter_output>result: 7652413 (1.61s)<jupyter_text>Coded triangle numbers Problem 42The nth term of the sequence of triangle numbers is given by, $t_n = \frac 1 2 n(n+1)$; so the first ten triangle numbers are:  $1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...$  By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is $19 + 11 + 25 = 55 = t_{10}$. If the word value is a triangle number then we shall call the word a triangle word.  Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?<jupyter_code>from euler import Seq, timer
import re

def p042():
    
    words = re.compile('[A-Z]+').findall(open('data/p042.txt').read())    
    scores = words >> Seq.map(lambda x: x >> Seq.sumBy(lambda x: ord(x) - 64)) >> Seq.toList
    
    max_score = max(scores)

    tri_numbers = (
        Seq.initInfinite(lambda x: x*(x+1)/2) 
        >> Seq.skip(1)
        >> Seq.takeWhile(lambda x: x < max_score)
        >> Seq.toList)

    is_tri = lambda n: n == (tri_numbers >> Seq.find(lambda k: k >= n))

    return (
        scores
        >> Seq.filter(is_tri)
        >> Seq.length)

timer(p042)<jupyter_output>result: 162 (0.02s)<jupyter_text>Sub-string divisibility Problem 43The 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 $d_1$ be the 1st digit, $d_2$ be the 2nd digit, and so on. In this way, we note the following:  $d_2d_3d_4=406$ is divisible by 2  $d_3d_4d_5=063$ is divisible by 3  $d_4d_5d_6=635$ is divisible by 5  $d_5d_6d_7=357$ is divisible by 7  $d_6d_7d_8=572$ is divisible by 11  $d_7d_8d_9=728$ is divisible by 13  $d_8d_9d_{10}=289$ is divisible by 17  Find the sum of all $0$ to $9$ pandigital numbers with this property.<jupyter_code>from euler import Seq, timer
from itertools import permutations

def p043():
    def test(n):
        return (n[0] <> '0' and
            int(n[1:4]) % 2 == 0 and
            int(n[2:5]) % 3 == 0 and
            int(n[3:6]) % 5 == 0 and
            int(n[4:7]) % 7 == 0 and
            int(n[5:8]) % 11 == 0 and
            int(n[6:9]) % 13 == 0 and
            int(n[7:10]) % 17 == 0)

    return (
        permutations(range(10) >> Seq.map(str))
        >> Seq.map(lambda x: "".join(x))
        >> Seq.filter(test)
        >> Seq.sumBy(int))

timer(p043)<jupyter_output>result: 16695334890 (7.12s)<jupyter_text>Pentagon numbers Problem 44Pentagonal numbers are generated by the formula, $P_n=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 $P_4 + P_7 = 22 + 70 = 92 = P_8$. However, their difference, $70 − 22 = 48$, is not pentagonal.Find the pair of pentagonal numbers, $P_j$ and $P_k$, for which their sum and difference are pentagonal and $D = |Pk − Pj|$ is minimised; what is the value of $D$?<jupyter_code>from euler import Seq, timer

def p044():
    pentagonals = (
        Seq.initInfinite(lambda i: i*(3*i-1)/2)
        >> Seq.skip(1)
        >> Seq.takeWhile(lambda n: n < 10000000)
        >> Seq.toSet)

    # assuming that pj and pk are under 10M
    return (
        pentagonals 
        >> Seq.collect(lambda j: pentagonals >> Seq.map(lambda k: (j,k)))
        >> Seq.filter(lambda (j,k): (j+k) in pentagonals)
        >> Seq.filter(lambda (j,k): (k-j) in pentagonals)
        >> Seq.map(lambda (j,k): k-j)
        >> Seq.min)

timer(p044)<jupyter_output>result: 5482660 (3.76s)<jupyter_text>Triangular, pentagonal, and hexagonal Problem 45Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:  |            |                |                       || ---------- | -------------- | --------------------- || Triangle	 | $T_n=n(n+1)/2$  |	1, 3, 6, 10, 15, ...  || Pentagonal | $P_n=n(3n−1)/2$ | 1, 5, 12, 22, 35, ... || Hexagonal	 | $H_n=n(2n−1)$	  |	1, 6, 15, 28, 45, ... |  It can be verified that $T_{285} = P_{165} = H_{143} = 40755$. Find the next triangle number that is also pentagonal and hexagonal.<jupyter_code>from euler import Seq, timer

def p045():

    maxN = 10000000000

    hexs = (Seq.initInfinite(lambda i: i*(2*i-1)) 
            >> Seq.skipWhile(lambda n: n <= 40755) 
            >> Seq.takeWhile(lambda n: n < maxN) 
            >> Seq.toSet)

    pents = (Seq.initInfinite(lambda i: i*(3*i-1)/2) 
             >> Seq.skipWhile(lambda n: n <= 40755)
             >> Seq.takeWhile(lambda n: n < maxN)
             >> Seq.toSet)

    tris = (Seq.initInfinite(lambda i: i*(i+1)/2) 
            >> Seq.skipWhile(lambda n: n <= 40755) 
            >> Seq.takeWhile(lambda n: n < maxN) 
            >> Seq.toSet)

    return hexs.intersection(pents).intersection(tris).pop()

timer(p045)<jupyter_output>result: 1533776805 (0.22s)<jupyter_text>Goldbach's other conjecture Problem 46It was proposed by <NAME> that every odd composite number can be written as the sum of a prime and twice a square.  $9 = 7 + 2×1^2$  $15 = 7 + 2×2^2$  $21 = 3 + 2×3^2$  $25 = 7 + 2×3^2$  $27 = 19 + 2×2^2$  $33 = 31 + 2×1^2$  It turns out that the conjecture was false.  What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?<jupyter_code>from euler import Seq, timer, primes, is_prime
from math import sqrt

def p046():
    def is_square(n):
        t = int(sqrt(n))
        return n == t*t

    def valid(n):
        return (primes()
                >> Seq.takeWhile(lambda k: k < n) 
                >> Seq.exists(lambda k: is_square((n-k)/2)))

    return (
        Seq.initInfinite(lambda k: k*2+9) 
        >> Seq.filter(lambda k: not(is_prime(k))) 
        >> Seq.find(lambda k: not(valid(k))))

timer(p046)<jupyter_output>result: 5777 (0.26s)<jupyter_text>Distinct primes factors Problem 47The first two consecutive numbers to have two distinct prime factors are:  $14 = 2 × 7$  $15 = 3 × 5$  The first three consecutive numbers to have three distinct prime factors are:  $644 = 2^2 × 7 × 23$  $645 = 3 × 5 × 43$  $646 = 2 × 17 × 19$.Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?<jupyter_code>from euler import FactorInteger, timer, Seq

def p047():
    len = 4

    return (
        Seq.initInfinite(lambda x: x) 
        >> Seq.map(lambda n: FactorInteger(n) >> Seq.length) 
        >> Seq.window(len)
        >> Seq.findIndex(lambda xs: xs >> Seq.forall(lambda x: x == len)))

timer(p047)<jupyter_output>result: 134043 (5.48s)<jupyter_text>Self powers Problem 48The series, $1^1 + 2^2 + 3^3 + ... + 10^{10} = 10405071317$.  Find the last ten digits of the series, $1^1 + 2^2 + 3^3 + ... + 1000^{1000}$.<jupyter_code>from euler import timer

def p048():
    return (range(1,1001) >> Seq.sumBy(lambda i: i ** i)) % (10 ** 10)

timer(p048)
[ 1 .. 1000 ]
|> Seq.sumBy (fun i -> pown (bigint i) i)
|> fun n -> n%(pown 10I 10)<jupyter_output><empty_output><jupyter_text>Prime permutations Problem 49The 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?<jupyter_code>from euler import Seq, timer, is_prime, primes
from itertools import permutations, combinations

def p049():

    def get_prime_permutations(n):
        return (permutations(str(n) >> Seq.map(str))
                >> Seq.toSet
                >> Seq.map(lambda chars: int("".join(chars)))
                >> Seq.filter(lambda x: x >= 1000 and is_prime(x))
                >> Seq.sort
                >> Seq.toList)

    return (
        int("".join(
                primes()
                >> Seq.map(get_prime_permutations)
                >> Seq.filter(lambda l: l >> Seq.length >= 3)
                >> Seq.collect(lambda l: combinations(l,3) >> Seq.filter(lambda x: (x[1]-x[0]) == (x[2]-x[1])))
                >> Seq.distinct
                >> Seq.nth(1)
                >> Seq.map(str))))

timer(p049)<jupyter_output>result: 296962999629 (0.06s)<jupyter_text>Consecutive prime sum Problem 50The prime $41$, can be written as the sum of six consecutive primes:  $41 = 2 + 3 + 5 + 7 + 11 + 13$  This is the longest sum of consecutive primes that adds to a prime below one-hundred.  The longest sum of consecutive primes below one-thousand that adds to a prime, contains $21$ terms, and is equal to $953$.  Which prime, below one-million, can be written as the sum of the most consecutive primes?<jupyter_code>from euler import primes, Seq, fst, is_prime, primes, timer

def p050():
    def max_prime(skip):
        return (
            primes()
            >> Seq.skip(skip)
            >> Seq.scan(lambda state, n: (1+state[0], n+state[1]), (0,0))
            >> Seq.takeWhile(lambda n: n[1] < 1000000)
            >> Seq.filter(lambda n: is_prime(n[1]))
            >> Seq.maxBy(fst))

    def loop(k,result):
        test = primes() >> Seq.skip(k) >> Seq.take(result[0]) >> Seq.sum
        if (test > 1000000):
            return result[1]
        else:
            r = [max_prime(k), result] >> Seq.maxBy(fst)
            return loop(k+1, r)

    return loop(1, max_prime(0))

timer(p050)<jupyter_output>result: 997651 (0.03s)
{'fraction_non_alphanumeric': 0.1367892653731055, 'fraction_numerical': 0.06400231682594845, 'mean_word_length': 2.7199281867145424, 'pattern_counts': {'":': 0, '<': 44, '<?xml version=': 0, '>': 178, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '308961', 'license': 'MIT', 'n_tokens_mistral': 4134, 'n_tokens_neox': 3573, 'n_words': 1155, 'path': 'euler_041_050.ipynb', 'repo_name': 'mndrake/PythonEuler', 'size': '10371'}