PUMaC 2017 · 团队赛 · 第 12 题

PUMaC 2017 — Team Round — Problem 12

(10) Call a positive integer n tubular if for any two distinct primes p and q dividing n , ( p + q ) | n . Find the number of tubular numbers less than 100,000. (Integer powers of primes, including 1, 3, and 16, are not considered tubular.)

解析

Claim: all tubular numbers are divisible by 2520 = 2 · 3 · 5 · 7. Subclaim: 2 divides any tubular number. Suppose it doesn’t; then p, q 6 = 2 are primes dividing n that are both odd, so 2 | ( p + q ) | n . Now, consider 2 and any odd prime p > 3 dividing n . ( p + 2) | n ; either p + 2 is (an odd) prime, in which case p + 4 is composite, or p + 2 is itself composite. That composite value has a prime √ ′ ′ factor less than p ≤ p + 3 ± 1 < p , so p | n and we have found a smaller odd prime factor of n ; we can continue to use descent until we reach 3 | n . 3 | n = ⇒ 5 | n = ⇒ 7 , 8 | n = ⇒ 9 | n , 3 2 3 2 so combining all this gives 2 · 3 · 5 · 7. Call N = 2 · 3 · 5 · 7. Let’s say we want to construct a tubular number with a prime factor larger than 7, so we would ⌊ ⌋ 100000 have to multiply N by some other number k . However, N k ≤ 100000, so k ≤ = 39. 11 N is a reasonable place to start; however, that instantly entails 11 , 13 | k = ⇒ 143 | k . Trying 13 gives 13 , 15 , 16 , 18 , 20 | n , which is satisfied by n = 26 N . Trying 17 gives 17 , 19 | n = ⇒ 323 | k ; comparable problems arise for the other primes less than 39 (23, 29, 31, 37). So, our values of k are restricted to those divisible by exclusively 2, 3, 5, 7, 26; there are in fact 26 such values. Problem written by Zack Stier