Python Forum
Square reverse sum(overloaded)
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Square reverse sum(overloaded)
#1
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?
Reply
#2
(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).
Reply
#3
(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))
Reply
#4
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.
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#5
Whats your execution time? This only took 3.2 seconds for my machine to compute is that too slow?
Reply
#6
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.
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#7
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.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Finding square roots using long division. jahuja73 10 5,304 Feb-24-2021, 01:25 PM
Last Post: jahuja73
  Magic square! frequency 1 2,507 Dec-17-2018, 06:35 PM
Last Post: micseydel
  Perfect Square program forumer444 4 8,884 Sep-01-2017, 09:32 PM
Last Post: forumer444
  Magic Square Puzzle Harnick 1 4,843 Aug-09-2017, 04:51 PM
Last Post: nilamo
  Square Root on calculator MP1234593 1 7,863 Jun-06-2017, 06:58 PM
Last Post: nilamo
  List of square roots python py7 6 6,301 Apr-08-2017, 11:26 PM
Last Post: ichabod801
  Square root of a number mbestivert 1 4,005 Nov-24-2016, 04:35 PM
Last Post: casevh

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020