make_quadratic problem: failed to produce a correct result.

[DevelopDaily]

https://github.com/dwavesystems/dimod/blob/434f75d0fc958a6bc3e2658ec9bc758346a39f00/dimod/higherorder/utils.py#L102

That function does not lead to a correct sample set. Here is a simple test case (factoring).

I want to factor 15 to 3 and 5 and I know 6 variables are enough. But, I want to test the make_quadraticwith more variables, so I use 16 variables.

a = 128*q7 + 64*q6 + 32*q5 + 16*q4 + 8*q3 + 4*q2 + 2*q1 + q0
b = 128*q15 + 64*q14 + 32*q13 + 16*q12 + 8*q11 + 4*q10 + 2*q9 + q8

Expand P = (15 - a*b)**2, and you will get the polynomial shown below.

Then, do this:

strength = 10; # or whatever your recommend
bqm = make_quadratic(poly , strength, dimod.BINARY)

I tried the real QPU with DWaveSamplerof various solvers on that binary quadratic model. The results are always wrong. Could you please help address the issue? Thanks.

poly = {   
    (): 225,
    (0, 1, 8): 4,
    (0, 1, 8, 9): 16,
    (0, 1, 9): 16,
    (0, 1, 10): 64,
    (0, 1, 10, 8): 32,
    (0, 1, 10, 9): 64,
    (0, 1, 10, 11): 256,
    (0, 1, 10, 12): 512,
    (0, 1, 10, 13): 1024,
    (0, 1, 10, 14): 2048,
    (0, 1, 10, 15): 4096,
    (0, 1, 11): 256,
    (0, 1, 11, 8): 64,
    (0, 1, 11, 9): 128,
    (0, 1, 11, 12): 1024,
    (0, 1, 11, 13): 2048,
    (0, 1, 11, 14): 4096,
    (0, 1, 11, 15): 8192,
    (0, 1, 12): 1024,
    (0, 1, 12, 8): 128,
    (0, 1, 12, 9): 256,
    (0, 1, 12, 13): 4096,
    (0, 1, 12, 14): 8192,
    (0, 1, 12, 15): 16384,
    (0, 1, 13): 4096,
    (0, 1, 13, 8): 256,
    (0, 1, 13, 9): 512,
    (0, 1, 13, 14): 16384,
    (0, 1, 13, 15): 32768,
    (0, 1, 14): 16384,
    (0, 1, 14, 8): 512,
    (0, 1, 14, 9): 1024,
    (0, 1, 14, 15): 65536,
    (0, 1, 15): 65536,
    (0, 1, 15, 8): 1024,
    (0, 1, 15, 9): 2048,
    (0, 2, 8): 8,
    (0, 2, 8, 9): 32,
    (0, 2, 9): 32,
    (0, 2, 10): 128,
    (0, 2, 11): 512,
    (0, 2, 12): 2048,
    (0, 2, 13): 8192,
    (0, 2, 14): 32768,
    (0, 2, 15): 131072,
    (0, 3, 8): 16,
    (0, 3, 8, 9): 64,
    (0, 3, 9): 64,
    (0, 3, 10): 256,
    (0, 3, 11): 1024,
    (0, 3, 12): 4096,
    (0, 3, 13): 16384,
    (0, 3, 14): 65536,
    (0, 3, 15): 262144,
    (0, 4, 8): 32,
    (0, 4, 8, 9): 128,
    (0, 4, 9): 128,
    (0, 4, 10): 512,
    (0, 4, 11): 2048,
    (0, 4, 12): 8192,
    (0, 4, 13): 32768,
    (0, 4, 14): 131072,
    (0, 4, 15): 524288,
    (0, 5, 8): 64,
    (0, 5, 8, 9): 256,
    (0, 5, 9): 256,
    (0, 5, 10): 1024,
    (0, 5, 11): 4096,
    (0, 5, 12): 16384,
    (0, 5, 13): 65536,
    (0, 5, 14): 262144,
    (0, 5, 15): 1048576,
    (0, 6, 8): 128,
    (0, 6, 8, 9): 512,
    (0, 6, 9): 512,
    (0, 6, 10): 2048,
    (0, 6, 11): 8192,
    (0, 6, 12): 32768,
    (0, 6, 13): 131072,
    (0, 6, 14): 524288,
    (0, 6, 15): 2097152,
    (0, 7, 8): 256,
    (0, 7, 8, 9): 1024,
    (0, 7, 9): 1024,
    (0, 7, 10): 4096,
    (0, 7, 11): 16384,
    (0, 7, 12): 65536,
    (0, 7, 13): 262144,
    (0, 7, 14): 1048576,
    (0, 7, 15): 4194304,
    (0, 8): -29,
    (0, 9): -56,
    (0, 10): -104,
    (0, 10, 2, 8): 64,
    (0, 10, 2, 9): 128,
    (0, 10, 3, 8): 128,
    (0, 10, 3, 9): 256,
    (0, 10, 4, 8): 256,
    (0, 10, 4, 9): 512,
    (0, 10, 5, 8): 512,
    (0, 10, 5, 9): 1024,
    (0, 10, 6, 8): 1024,
    (0, 10, 6, 9): 2048,
    (0, 10, 7, 8): 2048,
    (0, 10, 7, 9): 4096,
    (0, 10, 11, 2): 512,
    (0, 10, 11, 3): 1024,
    (0, 10, 11, 4): 2048,
    (0, 10, 11, 5): 4096,
    (0, 10, 11, 6): 8192,
    (0, 10, 11, 7): 16384,
    (0, 10, 12, 2): 1024,
    (0, 10, 12, 3): 2048,
    (0, 10, 12, 4): 4096,
    (0, 10, 12, 5): 8192,
    (0, 10, 12, 6): 16384,
    (0, 10, 12, 7): 32768,
    (0, 10, 13, 2): 2048,
    (0, 10, 13, 3): 4096,
    (0, 10, 13, 4): 8192,
    (0, 10, 13, 5): 16384,
    (0, 10, 13, 6): 32768,
    (0, 10, 13, 7): 65536,
    (0, 10, 14, 2): 4096,
    (0, 10, 14, 3): 8192,
    (0, 10, 14, 4): 16384,
    (0, 10, 14, 5): 32768,
    (0, 10, 14, 6): 65536,
    (0, 10, 14, 7): 131072,
    (0, 10, 15, 2): 8192,
    (0, 10, 15, 3): 16384,
    (0, 10, 15, 4): 32768,
    (0, 10, 15, 5): 65536,
    (0, 10, 15, 6): 131072,
    (0, 10, 15, 7): 262144,
    (0, 11): -176,
    (0, 11, 2, 8): 128,
    (0, 11, 2, 9): 256,
    (0, 11, 3, 8): 256,
    (0, 11, 3, 9): 512,
    (0, 11, 4, 8): 512,
    (0, 11, 4, 9): 1024,
    (0, 11, 5, 8): 1024,
    (0, 11, 5, 9): 2048,
    (0, 11, 6, 8): 2048,
    (0, 11, 6, 9): 4096,
    (0, 11, 7, 8): 4096,
    (0, 11, 7, 9): 8192,
    (0, 11, 12, 2): 2048,
    (0, 11, 12, 3): 4096,
    (0, 11, 12, 4): 8192,
    (0, 11, 12, 5): 16384,
    (0, 11, 12, 6): 32768,
    (0, 11, 12, 7): 65536,
    (0, 11, 13, 2): 4096,
    (0, 11, 13, 3): 8192,
    (0, 11, 13, 4): 16384,
    (0, 11, 13, 5): 32768,
    (0, 11, 13, 6): 65536,
    (0, 11, 13, 7): 131072,
    (0, 11, 14, 2): 8192,
    (0, 11, 14, 3): 16384,
    (0, 11, 14, 4): 32768,
    (0, 11, 14, 5): 65536,
    (0, 11, 14, 6): 131072,
    (0, 11, 14, 7): 262144,
    (0, 11, 15, 2): 16384,
    (0, 11, 15, 3): 32768,
    (0, 11, 15, 4): 65536,
    (0, 11, 15, 5): 131072,
    (0, 11, 15, 6): 262144,
    (0, 11, 15, 7): 524288,
    (0, 12): -224,
    (0, 12, 2, 8): 256,
    (0, 12, 2, 9): 512,
    (0, 12, 3, 8): 512,
    (0, 12, 3, 9): 1024,
    (0, 12, 4, 8): 1024,
    (0, 12, 4, 9): 2048,
    (0, 12, 5, 8): 2048,
    (0, 12, 5, 9): 4096,
    (0, 12, 6, 8): 4096,
    (0, 12, 6, 9): 8192,
    (0, 12, 7, 8): 8192,
    (0, 12, 7, 9): 16384,
    (0, 12, 13, 2): 8192,
    (0, 12, 13, 3): 16384,
    (0, 12, 13, 4): 32768,
    (0, 12, 13, 5): 65536,
    (0, 12, 13, 6): 131072,
    (0, 12, 13, 7): 262144,
    (0, 12, 14, 2): 16384,
    (0, 12, 14, 3): 32768,
    (0, 12, 14, 4): 65536,
    (0, 12, 14, 5): 131072,
    (0, 12, 14, 6): 262144,
    (0, 12, 14, 7): 524288,
    (0, 12, 15, 2): 32768,
    (0, 12, 15, 3): 65536,
    (0, 12, 15, 4): 131072,
    (0, 12, 15, 5): 262144,
    (0, 12, 15, 6): 524288,
    (0, 12, 15, 7): 1048576,
    (0, 13): 64,
    (0, 13, 2, 8): 512,
    (0, 13, 2, 9): 1024,
    (0, 13, 3, 8): 1024,
    (0, 13, 3, 9): 2048,
    (0, 13, 4, 8): 2048,
    (0, 13, 4, 9): 4096,
    (0, 13, 5, 8): 4096,
    (0, 13, 5, 9): 8192,
    (0, 13, 6, 8): 8192,
    (0, 13, 6, 9): 16384,
    (0, 13, 7, 8): 16384,
    (0, 13, 7, 9): 32768,
    (0, 13, 14, 2): 32768,
    (0, 13, 14, 3): 65536,
    (0, 13, 14, 4): 131072,
    (0, 13, 14, 5): 262144,
    (0, 13, 14, 6): 524288,
    (0, 13, 14, 7): 1048576,
    (0, 13, 15, 2): 65536,
    (0, 13, 15, 3): 131072,
    (0, 13, 15, 4): 262144,
    (0, 13, 15, 5): 524288,
    (0, 13, 15, 6): 1048576,
    (0, 13, 15, 7): 2097152,
    (0, 14): 2176,
    (0, 14, 2, 8): 1024,
    (0, 14, 2, 9): 2048,
    (0, 14, 3, 8): 2048,
    (0, 14, 3, 9): 4096,
    (0, 14, 4, 8): 4096,
    (0, 14, 4, 9): 8192,
    (0, 14, 5, 8): 8192,
    (0, 14, 5, 9): 16384,
    (0, 14, 6, 8): 16384,
    (0, 14, 6, 9): 32768,
    (0, 14, 7, 8): 32768,
    (0, 14, 7, 9): 65536,
    (0, 14, 15, 2): 131072,
    (0, 14, 15, 3): 262144,
    (0, 14, 15, 4): 524288,
    (0, 14, 15, 5): 1048576,
    (0, 14, 15, 6): 2097152,
    (0, 14, 15, 7): 4194304,
    (0, 15): 12544,
    (0, 15, 2, 8): 2048,
    (0, 15, 2, 9): 4096,
    (0, 15, 3, 8): 4096,
    (0, 15, 3, 9): 8192,
    (0, 15, 4, 8): 8192,
    (0, 15, 4, 9): 16384,
    (0, 15, 5, 8): 16384,
    (0, 15, 5, 9): 32768,
    (0, 15, 6, 8): 32768,
    (0, 15, 6, 9): 65536,
    (0, 15, 7, 8): 65536,
    (0, 15, 7, 9): 131072,
    (1, 2, 8): 16,
    (1, 2, 8, 9): 64,
    (1, 2, 9): 64,
    (1, 2, 10): 256,
    (1, 2, 11): 1024,
    (1, 2, 12): 4096,
    (1, 2, 13): 16384,
    (1, 2, 14): 65536,
    (1, 2, 15): 262144,
    (1, 3, 8): 32,
    (1, 3, 8, 9): 128,
    (1, 3, 9): 128,
    (1, 3, 10): 512,
    (1, 3, 11): 2048,
    (1, 3, 12): 8192,
    (1, 3, 13): 32768,
    (1, 3, 14): 131072,
    (1, 3, 15): 524288,
    (1, 4, 8): 64,
    (1, 4, 8, 9): 256,
    (1, 4, 9): 256,
    (1, 4, 10): 1024,
    (1, 4, 11): 4096,
    (1, 4, 12): 16384,
    (1, 4, 13): 65536,
    (1, 4, 14): 262144,
    (1, 4, 15): 1048576,
    (1, 5, 8): 128,
    (1, 5, 8, 9): 512,
    (1, 5, 9): 512,
    (1, 5, 10): 2048,
    (1, 5, 11): 8192,
    (1, 5, 12): 32768,
    (1, 5, 13): 131072,
    (1, 5, 14): 524288,
    (1, 5, 15): 2097152,
    (1, 6, 8): 256,
    (1, 6, 8, 9): 1024,
    (1, 6, 9): 1024,
    (1, 6, 10): 4096,
    (1, 6, 11): 16384,
    (1, 6, 12): 65536,
    (1, 6, 13): 262144,
    (1, 6, 14): 1048576,
    (1, 6, 15): 4194304,
    (1, 7, 8): 512,
    (1, 7, 8, 9): 2048,
    (1, 7, 9): 2048,
    (1, 7, 10): 8192,
    (1, 7, 11): 32768,
    (1, 7, 12): 131072,
    (1, 7, 13): 524288,
    (1, 7, 14): 2097152,
    (1, 7, 15): 8388608,
    (1, 8): -56,
    (1, 9): -104,
    (1, 10): -176,
    (1, 10, 2, 8): 128,
    (1, 10, 2, 9): 256,
    (1, 10, 3, 8): 256,
    (1, 10, 3, 9): 512,
    (1, 10, 4, 8): 512,
    (1, 10, 4, 9): 1024,
    (1, 10, 5, 8): 1024,
    (1, 10, 5, 9): 2048,
    (1, 10, 6, 8): 2048,
    (1, 10, 6, 9): 4096,
    (1, 10, 7, 8): 4096,
    (1, 10, 7, 9): 8192,
    (1, 10, 11, 2): 1024,
    (1, 10, 11, 3): 2048,
    (1, 10, 11, 4): 4096,
    (1, 10, 11, 5): 8192,
    (1, 10, 11, 6): 16384,
    (1, 10, 11, 7): 32768,
    (1, 10, 12, 2): 2048,
    (1, 10, 12, 3): 4096,
    (1, 10, 12, 4): 8192,
    (1, 10, 12, 5): 16384,
    (1, 10, 12, 6): 32768,
    (1, 10, 12, 7): 65536,
    (1, 10, 13, 2): 4096,
    (1, 10, 13, 3): 8192,
    (1, 10, 13, 4): 16384,
    (1, 10, 13, 5): 32768,
    (1, 10, 13, 6): 65536,
    (1, 10, 13, 7): 131072,
    (1, 10, 14, 2): 8192,
    (1, 10, 14, 3): 16384,
    (1, 10, 14, 4): 32768,
    (1, 10, 14, 5): 65536,
    (1, 10, 14, 6): 131072,
    (1, 10, 14, 7): 262144,
    (1, 10, 15, 2): 16384,
    (1, 10, 15, 3): 32768,
    (1, 10, 15, 4): 65536,
    (1, 10, 15, 5): 131072,
    (1, 10, 15, 6): 262144,
    (1, 10, 15, 7): 524288,
    (1, 11): -224,
    (1, 11, 2, 8): 256,
    (1, 11, 2, 9): 512,
    (1, 11, 3, 8): 512,
    (1, 11, 3, 9): 1024,
    (1, 11, 4, 8): 1024,
    (1, 11, 4, 9): 2048,
    (1, 11, 5, 8): 2048,
    (1, 11, 5, 9): 4096,
    (1, 11, 6, 8): 4096,
    (1, 11, 6, 9): 8192,
    (1, 11, 7, 8): 8192,
    (1, 11, 7, 9): 16384,
    (1, 11, 12, 2): 4096,
    (1, 11, 12, 3): 8192,
    (1, 11, 12, 4): 16384,
    (1, 11, 12, 5): 32768,
    (1, 11, 12, 6): 65536,
    (1, 11, 12, 7): 131072,
    (1, 11, 13, 2): 8192,
    (1, 11, 13, 3): 16384,
    (1, 11, 13, 4): 32768,
    (1, 11, 13, 5): 65536,
    (1, 11, 13, 6): 131072,
    (1, 11, 13, 7): 262144,
    (1, 11, 14, 2): 16384,
    (1, 11, 14, 3): 32768,
    (1, 11, 14, 4): 65536,
    (1, 11, 14, 5): 131072,
    (1, 11, 14, 6): 262144,
    (1, 11, 14, 7): 524288,
    (1, 11, 15, 2): 32768,
    (1, 11, 15, 3): 65536,
    (1, 11, 15, 4): 131072,
    (1, 11, 15, 5): 262144,
    (1, 11, 15, 6): 524288,
    (1, 11, 15, 7): 1048576,
    (1, 12): 64,
    (1, 12, 2, 8): 512,
    (1, 12, 2, 9): 1024,
    (1, 12, 3, 8): 1024,
    (1, 12, 3, 9): 2048,
    (1, 12, 4, 8): 2048,
    (1, 12, 4, 9): 4096,
    (1, 12, 5, 8): 4096,
    (1, 12, 5, 9): 8192,
    (1, 12, 6, 8): 8192,
    (1, 12, 6, 9): 16384,
    (1, 12, 7, 8): 16384,
    (1, 12, 7, 9): 32768,
    (1, 12, 13, 2): 16384,
    (1, 12, 13, 3): 32768,
    (1, 12, 13, 4): 65536,
    (1, 12, 13, 5): 131072,
    (1, 12, 13, 6): 262144,
    (1, 12, 13, 7): 524288,
    (1, 12, 14, 2): 32768,
    (1, 12, 14, 3): 65536,
    (1, 12, 14, 4): 131072,
    (1, 12, 14, 5): 262144,
    (1, 12, 14, 6): 524288,
    (1, 12, 14, 7): 1048576,
    (1, 12, 15, 2): 65536,
    (1, 12, 15, 3): 131072,
    (1, 12, 15, 4): 262144,
    (1, 12, 15, 5): 524288,
    (1, 12, 15, 6): 1048576,
    (1, 12, 15, 7): 2097152,
    (1, 13): 2176,
    (1, 13, 2, 8): 1024,
    (1, 13, 2, 9): 2048,
    (1, 13, 3, 8): 2048,
    (1, 13, 3, 9): 4096,
    (1, 13, 4, 8): 4096,
    (1, 13, 4, 9): 8192,
    (1, 13, 5, 8): 8192,
    (1, 13, 5, 9): 16384,
    (1, 13, 6, 8): 16384,
    (1, 13, 6, 9): 32768,
    (1, 13, 7, 8): 32768,
    (1, 13, 7, 9): 65536,
    (1, 13, 14, 2): 65536,
    (1, 13, 14, 3): 131072,
    (1, 13, 14, 4): 262144,
    (1, 13, 14, 5): 524288,
    (1, 13, 14, 6): 1048576,
    (1, 13, 14, 7): 2097152,
    (1, 13, 15, 2): 131072,
    (1, 13, 15, 3): 262144,
    (1, 13, 15, 4): 524288,
    (1, 13, 15, 5): 1048576,
    (1, 13, 15, 6): 2097152,
    (1, 13, 15, 7): 4194304,
    (1, 14): 12544,
    (1, 14, 2, 8): 2048,
    (1, 14, 2, 9): 4096,
    (1, 14, 3, 8): 4096,
    (1, 14, 3, 9): 8192,
    (1, 14, 4, 8): 8192,
    (1, 14, 4, 9): 16384,
    (1, 14, 5, 8): 16384,
    (1, 14, 5, 9): 32768,
    (1, 14, 6, 8): 32768,
    (1, 14, 6, 9): 65536,
    (1, 14, 7, 8): 65536,
    (1, 14, 7, 9): 131072,
    (1, 14, 15, 2): 262144,
    (1, 14, 15, 3): 524288,
    (1, 14, 15, 4): 1048576,
    (1, 14, 15, 5): 2097152,
    (1, 14, 15, 6): 4194304,
    (1, 14, 15, 7): 8388608,
    (1, 15): 57856,
    (1, 15, 2, 8): 4096,
    (1, 15, 2, 9): 8192,
    (1, 15, 3, 8): 8192,
    (1, 15, 3, 9): 16384,
    (1, 15, 4, 8): 16384,
    (1, 15, 4, 9): 32768,
    (1, 15, 5, 8): 32768,
    (1, 15, 5, 9): 65536,
    (1, 15, 6, 8): 65536,
    (1, 15, 6, 9): 131072,
    (1, 15, 7, 8): 131072,
    (1, 15, 7, 9): 262144,
    (2, 3, 8): 64,
    (2, 3, 8, 9): 256,
    (2, 3, 9): 256,
    (2, 3, 10): 1024,
    (2, 3, 11): 4096,
    (2, 3, 12): 16384,
    (2, 3, 13): 65536,
    (2, 3, 14): 262144,
    (2, 3, 15): 1048576,
    (2, 4, 8): 128,
    (2, 4, 8, 9): 512,
    (2, 4, 9): 512,
    (2, 4, 10): 2048,
    (2, 4, 11): 8192,
    (2, 4, 12): 32768,
    (2, 4, 13): 131072,
    (2, 4, 14): 524288,
    (2, 4, 15): 2097152,
    (2, 5, 8): 256,
    (2, 5, 8, 9): 1024,
    (2, 5, 9): 1024,
    (2, 5, 10): 4096,
    (2, 5, 11): 16384,
    (2, 5, 12): 65536,
    (2, 5, 13): 262144,
    (2, 5, 14): 1048576,
    (2, 5, 15): 4194304,
    (2, 6, 8): 512,
    (2, 6, 8, 9): 2048,
    (2, 6, 9): 2048,
    (2, 6, 10): 8192,
    (2, 6, 11): 32768,
    (2, 6, 12): 131072,
    (2, 6, 13): 524288,
    (2, 6, 14): 2097152,
    (2, 6, 15): 8388608,
    (2, 7, 8): 1024,
    (2, 7, 8, 9): 4096,
    (2, 7, 9): 4096,
    (2, 7, 10): 16384,
    (2, 7, 11): 65536,
    (2, 7, 12): 262144,
    (2, 7, 13): 1048576,
    (2, 7, 14): 4194304,
    (2, 7, 15): 16777216,
    (2, 8): -104,
    (2, 9): -176,
    (3, 4, 8): 256,
    (3, 4, 8, 9): 1024,
    (3, 4, 9): 1024,
    (3, 4, 10): 4096,
    (3, 4, 11): 16384,
    (3, 4, 12): 65536,
    (3, 4, 13): 262144,
    (3, 4, 14): 1048576,
    (3, 4, 15): 4194304,
    (3, 5, 8): 512,
    (3, 5, 8, 9): 2048,
    (3, 5, 9): 2048,
    (3, 5, 10): 8192,
    (3, 5, 11): 32768,
    (3, 5, 12): 131072,
    (3, 5, 13): 524288,
    (3, 5, 14): 2097152,
    (3, 5, 15): 8388608,
    (3, 6, 8): 1024,
    (3, 6, 8, 9): 4096,
    (3, 6, 9): 4096,
    (3, 6, 10): 16384,
    (3, 6, 11): 65536,
    (3, 6, 12): 262144,
    (3, 6, 13): 1048576,
    (3, 6, 14): 4194304,
    (3, 6, 15): 16777216,
    (3, 7, 8): 2048,
    (3, 7, 8, 9): 8192,
    (3, 7, 9): 8192,
    (3, 7, 10): 32768,
    (3, 7, 11): 131072,
    (3, 7, 12): 524288,
    (3, 7, 13): 2097152,
    (3, 7, 14): 8388608,
    (3, 7, 15): 33554432,
    (3, 8): -176,
    (3, 9): -224,
    (4, 5, 8): 1024,
    (4, 5, 8, 9): 4096,
    (4, 5, 9): 4096,
    (4, 5, 10): 16384,
    (4, 5, 11): 65536,
    (4, 5, 12): 262144,
    (4, 5, 13): 1048576,
    (4, 5, 14): 4194304,
    (4, 5, 15): 16777216,
    (4, 6, 8): 2048,
    (4, 6, 8, 9): 8192,
    (4, 6, 9): 8192,
    (4, 6, 10): 32768,
    (4, 6, 11): 131072,
    (4, 6, 12): 524288,
    (4, 6, 13): 2097152,
    (4, 6, 14): 8388608,
    (4, 6, 15): 33554432,
    (4, 7, 8): 4096,
    (4, 7, 8, 9): 16384,
    (4, 7, 9): 16384,
    (4, 7, 10): 65536,
    (4, 7, 11): 262144,
    (4, 7, 12): 1048576,
    (4, 7, 13): 4194304,
    (4, 7, 14): 16777216,
    (4, 7, 15): 67108864,
    (4, 8): -224,
    (4, 9): 64,
    (5, 6, 8): 4096,
    (5, 6, 8, 9): 16384,
    (5, 6, 9): 16384,
    (5, 6, 10): 65536,
    (5, 6, 11): 262144,
    (5, 6, 12): 1048576,
    (5, 6, 13): 4194304,
    (5, 6, 14): 16777216,
    (5, 6, 15): 67108864,
    (5, 7, 8): 8192,
    (5, 7, 8, 9): 32768,
    (5, 7, 9): 32768,
    (5, 7, 10): 131072,
    (5, 7, 11): 524288,
    (5, 7, 12): 2097152,
    (5, 7, 13): 8388608,
    (5, 7, 14): 33554432,
    (5, 7, 15): 134217728,
    (5, 8): 64,
    (5, 9): 2176,
    (6, 7, 8): 16384,
    (6, 7, 8, 9): 65536,
    (6, 7, 9): 65536,
    (6, 7, 10): 262144,
    (6, 7, 11): 1048576,
    (6, 7, 12): 4194304,
    (6, 7, 13): 16777216,
    (6, 7, 14): 67108864,
    (6, 7, 15): 268435456,
    (6, 8): 2176,
    (6, 9): 12544,
    (7, 8): 12544,
    (7, 9): 57856,
    (8, 9, 0): 4,
    (8, 9, 1): 16,
    (8, 9, 2): 64,
    (8, 9, 3): 256,
    (8, 9, 4): 1024,
    (8, 9, 5): 4096,
    (8, 9, 6): 16384,
    (8, 9, 7): 65536,
    (10, 2): -224,
    (10, 2, 3, 8): 512,
    (10, 2, 3, 9): 1024,
    (10, 2, 4, 8): 1024,
    (10, 2, 4, 9): 2048,
    (10, 2, 5, 8): 2048,
    (10, 2, 5, 9): 4096,
    (10, 2, 6, 8): 4096,
    (10, 2, 6, 9): 8192,
    (10, 2, 7, 8): 8192,
    (10, 2, 7, 9): 16384,
    (10, 3): 64,
    (10, 3, 4, 8): 2048,
    (10, 3, 4, 9): 4096,
    (10, 3, 5, 8): 4096,
    (10, 3, 5, 9): 8192,
    (10, 3, 6, 8): 8192,
    (10, 3, 6, 9): 16384,
    (10, 3, 7, 8): 16384,
    (10, 3, 7, 9): 32768,
    (10, 4): 2176,
    (10, 4, 5, 8): 8192,
    (10, 4, 5, 9): 16384,
    (10, 4, 6, 8): 16384,
    (10, 4, 6, 9): 32768,
    (10, 4, 7, 8): 32768,
    (10, 4, 7, 9): 65536,
    (10, 5): 12544,
    (10, 5, 6, 8): 32768,
    (10, 5, 6, 9): 65536,
    (10, 5, 7, 8): 65536,
    (10, 5, 7, 9): 131072,
    (10, 6): 57856,
    (10, 6, 7, 8): 131072,
    (10, 6, 7, 9): 262144,
    (10, 7): 246784,
    (10, 8, 0): 8,
    (10, 8, 1): 32,
    (10, 8, 2): 128,
    (10, 8, 3): 512,
    (10, 8, 4): 2048,
    (10, 8, 5): 8192,
    (10, 8, 6): 32768,
    (10, 8, 7): 131072,
    (10, 9, 0): 16,
    (10, 9, 1): 64,
    (10, 9, 2): 256,
    (10, 9, 3): 1024,
    (10, 9, 4): 4096,
    (10, 9, 5): 16384,
    (10, 9, 6): 65536,
    (10, 9, 7): 262144,
    (10, 11, 0): 64,
    (10, 11, 1): 256,
    (10, 11, 2): 1024,
    (10, 11, 2, 3): 4096,
    (10, 11, 2, 4): 8192,
    (10, 11, 2, 5): 16384,
    (10, 11, 2, 6): 32768,
    (10, 11, 2, 7): 65536,
    (10, 11, 3): 4096,
    (10, 11, 3, 4): 16384,
    (10, 11, 3, 5): 32768,
    (10, 11, 3, 6): 65536,
    (10, 11, 3, 7): 131072,
    (10, 11, 4): 16384,
    (10, 11, 4, 5): 65536,
    (10, 11, 4, 6): 131072,
    (10, 11, 4, 7): 262144,
    (10, 11, 5): 65536,
    (10, 11, 5, 6): 262144,
    (10, 11, 5, 7): 524288,
    (10, 11, 6): 262144,
    (10, 11, 6, 7): 1048576,
    (10, 11, 7): 1048576,
    (10, 12, 0): 128,
    (10, 12, 1): 512,
    (10, 12, 2): 2048,
    (10, 12, 2, 3): 8192,
    (10, 12, 2, 4): 16384,
    (10, 12, 2, 5): 32768,
    (10, 12, 2, 6): 65536,
    (10, 12, 2, 7): 131072,
    (10, 12, 3): 8192,
    (10, 12, 3, 4): 32768,
    (10, 12, 3, 5): 65536,
    (10, 12, 3, 6): 131072,
    (10, 12, 3, 7): 262144,
    (10, 12, 4): 32768,
    (10, 12, 4, 5): 131072,
    (10, 12, 4, 6): 262144,
    (10, 12, 4, 7): 524288,
    (10, 12, 5): 131072,
    (10, 12, 5, 6): 524288,
    (10, 12, 5, 7): 1048576,
    (10, 12, 6): 524288,
    (10, 12, 6, 7): 2097152,
    (10, 12, 7): 2097152,
    (10, 13, 0): 256,
    (10, 13, 1): 1024,
    (10, 13, 2): 4096,
    (10, 13, 2, 3): 16384,
    (10, 13, 2, 4): 32768,
    (10, 13, 2, 5): 65536,
    (10, 13, 2, 6): 131072,
    (10, 13, 2, 7): 262144,
    (10, 13, 3): 16384,
    (10, 13, 3, 4): 65536,
    (10, 13, 3, 5): 131072,
    (10, 13, 3, 6): 262144,
    (10, 13, 3, 7): 524288,
    (10, 13, 4): 65536,
    (10, 13, 4, 5): 262144,
    (10, 13, 4, 6): 524288,
    (10, 13, 4, 7): 1048576,
    (10, 13, 5): 262144,
    (10, 13, 5, 6): 1048576,
    (10, 13, 5, 7): 2097152,
    (10, 13, 6): 1048576,
    (10, 13, 6, 7): 4194304,
    (10, 13, 7): 4194304,
    (10, 14, 0): 512,
    (10, 14, 1): 2048,
    (10, 14, 2): 8192,
    (10, 14, 2, 3): 32768,
    (10, 14, 2, 4): 65536,
    (10, 14, 2, 5): 131072,
    (10, 14, 2, 6): 262144,
    (10, 14, 2, 7): 524288,
    (10, 14, 3): 32768,
    (10, 14, 3, 4): 131072,
    (10, 14, 3, 5): 262144,
    (10, 14, 3, 6): 524288,
    (10, 14, 3, 7): 1048576,
    (10, 14, 4): 131072,
    (10, 14, 4, 5): 524288,
    (10, 14, 4, 6): 1048576,
    (10, 14, 4, 7): 2097152,
    (10, 14, 5): 524288,
    (10, 14, 5, 6): 2097152,
    (10, 14, 5, 7): 4194304,
    (10, 14, 6): 2097152,
    (10, 14, 6, 7): 8388608,
    (10, 14, 7): 8388608,
    (10, 15, 0): 1024,
    (10, 15, 1): 4096,
    (10, 15, 2): 16384,
    (10, 15, 2, 3): 65536,
    (10, 15, 2, 4): 131072,
    (10, 15, 2, 5): 262144,
    (10, 15, 2, 6): 524288,
    (10, 15, 2, 7): 1048576,
    (10, 15, 3): 65536,
    (10, 15, 3, 4): 262144,
    (10, 15, 3, 5): 524288,
    (10, 15, 3, 6): 1048576,
    (10, 15, 3, 7): 2097152,
    (10, 15, 4): 262144,
    (10, 15, 4, 5): 1048576,
    (10, 15, 4, 6): 2097152,
    (10, 15, 4, 7): 4194304,
    (10, 15, 5): 1048576,
    (10, 15, 5, 6): 4194304,
    (10, 15, 5, 7): 8388608,
    (10, 15, 6): 4194304,
    (10, 15, 6, 7): 16777216,
    (10, 15, 7): 16777216,
    (11, 2): 64,
    (11, 2, 3, 8): 1024,
    (11, 2, 3, 9): 2048,
    (11, 2, 4, 8): 2048,
    (11, 2, 4, 9): 4096,
    (11, 2, 5, 8): 4096,
    (11, 2, 5, 9): 8192,
    (11, 2, 6, 8): 8192,
    (11, 2, 6, 9): 16384,
    (11, 2, 7, 8): 16384,
    (11, 2, 7, 9): 32768,
    (11, 3): 2176,
    (11, 3, 4, 8): 4096,
    (11, 3, 4, 9): 8192,
    (11, 3, 5, 8): 8192,
    (11, 3, 5, 9): 16384,
    (11, 3, 6, 8): 16384,
    (11, 3, 6, 9): 32768,
    (11, 3, 7, 8): 32768,
    (11, 3, 7, 9): 65536,
    (11, 4): 12544,
    (11, 4, 5, 8): 16384,
    (11, 4, 5, 9): 32768,
    (11, 4, 6, 8): 32768,
    (11, 4, 6, 9): 65536,
    (11, 4, 7, 8): 65536,
    (11, 4, 7, 9): 131072,
    (11, 5): 57856,
    (11, 5, 6, 8): 65536,
    (11, 5, 6, 9): 131072,
    (11, 5, 7, 8): 131072,
    (11, 5, 7, 9): 262144,
    (11, 6): 246784,
    (11, 6, 7, 8): 262144,
    (11, 6, 7, 9): 524288,
    (11, 7): 1017856,
    (11, 8, 0): 16,
    (11, 8, 1): 64,
    (11, 8, 2): 256,
    (11, 8, 3): 1024,
    (11, 8, 4): 4096,
    (11, 8, 5): 16384,
    (11, 8, 6): 65536,
    (11, 8, 7): 262144,
    (11, 9, 0): 32,
    (11, 9, 1): 128,
    (11, 9, 2): 512,
    (11, 9, 3): 2048,
    (11, 9, 4): 8192,
    (11, 9, 5): 32768,
    (11, 9, 6): 131072,
    (11, 9, 7): 524288,
    (11, 12, 0): 256,
    (11, 12, 1): 1024,
    (11, 12, 2): 4096,
    (11, 12, 2, 3): 16384,
    (11, 12, 2, 4): 32768,
    (11, 12, 2, 5): 65536,
    (11, 12, 2, 6): 131072,
    (11, 12, 2, 7): 262144,
    (11, 12, 3): 16384,
    (11, 12, 3, 4): 65536,
    (11, 12, 3, 5): 131072,
    (11, 12, 3, 6): 262144,
    (11, 12, 3, 7): 524288,
    (11, 12, 4): 65536,
    (11, 12, 4, 5): 262144,
    (11, 12, 4, 6): 524288,
    (11, 12, 4, 7): 1048576,
    (11, 12, 5): 262144,
    (11, 12, 5, 6): 1048576,
    (11, 12, 5, 7): 2097152,
    (11, 12, 6): 1048576,
    (11, 12, 6, 7): 4194304,
    (11, 12, 7): 4194304,
    (11, 13, 0): 512,
    (11, 13, 1): 2048,
    (11, 13, 2): 8192,
    (11, 13, 2, 3): 32768,
    (11, 13, 2, 4): 65536,
    (11, 13, 2, 5): 131072,
    (11, 13, 2, 6): 262144,
    (11, 13, 2, 7): 524288,
    (11, 13, 3): 32768,
    (11, 13, 3, 4): 131072,
    (11, 13, 3, 5): 262144,
    (11, 13, 3, 6): 524288,
    (11, 13, 3, 7): 1048576,
    (11, 13, 4): 131072,
    (11, 13, 4, 5): 524288,
    (11, 13, 4, 6): 1048576,
    (11, 13, 4, 7): 2097152,
    (11, 13, 5): 524288,
    (11, 13, 5, 6): 2097152,
    (11, 13, 5, 7): 4194304,
    (11, 13, 6): 2097152,
    (11, 13, 6, 7): 8388608,
    (11, 13, 7): 8388608,
    (11, 14, 0): 1024,
    (11, 14, 1): 4096,
    (11, 14, 2): 16384,
    (11, 14, 2, 3): 65536,
    (11, 14, 2, 4): 131072,
    (11, 14, 2, 5): 262144,
    (11, 14, 2, 6): 524288,
    (11, 14, 2, 7): 1048576,
    (11, 14, 3): 65536,
    (11, 14, 3, 4): 262144,
    (11, 14, 3, 5): 524288,
    (11, 14, 3, 6): 1048576,
    (11, 14, 3, 7): 2097152,
    (11, 14, 4): 262144,
    (11, 14, 4, 5): 1048576,
    (11, 14, 4, 6): 2097152,
    (11, 14, 4, 7): 4194304,
    (11, 14, 5): 1048576,
    (11, 14, 5, 6): 4194304,
    (11, 14, 5, 7): 8388608,
    (11, 14, 6): 4194304,
    (11, 14, 6, 7): 16777216,
    (11, 14, 7): 16777216,
    (11, 15, 0): 2048,
    (11, 15, 1): 8192,
    (11, 15, 2): 32768,
    (11, 15, 2, 3): 131072,
    (11, 15, 2, 4): 262144,
    (11, 15, 2, 5): 524288,
    (11, 15, 2, 6): 1048576,
    (11, 15, 2, 7): 2097152,
    (11, 15, 3): 131072,
    (11, 15, 3, 4): 524288,
    (11, 15, 3, 5): 1048576,
    (11, 15, 3, 6): 2097152,
    (11, 15, 3, 7): 4194304,
    (11, 15, 4): 524288,
    (11, 15, 4, 5): 2097152,
    (11, 15, 4, 6): 4194304,
    (11, 15, 4, 7): 8388608,
    (11, 15, 5): 2097152,
    (11, 15, 5, 6): 8388608,
    (11, 15, 5, 7): 16777216,
    (11, 15, 6): 8388608,
    (11, 15, 6, 7): 33554432,
    (11, 15, 7): 33554432,
    (12, 2): 2176,
    (12, 2, 3, 8): 2048,
    (12, 2, 3, 9): 4096,
    (12, 2, 4, 8): 4096,
    (12, 2, 4, 9): 8192,
    (12, 2, 5, 8): 8192,
    (12, 2, 5, 9): 16384,
    (12, 2, 6, 8): 16384,
    (12, 2, 6, 9): 32768,
    (12, 2, 7, 8): 32768,
    (12, 2, 7, 9): 65536,
    (12, 3): 12544,
    (12, 3, 4, 8): 8192,
    (12, 3, 4, 9): 16384,
    (12, 3, 5, 8): 16384,
    (12, 3, 5, 9): 32768,
    (12, 3, 6, 8): 32768,
    (12, 3, 6, 9): 65536,
    (12, 3, 7, 8): 65536,
    (12, 3, 7, 9): 131072,
    (12, 4): 57856,
    (12, 4, 5, 8): 32768,
    (12, 4, 5, 9): 65536,
    (12, 4, 6, 8): 65536,
    (12, 4, 6, 9): 131072,
    (12, 4, 7, 8): 131072,
    (12, 4, 7, 9): 262144,
    (12, 5): 246784,
    (12, 5, 6, 8): 131072,
    (12, 5, 6, 9): 262144,
    (12, 5, 7, 8): 262144,
    (12, 5, 7, 9): 524288,
    (12, 6): 1017856,
    (12, 6, 7, 8): 524288,
    (12, 6, 7, 9): 1048576,
    (12, 7): 4132864,
    (12, 8, 0): 32,
    (12, 8, 1): 128,
    (12, 8, 2): 512,
    (12, 8, 3): 2048,
    (12, 8, 4): 8192,
    (12, 8, 5): 32768,
    (12, 8, 6): 131072,
    (12, 8, 7): 524288,
    (12, 9, 0): 64,
    (12, 9, 1): 256,
    (12, 9, 2): 1024,
    (12, 9, 3): 4096,
    (12, 9, 4): 16384,
    (12, 9, 5): 65536,
    (12, 9, 6): 262144,
    (12, 9, 7): 1048576,
    (12, 13, 0): 1024,
    (12, 13, 1): 4096,
    (12, 13, 2): 16384,
    (12, 13, 2, 3): 65536,
    (12, 13, 2, 4): 131072,
    (12, 13, 2, 5): 262144,
    (12, 13, 2, 6): 524288,
    (12, 13, 2, 7): 1048576,
    (12, 13, 3): 65536,
    (12, 13, 3, 4): 262144,
    (12, 13, 3, 5): 524288,
    (12, 13, 3, 6): 1048576,
    (12, 13, 3, 7): 2097152,
    (12, 13, 4): 262144,
    (12, 13, 4, 5): 1048576,
    (12, 13, 4, 6): 2097152,
    (12, 13, 4, 7): 4194304,
    (12, 13, 5): 1048576,
    (12, 13, 5, 6): 4194304,
    (12, 13, 5, 7): 8388608,
    (12, 13, 6): 4194304,
    (12, 13, 6, 7): 16777216,
    (12, 13, 7): 16777216,
    (12, 14, 0): 2048,
    (12, 14, 1): 8192,
    (12, 14, 2): 32768,
    (12, 14, 2, 3): 131072,
    (12, 14, 2, 4): 262144,
    (12, 14, 2, 5): 524288,
    (12, 14, 2, 6): 1048576,
    (12, 14, 2, 7): 2097152,
    (12, 14, 3): 131072,
    (12, 14, 3, 4): 524288,
    (12, 14, 3, 5): 1048576,
    (12, 14, 3, 6): 2097152,
    (12, 14, 3, 7): 4194304,
    (12, 14, 4): 524288,
    (12, 14, 4, 5): 2097152,
    (12, 14, 4, 6): 4194304,
    (12, 14, 4, 7): 8388608,
    (12, 14, 5): 2097152,
    (12, 14, 5, 6): 8388608,
    (12, 14, 5, 7): 16777216,
    (12, 14, 6): 8388608,
    (12, 14, 6, 7): 33554432,
    (12, 14, 7): 33554432,
    (12, 15, 0): 4096,
    (12, 15, 1): 16384,
    (12, 15, 2): 65536,
    (12, 15, 2, 3): 262144,
    (12, 15, 2, 4): 524288,
    (12, 15, 2, 5): 1048576,
    (12, 15, 2, 6): 2097152,
    (12, 15, 2, 7): 4194304,
    (12, 15, 3): 262144,
    (12, 15, 3, 4): 1048576,
    (12, 15, 3, 5): 2097152,
    (12, 15, 3, 6): 4194304,
    (12, 15, 3, 7): 8388608,
    (12, 15, 4): 1048576,
    (12, 15, 4, 5): 4194304,
    (12, 15, 4, 6): 8388608,
    (12, 15, 4, 7): 16777216,
    (12, 15, 5): 4194304,
    (12, 15, 5, 6): 16777216,
    (12, 15, 5, 7): 33554432,
    (12, 15, 6): 16777216,
    (12, 15, 6, 7): 67108864,
    (12, 15, 7): 67108864,
    (13, 2): 12544,
    (13, 2, 3, 8): 4096,
    (13, 2, 3, 9): 8192,
    (13, 2, 4, 8): 8192,
    (13, 2, 4, 9): 16384,
    (13, 2, 5, 8): 16384,
    (13, 2, 5, 9): 32768,
    (13, 2, 6, 8): 32768,
    (13, 2, 6, 9): 65536,
    (13, 2, 7, 8): 65536,
    (13, 2, 7, 9): 131072,
    (13, 3): 57856,
    (13, 3, 4, 8): 16384,
    (13, 3, 4, 9): 32768,
    (13, 3, 5, 8): 32768,
    (13, 3, 5, 9): 65536,
    (13, 3, 6, 8): 65536,
    (13, 3, 6, 9): 131072,
    (13, 3, 7, 8): 131072,
    (13, 3, 7, 9): 262144,
    (13, 4): 246784,
    (13, 4, 5, 8): 65536,
    (13, 4, 5, 9): 131072,
    (13, 4, 6, 8): 131072,
    (13, 4, 6, 9): 262144,
    (13, 4, 7, 8): 262144,
    (13, 4, 7, 9): 524288,
    (13, 5): 1017856,
    (13, 5, 6, 8): 262144,
    (13, 5, 6, 9): 524288,
    (13, 5, 7, 8): 524288,
    (13, 5, 7, 9): 1048576,
    (13, 6): 4132864,
    (13, 6, 7, 8): 1048576,
    (13, 6, 7, 9): 2097152,
    (13, 7): 16654336,
    (13, 8, 0): 64,
    (13, 8, 1): 256,
    (13, 8, 2): 1024,
    (13, 8, 3): 4096,
    (13, 8, 4): 16384,
    (13, 8, 5): 65536,
    (13, 8, 6): 262144,
    (13, 8, 7): 1048576,
    (13, 9, 0): 128,
    (13, 9, 1): 512,
    (13, 9, 2): 2048,
    (13, 9, 3): 8192,
    (13, 9, 4): 32768,
    (13, 9, 5): 131072,
    (13, 9, 6): 524288,
    (13, 9, 7): 2097152,
    (13, 14, 0): 4096,
    (13, 14, 1): 16384,
    (13, 14, 2): 65536,
    (13, 14, 2, 3): 262144,
    (13, 14, 2, 4): 524288,
    (13, 14, 2, 5): 1048576,
    (13, 14, 2, 6): 2097152,
    (13, 14, 2, 7): 4194304,
    (13, 14, 3): 262144,
    (13, 14, 3, 4): 1048576,
    (13, 14, 3, 5): 2097152,
    (13, 14, 3, 6): 4194304,
    (13, 14, 3, 7): 8388608,
    (13, 14, 4): 1048576,
    (13, 14, 4, 5): 4194304,
    (13, 14, 4, 6): 8388608,
    (13, 14, 4, 7): 16777216,
    (13, 14, 5): 4194304,
    (13, 14, 5, 6): 16777216,
    (13, 14, 5, 7): 33554432,
    (13, 14, 6): 16777216,
    (13, 14, 6, 7): 67108864,
    (13, 14, 7): 67108864,
    (13, 15, 0): 8192,
    (13, 15, 1): 32768,
    (13, 15, 2): 131072,
    (13, 15, 2, 3): 524288,
    (13, 15, 2, 4): 1048576,
    (13, 15, 2, 5): 2097152,
    (13, 15, 2, 6): 4194304,
    (13, 15, 2, 7): 8388608,
    (13, 15, 3): 524288,
    (13, 15, 3, 4): 2097152,
    (13, 15, 3, 5): 4194304,
    (13, 15, 3, 6): 8388608,
    (13, 15, 3, 7): 16777216,
    (13, 15, 4): 2097152,
    (13, 15, 4, 5): 8388608,
    (13, 15, 4, 6): 16777216,
    (13, 15, 4, 7): 33554432,
    (13, 15, 5): 8388608,
    (13, 15, 5, 6): 33554432,
    (13, 15, 5, 7): 67108864,
    (13, 15, 6): 33554432,
    (13, 15, 6, 7): 134217728,
    (13, 15, 7): 134217728,
    (14, 2): 57856,
    (14, 2, 3, 8): 8192,
    (14, 2, 3, 9): 16384,
    (14, 2, 4, 8): 16384,
    (14, 2, 4, 9): 32768,
    (14, 2, 5, 8): 32768,
    (14, 2, 5, 9): 65536,
    (14, 2, 6, 8): 65536,
    (14, 2, 6, 9): 131072,
    (14, 2, 7, 8): 131072,
    (14, 2, 7, 9): 262144,
    (14, 3): 246784,
    (14, 3, 4, 8): 32768,
    (14, 3, 4, 9): 65536,
    (14, 3, 5, 8): 65536,
    (14, 3, 5, 9): 131072,
    (14, 3, 6, 8): 131072,
    (14, 3, 6, 9): 262144,
    (14, 3, 7, 8): 262144,
    (14, 3, 7, 9): 524288,
    (14, 4): 1017856,
    (14, 4, 5, 8): 131072,
    (14, 4, 5, 9): 262144,
    (14, 4, 6, 8): 262144,
    (14, 4, 6, 9): 524288,
    (14, 4, 7, 8): 524288,
    (14, 4, 7, 9): 1048576,
    (14, 5): 4132864,
    (14, 5, 6, 8): 524288,
    (14, 5, 6, 9): 1048576,
    (14, 5, 7, 8): 1048576,
    (14, 5, 7, 9): 2097152,
    (14, 6): 16654336,
    (14, 6, 7, 8): 2097152,
    (14, 6, 7, 9): 4194304,
    (14, 7): 66863104,
    (14, 8, 0): 128,
    (14, 8, 1): 512,
    (14, 8, 2): 2048,
    (14, 8, 3): 8192,
    (14, 8, 4): 32768,
    (14, 8, 5): 131072,
    (14, 8, 6): 524288,
    (14, 8, 7): 2097152,
    (14, 9, 0): 256,
    (14, 9, 1): 1024,
    (14, 9, 2): 4096,
    (14, 9, 3): 16384,
    (14, 9, 4): 65536,
    (14, 9, 5): 262144,
    (14, 9, 6): 1048576,
    (14, 9, 7): 4194304,
    (14, 15, 0): 16384,
    (14, 15, 1): 65536,
    (14, 15, 2): 262144,
    (14, 15, 2, 3): 1048576,
    (14, 15, 2, 4): 2097152,
    (14, 15, 2, 5): 4194304,
    (14, 15, 2, 6): 8388608,
    (14, 15, 2, 7): 16777216,
    (14, 15, 3): 1048576,
    (14, 15, 3, 4): 4194304,
    (14, 15, 3, 5): 8388608,
    (14, 15, 3, 6): 16777216,
    (14, 15, 3, 7): 33554432,
    (14, 15, 4): 4194304,
    (14, 15, 4, 5): 16777216,
    (14, 15, 4, 6): 33554432,
    (14, 15, 4, 7): 67108864,
    (14, 15, 5): 16777216,
    (14, 15, 5, 6): 67108864,
    (14, 15, 5, 7): 134217728,
    (14, 15, 6): 67108864,
    (14, 15, 6, 7): 268435456,
    (14, 15, 7): 268435456,
    (15, 2): 246784,
    (15, 2, 3, 8): 16384,
    (15, 2, 3, 9): 32768,
    (15, 2, 4, 8): 32768,
    (15, 2, 4, 9): 65536,
    (15, 2, 5, 8): 65536,
    (15, 2, 5, 9): 131072,
    (15, 2, 6, 8): 131072,
    (15, 2, 6, 9): 262144,
    (15, 2, 7, 8): 262144,
    (15, 2, 7, 9): 524288,
    (15, 3): 1017856,
    (15, 3, 4, 8): 65536,
    (15, 3, 4, 9): 131072,
    (15, 3, 5, 8): 131072,
    (15, 3, 5, 9): 262144,
    (15, 3, 6, 8): 262144,
    (15, 3, 6, 9): 524288,
    (15, 3, 7, 8): 524288,
    (15, 3, 7, 9): 1048576,
    (15, 4): 4132864,
    (15, 4, 5, 8): 262144,
    (15, 4, 5, 9): 524288,
    (15, 4, 6, 8): 524288,
    (15, 4, 6, 9): 1048576,
    (15, 4, 7, 8): 1048576,
    (15, 4, 7, 9): 2097152,
    (15, 5): 16654336,
    (15, 5, 6, 8): 1048576,
    (15, 5, 6, 9): 2097152,
    (15, 5, 7, 8): 2097152,
    (15, 5, 7, 9): 4194304,
    (15, 6): 66863104,
    (15, 6, 7, 8): 4194304,
    (15, 6, 7, 9): 8388608,
    (15, 7): 267943936,
    (15, 8, 0): 256,
    (15, 8, 1): 1024,
    (15, 8, 2): 4096,
    (15, 8, 3): 16384,
    (15, 8, 4): 65536,
    (15, 8, 5): 262144,
    (15, 8, 6): 1048576,
    (15, 8, 7): 4194304,
    (15, 9, 0): 512,
    (15, 9, 1): 2048,
    (15, 9, 2): 8192,
    (15, 9, 3): 32768,
    (15, 9, 4): 131072,
    (15, 9, 5): 524288,
    (15, 9, 6): 2097152,
    (15, 9, 7): 8388608
}

