[seqfan] Re: Climb to a prime, yet another way.

[David Seal]

As a fairly minor negative result, I've written and run a program that (if bug-free) demonstrates that any finite cycle must involve a number >= 2^55, or equivalently must involve a number whose factorisation includes primes outside the first 55 primes 2, 3, 5, ..., 257.

The program works by searching for potential 'top of cycle' values - i.e. values that could potentially be the maximum value achieved within a finite cycle. Such a value must have a possible predecessor and a successor that are both <= itself.

The program looks first for values with possible predecessors <= themselves, doing this by a binary inclusion/exclusion search on whether bits are 1s in the value, and using the fact that if bits i1, i2, ..., in are set in the value, then its predecessor must be a multiple of the product p_(i1+1) * p_(i2+1) * ... * p_(in+1). If that product is > the value, that rules out the possibility that the value, or any other value that has a superset of those 1s, is a 'top of cycle' value.

Values that pass that test are then partially factorised by trial division by the first 55 primes. That either produces a complete factorisation, in which case the value's successor has been determined and can be checked to see whether it is <= the value, or an incomplete one, in which case the value's successor must be >= 2^55 and so the value cannot be a 'top of cycle' value.

Those two checks reduced the number of 'top of cycle' candidates to a bit over 170,000 values. The trajectory of each of them was then calculated until it reached itself (discovering that it was a real 'top of cycle' value) or 1, a value greater than itself or a previously-discovered 'top of cycle' value (in each case proving that it was not a 'top of cycle' value). Most reached values >= themselves, all the rest reached 1.

The decision to use the first 55 primes was just a preliminary investigation staying within the bounds of 64-bit arithmetic - the key point being that a 55-bit number times the 55th prime 257 cannot overflow a 64-bit number. A bit more work should permit the use of the first 64 primes, still staying within the bounds of 64-bit arithmetic, and obviously multi-precision arithmetic could potentially go a lot further.

However, not surprisingly considering the binary inclusion/exclusion search, the program's execution time appears to be rising exponentially with the number of primes being considered, with each additional prime multiplying it by about 1.5. It's already moderately long for 55 primes and while 64 primes looks achievable, there's clearly limited scope to push it much beyond that without algorithmic advances.

I only regard this as a fairly minor negative result because trajectories under the A087207 map are clearly capable of containing enormous 'spikes', going up to a very large value in one iteration and coming down again equally quickly. In particular, if p_n is the nth prime number, then p_n -> 2^(n-1) -> 1 is such a 'spike'. That particular 'spike' cannot be part of a finite cycle, of course, but there are plenty of other possibilities...

Best regards,

David

> On 21 June 2017 at 07:41 Antti Karttunen <antti.karttunen at gmail.com> wrote:
> 
> 
> Cheers all,
> 
> I offer €42 for the first proof or disproof of the conjecture I make
> in https://oeis.org/A087207 that starting with any natural number n >=
> 1, iterations of A087207 ("A binary representation of the primes that
> divide a number, shown in decimal") eventually lead to zero. That is,
> if we start from any n that itself is neither a prime nor a power of
> two, we will eventually hit a prime number.
> 
> For a simple disproof, show me a number n for which a positive number
> of applications of A087207 will lead back to the same n.
> 
> For a purely existential proof that at least one such cycle exists or
> that some trajectory can never reach zero, please publish a paper in a
> generally respected peer-reviewed mathematical journal.
> Likewise if you have a proof that all iterations of A087207 reach zero.
> 
> (Funny thought: Can we make conjectures more popular by offering money
> for their solutions?)
> 
> 
> Best regards,
> 
> Antti Karttunen
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/