The prime `149` has 3 permutations which are also primes: `419`, `491` and `941`.

There are 3 primes below `1000` with three prime permutations:
```python
149 ==> 419 ==> 491 ==> 941
179 ==> 197 ==> 719 ==> 971
379 ==> 397 ==> 739 ==> 937
```

But there are 9 primes below `1000` with two prime permutations:
```python
113 ==> 131 ==> 311
137 ==> 173 ==> 317
157 ==> 571 ==> 751
163 ==> 613 ==> 631
167 ==> 617 ==> 761
199 ==> 919 ==> 991
337 ==> 373 ==> 733
359 ==> 593 ==> 953
389 ==> 839 ==> 983
```

Finally, we can find 34 primes below `1000` with only one prime permutation: 
```python
[13, 17, 37, 79, 107, 127, 139, 181, 191, 239, 241, 251, 277, 281, 283, 313, 347, 349, 367, 457, 461, 463, 467, 479, 563, 569, 577, 587, 619, 683, 709, 769, 787, 797]
```

Each set of permuted primes are represented by its smallest value, for example the set `149, 419, 491, 941` is represented by `149`, and the set has 3 permutations.

**Notes**
* the original number (`149` in the above example) is **not** counted as a permutation;
* permutations with leading zeros are **not valid**

## Your Task

Your task is to create a function that takes two arguments:
* an upper limit (`n_max`) and
* the number of prime permutations (`k_perms`) that the primes should generate **below** `n_max`

The function should return the following three values as a list:
* the number of permutational primes below the given limit,
* the smallest prime such prime,
* and the largest such prime

If no eligible primes were found below the limit, the output should be `[0, 0, 0]`

## Examples

Let's see how it would be with the previous cases:
```python
permutational_primes(1000, 3) ==> [3, 149, 379]
''' 3 primes with 3 permutations below 1000, smallest: 149, largest: 379 '''

permutational_primes(1000, 2) ==> [9, 113, 389]
''' 9 primes with 2 permutations below 1000, smallest: 113, largest: 389 '''

permutational_primes(1000, 1) ==> [34, 13, 797]
''' 34 primes with 1 permutation below 1000, smallest: 13, largest: 797 '''
```

Happy coding!!

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Sorting

Combinatorics

Dynamic programming

Mathematics

Data structures

Starter code: def find_prime_kPerm(n, k):
	

Solutions:
def find_prime_kPerm(n, k):
	sieve = n // 2 * [True]
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i // 2]:
			sieve[i * i // 2::i] = ((n - i * i - 1) // (2 * i) + 1) * [False]
	cycles = {}
	for i in range(1, n // 2):
		if sieve[i]:
			cycles.setdefault(tuple(sorted(str(2 * i + 1))), set()).add(2 * i + 1)
	k_perms = [min(cycle) for cycle in cycles.values() if len(cycle) == k + 1]
	return [len(k_perms), min(k_perms, default=0), max(k_perms, default=0)]


from collections import defaultdict
SIEVE_LIMIT = 10 ** 5
sieve = list(range(SIEVE_LIMIT))
sieve[1] = 0
cache = defaultdict(list)
for n in sieve:
	if n:
		digits = tuple(sorted(str(n)))
		cache[digits].append(n)
		for i in range(n * n, SIEVE_LIMIT, n):
			sieve[i] = 0

def items_below_limit(arr, limit):
	return sum([x < limit for x in arr])

def find_prime_kPerm(limit, perms):
	res = []
	for (k, v) in list(cache.items()):
		if items_below_limit(v, limit) == perms + 1:
			res.append(v[0])
	return [len(res), min(res), max(res)] if res else [0, 0, 0]


from itertools import islice, count

def eratosthenes():
	D = {}
	yield 2
	for q in islice(count(3), 0, None, 2):
		p = D.pop(q, None)
		if p is None:
			D[q * q] = q
			yield q
		else:
			x = p + q
			while x in D or not x & 1:
				x += p
			D[x] = p

def find_prime_kPerm(n, kPerm):
	d = {}
	for p in eratosthenes():
		if p > n:
			break
		k = ''.join(sorted((c for c in str(p))))
		d[k] = d.get(k, []) + [p]
	r = [min(v) for v in d.values() if len(v) == kPerm + 1]
	return [len(r), min(r) if r else 0, max(r) if r else 0]


from itertools import permutations as perms

def prime_seive(n):
	nums = range(n)
	for i1 in nums:
		if i1 > 1:
			for i2 in range(i1 * 2, n, i1):
				nums[i2] = 0
	return [i for i in nums if i > 1]

def prime(n):
	if n % 2 == 0 or n < 3:
		return n == 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		if n % i == 0:
			return False
	return True

def prime_perms(p, m):
	ans = []
	for i in perms(str(p)):
		s = ''.join(i)
		num = int(s)
		if num == p:
			continue
		if num < m and prime(num):
			if len(str(num)) != len(s):
				continue
			if num < p:
				ans = []
				break
			if not num in ans:
				ans += [num]
	return ans

def find_prime_kPerm(n, k):
	primes = prime_seive(n)
	ans = []
	for p in primes:
		perm = prime_perms(p, n)
		l = len(perm)
		if l == k:
			ans += [p]
	return [len(ans), ans[0], ans[-1]] if len(ans) > 0 else [0, 0, 0]