Pagina's

2019/03/05

Largest left-truncatable prime in base 45


/* THE ON-LINE ENCYCLOPEDIA OF INTEGER SEQUENCES (OEIS),
sequence A103443, Largest left-truncatable prime in base n (given in decimal),
contains a table of n, a(n) for n = 3..89 (with some question marks).
The smallest odd n with a question mark is 45.
The largest left-truncatable prime in base 45 seems to be:

6418889846539907432243324898640584712447897570848322447697313961466124548502810052430598307

in base 45: Y8cE6UEE8SY4AcCGCiaiOWUgQeUSaeKOCaCWWSiKSQ8Ea8SYMU4E6ab

Until someone finds a larger left-truncatable prime in base 45 ;)
It took 32 hours and 12 minutes to find it.
Memory usage peaked at 9.6 GB, with the 9th prime: 23 (and a list of 18275774 primes). 
*/
using Mpir.NET;  // 0.4.0
using System;   // 4790@3.6
using System.Collections.Generic;
using System.Threading.Tasks;
class LLTPb
{
    static void Main()
    {
        uint b = 45;
        var sw = System.Diagnostics.Stopwatch.StartNew(); mpz_t p = M(b);
        Console.WriteLine(sw.Elapsed);
        Console.WriteLine(p);
        Console.WriteLine(mpir.mpz_get_string(b, p)); Console.Read();
    }

    static mpz_t M(uint b)
    {
        mpz_t m0 = 0, m1; uint s = 0;
        for (s = np(s, b); s > 0; s = np(s, b))
            if (m0 < (m1 = L(s, b))) m0 = m1;
        return m0;
    }

    static readonly object locker = new object();

    static mpz_t L(uint s, uint b)
    {
        Console.WriteLine("p: " + s);
        List<mpz_t> p1 = new List<mpz_t>(), p0 = new List<mpz_t>() { s };
        mpz_t n0 = 1, n; uint a;
        for (; ; )
        {
            for (n = 0, n0 *= b, a = 1; a < b; a++)
            {
                n += n0;
                Parallel.For(0, 8, t =>
                {
                    mpz_t np;
                    for (int j = p0.Count, i = t; i < j; i += 8)
                        if (mpir.mpz_probab_prime_p(np = n + p0[i], 15) > 0)
                            lock (locker) p1.Add(np);
                });
            }
            if (p1.Count == 0) return max(p0);
            Console.WriteLine(p0.Count);
            p0.Clear(); GC.Collect();
            for (n = 0, n0 *= b, a = 1; a < b; a++)
            {
                n += n0;
                Parallel.For(0, 8, t =>
                {
                    mpz_t np;
                    for (int j = p1.Count, i = t; i < j; i += 8)
                        if (mpir.mpz_probab_prime_p(np = n + p1[i], 15) > 0)
                            lock (locker) p0.Add(np);
                });
            }
            if (p0.Count == 0) return max(p1);
            Console.WriteLine(p1.Count);
            p1.Clear(); GC.Collect();
        }
    }

    static mpz_t max(List<mpz_t> p)
    {
        mpz_t m = p[0];
        for (int i = p.Count - 1; i > 0; i--) if (m < p[i]) m = p[i];
        return m;
    }

    static uint np(uint s, uint b)
    {
        if (s == 0) return 2 < b ? 2u : 0;
        if (s == 2) return 3 < b ? 3u : 0;
        if (s == 3) return 5 < b ? 5u : 0;
        if (s == 5) return 7 < b ? 7u : 0;
        for (s += 2; ; s += 2)
            if (s % 3 > 0 && s % 5 > 0 && s % 7 > 0) return s < b ? s : 0;
    }
}