Блог пользователя Aritra741

Автор Aritra741, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 $$$

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 8   Проголосовать: нравится +3 Проголосовать: не нравится

      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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    That cleared up a lot of confusion. Thanks a lot.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).