|
(I'm also replying myself concerning the problem itself). Unless I'm getting myself completely wrong, this also seems to be a very unusually simple problem for IMO's standards. I don't think I ever got myself solving one of them when I tried in the past, but if I'm not fooling myself the most natural approach for this one seems to bring to the solution: 1) Look at the two smallest divisors 1 < d_2 < d_3 of n. Then d_2 is necessarily a prime p, and d_3 is either p^2 or a different prime q. Let's first prove the latter can't be the case: if it where, looking at the biggest 3 divisors [n/q, n/p, n], we'd get that there's an integer a such that:
n/q * a = n/p + n.
Simplifying a bit, we get (1+p)q = ap, which is impossible because p divides neither p+1 nor q. 2) So, for n not to be a power of p, it must be 1 < d_2=p < d_3=p^2 < ... d_{k+1}=p^k < q. In particular, p^{k-1} must divide p^k+q. However this is also impossible, because p^{k-1} obviously divides p^k, but not q, so it can't divide the sum. Gosh I feel like a grumpy old man saying "those youngsters, on my days we used to have harder problems than this" ;-) |
1)notice it's prime powers
2)notice that 1,p,p^2 eventually leads to contradiction
3)use the last part of the factorization to rule out 1,p,q
I couldn't get GPT4 to do either 2 or 3 even with hints. It's surprising that either due to context length or something else I feel like its reasoning abilities are worse when you try to guide it. But maybe this is true for humans too.