[tmittal7]

I am looking into this problem and will get back to you soon.

[tmittal7]

In order to improve the results, strength parameter in make_quadratic(poly, strength = strength, dimod.Binary) needs to be tuned. It is recommended to scale it with the problem biases. Consider this trivial example, x = 2abc + bcd. This is converted into a quadratic problem with objective 2ay + yd and constraint y = bc where y is an auxiliary variable. The strength parameter acts as a Lagrange parameter on the constraint. So, with lower value of strength parameter, it becomes favorable to violate constraints in order to minimize the objective.

Also, given the complexity of the problem, it will be helpful to tune the chain_strength parameter to the largest absolute value(bias) in your problem. Here is a document to help you tune this parameter: https://www.dwavesys.com/sites/default/files/14-1041A-A_Setting_The_Chain_Strength.pdf.

I do want to point out that I noticed a few challenges in this problem, for example in your equation, the linear biases range from 0 - 267946936 and the quadratic biases range from -2000 to 268435456 and this range cannot be preserved when scaling down to a range of [-2.0, 2.0] and [-1.0, 1.0] respectively.

This might be a reason that this formulation of factoring problem as minimization of (P-ab)**2 is not recommended, it is provided to help understand the intuition but in practice it gets very complex. So, users are encouraged to formulate it as Constrained Satisfaction Problem: https://github.com/dwave-examples/factoring-notebook/blob/master/01-factoring-overview.ipynb

