Advent of code

◂ 20 décembre 2015 ▸

  Infinite Elves and Infinite Houses :

1. code_partie1.py
2. code_partie2.py
3. differences.diff

from math import ceil

PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, ... 1223]  # pas besoin d'autant   

MAX_PUISSANCE = 8
NB_PRIMES = 8

N = 36000000
N2 = int(ceil(N/11.))

def sumDiv(nbs):
    global PRIMES
    s = 0
    n = prod(nbs)
    for t in produitsMoinsDe(nbs, 50):
        s += n // prod(t)
    return s

def produitsMoinsDe(t, maximum):
    if len(t) == 0:
        return [[]]
    global PRIMES
    r = []
    p = PRIMES[len(t) - 1]
    i = 0
    v = 1
    while v <= maximum and i <= t[-1]:
        r.extend([r2 + [i] for r2 in produitsMoinsDe(t[:-1], maximum // v)])
        i += 1
        v *= p
    return r

# les exposants ne sont ici plus forcément décroissants
def puissances():
    t = NB_PRIMES * [0]
    while True:
        for i in range(NB_PRIMES):
            t[i] += 1
            if t[i] <= MAX_PUISSANCE:
                break
            if i == NB_PRIMES - 1:
                return
            t[i] = 0
        yield t

def prod(t):
    global PRIMES
    p = 1
    for i in range(len(t)):
        p *= (PRIMES[i]**t[i])
    return p


best = None
for t in puissances():
    s = sumDiv(t)
    if s >= N2:
        p = prod(t)
        if best == None or p < best:
            print(t, p, s)
            best = p