返回题库

HMMT 十一月 2018 · 冲刺赛 · 第 34 题

HMMT November 2018 — Guts Round — Problem 34

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 20 ] A positive integer is called primer if it has a prime number of distinct prime factors. A positiveinteger is called primest if it has a primer number of distinct primer factors. A positive integer iscalled prime-minister if it has a primest number of distinct primest factors. Let N be the smallestprime-minister number. Estimate N .
    ( )
    N E
    An estimate of E > 0 earns b 20 min , c points.
    E N
解析

英文解析

  1. [ 20 ] A positive integer is called primer if it has a prime number of distinct prime factors. A positiveinteger is called primest if it has a primer number of distinct primer factors. A positive integer iscalled prime-minister if it has a primest number of distinct primest factors. Let N be the smallestprime-minister number. Estimate N .
    N E
    An estimate of E > 0 earns b 20 min , c points.
    E N
    Proposed by: Yuan Yao
    4 3 3
    Answer: 2 · 3 · 5 · 7 = 378000
    q s
    One heuristic for estimating the answer is that numbers of the form p r for primes p, q, r, s withp 6 = r, q 6 = s are primest. Thus, primest numbers are not very rare, so we can expect the answer to berelatively small with only a few distinct prime factors.
    from operator import *
    primes = []
    primers = []
    primests = []
    for i in range(2,3000):
    prime_factors = 0
    primer_factors = 0
    temp = ifor x in primes:
    if x > temp:
    breakif temp % x == 0:
    prime_factors += 1
    while temp % x == 0:
    temp = temp // xif (prime_factors == 0):
    primes.append(i)
    continueelif (prime_factors in primes):
    primers.append(i)
    for x in primers:
    if i % x == 0:
    primer_factors += 1
    if (primer_factors in primers):
    primests.append(i)
    def product(L):
    ans = 1
    for i in L:
    ans*= ireturn ansdef sum_prime_product(L, curr = ()):
    if (L == ()):
    #print(curr)
    if len(curr) in primes:
    return product(curr)
    return 0
    return sum_prime_product(L[1:], curr + (L[0],)) + sum_prime_product(L[1:], curr)
    def count_primests(L, curr = ()):
    if (L == ()):
    if (sum_prime_product(curr) in primers):
    return 1
    return 0
    ans = 0
    for i in range(0,L[0]+1):
    ans += count_primests(L[1:], curr+(i,))
    return ansdef compute(L):
    ans = 1
    for i in range(len(L)):
    ans *= (primes[i]L[i])
    return ansdef find_best(M, best = 2
    20 * 3**5, curr = ()):
    num = compute(curr)
    if (num > best):
    return Falseif (count_primests(curr) in primests):
    print(num, curr)
    return numfor i in range(1,M):
    result = find_best(M, best, curr + (i,))
    if (result == False):
    breakelif (result < best):
    best = resultreturn bestprint("Answer:", find_best(30))