from itertools import accumulate, chain, cycle, groupby, product, combinations
from random import randrange

_small_primes = set((2, 3, 5, 7, 11, 13, 17, 19, 23))

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def td_factors(n):
    fs = []
    for f in accumulate(chain((2, 1, 2, 2), cycle((4, 2, 4, 2, 4, 6, 2, 6)))):
        if f * f > n:
            break
        if not n % f:
            fs.append(f)
            n //= f
            while not n % f:
                fs.append(f)
                n //= f
            if is_prime(n):
                break
    if n > 1:
        fs.append(n)
    return fs

def is_prime(n, k=25):
    """ Miller-Rabin
        returns: True if n is probably prime
                    False if n is composite
        k: number of random trial used
    """
    n = abs(n)
    if n < 29:
        return n in _small_primes
    for pi in _small_primes:
        if not n % pi:
            return False
    if pow(2, n-1, n) != 1:
        return False
    d, s = n - 1, 0
    while not d % 2:
        d //= 2
        s += 1

    def is_spsp(n, a):
        t = pow(a, d, n)
        if t in (1, n-1):
            return True
        for _ in range(s-1):
            t = (t * t) % n
            if t == n - 1:
                return True
            if t == 1:
                return False
        return False
    return all(is_spsp(n, randrange(2, n-1)) for _ in range(k))

n = 0
while 1:
    n += 1
    tri = (n + 1) * n // 2
    fac = td_factors(tri)
    if len(set(powerset(fac))) > 500:
        print("Euler12", tri)
        break