Timeline for Greatest prime factor of n and n+1
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 1, 2019 at 15:37 | comment | added | John Omielan | @DmitryKrachun Thanks for showing your approach. I feel a bit silly. For a given prime $p$ & $x$, the density of integers $n$ for which $\operatorname{gpf}(n) = p$ can be fairly large when $\log_p{x}$ is quite small, but the density among larger $n$ as $x$ increases becomes very small. I now don't doubt the existence for any given $p$ of nice pairs $(p,q)$ (e.g., Størmer's theorem Gerhard's comment mentioned). The challenge is determining & proving any given pair when the $p,q$ become larger, such as Gerhard's answer below indicates. | |
| Jun 1, 2019 at 5:08 | answer | added | Gerhard Paseman | timeline score: 9 | |
| May 31, 2019 at 21:14 | comment | added | Dmitry Krachun | @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)$. | |
| May 31, 2019 at 20:13 | comment | added | John Omielan | @DmitryKrachun Do you have any particular reason to believe there are any nice pair at all with $p,q \gt 2$? Even just for $p$ or $q$ being $3$, there are already so relatively many possible values for $n$ or $n+1$ being of the form $3^i 2^j$ where $i \ge 1$ and $j \ge 0$. | |
| May 31, 2019 at 19:55 | comment | added | Dmitry Krachun | @JohnOmielan I don't know any nice pair with $p,q>2$... | |
| May 31, 2019 at 18:10 | comment | added | John Omielan | @DmitryKrachun You're welcome. I haven't spent very much time thinking about or checking on your problem, but it seems the difficulty & complexity of finding & proving pairs of primes are nice is large, even where the smaller prime is a very small odd prime, and grows very quickly for larger primes. Do you know of any $p$ where $(3,p)$ is nice, much less where $(5,p), (7,p), \ldots$ are nice? | |
| May 31, 2019 at 18:05 | comment | added | John Omielan | @AsymptotiacK No worries. I have spent so much time programming where the OR operator is inclusive that I forgot with English, although "or" is somewhat ambiguous, it's usually used in an exclusive sense. However, this is a moot point here as the two conditions can never be simultaneously true. | |
| May 31, 2019 at 15:09 | comment | added | Dmitry Krachun | @JohnOmielan Yes, thanks, I edited the question. It's actually relatively easy to show that $(2, p)$ is nice for infinitely many primes $p$. | |
| May 31, 2019 at 15:06 | history | edited | Dmitry Krachun | CC BY-SA 4.0 |
edited body
|
| May 31, 2019 at 12:52 | comment | added | Alexander Kalmynin | @JohnOmielan Oops, I misread the question | |
| May 31, 2019 at 5:49 | comment | added | John Omielan | @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$. | |
| May 31, 2019 at 5:02 | comment | added | John Omielan | @AsymptotiacK The question says "... 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$." The condition is of the form $A \text{ or } B$, where I assume it's the standard inclusive English "or", so it holds if either or both $A$ & $B$ are true. In this particular case, $p = 2$, $q = 19$ & $n = 512$, with condition $A$ holding, & $B$ for $(19,2)$. Thus, as being nice requires no natural numbers $n$, both $(2,19)$ & $(19,2)$ are not nice. | |
| May 31, 2019 at 1:35 | comment | added | Alexander Kalmynin | @JohnOmielan You showed that $(19,2)$ is not nice, not $(2,19)$ | |
| May 31, 2019 at 0:26 | comment | added | John Omielan | @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. | |
| May 30, 2019 at 21:30 | comment | added | Gerhard Paseman | In fact, such a claim might be provable from an analysis of A,B, with Ap +Bq=1. I can see such arithmetic progressions avoiding pairs of smooth numbers. Gerhard "We'll Trace One Warm Line..." Paseman, 2019.05.30. | |
| May 30, 2019 at 21:27 | comment | added | Gerhard Paseman | 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. | |
| May 30, 2019 at 21:09 | history | asked | Dmitry Krachun | CC BY-SA 4.0 |