[seqfan] Re: Will this pattern continue for all numbers?

Ali Sada pemd70 at yahoo.com
Sat Apr 18 02:54:20 CEST 2020

 Hi Tim,
Thank you very much for your email. I am even more curious now about this algorithm. The meeting points count when they are in the same phase, i.e. when the algorithm moves in one direction after the meeting.I would really appreciate it if you could send me your results. My "fancy" VBA/Excel and my programming knowledge are limited.

    On Friday, April 17, 2020, 4:04:17 PM EDT, Tim Peters <tim.peters at gmail.com> wrote:  
 [Ali Sada via SeqFan <seqfan at list.seqfan.eu>]
> We start with n and use the map k-->k+p, where p alternates between
> the “largest prime factor” and the “smallest prime factor”.
> We have two versions here: a)    largest, smallest, largest, etc.; and
> b)    smallest, largest, smallest, etc.
> What is interesting is that it seems, at least for the small group of
> numbers I checked, that no matter what version we use, we will
> reach a meeting point. (I can't prove that.)

"Meeting point" needs some elaboration.  When k is a power of a prime,
(a) and (b) meet on their first iterations.  But the results later
seem to skip over all initial "meetings", waiting until (a) and (b)
diverge before a later "meeting" counts.  For example, 2 maps to 4
either way, and then 4 maps to 6 either way, but neither of those seem
to count.

> ...

> The sequence associated with this algorithm is the “meeting point” for each
>  number (starting from 2):
>  12, 12, 12, 15, 77, 30, 15, 21, 15, 77, 21, 77, 21, 77, 30, 77, 30, 77, 77,  30, 77, 91, 77, 51, 77, 77, 77, 105

And later Luca Petrone said he got 12 for k=6 instead of 77, and you
confirmed that.

Hans Haverman also got different results for 14, 19, 25, and 28.  He
didn't say what he got instead, and I didn't see a response to him.
So here's what I got ;-)

12, 12, 12, 15, 12, 30, 15, 21, 15, 77, 21, 77, 30, 77, 30, 77, 30,
57, 77, 30, 77, 91, 77, 77, 77, 77, 35, 105

That disagrees at the same positions Hans found disagreements.

Dr. Israel found it easy through k=6042, but 6043 looks tough.  I let
iterates get about 1000 times larger than where he stopped, but still
didn't find a meeting point.  The time for factoring is a real drag
then (although I'm using nothing fancier than Pollard rho for that).

So is 6043 uniquely hard - or common?  Alas, it's not unique.  Trying
larger starting points, they seem to fall in two categories:  "goes
fast" and "no end in sight"

Here are the smallest I found before giving up:

6043, 6551, 6791, 7057, 7177, 7213, 7229, 7411, 7499, 7529, 7541, 7547

Those are all primes.  Is it limited to primes?  I think that's a
natural question, since all iterates are composite (k+p is necessarily
divisible by p. since p divides k by construction).

So I tried changing the definition of "meeting point" to NOT overlook
initial meetings (so that powers of primes found a meeting point at
once), and the smallest hard case then was 11589 (3 * 3863), and next
after that 11733 (3 * 3911).

So:  no insights or striking patterns from me!  Those also serve who
only thrash and fail ;-)  

More information about the SeqFan mailing list