[arcondello]

I'll just add that the new default chain_strength added in dwave-system 0.9.13 will automatically scale with your problem.

[DevelopDaily]

Thanks for the info. I understand the CSP would be more appropriate for the factoring problem. But, the CSP has its own problems. If you are interested in them, I am tracking the issue here.

My main purpose is to evaluate the capabilities of the D-Wave API. So, the more challenging the problem is, the better. After all, real life applications can be even more challenging and we don't know their true minimums. That is the reason why I want to use the well-known factoring problem to test the system because we know its minimum.

I tried many values of chain_strength, but none of them worked. Does that mean some QUBO problems are not solvable?

By the way, it would be interesting to try the ExactSolverto find out if the model returned from make_quadraticis valid. Unfortunately, however, the problem is already too big for the ExactSolveron my machine. I got this error when I ran it:

ValueError: Maximum allowed dimension exceeded

Would you please try to run it?

[tmittal7]

The ExactSolver() calculates energy for every possible sample which increases exponentially with each additional variable. In your bqm, there are 80 variables this means 2^80 possible outputs which is beyond its capabilities. This is the reason ExactSolver() is recommended for testing and debugging purposes only.

If you would like to verify the output from make_quadratic, I would suggest starting from a small problem like the one I mentioned in my previous comment x = 2abc + bcd. In this problem, you can easily understand how make_quadratic is changing the higher order polynomial to the bqm as well as the impact of the strength parameter using ExactSolver().

As it is difficult to scale factoring on d-wave system, I am also looking for some other real-world verifiable problems to help you explore the power of the D-Wave QPU.

[DevelopDaily]

@tmittal7 Ah...I didn't realize it has already reached 2^80! Thanks for pointing that out.

My goal is indeed to look for some "verifiable problems"!