How can I solve this arithmetic puzzle? My solution is too slow after n = 14

Question

Given numbers 1 to 3n, construct n equations of the form a + b = c or a x b = c such that each number is used exactly once. For example:

n=1 => 1+2=3
n=2 => 1+4=5, 2x3=6
n=3 => 4+5=9, 1+7=8, 2x3=6

The question is, does a solution exist for every n?

I tried writing a basic program and it becomes too slow after n = 14. Here are the solutions I have so far:

1 ['1+2=3']
2 ['2*3=6', '1+4=5']
3 ['4+5=9', '1+7=8', '2*3=6']
4 ['3+6=9', '1+10=11', '4+8=12', '2+5=7']
5 ['2+8=10', '3+6=9', '1+13=14', '5+7=12', '11+4=15']
6 ['3*5=15', '2+8=10', '4+14=18', '6+11=17', '7+9=16', '1+12=13']
7 ['6+12=18', '3*5=15', '7+10=17', '1+20=21', '4+9=13', '2+14=16', '8+11=19']
8 ['8+14=22', '6+12=18', '7+10=17', '2+19=21', '1+15=16', '11+13=24', '4+5=9', '3+20=23']
9 ['6+19=25', '8+14=22', '4+13=17', '2+18=20', '1+26=27', '3+7=10', '9+15=24', '5+16=21', '11+12=23']
10 ['6+19=25', '14+15=29', '11+17=28', '4+26=30', '2+18=20', '1+21=22', '3*9=27', '8+16=24', '5+7=12', '10+13=23']
11 ['10+23=33', '6+19=25', '14+15=29', '11+17=28', '4+26=30', '2+18=20', '5+27=32', '1+12=13', '9+22=31', '3*7=21', '16+8=24']
12 ['10+23=33', '3+29=32', '6+19=25', '15+21=36', '11+17=28', '8+14=22', '4+16=20', '7+27=34', '2*12=24', '1+30=31', '5+13=18', '9+26=35']
13 ['10+23=33', '3+29=32', '7+30=37', '6+19=25', '5+34=39', '15+21=36', '11+17=28', '18+20=38', '4+31=35', '1+26=27', '9+13=22', '8+16=24', '2+12=14']
14 ['10+23=33', '4+37=41', '3+29=32', '9+25=34', '15+21=36', '11+17=28', '8+14=22', '6+24=30', '13+27=40', '5*7=35', '2+18=20', '1+38=39', '12+19=31', '16+26=42']

Here's the code for the program:

import sys
from itertools import combinations

def main(n):
    r = set(range(1, n*3+1))
    print(n, solve(n, r, []))

def solve(n, lst, solution):
    if not lst:
        if len(solution) != n:
            return False
        return solution
    for c in combinations(lst, 3):
        valid_solution = valid(c)
        if valid_solution:
            new_solution = solution + [valid_solution]
            result = solve(n, set(lst) - set(c), new_solution)
            if result:
                return result
    return False

def valid(lst):
    a = lst[0]
    b = lst[1]
    c = lst[2]
    if a + b == c:
        return "%s+%s=%s" % (a, b, c)
    if a * b == c:
        return "%s*%s=%s" % (a, b, c)
    return False

if __name__ == "__main__":
   n = int(sys.argv[1])
   main(n)

Answer 1

This looks like a combinatorial problem where its "messiness" suggests no mathematical answer can be formulated. The cheer number of allowed combinations makes it ever more likely that each n has a valid solution, especially given that for small n you already found solutions.

Finding solutions for larger n can be tricky. One approach is called "simulated annealing", where you would take a random set of equations, I try to improve it step by step. "Bad equations" (i.e. equations that have numbers overlapping with others in the set) get removed, and new equations are tried.

Whatever approach is used, it probably can be speed up with heuristics. Such as start creating equations for numbers that show up in the least number of possible equations.

A somewhat related problem is called "graceful labeling", which has no definite answer and for which similar algorithms are appropriate.

Here is an approach using z3py, a library which implements a sat/smt solver.

First, for each number, a list of possible expressions is made. For each possible expression, a symbolic boolean indicates whether the expression will be used in the solution. To have a valid solution, for each number, exactly one of its possible expressions should be True.

from z3 import Int, And, Or, Not, Bool, Sum, Solver, sat

def exactly_one(expr):
    return Or([And([(expr[j] == (i == j))
                    for j in range(len(expr))])
               for i in range(len(expr))])

