[seqfan] Why does this sequence make a staircase pattern?

[Elijah Beregovsky]

Hello, Seqfans!
In an earlier post (in Ali Sada's thread "Are we going to get anything
other than 2’s and 3’s from this algorithm?") I introduced a sequence.
Let f(n) be "Divide n by its largest prime factor and add the result to
n-1". Iterate this function. (Let's call the resulting sequence I(n,k),
where k is the number of an iteration).

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...

If n is prime, then f(n)=n, otherwise f(n)>n. Let's call "order of n" the
least k for which I(n,k) is prime. (The number of iterations before the
function starts going in cycles). The sequence of orders is what I'm
interested in. More precisely, the sequence of the numbers, for which a new
order occurs for the first time. I've made a little program in Mathematica
for generating it:

Clear[f,it,order,seq];
f[n_]:=f[n]=n-1+n/First[First[MaximalBy[FactorInteger[n],First]]];
it[n_,k_]:=it[n,k]=f[it[n,k-1]];
it[n_,1]=n;
order[n_]:=order[n]=SelectFirst[Range[1,100], it[n,#]==it[n,#+1]&];
(* Check, whether it works *)
Print[order/@Range[1,100]];
(*
{1,1,1,2,1,2,1,2,2,2,1,3,1,3,2,2,1,2,1,2,2,2,1,2,2,5,4,2,1,4,1,2,4,4,3,2,1,3,2,2,1,2,1,2,2,2,1,3,3,2,2,3,1,2,2,3,2,2,1,2,1,3,2,4,3,2,1,2,2,2,1,4,1,3,2,2,2,2,1,4,2,2,1,4,2,3,2,4,1,2,2,4,4,4,3,2,1,3,2,4}
*)

(* Now find the least number of order k for each k<62 *)
seq[n_]:=seq[n]=SelectFirst[Range[350000],order[#]==n&];
seq/@Range[61]
(*
{1,4,12,27,26,182,183,319,280,842,1045,1718,1989,1985,1983,1922,5673,8546,11760,13371,15606,16659,15827,15732,15833,15210,15416,15707,15334,15251,15006,14812,14674,14787,14786,55911,137068,283221,283091,301659,301655,292032,294932,256000,303513,290950,297269,296865,295836,298348,301522,294872,300501,300639,300620,300627,300611,298779,293260,299965,300434}
*)
(* Plot it *)
ListPlot[seq/@Range[30], PlotRange->All]
ListPlot[seq/@Range[61], PlotRange->All]
[image: image.png]

[image: image.png]

As you can see, the graphs of the sequence for k<31 and for k<62 are very
similar: more or less constant, then a rapid increase, then again more or
less constant. For k=62 the corresponding n is more than 590000. I couldn't
compute more terms, Wolfram just stopped working and reset all the values
whenever I tried. But nonetheless, there's definitely another "cliff" at
k=62.
So, could you explain, please, why could these "plateaus" and "cliffs"
occur?

Other questions:
Are all orders possible? (Seems, that the answer is yes. But, how to tackle
this question I don't know.)
And are there infinitely many numbers of each order? (Looks like that one
is also true. And I know for sure, that there's infinitely many numbers of
order more than 2. 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.)
Are there numbers of infinite order? (Unlikely, but I can't think of even
how to start disproving it.)
Which numbers can be reached at iteration k?

And a spreadsheet of I(n,k) for n<1000, just to get a feel for the sequence
(from column G on, primes are green). Feel free to alter it anyhow, I've
got a copy.
https://docs.google.com/spreadsheets/d/1-HQb1_kLPV0xT7Ki5BTRiVOA8MawgJO0ZLfAVM8JKk0/edit?usp=sharing

Thank you in advance!
Elijah