Monday 23 August 2021

Recursion involving the Totient Function

With plenty of time on my hands and my mind being lately obsessed with recursive processes, I contemplated what might happen if I took a number and added its totient plus one to it, repeating the process with the new number and only terminating when a prime number was reached. Put mathematically and applied to a number \(n\), we have:$$n \rightarrow n+\phi(n)+1$$The first thing to realise is that for any prime number \(p\), this process will yield:$$p \rightarrow p+\phi(p)+1=p+p-1+1=2p$$and so any prime is initially doubled by this process. Remember the totient \( \phi(n) \) of \(n\) is the number of coprime integers less than \(n\), including 1.

Using SageMathCell, I was able to quickly determine the trajectories for all numbers up to 6000  and the distribution is shown in Figure 1. The vertical axis shows the trajectory length while the horizontal axis shows the number. Some of the record trajectories are shown in Figure 1 as well e.g. (97, 152) indicates that the number 97 sets a new trajectory record length of 152.


Figure 1: permalink

Below are shown the numbers that produce trajectories of record length, together with those lengths:
  •       1  has a trajectory of record length      1
  •       2  has a trajectory of record length      2
  •       3  has a trajectory of record length      8
  •     31  has a trajectory of record length     10
  •     42  has a trajectory of record length     31
  •     97  has a trajectory of record length   152
  •  1907  has a trajectory of record length   166
  •  2130  has a trajectory of record length   217
  •  3067  has a trajectory of record length   224
  •  5243  has a trajectory of record length   232
  •  7355  has a trajectory of record length   302
  •  7604  has a trajectory of record length   307
  • 10956 has a trajectory of record length >344
SageMathCell timed out for 10956 because the composite numbers were becoming unwieldingly large. See Figure 2.


Figure 2

The final number is the list shown in Figure 2 is:

128273423043384555138014803867139463949464184741011497767099217473602278 

It was at this point that SageMathCell gave up. Presumably the trajectory of 10956 does terminate but so far I've not been able to determine its exact length, although we know it's larger than 344. The average number of iterations is slightly over 14 in the range up to 6000.

I may have more to add on this recursive process at a later date.

No comments:

Post a Comment