for N in range(1, 43):
    exp_for_i = [[] for i in range(3 * N + 1)]
    expressions = []
    for i in range(1, 3 * N - 1):
        for j in range(i + 1, 3 * N + 1):
            if i + j <= 3 * N:
                expr = Bool(f'{i}+{j}={i + j}')
                expressions.append(expr)
                exp_for_i[i].append(expr)
                exp_for_i[j].append(expr)
                exp_for_i[i + j].append(expr)
            if i > 1 and i * j <= 3 * N:
                expr = Int(f'{i}*{j}={i * j}')
                expressions.append(expr)
                exp_for_i[i].append(expr)
                exp_for_i[j].append(expr)
                exp_for_i[i * j].append(expr)

    s = Solver()
    s.add([exactly_one(expr) for expr in exp_for_i[1:]])
    if s.check() != sat:
        print(f'No solution for N={N}')
    else:
        m = s.model()
        print(f'N={N}:', [expr for expr in expressions if m.eval(expr) == True])
    s.reset()

N=1: [1+2=3]
N=2: [1+4=5, 2*3=6]
N=3: [1+7=8, 2*3=6, 4+5=9]
N=4: [1+10=11, 2*4=8, 3+6=9, 5+7=12]
N=5: [1+10=11, 2*7=14, 3*4=12, 5+8=13, 6+9=15]
N=6: [1+13=14, 2+7=9, 3*5=15, 4+12=16, 6+11=17, 8+10=18]
N=7: [1+17=18, 2+14=16, 3*5=15, 4+6=10, 7+13=20, 8+11=19, 9+12=21]
N=8: [1+18=19, 2+3=5, 4+17=21, 6+14=20, 7+9=16, 8+15=23, 10+12=22, 11+13=24]
N=9: [1+22=23, 2+19=21, 3+17=20, 4*6=24, 5+7=12, 8+10=18, 9+16=25, 11+15=26, 13+14=27]
N=10: [1+13=14, 2+23=25, 3*8=24, 4+22=26, 5+16=21, 6+9=15, 7+20=27, 10+19=29, 11+17=28, 12+18=30]
N=11: [1+23=24, 2*13=26, 3+25=28, 4+7=11, 5+22=27, 6+9=15, 8+21=29, 10+20=30, 12+19=31, 14+18=32, 16+17=33]
N=12: [1+6=7, 2+9=11, 3+26=29, 4+24=28, 5+25=30, 8+23=31, 10+22=32, 12+21=33, 13+14=27, 15+20=35, 16+18=34, 17+19=36]
N=13: [1+13=14, 2+8=10, 3+26=29, 4+28=32, 5+17=22, 6+25=31, 7+30=37, 9+24=33, 11+27=38, 12+23=35, 15+19=34, 16+20=36, 18+21=39]
N=14: [1+31=32, 2+12=14, 3*9=27, 4+30=34, 5+6=11, 7+28=35, 8+29=37, 10+26=36, 13+25=38, 15+24=39, 16+17=33, 18+23=41, 19+21=40, 20+22=42]
N=15: [1+5=6, 2+12=14, 3*11=33, 4+32=36, 7+31=38, 8+29=37, 9+30=39, 10+25=35, 13+28=41, 15+27=42, 16+18=34, 17+26=43, 19+21=40, 20+24=44, 22+23=45]
N=16: [1+25=26, 2+34=36, 3+11=14, 4+35=39, 5+37=42, 6+32=38, 7+13=20, 8+33=41, 9+10=19, 12+31=43, 15+29=44, 16+24=40, 17+30=47, 18+28=46, 21+27=48, 22+23=45]
N=17: [1+38=39, 2+25=27, 3+37=40, 4+13=17, 5+36=41, 6+9=15, 7+35=42, 8+11=19, 10+34=44, 12+33=45, 14+32=46, 16+31=47, 18+30=48, 20+29=49, 21+22=43, 23+28=51, 24+26=50]
N=18: [1+44=45, 2*25=50, 3+51=54, 4+42=46, 5+14=19, 6+22=28, 7+24=31, 8+33=41, 9+39=48, 10+30=40, 11+27=38, 12+35=47, 13+23=36, 15+37=52, 16+18=34, 17+26=43, 20+29=49, 21+32=53]
N=19: [1+18=19, 2+41=43, 3*14=42, 4+8=12, 5+40=45, 6+10=16, 7+39=46, 9+38=47, 11+37=48, 13+36=49, 15+35=50, 17+34=51, 20+33=53, 21+23=44, 22+32=54, 24+31=55, 25+27=52, 26+30=56, 28+29=57]
N=20: [1+44=45, 2+15=17, 3+43=46, 4+10=14, 5+42=47, 6+18=24, 7+41=48, 8+12=20, 9+40=49, 11+39=50, 13+38=51, 16+37=53, 19+36=55, 21+35=56, 22+30=52, 23+34=57, 25+33=58, 26+28=54, 27+32=59, 29+31=60]
N=21: [1+46=47, 2+17=19, 3+45=48, 4+7=11, 5+44=49, 6+15=21, 8+43=51, 9+13=22, 10+42=52, 12+41=53, 14+40=54, 16+39=55, 18+38=56, 20+37=57, 23+36=59, 24+26=50, 25+35=60, 27+34=61, 28+30=58, 29+33=62, 31+32=63]
N=22: [1+49=50, 2+21=23, 3*17=51, 4+15=19, 5+47=52, 6*8=48, 7+46=53, 9+45=54, 10+14=24, 11+44=55, 12+26=38, 13+43=56, 16+42=58, 18+41=59, 20+40=60, 22+39=61, 25+37=62, 27+36=63, 28+29=57, 30+35=65, 31+33=64, 32+34=66]
N=23: [1+40=41, 2*27=54, 3+13=16, 4+42=46, 5+62=67, 6+55=61, 7+45=52, 8+49=57, 9+59=68, 10+56=66, 11+14=25, 12+48=60, 15+29=44, 17+34=51, 18+35=53, 19+39=58, 20+30=50, 21+22=43, 23+24=47, 26+38=64, 28+37=65, 31+32=63, 33+36=69]
N=24: [1+18=19, 2+53=55, 3+51=54, 4*14=56, 5+52=57, 6+7=13, 8+21=29, 9+16=25, 10+49=59, 11+47=58, 12+48=60, 15+46=61, 17+45=62, 20+44=64, 22+43=65, 23+27=50, 24+42=66, 26+41=67, 28+40=68, 30+39=69, 31+32=63, 33+38=71, 34+36=70, 35+37=72]
N=25: [1+57=58, 2*32=64, 3+60=63, 4+41=45, 5+37=42, 6+69=75, 7+46=53, 8+62=70, 9+13=22, 10+49=59, 11+29=40, 12+61=73, 14+25=39, 15+35=50, 16+52=68, 17+55=72, 18+48=66, 19+24=43, 20+47=67, 21+30=51, 23+33=56, 26+28=54, 27+44=71, 31+34=65, 36+38=74]
N=26: [1+70=71, 2*17=34, 3+26=29, 4+44=48, 5+18=23, 6+57=63, 7+66=73, 8+37=45, 9+51=60, 10+68=78, 11+61=72, 12+52=64, 13+43=56, 14+40=54, 15+50=65, 16+33=49, 19+39=58, 20+55=75, 21+53=74, 22+25=47, 24+38=62, 27+42=69, 28+31=59, 30+46=76, 32+35=67, 36+41=77]
N=27: [1+15=16, 2*30=60, 3+58=61, 4+18=22, 5+57=62, 6+20=26, 7*9=63, 8+56=64, 10+55=65, 11+13=24, 12+54=66, 14+53=67, 17+52=69, 19+51=70, 21+50=71, 23+49=72, 25+48=73, 27+47=74, 28+31=59, 29+46=75, 32+45=77, 33+35=68, 34+44=78, 36+43=79, 37+39=76, 38+42=80, 40+41=81]
N=28: [1+61=62, 2+20=22, 3+68=71, 4+49=53, 5+51=56, 6+35=41, 7+70=77, 8+21=29, 9+57=66, 10+13=23, 11+54=65, 12+64=76, 14+67=81, 15+58=73, 16+34=50, 17+46=63, 18+24=42, 19+60=79, 25+55=80, 26+33=59, 27+48=75, 28+44=72, 30+52=82, 31+47=78, 32+37=69, 36+38=74, 39+45=84, 40+43=83]
N=29: [1+64=65, 2+61=63, 3+26=29, 4+27=31, 5+17=22, 6+74=80, 7+48=55, 8+62=70, 9+11=20, 10+43=53, 12+69=81, 13+54=67, 14+57=71, 15+21=36, 16+52=68, 18+60=78, 19+58=77, 23+56=79, 24+49=73, 25+59=84, 28+44=72, 30+45=75, 32+34=66, 33+50=83, 35+51=86, 37+39=76, 38+47=85, 40+42=82, 41+46=87]
N=30: [1+64=65, 2+28=30, 3*22=66, 4+63=67, 5+15=20, 6+26=32, 7+62=69, 8+9=17, 10+61=71, 11+13=24, 12+60=72, 14+59=73, 16+58=74, 18+70=88, 19+57=76, 21+56=77, 23+55=78, 25+54=79, 27+53=80, 29+52=81, 31+51=82, 33+35=68, 34+50=84, 36+49=85, 37+38=75, 39+48=87, 40+43=83, 41+45=86, 42+47=89, 44+46=90]
N=31: [1+69=70, 2+83=85, 3+20=23, 4+75=79, 5+68=73, 6*7=42, 8+82=90, 9+41=50, 10+43=53, 11+46=57, 12+51=63, 13+39=52, 14+66=80, 15+25=40, 16+76=92, 17+64=81, 18+56=74, 19+59=78, 21+37=58, 22+71=93, 24+48=72, 26+35=61, 27+62=89, 28+60=88, 29+36=65, 30+54=84, 31+55=86, 32+45=77, 33+34=67, 38+49=87, 44+47=91]
N=32: [1+75=76, 2*36=72, 3+74=77, 4+17=21, 5+24=29, 6+67=73, 7+19=26, 8+58=66, 9+53=62, 10+85=95, 11+60=71, 12+68=80, 13+20=33, 14+79=93, 15+39=54, 16+41=57, 18+65=83, 22+48=70, 23+61=84, 25+56=81, 27+63=90, 28+64=92, 30+59=89, 31+47=78, 32+55=87, 34+35=69, 37+49=86, 38+50=88, 40+42=82, 43+51=94, 44+52=96, 45+46=91]
N=33: [1+27=28, 2+73=75, 3+22=25, 4+72=76, 5+11=16, 6+71=77, 7+54=61, 8+70=78, 9+23=32, 10+69=79, 12+18=30, 13+68=81, 14+20=34, 15+67=82, 17+66=83, 19+65=84, 21+64=85, 24+63=87, 26+62=88, 29+60=89, 31+59=90, 33+58=91, 35+57=92, 36+38=74, 37+56=93, 39+41=80, 40+55=95, 42+44=86, 43+53=96, 45+52=97, 46+48=94, 47+51=98, 49+50=99]
N=34: [1+74=75, 2+19=21, 3+73=76, 4+28=32, 5+18=23, 6*13=78, 7+70=77, 8+71=79, 9+72=81, 10+24=34, 11+69=80, 12+26=38, 14+16=30, 15+68=83, 17+67=84, 20+66=86, 22+65=87, 25+64=89, 27+63=90, 29+62=91, 31+61=92, 33+60=93, 35+59=94, 36+49=85, 37+58=95, 39+57=96, 40+42=82, 41+56=97, 43+45=88, 44+55=99, 46+54=100, 47+51=98, 48+53=101, 50+52=102]
N=35: [1+62=63, 2+76=78, 3*25=75, 4*24=96, 5+94=99, 6+59=65, 7+74=81, 8+82=90, 9+38=47, 10+57=67, 11+73=84, 12+31=43, 13+21=34, 14+86=100, 15+49=64, 16+85=101, 17+60=77, 18+80=98, 19+23=42, 20+71=91, 22+50=72, 26+79=105, 27+61=88, 28+41=69, 29+68=97, 30+36=66, 32+55=87, 33+70=103, 35+58=93, 37+46=83, 39+56=95, 40+52=92, 44+45=89, 48+54=102, 51+53=104]
N=36: [1+81=82, 2+24=26, 3+76=79, 4+15=19, 5+78=83, 6+31=37, 7+77=84, 8+35=43, 9+21=30, 10+75=85, 11+17=28, 12+74=86, 13+23=36, 14+73=87, 16+72=88, 18+71=89, 20+70=90, 22+69=91, 25+68=93, 27+67=94, 29+66=95, 32+65=97, 33+63=96, 34+64=98, 38+62=100, 39+41=80, 40+61=101, 42+60=102, 44+59=103, 45+47=92, 46+58=104, 48+57=105, 49+50=99, 51+56=107, 52+54=106, 53+55=108]
N=37: [1+76=77, 2+65=67, 3+37=40, 4+23=27, 5+55=60, 6+103=109, 7+87=94, 8+80=88, 9+66=75, 10+31=41, 11+47=58, 12+84=96, 13+59=72, 14+91=105, 15+93=108, 16+79=95, 17+73=90, 18+30=48, 19+78=97, 20+62=82, 21+71=92, 22+89=111, 24+61=85, 25+39=64, 26+42=68, 28+35=63, 29+81=110, 32+74=106, 33+69=102, 34+70=104, 36+50=86, 38+45=83, 43+57=100, 44+54=98, 46+53=99, 49+52=101, 51+56=107]
N=38: [1+83=84, 2+32=34, 3*9=27, 4+82=86, 5+15=20, 6+81=87, 7+23=30, 8+80=88, 10+79=89, 11+25=36, 12+78=90, 13+16=29, 14+77=91, 17+76=93, 18+22=40, 19+75=94, 21+74=95, 24+73=97, 26+72=98, 28+71=99, 31+70=101, 33+69=102, 35+68=103, 37+67=104, 38+58=96, 39+66=105, 41+65=106, 42+43=85, 44+64=108, 45+47=92, 46+63=109, 48+62=110, 49+51=100, 50+61=111, 52+60=112, 53+54=107, 55+59=114, 56+57=113]
N=39: [1+86=87, 2*19=38, 3+85=88, 4*10=40, 5+84=89, 6+30=36, 7+83=90, 8+34=42, 9+82=91, 11+81=92, 12+14=26, 13+80=93, 15+17=32, 16+79=95, 18+78=96, 20+77=97, 21+23=44, 22+76=98, 24+75=99, 25+28=53, 27+74=101, 29+73=102, 31+72=103, 33+71=104, 35+70=105, 37+69=106, 39+68=107, 41+67=108, 43+66=109, 45+65=110, 46+48=94, 47+64=111, 49+51=100, 50+63=113, 52+62=114, 54+61=115, 55+57=112, 56+60=116, 58+59=117]
N=40: [1+96=97, 2+85=87, 3+60=63, 4+69=73, 5+104=109, 6+76=82, 7+71=78, 8+53=61, 9+58=67, 10+98=108, 11+106=117, 12+14=26, 13+28=41, 15+90=105, 16+86=102, 17+33=50, 18+81=99, 19+29=48, 20+42=62, 21+59=80, 22+91=113, 23+77=100, 24+94=118, 25+95=120, 27+74=101, 30+49=79, 31+83=114, 32+84=116, 34+54=88, 35+40=75, 36+56=92, 37+52=89, 38+65=103, 39+72=111, 43+64=107, 44+66=110, 45+70=115, 46+47=93, 51+68=119, 55+57=112]
N=41: [1+110=111, 2+13=15, 3+51=54, 4+77=81, 5+84=89, 6+97=103, 7+99=106, 8+85=93, 9+11=20, 10+34=44, 12+75=87, 14+43=57, 16+79=95, 17+88=105, 18+98=116, 19+90=109, 21+96=117, 22+64=86, 23+37=60, 24+70=94, 25+42=67, 26+39=65, 27+74=101, 28+55=83, 29+78=107, 30+92=122, 31+35=66, 32+59=91, 33+82=115, 36+72=108, 38+76=114, 40+80=120, 41+63=104, 45+68=113, 46+56=102, 47+53=100, 48+73=121, 49+69=118, 50+62=112, 52+71=123, 58+61=119]
N=42: [1+88=89, 2+94=96, 3*42=126, 4+47=51, 5+109=114, 6+69=75, 7+52=59, 8+33=41, 9+108=117, 10+60=70, 11+84=95, 12+111=123, 13+48=61, 14+85=99, 15+43=58, 16+81=97, 17+38=55, 18+80=98, 19+34=53, 20+105=125, 21+103=124, 22+68=90, 23+87=110, 24+83=107, 25+67=92, 26+56=82, 27+91=118, 28+78=106, 29+86=115, 30+71=101, 31+73=104, 32+40=72, 35+65=100, 36+66=102, 37+79=116, 39+54=93, 44+77=121, 45+74=119, 46+76=122, 49+64=113, 50+62=112, 57+63=120]
N=43: [1+79=80, 2+109=111, 3*14=42, 4+50=54, 5+112=117, 6+89=95, 7+90=97, 8+21=29, 9+74=83, 10+88=98, 11+32=43, 12+114=126, 13+110=123, 15+103=118, 16+68=84, 17+35=52, 18+59=77, 19+86=105, 20+82=102, 22+34=56, 23+58=81, 24+101=125, 25+60=85, 26+96=122, 27+100=127, 28+93=121, 30+61=91, 31+63=94, 33+66=99, 36+70=106, 37+76=113, 38+49=87, 39+65=104, 40+67=107, 41+78=119, 44+48=92, 45+71=116, 46+62=108, 47+73=120, 51+64=115, 53+75=128, 55+69=124, 57+72=129]
N=44: [1+28=29, 2+83=85, 3+86=89, 4+117=121, 5+96=101, 6+42=48, 7+70=77, 8+118=126, 9+30=39, 10+100=110, 11+120=131, 12+80=92, 13+82=95, 14+19=33, 15+51=66, 16+90=106, 17+99=116, 18+53=71, 20+107=127, 21+36=57, 22+81=103, 23+109=132, 24+91=115, 25+54=79, 26+97=123, 27+67=94, 31+88=119, 32+72=104, 34+78=112, 35+63=98, 37+74=111, 38+84=122, 40+47=87, 41+73=114, 43+50=93, 44+58=102, 45+60=105, 46+62=108, 49+76=125, 52+61=113, 55+75=130, 56+68=124, 59+69=128, 64+65=129]
N=45: [1+41=42, 2+98=100, 3+92=95, 4+97=101, 5+48=53, 6+122=128, 7+107=114, 8+62=70, 9+102=111, 10+108=118, 11+73=84, 12+21=33, 13+78=91, 14+112=126, 15+65=80, 16+45=61, 17+49=66, 18+29=47, 19+74=93, 20+55=75, 22+68=90, 23+56=79, 24+105=129, 25+110=135, 26+99=125, 27+86=113, 28+39=67, 30+85=115, 31+96=127, 32+89=121, 34+72=106, 35+88=123, 36+94=130, 37+87=124, 38+82=120, 40+69=109, 43+76=119, 44+59=103, 46+58=104, 50+83=133, 51+81=132, 52+64=116, 54+77=131, 57+60=117, 63+71=134]
N=46: [1+100=101, 2+128=130, 3*34=102, 4+121=125, 5+24=29, 6+30=36, 7+40=47, 8+58=66, 9+32=41, 10+124=134, 11+67=78, 12+115=127, 13+83=96, 14+91=105, 15+57=72, 16+73=89, 17+87=104, 18+81=99, 19+60=79, 20+97=117, 21+95=116, 22+62=84, 23+53=76, 25+93=118, 26+103=129, 27+108=135, 28+85=113, 31+88=119, 33+90=123, 35+71=106, 37+74=111, 38+69=107, 39+98=137, 42+80=122, 43+51=94, 44+92=136, 45+75=120, 46+68=114, 48+64=112, 49+82=131, 50+59=109, 52+86=138, 54+56=110, 55+77=132, 61+65=126, 63+70=133]
N=47: [1+102=103, 2+41=43, 3+45=48, 4*26=104, 5+32=37, 6+101=107, 7*15=105, 8+100=108, 9+24=33, 10+99=109, 11+35=46, 12+98=110, 13+17=30, 14+97=111, 16+96=112, 18+95=113, 19+20=39, 21+94=115, 22+28=50, 23+93=116, 25+92=117, 27+91=118, 29+90=119, 31+89=120, 34+88=122, 36+87=123, 38+86=124, 40+85=125, 42+84=126, 44+83=127, 47+82=129, 49+81=130, 51+80=131, 52+54=106, 53+79=132, 55+78=133, 56+58=114, 57+77=134, 59+76=135, 60+61=121, 62+75=137, 63+65=128, 64+74=138, 66+73=139, 67+69=136, 68+72=140, 70+71=141]
N=48: [1+126=127, 2*26=52, 3+105=108, 4+103=107, 5+101=106, 6+31=37, 7+102=109, 8+33=41, 9+39=48, 10+100=110, 11+35=46, 12+99=111, 13+16=29, 14+28=42, 15+98=113, 17+97=114, 18+22=40, 19+96=115, 20+24=44, 21+95=116, 23+94=117, 25+93=118, 27+92=119, 30+91=121, 32+90=122, 34+89=123, 36+88=124, 38+87=125, 43+86=129, 45+85=130, 47+84=131, 49+83=132, 50+54=104, 51+82=133, 53+81=134, 55+57=112, 56+80=136, 58+79=137, 59+61=120, 60+78=138, 62+77=139, 63+65=128, 64+76=140, 66+75=141, 67+68=135, 69+74=143, 70+72=142, 71+73=144]
N=49: [1+136=137, 2+34=36, 3+135=138, 4+126=130, 5+61=66, 6+32=38, 7+81=88, 8+109=117, 9+105=114, 10+58=68, 11+120=131, 12+80=92, 13+42=55, 14+97=111, 15+71=86, 16+102=118, 17+46=63, 18+101=119, 19+122=141, 20+112=132, 21+48=69, 22+94=116, 23+29=52, 24+91=115, 25+75=100, 26+98=124, 27+106=133, 28+79=107, 30+99=129, 31+96=127, 33+70=103, 35+37=72, 39+89=128, 40+73=113, 41+82=123, 43+65=108, 44+60=104, 45+95=140, 47+74=121, 49+76=125, 50+84=134, 51+59=110, 53+93=146, 54+90=144, 56+87=143, 57+85=142, 62+77=139, 64+83=147, 67+78=145]
N=50: [1+7=8, 2+40=42, 3*37=111, 4+109=113, 5+39=44, 6+108=114, 9+106=115, 10+35=45, 11+105=116, 12+15=27, 13+104=117, 14+33=47, 16+103=119, 17+95=112, 18+102=120, 19+32=51, 20+29=49, 21+101=122, 22+99=121, 23+100=123, 24+107=131, 25+30=55, 26+98=124, 28+97=125, 31+96=127, 34+94=128, 36+93=129, 38+92=130, 41+91=132, 43+90=133, 46+89=135, 48+88=136, 50+87=137, 52+86=138, 53+57=110, 54+85=139, 56+84=140, 58+60=118, 59+83=142, 61+82=143, 62+64=126, 63+81=144, 65+80=145, 66+68=134, 67+79=146, 69+78=147, 70+71=141, 72+77=149, 73+75=148, 74+76=150]
N=51: [1+51=52, 2+111=113, 3+38=41, 4+45=49, 5+110=115, 6*19=114, 7+109=116, 8*14=112, 9+108=117, 10+24=34, 11+32=43, 12+107=119, 13+26=39, 15+105=120, 16+31=47, 17+104=121, 18+36=54, 20+103=123, 21+101=122, 22+102=124, 23+106=129, 25+100=125, 27+29=56, 28+99=127, 30+98=128, 33+97=130, 35+96=131, 37+95=132, 40+94=134, 42+93=135, 44+92=136, 46+91=137, 48+90=138, 50+89=139, 53+88=141, 55+87=142, 57+86=143, 58+60=118, 59+85=144, 61+84=145, 62+64=126, 63+83=146, 65+82=147, 66+67=133, 68+81=149, 69+71=140, 70+80=150, 72+79=151, 73+75=148, 74+78=152, 76+77=153]
N=52: [1+115=116, 2+17=19, 3+114=117, 4+50=54, 5+113=118, 6+37=43, 7+38=45, 8+111=119, 9+112=121, 10+13=23, 11+109=120, 12+110=122, 14+33=47, 15+108=123, 16+32=48, 18+107=125, 20+106=126, 21+35=56, 22+105=127, 24+104=128, 25+27=52, 26+103=129, 28+102=130, 29+31=60, 30+101=131, 34+99=133, 36+98=134, 39+97=136, 40+95=135, 41+96=137, 42+58=100, 44+94=138, 46+93=139, 49+92=141, 51+91=142, 53+90=143, 55+89=144, 57+88=145, 59+87=146, 61+63=124, 62+86=148, 64+85=149, 65+67=132, 66+84=150, 68+83=151, 69+71=140, 70+82=152, 72+81=153, 73+74=147, 75+80=155, 76+78=154, 77+79=156]
N=53: [1+114=115, 2+30=32, 3+113=116, 4+38=42, 5+51=56, 6+43=49, 7*17=119, 8+112=120, 9*13=117, 10+111=121, 11+34=45, 12+110=122, 14+109=123, 15+25=40, 16+108=124, 18+107=125, 19+36=55, 20+27=47, 21+106=127, 22+129=151, 23+105=128, 24+29=53, 26+104=130, 28+103=131, 31+102=133, 33+101=134, 35+100=135, 37+99=136, 39+98=137, 41+97=138, 44+96=140, 46+95=141, 48+94=142, 50+93=143, 52+92=144, 54+91=145, 57+90=147, 58+60=118, 59+89=148, 61+88=149, 62+64=126, 63+87=150, 65+67=132, 66+86=152, 68+85=153, 69+70=139, 71+84=155, 72+74=146, 73+83=156, 75+82=157, 76+78=154, 77+81=158, 79+80=159]
N=54: [1+22=23, 2+57=59, 3*42=126, 4+91=95, 5+136=141, 6+52=58, 7+37=44, 8+104=112, 9+153=162, 10+46=56, 11+113=124, 12+115=127, 13+84=97, 14+118=132, 15+119=134, 16+133=149, 17+63=80, 18+96=114, 19+139=158, 20+31=51, 21+62=83, 24+74=98, 25+121=146, 26+116=142, 27+120=147, 28+81=109, 29+99=128, 30+105=135, 32+129=161, 33+107=140, 34+88=122, 35+108=143, 36+87=123, 38+100=138, 39+72=111, 40+53=93, 41+69=110, 43+102=145, 45+92=137, 47+70=117, 48+103=151, 49+101=150, 50+106=156, 54+90=144, 55+76=131, 60+65=125, 61+94=155, 64+66=130, 67+85=152, 68+89=157, 71+77=148, 73+86=159, 75+79=154, 78+82=160]
N=55: [1+31=32, 2*76=152, 3+138=141, 4+62=66, 5*21=105, 6+159=165, 7+58=65, 8+117=125, 9+144=153, 10+147=157, 11+73=84, 12+83=95, 13+118=131, 14+55=69, 15+124=139, 16+146=162, 17+61=78, 18+103=121, 19+70=89, 20+116=136, 22+107=129, 23+92=115, 24+110=134, 25+112=137, 26+94=120, 27+122=149, 28+130=158, 29+111=140, 30+96=126, 33+75=108, 34+127=161, 35+74=109, 36+114=150, 37+91=128, 38+41=79, 39+54=93, 40+102=142, 42+106=148, 43+80=123, 44+46=90, 45+88=133, 47+98=145, 48+49=97, 50+104=154, 51+100=151, 52+67=119, 53+60=113, 56+99=155, 57+86=143, 59+101=160, 63+72=135, 64+68=132, 71+85=156, 77+87=164, 81+82=163]
N=56: [1+53=54, 2+122=124, 3*41=123, 4+121=125, 5+51=56, 6*21=126, 7+120=127, 8+28=36, 9+119=128, 10+39=49, 11+118=129, 12+26=38, 13+45=58, 14+117=131, 15+19=34, 16+116=132, 17+43=60, 18+115=133, 20+114=134, 22+113=135, 23+24=47, 25+112=137, 27+111=138, 29+110=139, 30+32=62, 31+109=140, 33+108=141, 35+107=142, 37+106=143, 40+105=145, 42+104=146, 44+103=147, 46+102=148, 48+101=149, 50+100=150, 52+99=151, 55+98=153, 57+97=154, 59+96=155, 61+95=156, 63+94=157, 64+66=130, 65+93=158, 67+69=136, 68+92=160, 70+91=161, 71+73=144, 72+90=162, 74+89=163, 75+77=152, 76+88=164, 78+87=165, 79+80=159, 81+86=167, 82+84=166, 83+85=168]
N=57: [1+36=37, 2+149=151, 3+56=59, 4+166=170, 5+80=85, 6+135=141, 7+114=121, 8+90=98, 9+128=137, 10+113=123, 11+143=154, 12+148=160, 13+47=60, 14+52=66, 15+150=165, 16+100=116, 17+34=51, 18+146=164, 19+140=159, 20+53=73, 21+115=136, 22+110=132, 23+102=125, 24+88=112, 25+78=103, 26+79=105, 27+74=101, 28+134=162, 29+129=158, 30+89=119, 31+107=138, 32+139=171, 33+75=108, 35+109=144, 38+104=142, 39+57=96, 40+117=157, 41+106=147, 42+76=118, 43+87=130, 44+83=127, 45+124=169, 46+99=145, 48+63=111, 49+84=133, 50+70=120, 54+77=131, 55+67=122, 58+94=152, 61+65=126, 62+91=153, 64+92=156, 68+93=161, 69+86=155, 71+97=168, 72+95=167, 81+82=163]
N=58: [1+127=128, 2+16=18, 3+126=129, 4+50=54, 5*26=130, 6+125=131, 7+52=59, 8+124=132, 9+33=42, 10+123=133, 11+35=46, 12+122=134, 13+31=44, 14+121=135, 15+48=63, 17+120=137, 19+119=138, 20+37=57, 21+118=139, 22+39=61, 23+117=140, 24+41=65, 25+116=141, 27+29=56, 28+115=143, 30+114=144, 32+113=145, 34+112=146, 36+111=147, 38+110=148, 40+109=149, 43+108=151, 45+107=152, 47+106=153, 49+105=154, 51+104=155, 53+103=156, 55+102=157, 58+101=159, 60+100=160, 62+99=161, 64+98=162, 66+97=163, 67+69=136, 68+96=164, 70+72=142, 71+95=166, 73+94=167, 74+76=150, 75+93=168, 77+92=169, 78+80=158, 79+91=170, 81+90=171, 82+83=165, 84+89=173, 85+87=172, 86+88=174]
N=59: [1+129=130, 2+47=49, 3+128=131, 4+54=58, 5+40=45, 6*22=132, 7+127=134, 8+20=28, 9*15=135, 10+126=136, 11+41=52, 12+125=137, 13+38=51, 14+124=138, 16+123=139, 17+43=60, 18+122=140, 19+72=91, 21+121=142, 23+120=143, 24+32=56, 25+119=144, 26+36=62, 27+118=145, 29+117=146, 30+34=64, 31+116=147, 33+115=148, 35+114=149, 37+113=150, 39+112=151, 42+111=153, 44+110=154, 46+109=155, 48+108=156, 50+107=157, 53+106=159, 55+105=160, 57+104=161, 59+103=162, 61+102=163, 63+101=164, 65+100=165, 66+67=133, 68+73=141, 69+99=168, 70+97=167, 71+98=169, 74+96=170, 75+77=152, 76+95=171, 78+80=158, 79+94=173, 81+93=174, 82+84=166, 83+92=175, 85+87=172, 86+90=176, 88+89=177]
N=60: [1+125=126, 2*71=142, 3+148=151, 4+74=78, 5+168=173, 6+91=97, 7*20=140, 8+81=89, 9+158=167, 10+47=57, 11+128=139, 12+164=176, 13+124=137, 14+18=32, 15+75=90, 16+66=82, 17+45=62, 19+93=112, 21+38=59, 22+100=122, 23+130=153, 24+121=145, 25+102=127, 26+88=114, 27+143=170, 28+95=123, 29+109=138, 30+136=166, 31+70=101, 33+129=162, 34+118=152, 35+106=141, 36+98=134, 37+132=169, 39+41=80, 40+77=117, 42+104=146, 43+135=178, 44+133=177, 46+108=154, 48+113=161, 49+61=110, 50+99=149, 51+120=171, 52+79=131, 53+119=172, 54+111=165, 55+92=147, 56+103=159, 58+86=144, 60+115=175, 63+94=157, 64+116=180, 65+85=150, 67+96=163, 68+87=155, 69+105=174, 72+107=179, 73+83=156, 76+84=160]