# Python program for OEIS A166921 # Michael S. Branicky, 2021-02-14 # A166921 Least prime with exactly n prime anagrams not equal to itself. 1 data = [2, 13, 113, 149, 1013, 1039, 1427, 1123, 1439, 1579, 1237, 10271, 10453, 10139, 10253, 10243, 10457, 11579, 10789, 10273, 11239, 12457, 10729, 13249, 12347, 13687, 12539, 14759, 13799, 10739, 12637, 12893, 23957, 13597, 100493, 12379, 14593, 101383, 13789] # Produced terms through n=1476 in ~1 hour when run on Google Colab (w/50GB RAM) from sympy import isprime from sympy.utilities.iterables import multiset_permutations from itertools import permutations from functools import lru_cache @lru_cache(maxsize=None) def myisprime(n): return isprime(n) def anagrams(n): s = str(n) return set(int("".join(p)) for p in multiset_permutations(s) if p[0] != '0') def num_prime_anagrams(n): return sum(isprime(i) for i in anagrams(n)) # unit tests print(anagrams(13), num_prime_anagrams(13)) print(anagrams(103), num_prime_anagrams(103)) print() from time import time time0 = time() VERBOSE = False # prints out-of-order terms if True tested = set() adict = {0: 2} k = 3 n = 1 for n in range(10001): if n in adict: print(n, adict[n], time()-time0, "*"*40) with open('b166921.txt', 'a') as f: f.write(f"{n} {adict[n]}\n") continue while True: if isprime(k): key = "".join(sorted(str(k))) if key in tested: k += 2; continue else: tested.add(key) nk = num_prime_anagrams(k) if nk-1 not in adict: adict[nk-1] = k if VERBOSE: print(nk-1, k, time()-time0, "found out of order") if nk == n+1: print(n, k, time()-time0, "*"*40) with open('b166921.txt', 'a') as f: f.write(f"{n} {adict[n]}\n") break k += 2