HMMT 十一月 2018 · 冲刺赛 · 第 34 题
HMMT November 2018 — Guts Round — Problem 34
题目详情
- [ 20 ] A positive integer is called primer if it has a prime number of distinct prime factors. A positive integer is called primest if it has a primer number of distinct primer factors. A positive integer is called prime-minister if it has a primest number of distinct primest factors. Let N be the smallest prime-minister number. Estimate N . ( ) N E An estimate of E > 0 earns b 20 min , c points. E N
解析
- [ 20 ] A positive integer is called primer if it has a prime number of distinct prime factors. A positive integer is called primest if it has a primer number of distinct primer factors. A positive integer is called prime-minister if it has a primest number of distinct primest factors. Let N be the smallest prime-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 with p 6 = r, q 6 = s are primest. Thus, primest numbers are not very rare, so we can expect the answer to be relatively 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 = i for x in primes: if x > temp: break if temp % x == 0: prime_factors += 1 while temp % x == 0: temp = temp // x if (prime_factors == 0): primes.append(i) continue elif (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*= i return ans def 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 ans def compute(L): ans = 1 for i in range(len(L)): ans *= (primes[i]L[i]) return ans def find_best(M, best = 220 * 3**5, curr = ()): num = compute(curr) if (num > best): return False if (count_primests(curr) in primests): print(num, curr) return num for i in range(1,M): result = find_best(M, best, curr + (i,)) if (result == False): break elif (result < best): best = result return best print("Answer:", find_best(30))