I was trying to solve this(LightOJ 1370) problem. When I failed to come up with a memory efficient solution, I looked at some AC solutions.
Interestingly, the solutions used a property that states that the minimum number that has a phi value greater than or equal to a given number, must be the first prime number greater than the given number. For example, For 20, the answer is 23. I am looking for a proof of this property.
Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).
Let's say that x is the next number you're evaluating phi to check if it's >= the given number and it has more than one prime (it's composite). Let's call p the smallest prime in x.
phi(x) < x * (p — 1) / p. p is also <= sqrt(x) (because it's composite) so we get phi(x) < x * (sqrt(x) — 1) / sqrt(x), phi(x) < x — x / sqrt(x), phi(x) < x — sqrt(x).
That proves that no composite number x < given number + sqrt(given number) has phi(x) >= given number. If we assume the prime gap is smaller than sqrt(X) (it's actually much smaller but I don't know how smaller) then it proves that there will be a prime < given number + sqrt(given number) so that prime is the first one that has phi(x) >= given number.
Edit: looks like it's not proved that the prime gap is that small but those are conjectures yet to be disproven, so for our limited set of workable numbers in cp you can assume it's true: https://en.wikipedia.org/wiki/Prime_gap#Conjectures_about_gaps_between_primes
Nice solution, but this requires some knowledge about prime gaps it seems. Is there another way to prove it?
Let's say given number is $$$x$$$, and first prime above $$$x$$$ is $$$p$$$. The existence part of the proof is easy, because clearly $$$phi(p) >= x$$$.
Now you require to prove that $$$ \forall y \in (x,p), phi(y) < x $$$
If you prove that you almost prove that the prime gap is at least < 2*sqrt(prime)+1 and that's exactly one of the unproven conjectures so I don't think there's another way to prove it. Actually you could try proving this conjecture: https://en.wikipedia.org/wiki/Legendre%27s_conjecture but it's still the same problem of solving long standing mathematical conjectures lol
Edit: this property doesn't really imply on these conjectures but it's really close to that. It implies those conjectures near squares of primes though.
That cleared up a lot of confusion. Thanks a lot.
Because of the relationship with old unresolved conjectures on prime gaps, the easiest way by far to prove that this strategy works is to compute the possible minimum costs for every legal lucky number input on your own machine and notice (and check) that they are all prime. (But I would expect 32MB to be enough memory to perform the totient function calculations on the judge machine as well.)
Yeah I generated the answers for the legal numbers and checked that this strategy works. But I was wondering what may have caused this pattern to occur.
Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).