https://en.wikipedia.org/wiki/Leonhard_Euler
What: Solution for https://projecteuler.net/problem=49.
Why: I like numbers, primes are interesting, and the RSA problem is fascinating so let's do a prime puzzle!
Note that I took this from the perspective of the question is vague.
That is to say I don't know if they are looking for another series of 4-digit primes with a delta of 3330
or another delta entirely. So let's explore what the data and see what comes of it. As you can see at the end
there is an interesting series of 3 4-digit prime permutations with a common delta (990) but are not in series
with each other!
If you'd like to run the solution, simply copy and paste both Python scripts in the same directory, and run
prime_euler_49.py. Sample output is given at the end of that script.
#!/usr/bin/python3
def prime(num):
""" Title: prime_func.py """
""" """
""" Description: Take a num and see if it's prime """
""" """
""" TBD: use sqrt() to get performance boost """
""" """
""" Note:this is not the fastest but a quick script """
""" My PC's fast enough to do 1000 in a few seconds """
""" """
toosmall = [0,1]
if all(num < 2 for x in toosmall):
quote="TooSmall"
print (quote,num)
return quote
phi=0
num_range=[x for x in range (2,num)]
for x in num_range:
if num%x == 0:
quote="not prime"
break
else:
phi+=1
""" not counting 1 and itself,the number of numbers unevenly dividing """
""" a num should be num - 2 """
if phi == num-2:
quote="prime"
return quote
#!/usr/bin/python3
""" """
""" Title: prime_euler_49.py """
""" Description: Solution for https://projecteuler.net/problem=49 """
""" """
from collections import defaultdict
from prime_func import prime
""" Bounds of the problem is from 1000 to 1000 """
number=1000
endnum=10000
primes_list=[]
""" Figure out if each number is prime """
""" Spoiler: Whittle count to 1061 from 9000 possibilities """
while number < endnum:
isitprime=prime(number)
if isitprime == 'prime':
primes_list.append(number)
number+=1
#Members are simply 4-digit primes : (4799)
""" Create dict (prime_dict) with each prime being a member of a list of values """
""" that is keyed by the numerically sorted numbers shared by the primes. """
""" NOTE: Convert each prime's string to digits, sort,concat back and join them """
""" and store in dict again as we did primes_list above """
""" Spoiler: We now have 336 unique sets """
prime_dict = defaultdict(list)
for each_prime in primes_list:
digits = [int(x) for x in str(each_prime)]
digits.sort()
digits = [str(x) for x in digits]
digits_sorted=str.join('',digits)
prime_dict[digits_sorted].append(each_prime)
#Members look like:
#4799 : [9497, 9479])
#0113 : [1013,1031,1103,1301]
"""
#save for debugging
for key,list in prime_dict.items():
print ("k:",key)
for x in list:
print ("vals:",x)
"""
"""
Get a visual to scroll through and then massage the data. Reading the problem it seems like
the numbers should also share a delta of 3300 but it could be 'some common delta'. Here we
get some candidates to focus on. You should see a pattern emerge like a sore thumb.
Spoiler: Down to 174
"""
for digits,prime_combos in prime_dict.items():
if len(prime_combos) > 2:
#We need only look at sets with 3 values or more
#Make a copy of the list to reduce visual confusion
cp_prime_combos=prime_combos
delta_prime_pairs=[]
#Push dict of the primes abs() delta value mapped to tuple of primes compared
for prime in prime_combos:
for other_prime in cp_prime_combos:
delta_prime_pairs.append({ abs(other_prime-prime):(other_prime,prime)})
#Members look like: 2700 [(6337, 3637)]
# : 2700 [(6373, 3673)]
# : 2700 [(3637, 6337)]
delta_dict = defaultdict(list)
for dicts in delta_prime_pairs:
for delta,prime_tuple in dicts.items():
delta_dict[delta].append(prime_tuple)
#
#Members look like: 2700 [(6337, 3637), (6373, 3673), (3637, 6337), (3673, 6373)]
#
#At this point we can clearly see patterns based on the delta betwen primes
#when printing the deltas and members.
#Pull out the data and unpack
#Having run the numbers I can see the delta is 3330 that solves this puzzle.
for delta,num_pairs in delta_dict.items():
#print (delta,num_pairs)
if delta == 3330:
if len(num_pairs) == 4:
print (delta,num_pairs)
"""
== Answer ==
Found: (2969, 6299,9629) all share a delta of 3330 and are permutations of one another
Interesting: (1123,1321,2131) are three terms that are permutations of each other and if increased by
an equal delta (990) reach a prime that is a permutation of itself, but not one of the others in the set.
1123 -> 2113 || 1321 -> 2311 || 2131 -> 3121
Spoiler: We knew there were 2 sets
== Expected Output ==
john@linux:~/python$ ./prime_euler_49.py
3330 [(6299, 2969), (2969, 6299), (9629, 6299), (6299, 9629)]
3330 [(4817, 1487), (1487, 4817), (8147, 4817), (4817, 8147)]
"""
Comments
Post a Comment