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

[Neil Sloane]

Dear Elijah,  I think these two sequences should be in the OEIS, can you
please submit them?

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}
*)

Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com



On Sat, Feb 15, 2020 at 6:52 AM Elijah Beregovsky <
elijah.beregovsky at gmail.com> wrote:

> 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
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>