I'm sure something like this has been asked, but I can't seem to find it.
Let $a,b$ be two natural numbers such that $a<b$ and $\text{lpf}(a)=\text{lpf}(b)$. Is there always an $n\in\mathbb N$ such that $a<n<b$ and $\text{lpf}(n)>\text{lpf}(a)$?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ oeis.org/A020639 $\endgroup$– Will JagyJul 27, 2019 at 1:33
-
$\begingroup$ Note a fairly closed related question is In a given sequence of consecutive integers, finding the count of integers with a least prime factor greater than $p$. $\endgroup$– John OmielanJul 27, 2019 at 1:53
-
2$\begingroup$ @Trev I wrote & ran a C++ program which tested all integers up to $8 \times 10^{8}$ and didn't find any exceptions, i.e., there's always an $n$ where it's lpf is larger between any $2$ consecutive integers with the same lpf. $\endgroup$– John OmielanJul 27, 2019 at 5:03
-
1$\begingroup$ @Trev A very closely related question is MO's Least Prime Factor in a sequence of 2n consecutive integers. The comments indicate using A058989, which points to the associated A049300. What these $2$ show is the least prime $p$ where at least $2p$ consecutive integers have a lpf $\le p$ is $43$, for $89$ values, starting at $14,478,292,443,584$. As this is more than $1.4\times 10^{13}$, it shows counter-examples, if any, are very large. $\endgroup$– John OmielanJul 27, 2019 at 5:34
-
$\begingroup$ @JohnOmielan Thanks! It also seems to hold for arithmetical progressions, but seems to be untrue for quadratic functions. I tried it on $f(x)=x^2+k$ for small $k$, and there are generally small counterexamples. Weirdly, $x^2+1$ has a counterexample at $x=846$ and that's the highest you see until $x^2+138$, and more surprisingly, $x^2-2$ has its first at $x=116279$, with nothing else nearby remotely as high. $\endgroup$– TrevorJul 27, 2019 at 20:44
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
6
I am kind of astonished, but I've eventually discovered this to be false. There is a counterexample in the interval 724968762211953720363081773921156853174119094876349 to 724968762211953720363081773921156853174119094876611, which both have lpf of 131, with intervening values all lower.
-
$\begingroup$ I assume this was found by a modified version of brute force. What optimizations did you use make the program run fast enough? $\endgroup$ Nov 8, 2020 at 14:30
-
2$\begingroup$ Not really, these numbers are far far too big for any kind of brute force of the type needed. IIRC I found these numbers in a list in a recent paper on computing the Jacobsthal function, cross checked their numbers against my conjecture, and found this one broke it. $\endgroup$– TrevorNov 11, 2020 at 1:25
-
-
1$\begingroup$ I'm not sure now, but from my Google activity history, probably Hagedorn's Computation of Jacobsthal's function h(n) for n<50. See also oeis.org/A048670. $\endgroup$– TrevorAug 20 at 23:04
-
$\begingroup$ How did you get those specific numbers? Those two numbers don't appear in the paper? $\endgroup$ Aug 21 at 23:21