There are several ways to write the number 1/2 as a sum of inverse squares using distinct integers.
In fact, only using integers between 2 and 45 inclusive, there are exactly three ways to do it: {2,3,4,6,7,9,10,20,28,35,36,45} and {2,3,4,6,7,9,12,15,28,30,35,36,45} and {2,3,4,5,7,12,15,20,28,35}
How many ways are there to write the number 1/2 as a sum of inverse squares using distinct integers between 2 and 80 inclusive?
That's my homework, guys.
Basically, algorithm is quite easy to find out, but the problem is python seems to be overloaded. I tried multiprocessing method but still get stuck. Could you guys help me with this?
(Aug-17-2018, 03:01 AM)shihomiyano Wrote: [ -> ]I tried multiprocessing method but still get stuck.
What's your best try? If you show us, we can help you figure it out from there. But posts like this sometimes get mistaken for "do it for me" posts, so it's important that you show us your attempt(s).
(Aug-17-2018, 05:34 AM)micseydel Wrote: [ -> ] (Aug-17-2018, 03:01 AM)shihomiyano Wrote: [ -> ]I tried multiprocessing method but still get stuck.
What's your best try? If you show us, we can help you figure it out from there. But posts like this sometimes get mistaken for "do it for me" posts, so it's important that you show us your attempt(s).
ok,I figure out that working with 80 is quite big, so I've tried working with 45. My consideration is not about code or algorithm it's about execution time of the program.
import itertools
import multiprocessing
import time
start=time.time()
inital_list=[]
final_list=[]
for i in range(1,46):
inital_list.append(i)
map_list=list(itertools.combinations(inital_list,6))
map_list1 = map_list[:(len(map_list)//2)]
map_list2 = map_list[(len(map_list)//2):]
def first():
for item in map_list1:
sum=0
for num in item:
sum+=(1/(num*num))
if sum == 1/2:
final_list.append(item)
else:
pass
def second():
for item in map_list2:
sum=0
for num in item:
sum+=(1/(num*num))
if sum == 1/2:
final_list.append(item)
else:
pass
if __name__ == '__main__':
p1 = multiprocessing.Process(target=first)
p2 = multiprocessing.Process(target=second)
p1.start()
p2.start()
p1.join()
p2.join()
end=time.time()
print(final_list)
print('execution time: {}'.format(end-start))
What about a tree search? Start with 2 (1/4). Then for all numbers greater than 2, add the inverse square. If any of those numbers are >= 1/2, stop searching them. Otherwise, repeat adding inverse squares of greater numbers.
For example, the sum of inverse squares for [2, 3, 4, 5, 6, 7] is 0.5117. But your method would search every combination starting with those numbers, even though they are guaranteed to fail.
Whats your execution time? This only took 3.2 seconds for my machine to compute is that too slow?
The code he posted is test code. It only tests six item combinations of numbers up to 45. He needs to test all combinations of numbers up to 80.
This is also a Project Euler question -
https://projecteuler.net/problem=152
I haven't solved that particular one, but typically you solve the problem with big-O optimization. Parallelization probably isn't the right way to approach the problem.