[seqfan] Re: a new survey about recent sequences with nice problems and pictures

[David Seal]

With regard to the following passage on page 15:

"The method used by James Davis to find D_0 is quite simple. Suppose n = m * p is fixed by f, where p is a prime greater than all the prime factors of m. Then f(n) = f(m)10^y + p, where y is the number of digits in p. From f(n) = n we have p = f(m)10^y/(m-1). Make another guess that m = x10^y + 1, so we want p = f(m)/x to be a prime. A computer easily finds the solution x = 1407, y = 5, m = 140700001, p = 96179, and so n = D_0.

No other composite fixed points are known, and it is not even known if D_0 is the smallest."

I can report that a fairly brute-force search that completed on my computer in January established that D_0 is the only composite 'top-of-loop' value (i.e. the maximal element of a loop of iterates that comes back to its starting value) that is <= 13550725439160. Since a fixed point is simply the only (and therefore maximal) element of a loop of length 1, it is therefore the only composite fixed point up to there, and thus the smallest composite fixed point.

The search used the method I described last June in http://list.seqfan.eu/pipermail/seqfan/2017-June/017689.html. The odd-looking choice of 13550725439160 as the final value to be checked is (p_(2^18))^2 - 1, and is a consequence of the binary-heap method I used to generate all multiples of the appropriate prime powers in ascending order (for base 10, those prime powers are 2^5, 3^4, 5^3, 7^3 and p^2 for all primes p >= 11). The fact that it is just greater than 13532385396179 is a happy coincidence!

The search took a very long time (probably a couple of CPU years, split between a few CPU cores to reduce the elapsed time to about 6 months) because even restricting to only checking multiples of those prime powers still left about 8.233% of numbers up to the limit to be checked - which is somewhere in excess of 10^12 numbers. That was made bigger by the fact that I was interested in all loops, not just fixed points, so potentially had a large number of f() evaluations to do for each number being checked. That could obviously be reduced to just one evaluation if looking for fixed points only, but how much by depends on the statistics of how many evaluations were needed per number checked, and I'm afraid I didn't gather those. The program might also be speeded up by using a more efficient factorisation method than trial division - I originally wrote it to search up to rather lower limits, for which trial division was easily adequate, and when I decided to extend the search up to D_0, I went for the lazy option of putting in very little extra effort myself even if it meant waiting a few extra months for the search to complete!

One other observation is that the "guess" that [there is an integer x such that] m = x10^y + 1 is not really a guess unless p is 2 or 5, as otherwise it can be deduced from p = f(m)10^y/(m-1). Specifically, that implies that p divides f(m)10^y, and provided p is neither 2 nor 5, p does not divide 10^y. Since p is prime, that means that it must divide f(m). So we can choose x to be the integer f(m)/p, and it then follows that p = (p*x)10^y/(m-1), from which it easily follows that m = x10^y + 1.

If I remember correctly, James Davis did describe it as a guess, so that's just an observation, not a correction to what the paper says. My reason for mentioning it is that it does make a considerably faster search possible if one is willing to only find composite fixed points that can be expressed in the form n = m * p, where p is a prime greater than all the prime factors of m (and m > 1, otherwise n = p is not composite). Or in other words, composite fixed points whose largest prime factor only appears in their factorisation with multiplicity 1.

Specifically, in that case m must be of the form x10^y + 1, when y is the length of p, and so for n to be <= a limit L, x must be <= L/(p10^y) - 1 < L/(p10^y) < L/(10^(2y-1)). For p reasonably large, that considerably reduces the search space - for example, for y=5 (the case that leads to D_0), each 5-digit prime p only needs < L/10^9 possibilities for x to be searched. That does need to be multiplied up by 8363 for the fact that there are that many 5-digit primes to be checked, of course, and more seriously, the number of possibilities needs to be calculated similarly for each possible value of y and the results added together, but that leaves very considerable savings in the number of possibilities to be searched for all but the smallest values of y. For them, it's more efficient to search values of m that only have prime factors < p than to search ones that are one more than a multiple of 10^y. (As the extreme case of that, if p=3, then y=1 and m can only be a power of 2, so there are about log_2(L) possibilities to search rather than about L/(10^(2y-1)) = L/10. And of course, because of the exclusion of p = 2 or 5 in the above argument, those two values of p cannot be handled using the search for values of m of the form x10^y + 1 anyway.)

That method can find all fixed points whose largest prime factor is reasonably small (where some work is needed to determine how small should count as "reasonably small" for the best efficiency), and all of them whose largest prime factor appears in their factorisation with multiplicity 1. That leaves the case where the fixed point's largest prime factor is not reasonably small and appears in its factorisation with multiplicity 2 or more. But that case can also be speeded up considerably, since we can put n = m * p^2 with p greater than or equal to all the prime factors of m. That limits the number of possibilities to be checked for m to be less than L/(2*y-2) per value of p, which is not as good a limit as the L/(2*y-1) when the multiplicity is 1, but still a major improvement when y=1.

Finally, a brief explanation as to why I haven't done all of that, and why I'm only reporting the search results now when the search completed in January: other events in my life, including a significant health problem, forced me to put working on this on to the back burner, and I'm afraid I've been rather slow to take it off the back burner again!

Regards,

David


> On 14 May 2018 at 22:39 Neil Sloane <njasloane at gmail.com> wrote:
> 
> 
> Here is a draft of an article for the Notices of the AMS,
> although it will probably get changed a lot before it appears (if it ever
> does appear).  But I will also put it on the arXiv. Comments welcomed. See:
> http://NeilSloane.com/doc/notices2.pdf
> 
> (I thought I sent this to the list a few days ago, but I was told it never
> arrived.  Apologies if you got this twice)
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/