Find all ways to express each of a list of even numbers as the sum of 2 positive, even numbers

Question

This code was a challenge from a friend. Essentially she wanted a way to

"Divide an even number into 2 even numbers."

So I made this quick and dirty Python program to find the solutions up to 1000000. I'd like to know if there's a way to make it faster and improve readability.

from progress.bar import Bar
def checksolve(a,b,c):
    return a==(2*b+2*c)
def checknumber(a):
    results=[]
    for b in range(1,a):
        for c in range(1,a):
            if checksolve(a,b,c) and tuple((a,2*c,2*b)) not in results:
                results.append(tuple((a,2*b,2*c)))
    return results

if __name__=='__main__':
    bar=Bar('computing',max=len(range(0,1000002,2)),suffix='%(percent)d%%')
    for a in range(0,1000002,2):
        solutions=checknumber(a)
        for solution in solutions:
            x,y,z=solution
            with open('caro.txt', 'a+') as f:
                f.write('{}={}+{}\n'.format(x,y,z))
        bar.next()

Answer 1

In terms of readability, one major thing is spacing. PEP-8 recommends 2 blank lines between top level functions (although that's probably unnecessary for something this short), a space on each side of most binary operators including assignment, and a space after commas in places like sequences and function calls.

For more specific things in your code, there are a couple things that could be more clear.

if checksolve(a,b,c) and tuple((a,2*c,2*b)) not in results:
    results.append(tuple((a,2*b,2*c)))

The tuple() is unneeded since using parentheses like in (a,2*b,2*c) is already the form of a tuple literal. Also while keeping your algorithm, we can change the loop to be more efficient. Since we don't care about the order of b and c, it's redundant to check numbers for c that are less than b (they will have already been tested when b was that value previously). This avoids equivalent checksolve calls, and can also simplify the logic since we don't have to check for duplicate solutions.

for b in range(1, a):
    for c in range(b, a): # Start from b
        if checksolve(a, b, c):
            results.append((a, 2*b, 2*c))

For your main code, I like that you're using a with to open the file and a __name__ == '__main__' guard, but I think it would make sense to open it once for writing instead of once for every solution for appending. You might also want to put the logic into a main() function for if you import the module somewhere else.

if __name__ == '__main__':
    bar = Bar('computing', max=len(range(0, 1000002, 2)), suffix='%(percent)d%%')

    with open('caro.txt', 'w') as f: # Will overwrite a current file instead of appending to
        for a in range(0, 1000002, 2):
            solutions = checknumber(a)
            for solution in solutions:
                x, y, z = solution
                f.write(f'{x}={y}+{z}\n') # I'd prefer f-string formatting if on python>=3.6

            bar.next()

All together this ran about 360 times as fast for me when doing up to 100.

However, even though this was an improvement to your algorithm, using a search solution like this at all is unnecessary. It's pretty simple to see that as we increase one term by two, the other should decrease by two. Implementing this is also about 3 times as fast as before, and completely removes the need for a separate function.

if __name__ == '__main__':
    bar = Bar('computing', max=len(range(0, 1000002, 2)), suffix='%(percent)d%%')

    with open('caro.txt', 'w') as f:
        for a in range(0, 1000002, 2):
            for off in range(2, a//2 + 1, 2):
                f.write(f'{a}={off}+{a - off}\n')

        bar.next()

Algorithmically, this will be very fast. However it's still going to be an issue for writing the output to the file. The size of output for all the numbers up to 1,000,000 like in your example would be somewhere around 5TB I believe. So I'd recommend sticking to a smaller size.

Answer 2

You can divide any even number A into 2 (even) and A-2 (even).

Do you want all the solutions instead? There's infinitely many. Negative numbers can also be even. Are we talking about just natural numbers, or maybe all positive integers (including zero)?

Let me assume that indeed we want all solutions in natural numbers (where the input number A is also natural)

You should actually check that the input is even and throw error otherwise.

Then, your solution can indeed be simplified. My first sentence in this answer is the hint.

Just take the input A, subtract 2 and you have a first solution [2, A-2]. Continue subtracting 2 to generate next solutions ([4, A-4], [6, A-6], ...) until you reach zero, in which case you jumped out of bounds of natural numbers and you can end the process. In case of all positive integers that last pair [A, 0] is also a solution but then you end anyway. Actually since addition is commutative, you can actually stop at A/2 (assuming you've actually started at [0, A-0] if zero is allowed), because since then you start getting solutions that you already have, only with its components switched ([2, A-2] -> [A-2, 2], etc...)

EDIT: a bit of complexity analysis

Your solution has two nested for loops of the size A followed by a "not in" check which itself hides a loop. This results in your solution being O(A^3) in time. The solution as i described will yield the results in O(A) time.

Answer 3

Making it faster

Before jumping into coding, it's good to take a moment to consider the time and space complexity of an idea. It seems you had a gut feeling that this could be faster, and that was right. It's good to practice listening to that feeling :-)

To find an idea that's faster, a common technique is to solve the problem by hand for small inputs. Many times a pattern becomes easily visible. Consider for example:

• for target 10 the unique solutions are: 0 + 10, 2 + 8, 4 + 6
• for target 12 the unique solutions are: 0 + 12, 2 + 10, 4 + 8, 6 + 6

The pattern looks quite simple, and we can also see that the solution grows linearly by the target value, which hints at the likely time and space complexity. It also suggests a simple way to compute the pairs in a way that guarantees uniqueness.

Improving readability

I think the most important thing that improves readability is a combination of two things:

• separate key elements of the logic to functions
• use descriptive names for functions and variables

In the posted code:

• checknumber computes a list of results, but I wouldn't be able to guess this by the name alone. This makes it difficult to read the code that calls this function.
• The nameless block of code in if __name__=='__main__' does:
  • Loops over a range of target values to compute solutions
  • Writes solutions to a file
  • Displays a progress bar
• checksolve checks if a solution is valid; this one I can guess by the name, so that's OK

Overall, the separation of concerns is quite fine, I suggest to move the nameless block of code to a function, and to use more descriptive names for the functions, so that readers can get an idea what they do without reading their implementations.

Some of the variable names are also not helpful:

• a is used in multiple places to represent the target number. It could be named target.
• solution is very generic. And destructuring it with x, y, z = solution misses an opportunity give names to its parts. In fact if we tried to give names we might come up with target, left, right = ... and notice that target duplicates what we already know.

Using less memory

checknumber stores in a list a tuple of the target number and the possible pairs. Since the caller only loops over the items once, a generator function would be suitable without other code change, and save storage. The target number is also unnecessary to return.

def find_pairs(target):
    left = 0
    right = target
    while left <= right:
        yield left, right

for target in even_targets:
    for left, right in find_pairs(target):
        # ...

Writing to the same file repeatedly

Since all results are appended to the same file, there's no need to reopen for every target, you could open just once.

Note that since the script appends to the file, if you run the script repeatedly, there will be duplicate content. If you open the file once, you can use the mode 'w' to overwrite the content, that might be less confusing to users.

Use f-strings

Instead of:

f.write('{}={}+{}\n'.format(x,y,z))

f-strings are generally recommended:

f.write(f'{x}={y}+{x}\n')

Answer 4

You have several reviews already. Here I'll emphasize a theme that I did not catch in my probably-too-quick scans of the other reviews.

The solutions for a target follow obvious patterns running across the two numeric sequences: one going from 2 up to roughly half the target; and the other going from the target minus 2 down to roughly half. For example, here are the pairs for the target 14.

(2, 12)
(4, 10)
(6, 8)

Those sequences can be expressed as range objects. To solve, we just zip them together.

def get_solutions(target):
    # Assumes an even target.
    half = target // 2
    xs = range(2, half + 1, 2)
    ys = range(target - 2, half - 1, -2)
    return list(zip(xs, ys))