◂ 20 décembre 2015 ▸
Infinite Elves and Infinite Houses :
- code_partie1.py
- code_partie2.py
- differences.diff
from math import ceil from math import ceil
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
MAX_PUISSANCE = 8 MAX_PUISSANCE = 8
NB_PRIMES = 8 NB_PRIMES = 8
N = 36000000 N = 36000000
N1 = N // 10 | N2 = int(ceil(N/11.))
def sumDiv(nbs): def sumDiv(nbs):
global PRIMES global PRIMES
s = 1 | s = 0
for i in range(len(nbs)): | n = prod(nbs)
p = PRIMES[i] | for t in produitsMoinsDe(nbs, 50):
nb = nbs[i] | s += n // prod(t)
s *= (p**(nb+1) - 1) <
s //= (p-1) <
return s 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],
> i += 1
> v *= p
> return r
# si p < q, alors p a un exposant aussi grand que celui de q | # les exposants ne sont ici plus forcément décroissants
def puissances(): def puissances():
t = NB_PRIMES * [0] t = NB_PRIMES * [0]
while True: while True:
for i in range(NB_PRIMES): for i in range(NB_PRIMES):
t[i] += 1 t[i] += 1
if t[i] <= MAX_PUISSANCE: if t[i] <= MAX_PUISSANCE:
for j in range(i): <
t[j] = t[i] <
break break
if i == NB_PRIMES - 1: if i == NB_PRIMES - 1:
return return
#t[i] = 0 | t[i] = 0
yield t yield t
def prod(t): def prod(t):
global PRIMES global PRIMES
p = 1 p = 1
for i in range(len(t)): for i in range(len(t)):
p *= (PRIMES[i]**t[i]) p *= (PRIMES[i]**t[i])
return p return p
best = None best = None
for t in puissances(): for t in puissances():
s = sumDiv(t) s = sumDiv(t)
if s >= N1: | if s >= N2:
p = prod(t) p = prod(t)
if best == None or p < best: if best == None or p < best:
print(t, p, s) print(t, p, s)
best = p best = p