# Python program for OEIS A110456 # Michael S Branicky, Sep 07 2024 # A110456 Largest prime obtained by concatenation of parts of a distinct partition of n. 0 if no such number exist. 0 data = [0, 2, 3, 31, 41, 0, 421, 521, 0, 4231, 5231, 0, 7321, 8231, 0, 64231, 74231, 0, 94321, 431021, 0, 754123, 854213, 0, 5431021, 6421013, 0, 8431021, 9431021, 0, 65412103, 75411023, 0, 95421103, 96412103, 0, 643110211, 765324101, 0, 965421013, 975431021, 0, 7542103111, 8543121011] from itertools import permutations from gmpy2 import digits, is_prime, mpz def dparts(n, high=0): # distinct partitions of n with terms > high if n > high: yield (n,) for i in range(high+1, n): yield from ((i,)+p for p in dparts(n-i, i)) def a(n): if n == 1 or (n > 3 and n%3 == 0): return 0 m, argm = 0, "" for dp in dparts(n): sdp = list(map(digits, dp)) s = "".join(sdp) if len(s) < len(argm): continue for p in permutations(sdp): sp = "".join(p) if len(sp) == len(argm) and sp < argm: continue t = mpz(sp) if is_prime(t): m, argm = t, sp return int(m) print([a(n) for n in range(1, 45)]) print(data) assert data == [a(n) for n in range(1, 1+len(data))] from time import time time0 = time() alst = [] for n in range(1, 101): an = a(n) alst.append(an) print(n, an, time()-time0) with open("b110456.txt", "a") as bfile: bfile.write(f"{n} {an}\n")