[seqfan] Re: Are we going to get anything other than 2’s and 3’s from this algorithm?
elijah.beregovsky at gmail.com
Sun Jan 26 19:26:20 CET 2020
The issue is not totally closed, yet.
Before I saw the example, I thought that Ali’s algorithm iterates the
function "Divide n by its largest prime factor and add the result to
n-1" instead of going steadily down. So, in terms of David’s triangle
the sequence it produces is not this:
For example, for n=12 it goes:
It's quite different from Ali's algorithm. First, my version can go on
forever: it doesn't have a stopping condition and the next term is
never less than the previous. Second, when it encounters a prime, it
starts going in cycles. Moreover, only primes make it do that, as it
is strictly increasing otherwise.
So, I've got some questions for you:
Let's call the number of different terms in the sequence generated by
n "order of n". For example order of 12 is 3 (12, 15, 17) and order of
26 is 5 (26, 27, 35, 39, 41). Are all orders possible? And are there
infinitely many numbers of each order? Are there numbers of infinite
What I already know (not much, I didn't spend any substantial amount
of time on this, just write here to get it out of my mind for a
The first numbers of order k are:
The next one goes above 1000 at some point, so it didn't fit in my sheet.
The sequence of orders starts (offset=2):
That is close to A269252, but only in first terms, after that they are
very different, so it might be a coincidence.
And I know for sure, that numbers of order more than 2 are infinite.
They (though, sadly, not nearly all of them) can be generated as
p*(p+1), for prime p. As p and p+1 don't have common factors, the
largest prime factor of p*(p+1) is p, so the second term in the
sequence is p*(p+1) - 1 + (p+1) = (p+2)*p, which is composite,
therefore of order not less than 2.
>From David's argument I know, that all numbers after the first step are odd.
I attached a Google sheet with a thousand rows, showing results of the
algorithm on every iteration. (Look from column G on, everything
before is just preparation.) The primes are highlighted green. Some of
the last rows went over 1000 and broke, that's not a bug. There might
be a few bugs, but I'm pretty confident in my formulas.
More information about the SeqFan