# [seqfan] Re: Iterating some number-theoretic functions

Hugo Pfoertner yae9911 at gmail.com
Tue Sep 19 17:20:52 CEST 2017

```All,

to support the observations on the behavior of the iteration for large
starting values, I have run samples of 100 consecutive starting values
10^k+1...10^k+100 for values of k=2...16. The results are summarized in the
following table:

............Start....die....immortal.prime.escaped..primes.2*n^(1/2)/
..............100...48.22....31...26....21.....0.......2.......3
.............1000...17.13....49...84....16....18......10.......9
............10000...16.18....31...62....11....42......20......22
...........100000....2.21....24..119.....6....68......51......55
..........1000000....0..0....17...73.....6....77.....140.....145
.........10000000....1..3....11...88.....2....86.....384.....392
........100000000....1..2....15...52.....6....78....1084....1086
.......1000000000....1..5.....7...59.....7....85....3057....3052
......10000000000....0..0.....8...50.....5....87....8612....8686
.....100000000000....0..0.....3..178.....7....90...24994...24970
....1000000000000....0..0.....4...39.....4....92...72694...72382
...10000000000000....0..0.....3...20.....3....94..211473..211286
..100000000000000....0..0.....1...70.....4....95..621039..620421
.1000000000000000....0..0.....1...23.....2....97.1831712.1831146
10000000000000000....0..0.....1..127.....2....97.5428723.5428681

Using the example of the line
1000   17 13    49   84    16    18      10       9
the meaning of the items in the line is
1000: Start of checked interval is 1001, end of checked interval is 1100.
17: There are 17 broken trajectories ending at an odd number
13: maximum length seen in all dead end trajectories
49: Trajectories reaching a prime and cycling there
84: maximum length seen in the trajectories reaching a prime
16: Number of primes in the starting interval, leading to immediate cycling
18: Trajectories managing to "escape" and grow at least for 200 iterations
10: Number of primes in the interval of consecutive squares containing
10^k+1
9: Estimate for the previous count

As expected, the percentage of "escapes" approaches 100 % and the
contribution of hitting a dead end at an odd number (hitting a square or
twice a square) becomes extremely unlikely.
The occurrence of a trajectory of length 178 (starting at 100000000026)
leading to a prime is an indication that there might be such hits beyond my
heuristically chosen termination criterion of 200 steps.

Hugo Pfoertner

On Mon, Sep 18, 2017 at 11:20 PM, Sean A. Irvine <sairvin at gmail.com> wrote:

> Andrew Booker makes the following observations:
>
> I would guess that asymptotically 100% of positive integers have unbounded
> trajectory, and it might be possible to prove something along those lines.
>
> Note that (sigma(n)+phi(n))/2 is an integer unless n is a square or twice a
> square, and those are very rare among large numbers. Further, if n>1 and
> (sigma(n)+phi(n))/2 is odd then n must be of the form pm^2 or 2pm^2 for an
> odd prime p. Combining this with some sieve theory, one can show that the
> number of composite n<=x with (sigma(n)+phi(n))/2 prime is O(x/log^2x).
> Since the map tends to increase geometrically and sum 1/k^2 converges, this
> suggests that a typical large composite has little chance of ever reaching
> a prime.
>
> Sean.
>
>
> On 14 September 2017 at 16:42, Sean A. Irvine <sairvin at gmail.com> wrote:
>
> > A summary of computation done for the (sigma(n)+phi(n))/2 iterated map.
> >
> > For n <= 1000, there are 9 main trajectories for which the outcome is
> > unknown (i.e. repeated iteration of the map seems to always give an
> > integer).  There are actually more than 9 starting points, but a bunch of
> > them converge and we end up with 9 main lines. There is a picture in
> > A291790 which shows this.
> >
> > The smallest members of each of these nine trajectories are 270, 440,
> 496,
> > 702, 737, 813, 828, 897, 905.
> >
> > I have iterated all of the 9 trajectories for at least 400 steps as shown
> > below.  I had been hoping that at least one of these would have fractured
> > by now, but it was not to be.  I think it is over to the theory guys now
> to
> > explain :-)
> >
> > start value, number of known terms, last known term
> > 270 515 766431583175462762130381515662187930626060289448722569860560
> > 024833735066967138095365846432527969442969920899339325281010
> 6664744901740672517008
> >
> > 440 484 820592372224724578936331208771944114408888086190107072338829
> > 838271921194090028163759134652444477758963320036027410363866
> 196889253338112
> >
> > 496 413 584312582216816725920147810109410523690065654337049514240252
> > 7907753582982754877434126465705917383073237325824
> > 702 404 126251452114427769757166118472128627038379408031427558360064
> > 354641637918168792707424465732797790457902669435072
> > 737 402 283797546155754217301048520274749519198606895782115901466430
> > 74098002112474486185406438722917960742713527040
> > 813 408 113022102836300508719080691707204575063141106900327215081396
> > 1006171199412698705455907629229684455325220217689600
> > 828 403 455532144721661509141700260843225180989580666045895972886381
> > 942233201091585638600868459337792419151007988203520
> > 897 406 108940233399970132387522851290707383338719377108227439287474
> > 8695473478395781640270557738150084391944706967040
> > 905 404 100620027787656599681514901460240738592719142739691263136185
> > 0971140981478254530295756493557282131306214400
> >
> > Sean.
> >
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
```