Friday, January 26, 2024

A million-digit Leyland prime (end of 2nd run)

My second run of 59754 Leyland-prime candidates was started on 27 April 2023 and resulted in my finding three PRPs (the first column is the number of decimal digits):

1000905  (197180,119151)  Aug 2023
1000910  (191319,170462)  Jul 2023
1000999  (194968,136197)  Dec 2023

I blogged my first run here. As I did last year, I have documented my primality-test output. Search for PRP therein to situate the three primes. I have improved my average evaluation time per test from 9.45 hours to 5.55 hours but I was wrong in predicting that "I might be able to shave a couple of months off the total time required". It still took nine months. Some of that expected time saving was eaten up by the additional 218 tests. Some more, perhaps, by down-time as I have had a few battery-back-up units shutting themselves off, presumably because they are getting old. The remainder of the unmaterialized time saving would be an early start on a third search which began on some of my machines back on December 11.

Tuesday, January 09, 2024

Confined

In Éric Angelini's latest effort, he posits some interesting sequences. Specifically, half-way down the page, we have "replace the chunk by [the chunk + 1]". In case this is not entirely clear, allow me to restate the rule. Any integer that contains one or more blocks of identical adjacent digits evolves into another integer where each of these blocks is replaced with the value of the block plus one. Thus 133555777799999000000 becomes 13455677781000001. The two 3s are replaced with 34, the three 5s with 556, the four 7s with 7778, the five 9s with 100000, and the six 0s with 1. If our integer does not contain any blocks of identical adjacent digits, it becomes twice that integer. A starting integer evolves by the repeated application of these rules:

133555777799999000000
    13455677781000001
        1345667788111
        1345677889112
        1345678899122
       13456789100123
        1345678911123
        1345678911223
        1345678912233
        1345678912334
        1345678912344
        1345678912345
        2691357824690
        5382715649380
       10765431298760
       21530862597520
       43061725195040
       86123450390080
        8612345039180
       17224690078360
        1723469178360
...

Starting with the integer 1, Giorgos Kalogeropoulos makes the evolution out to be:

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 65636, 131272, 262544, 262545, 525090, 1050180, 2100360, 211360, 212360, 424720, 849440, 849450, 1698900, 169891, 339782, 349782, 699564, 6100564, 611564, 612564, 1225128, 1235128, 2470256, 4940512, 9881024, 9891024, 19782048, 39564096, 79128192, 158256384, 316512768, 633025536, 634025636, 1268051272, 2536102544, 2536102545, 5072205090, 5072305090, 10144610180, 10145610180, 20291220360, 20291230360, 40582460720, 81164921440, 81264921450, 162529842900, 16252984291, 32505968582, ...

He suggests that the sequence seems to "explode to infinity". Actually, that initial explosion levels off after a thousand or so terms:

click to enlarge

I was sufficiently interested in this sequence to generate 15 billion terms. I graphed only the local minima and maxima, one each for every million terms. The initial explosion terms are ignored by setting the first minimum to 114782627657382. This way we see the sequence's confined space. Three extrema (one maximum, two 11-digit minima) are identified:

click to enlarge

The minima and maxima medians are ~10^18 and ~10^54. Because of the confined space the sequence will evolve into a loop, but particulars about this loop might never be known. To get a sense of this, be aware that in the graphed 15 billion sequence terms there are only 15 confined 11-digit integers. An additional 23 exist at the start but I cannot include these as being confined. So the sequence generates about one 11-digit integer every 10^9 terms. It could of course be more, or less, because the statistical estimate is based empirically on the 15 billion terms that we have so far examined.

How many random 11-digit integers are required in order to have a 50% chance that two of them are duplicates? It is roughly 350000. So, we need to generate some 350*10^3*10^9 = 350 trillion terms in order to have a decent shot at finding a loop.