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!!

Difficulty: interview

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 ** .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

# generate list of primes
SIEVE_LIMIT = 10**5
sieve = list(range(SIEVE_LIMIT))
sieve[1] = 0
# and store them based on used digits
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


# return the number of items in arr below given limit
def items_below_limit(arr, limit):
    return sum( [x < limit for x in arr] )


# return number of primes with given permutations below limit
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

#Python cookbook
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]