lazyhash's blog

Need help | Range coprime bound
By lazyhash, 12 hours ago, In English

Can someone please help me understand or prove this (intuitively or formally)?

We are given an integer x < 1e18, How can we determine a lower bound on the length of a range [a, b], such that there is at least one number in [a, b] that is coprime to x?

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
11 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I would say use the idea of euler's formula, x <= 1e18 would have atmax 20 primes.

Let the length of range be L, after using each of the primes to discard numbers, number of coprime numbers in range would probably be

$$$N = L * (1 - 1 / 2) * (1 - 1 / 3) * (1 - 1 / 5) ...$$$

for first 20 primes thats about $$$0.12L$$$. So for about $$$L >= 10$$$ you should expect to see atleast one coprime number.

I know this may be a totally wrong way of proving, but thats just my intution for this.

→ Reply
  • »
    »
    9 hours ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    This is wrong.

    You are implicitly using the lemma:

    For a range of $$$L$$$ consecutive numbers, at-least $$$L(1-1/p)$$$ numbers remain after removing all multiples of $$$p$$$

    However, once you do this for one of the primes, the range is no longer consecutive, and this lemma does not apply. It might be the case that the remaining numbers are all divisible by the next prime considered.

    The state-of-the-art approximation for $$$g(n)$$$ is

    $$$g(n) = O(\log^{2} n)$$$ reference

    where $$$g(n)$$$ is the Ordinary Jacobsthal function (which for instance is defined here) defined as the smallest positive integer such that every sequence of $$$g(n)$$$ consecutive positive integers contains an integer relatively prime to $$$n$$$.

    As to the OP's question, assuming that he is keen to prove the solution for Problem about GCD, I believe the lemma that will actually prove the solution is:

    For any two pairs of sequences of consecutive integers $$$(a, a+1 ... a+k)$$$ and $$$(b, b+1 ... b+k)$$$, there always exists a coprime pair $$$(a+i, b+j)$$$.

    Maybe it is possible to prove that $$$k=log(A)$$$? No idea though.

    rather than proving an unsolved conjecture 🤪

    → Reply
»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Your text to link here... This is what i followed, but one could think of it as its obvious we wont be expected to check all pairs given range of l and r is too too big. Prime gap was the primary idea after contest.

→ Reply