Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- @print the prime numbers that have permutated primes and Remove Duplicate primes Such as 13:31 and 31:13.
- Empty list means no prime permutation is available
- An example is given below where the numbers are under 300:
- =====================================================================================================================================
- {2: [], 3: [], 5: [], 7: [], 11: [], 13: [31], 17: [71], 19: [], 23: [], 29: [], 37: [73], 41: [], 43: [], 47: [], 53: [], 59: [], 61: [], 67: [], 79: [97], 83: [], 89: [], 101: [], 107: [701], 109: [], 113: [131, 311], 127: [271], 137: [317, 173], 139: [193], 149: [419, 941, 491], 151: [], 157: [571, 751], 163: [613, 631], 167: [617, 761], 179: [971, 197, 719], 181: [811], 191: [911], 199: [919, 991], 211: [], 223: [], 227: [], 229: [], 233: [], 239: [293], 241: [421], 251: [521], 257: [], 263: [], 269: [], 277: [727], 281: [821], 283: [823]}
- TASK
- =====================================================================================================================================
- The prime 149 has 3 permutations which are also primes: 419, 491 and 941.
- There are 3 primes below 1000 with three prime permutations:
- 149 ==> 419 ==> 491 ==> 941
- 179 ==> 197 ==> 719 ==> 971
- 379 ==> 397 ==> 739 ==> 937
- But there are 9 primes below 1000 with two prime permutations:
- 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:
- [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:
- 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 '''
- @code
- import math
- import itertools
- def prime(n):
- primes=[]
- for i in range(2,n+1):
- primes.append(i)
- i=2
- while (i<=(math.sqrt(n))):
- if i in primes:
- for j in range(i*2,n+1,i):
- if j in primes:
- primes.remove(j)
- i+=1
- a = [int(k) for k in primes]
- import collections
- numbers = collections.OrderedDict()
- for ele in a:
- x = ''.join(sorted(str(ele)))
- if x not in numbers:
- numbers[x] = []
- numbers[x].append(int(ele))
- a1= [v[0] for v in numbers.values()]
- return a1
- # return
- def permutational_prime(n_max,k_perms):
- a1 = prime(n_max)
- lst1=[]
- for j in a1:
- j = str(j)
- perm_iterator = itertools.permutations(j)
- lst = []
- for item in perm_iterator:
- x = int(''.join(item))
- if x> 1 and x<n_max:
- for j in range(2, int(math.sqrt(x)) + 1):
- if (x% j) == 0:
- break
- else:
- lst.append(x)
- lst1.append(lst)
- dup_lst_sort={i[0]:i[1:] for i in lst1}
- dict = {key: list(set(value)) for key, value in dup_lst_sort.items()}
- l = [] # list for keys
- for key in dict: # for each key
- if len(dict[key]) > 0:
- for item in dict[key]:
- if len(str(key)) != len(str(item)): # if the length of key is different from length of element in the list
- # try:
- # l.index(key) # see if they key is already there
- # except: # if not
- # l.append(key) # add key to list
- dict[key].remove(item)
- for key in dict: # for each key
- if len(dict[key]) > 0:
- for item in dict[key]:
- if len(str(key)) != len(str(item)): # if the length of key is different from length of element in the list
- try:
- l.index(key) # see if they key is already there
- except: # if not
- l.append(key) # add key to list
- for k in l: # for each key in the list
- del dict[k] # delete key
- for k,v in dict.items():
- if k in v:
- v.remove(k)
- final=[]
- for key,value in dict.items():
- if k_perms==len(value):
- final.append(key)
- return [len(final),min(final,default=0),max(final,default=0)]
- #
- # print(dict)
- print(permutational_prime(2000,1))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
