[seqfan] Re: Are we going to get anything other than 2’s and 3’s from this algorithm?

Elijah Beregovsky elijah.beregovsky at gmail.com
Sun Jan 26 19:26:20 CET 2020


Hello!
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:
A(n,n),
A(n,n-1),
A(n,n-2)...,

but this:
A(n,n),
A(n,n-1),
A(A(n,n-1),A(n,n-1)-1),
A(A(A(n,n-1),A(n,n-1)-1),A(A(n,n-1),A(n,n-1)-1)-1)...

For example, for n=12 it goes:
12/3=4, 12-1+4=15;
15/5=3, 15-1+3=17;
17/17=1, 17-1+1=17;
17/17=1, 17-1+1=17...

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
order?

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
while):
The first numbers of order k are:
k  n
1  2
2  4
3  12
4  27
5  26
6  182
7  183
8  319
9  280
The next one goes above 1000 at some point, so it didn't fit in my sheet.
The sequence of orders starts (offset=2):
1,1,2,1,2,1,2,2,2,1,3,1,3,2,2,1,2,1,2,2,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.
https://docs.google.com/spreadsheets/d/1-HQb1_kLPV0xT7Ki5BTRiVOA8MawgJO0ZLfAVM8JKk0/edit?usp=sharing



More information about the SeqFan mailing list