15
$\begingroup$

For a positive integer $n$ we denote its largest prime factor by $\operatorname{gpf}(n)$. Let's call a pair of distinct primes $(p,q)$ $\textbf{nice}$ if there are no natural numbers $n$ such that $\operatorname{gpf}(n)=p, \operatorname{gpf}(n+1)=q$ or $\operatorname{gpf}(n)=q, \operatorname{gpf}(n+1)=p$. For example, $(2,23)$ is nice.

Are there nice pairs $(p,q)$ with $p,q>100$?

Improve this question
$\endgroup$
14
  • 4
    $\begingroup$ Likely yes. One place to look is Stoermer's theorem on consecutive smooth integers. If you set a bound N (so gpf of such smooth integers is at most N), there will be finitely many consecutive pairs of such smooth integers, so I believe the claim that (2,19) is nice. I don't know, but I suspect a theorem like for every prime p there are infinitely many q with (p,q) is approachable from Stoermers theorem. Gerhard "Too Tired To Stroke Now" Paseman, 2019.05.30. $\endgroup$
    – Gerhard Paseman
    Commented May 30, 2019 at 21:27
  • 7
    $\begingroup$ @DmitryKrachun Actually, with $n = 512$, note that $512 = 2^9$, so $\text{gpf}(512) = 2$, and $513 = 3^3 \times 19$, so $\text{gpf}(513) = 19$. This shows by your definition that $(2,19)$ is not nice. $\endgroup$
    – John Omielan
    Commented May 31, 2019 at 0:26
  • 2
    $\begingroup$ @DmitryKrachun Both $(2,23)$ and $(23,2)$ are nice (actually, as you know, if $(p,q)$ is nice, then so is $(q.p)$) since $2^{11} - 1 = 23 \times 89$ and $23$ doesn't divide any $2^n \pm 1$ for an $n \lt 11$. $\endgroup$
    – John Omielan
    Commented May 31, 2019 at 5:49
  • 2
    $\begingroup$ @JohnOmielan Yes, thanks, I edited the question. It's actually relatively easy to show that $(2, p)$ is nice for infinitely many primes $p$. $\endgroup$
    – Dmitry Krachun
    Commented May 31, 2019 at 15:09
  • 2
    $\begingroup$ @JohnOmielan So here is an argument why I believe there are in fact nice pairs with $p,q>100$. Take $p=101$ and let $S$ be the set of $101-$smooth numbers . There are around $\log^A{x}$ of such numbers up to $x$ for constant $A$. For each $x\in S$ number $x\pm 1$ is kind of a random number so it has probability $x^{-1/(2A)+o(1)}$ to be $\log^{2A}{x}$-smooth. Since $\sum_{x\in S}x^{-1/(2A)}<\infty$ there are only finitely many numbers $x\in S$ for which $x+1$ or $x-1$ is $\log^{2A}{x}$-smooth. From that, it is easy to see that most primes are not appearing as $\operatorname{gpf}(x\pm 1)$. $\endgroup$
    – Dmitry Krachun
    Commented May 31, 2019 at 21:14

1 Answer 1

Reset to default
9
$\begingroup$

So running a simple sieve algorithm allows for recording pairs which are not nice, and there are many of them below 9 million. I get that the complement includes (2,q) for q=23,29,37,47, and more, (3,q) for q=89,103,113,131,137 and more, (5,q) for q=307,503,509,613,619 and some more, (7,q) for q=967,971,1031,1039,1049 and some more, (11,q) for q=2381,2543,2551,2591,2801 and a few more, and (13,q) for q=2531,2689,2797. For larger values of 13 $\lt p \lt q \lt$ 3000, there are no nice pairs.

I am willing to believe there is a q less than 2^2^101 for which (101,q) is nice. Based on preliminary data, I doubt q would be less than 2^101.

Gerhard "These Are Rather Big Numbers" Paseman, 2019.05.31.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .