# Python Program for OEIS A076449, A072857, A076730, A134596
# Michael S. Branicky, Jun 05 2021

# A076449   Least number whose digits can be used to form exactly n different primes (not necessarily using all digits).
data = [1, 2, 25, 13, 37, 107, 127, 113, 167, 1027, 179, 137, 1036, 1127, 1013, 1137, 1235, 1136, 1123, 1037, 1139, 1079, 10124, 10126, 1349, 1279, 1237, 3479, 10699, 1367, 10179, 1379, 10127, 10079, 10138, 10123, 10234, 10235, 10247, 10339, 10267]

# A072857   Primeval numbers: numbers that set a record for the number of distinct primes that can be obtained by permuting some subset of their digits.
rdata = [1, 2, 13, 37, 107, 113, 137, 1013, 1037, 1079, 1237, 1367, 1379, 10079, 10123, 10136, 10139, 10237, 10279, 10367, 10379, 12379, 13679, 100279, 100379, 101237, 102347, 102379, 103679, 123479, 1001237, 1002347, 1002379, 1003679, 1012349, 1012379, 1023457, 1023467, 1023479, 1234579, 1234679, 10012349]

# A076730   Maximum number of (distinct) primes that an n-digit number may shelter (i.e., primes contained among all digital substrings' permutations).
mdata = [1, 4, 11, 31, 106, 402, 1953, 10542, 64905, 362451, 2970505]

# A134596   The largest n-digit primeval number A072857.
amdata = [2, 37, 137, 1379, 13679, 123479, 1234679, 12345679, 102345679, 1123456789, 10123456789]

from time import time
time0 = time()

from sympy import isprime
from itertools import permutations, combinations_with_replacement as mc
def afind_bfile(limit):
    digits = 0
    adict = dict()
    n = 0
    records = []
    lastrecord = -1
    mrecords = []
    amrecords = []
    while n < limit:
        digits += 1
        for first in "123456789":
            validrest = "0" + "".join(str(d) for d in range(int(first), 10)) 
            for rest in mc(validrest, digits-1):
                s = "".join((first, )+rest)
                if n > len(s) and set(s) & set("1379") == set(): continue
                k = int(s)
                t = set(int("".join(p)) for l in range(1, len(s)+1) for p in permutations(s, l))
                c = len(list(filter(isprime, t)))
                if c not in adict: adict[c] = k
                if c == n:
                    print(n, k, time()-time0)
                    with open('b076449.txt', 'a') as f:
                        f.write(f"{n} {k}\n")
                    n += 1
                if c > lastrecord:
                    records.append(k)
                    print(f"    NEW RECORD: A072875({len(records)}) = {k}")
                    with open('b072857.txt', 'a') as f:
                        f.write(f"{len(records)} {k}\n")
                    print("        A072857 found:", records)
                    print("        A072857  data:", rdata)
                    lastrecord = c    
                while n in adict:
                    print(n, adict[n], time()-time0, len(adict))
                    with open('b076449.txt', 'a') as f:
                        f.write(f"{n} {adict[n]}\n")
                    n += 1
        print("\n    DONE THROUGH", digits, "DIGITS", time()-time0, len(adict), len(records))
        amrecords.append(records[-1])
        mrecords.append(min(k for k, v in adict.items() if v == records[-1]))
        print("        A076730 found:", mrecords)
        print("        A076730  data:", mdata)
        print("        A134596 found:", amrecords)
        print("        A134596  data:", amdata)
        print()
afind_bfile(10000) # ~~~~