1
$\begingroup$

Recently I asked this question and quickly got back some excellent responses. I asked the question because I came across a paper by Eric Rowland called "A Natural Prime-Generating Recurrence". The main results on page 4. It appears there was much fanfare in academic news when the paper was released which turns out to be basically the question I asked yesterday except, instead of subtracting the lpf, he added it causing his function to climb indefinitely, whereas mine is decreasing.

So basically Rowland's iterations is $$f(n) = n + lpf – 1$$ starting at 5 (where lpf = least prime factor of $n$) which yields: $$5→9→11→21→23→45→47→93→95→99→101→201→203→209…$$

The sequence above is exactly the sequence Roweland has in column 2 on page 4 of his article without the duplicates.

Am I missing why Roweland's sequence is a significant discovery?

$\endgroup$
0

1 Answer 1

Reset to default
0
$\begingroup$

This is OEIS sequence A190894, which is not Rowland's sequence A106108 but an auxiliary sequence used in proving the properties of Rowland's sequence. Rowland's sequence is $$ 7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69, \ldots $$ which has the recurrence $a(n) = a(n-1) + \gcd(n, a(n-1))$ with $a(1) = 7$, and the property that the difference between any two terms is either $1$ or a prime.

$\endgroup$
3
  • $\begingroup$ But aren’t the differences of Roweland’s sequence which are not 1s simply the lpf of the auxiliary sequence. For example, lpf(5) = 15 – 10, lpf(9)=18 – 15, lpf(11)=33 – 22, lpf(21)=36 – 33, lpf(23)=69 – 46, and so on; consequently we are merely finding lpf's using the Sieve of Eratosthenes? $\endgroup$
    – Math777
    Commented Feb 2, 2021 at 23:18
  • $\begingroup$ Just want to ensure that I'm not going insane. Isn't it true that given $n \geq2$, $n\in\mathbb{N}$, the iteration $f(n) = n + lpf – 1$ will always produce a sequence whose first differences plus 1 is always prime? $\endgroup$
    – Math777
    Commented Feb 5, 2021 at 10:46
  • 1
    $\begingroup$ I think you mean $f(n+1) = f(n) + \text{lpf}(f(n)) - 1$. Yes, the first difference + 1 of that will be $f(n+1) - f(n) + 1 = \text{lpf}(f(n))$, which by definition of $\text{lpf}$ is always prime as long as $f(n)$ is an integer $\ge 2$. $\endgroup$
    – Robert Israel
    Commented Feb 5, 2021 at 15:31

You must log in to answer this question.

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