[seqfan] Re: Iterating some number-theoretic functions

Tue Sep 19 17:39:22 CEST 2017

Sean, Hugo:  All this is extremely interesting to me, especially Andrew
Booker's analysis.  The clouds in front of this problem are beginning to
clear!

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 Tue, Sep 19, 2017 at 11:20 AM, Hugo Pfoertner <yae9911 at gmail.com> wrote:

> 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)/
> ...............n.#dead.max.#loop.max............../squares...log(n)
> ..............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/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>