Finding Integer Solutions of Nonlinear Systems of Equations

Jsun Yui Wong

The computer program below seeks to solve simultaneously the following system of 14 equations:  

 5 ^ X(5) + 5 ^ X(6) - 3 ^ X(8) - 7 ^ X(4)=0,
 2 ^ X(5) + 7 ^ X(6) - 3 ^ X(8) - 5 ^ X(4)=-1,
   -X(1)  -3 + X(3) - 2 * X(5) + X(7) + X(9)=0,
    (-24 - X(1) ^ 2 + 2 * (X(2) + X(4)) ^ 3 - X(5) + 3 * X(6) + X(7) - 4 * X(9)) -15*X(10)=0,
  -X(8)  -8 + X(2) + (2 * X(4)) ^ 2 - 6 * X(6) + 2 * X(10)=0,
 - 2 * X(1) - (X(2) + 3 * X(4)) ^ 3 - (5 * X(7)) ^ 2 + 6 * X(8) - X(9) + 9 * X(10)=-31,
 - X(1) + 3 * X(2) - 4 * X(4) - X(6) + 6 * X(7) - X(8) + 2 * X(9)=16,
 - (2 * X(1) + X(2)) ^ 2 - 3 * X(3) + 10 * X(5) + (X(6) + 3 * X(7)) ^ 3 + X(8) + 6 * X(9)=-27,
 - 5 * X(1) - 2 * X(2) + 8 * X(4) + 3 * X(5) - 4 * X(6) - X(7) + X(9)=-23,
 - 3 * X(1) - 2 * X(2) + 5 * X(3) + X(4) ^ 4 + 2 * X(5) - X(6) - 4 * X(7) + 10 * X(8) - 8 * X(9)=9,
 - 3 * X(1) + (2 * X(2)) ^ 2 - 10 * X(3) + 9 * X(4) - 3 * X(5) - X(6) + 2 * X(7) + 8 * X(8) - 12 * X(9) + 5 * X(10)=25,
 5 * X(1) + 10 * X(2) - 5 * X(3) + X(5) ^ 3 + 8 * X(6)=39,
 6 * X(1) + X(3) - 99 * X(2) + (15 * X(6)) ^ 2=-148,
 (X(1) + X(2)) ^ 2 - 7 * X(3) + 5 * X(4) + 12 * X(5) - 8 * X(6)=18.

These equations, including the two exponential diophantine equations above, are based on the equations in Perez, Amaya, and Correa [3].


0 REM DEFDBL A-Z
1 DEFINT I, J, K

2 DIM B(99), N(99), A(2002), H(99), L(99), U(99), X(2002), D(111), P(111), PS(33), J(99), AA(99), HR(32), HHR(32), LHS(44), PLHS(44), LB(22), UB(22), PX(44), J44(44), PN(22), NN(22)
88 FOR JJJJ = -32000 TO 32000
    89 RANDOMIZE JJJJ
    90 M = -3D+30
    111 FOR J44 = 1 TO 10
        113 A(J44) = FIX(RND * 30)

    115 NEXT J44

    128 FOR I = 1 TO 1000
        129 FOR KKQQ = 1 TO 10
            130 X(KKQQ) = A(KKQQ)
        131 NEXT KKQQ
        139 FOR IPP = 1 TO FIX(1 + RND * 3)
            140 B = 1 + FIX(RND * 10)
            160 R = (1 - RND * 2) * A(B)

            163 IF RND < .5 THEN 165 ELSE GOTO 167
            165 IF RND < .5 THEN X(B) = CINT(A(B) - RND ^ 3 * R) ELSE X(B) = CINT(A(B) + RND ^ 3 * R)

            166 GOTO 168
            167 IF RND < .5 THEN X(B) = CINT(A(B) - 1) ELSE X(B) = CINT(A(B) + 1)
        168 NEXT IPP
        177 X(1) = -3 + X(3) - 2 * X(5) + X(7) + X(9)
        179 X(10) = (-24 - X(1) ^ 2 + 2 * (X(2) + X(4)) ^ 3 - X(5) + 3 * X(6) + X(7) - 4 * X(9)) / 15
        183 X(8) = -8 + X(2) + (2 * X(4)) ^ 2 - 6 * X(6) + 2 * X(10)
        192 FOR J44 = 1 TO 10
            193 IF X(J44) < 0 THEN 1670
        194 NEXT J44
        195 N(11) = 31 - 2 * X(1) - (X(2) + 3 * X(4)) ^ 3 - (5 * X(7)) ^ 2 + 6 * X(8) - X(9) + 9 * X(10)
        197 N(12) = -16 - X(1) + 3 * X(2) - 4 * X(4) - X(6) + 6 * X(7) - X(8) + 2 * X(9)
        199 N(13) = 27 - (2 * X(1) + X(2)) ^ 2 - 3 * X(3) + 10 * X(5) + (X(6) + 3 * X(7)) ^ 3 + X(8) + 6 * X(9)
        201 N(14) = 23 - 5 * X(1) - 2 * X(2) + 8 * X(4) + 3 * X(5) - 4 * X(6) - X(7) + X(9)
        203 N(15) = -9 - 3 * X(1) - 2 * X(2) + 5 * X(3) + X(4) ^ 4 + 2 * X(5) - X(6) - 4 * X(7) + 10 * X(8) - 8 * X(9)
        205 N(16) = -25 - 3 * X(1) + (2 * X(2)) ^ 2 - 10 * X(3) + 9 * X(4) - 3 * X(5) - X(6) + 2 * X(7) + 8 * X(8) - 12 * X(9) + 5 * X(10)


        209 N(17) = -39 + 5 * X(1) + 10 * X(2) - 5 * X(3) + X(5) ^ 3 + 8 * X(6)
        210 N(18) = 148 + 6 * X(1) + X(3) - 99 * X(2) + (15 * X(6)) ^ 2

        212 N(19) = -18 + (X(1) + X(2)) ^ 2 - 7 * X(3) + 5 * X(4) + 12 * X(5) - 8 * X(6)
        213 N(20) = 5 ^ X(5) + 5 ^ X(6) - 3 ^ X(8) - 7 ^ X(4)

        214 N(21) = 1 + 2 ^ X(5) + 7 ^ X(6) - 3 ^ X(8) - 5 ^ X(4)


        555 P = -ABS(N(11)) - ABS(N(12)) - ABS(N(13)) - ABS(N(14)) - ABS(N(15)) - ABS(N(16)) - ABS(N(17)) - ABS(N(18)) - ABS(N(19)) - ABS(N(20)) - ABS(N(21))


        1111 IF P <= M THEN 1670
        1452 M = P
        1454 FOR KLX = 1 TO 10
            1455 A(KLX) = X(KLX)
        1456 NEXT KLX
        1557 GOTO 128
    1670 NEXT I
    1889 IF M < -1 THEN 1999

    1904 PRINT A(1), A(2), A(3)
    1906 PRINT A(4), A(5), A(6)
    1907 PRINT A(7), A(8), A(9), A(10)
    1917 PRINT M, JJJJ

1999 NEXT JJJJ

This computer program was run with qb64v1000-win [5]. Copied by hand from the screen, the computer program’s complete output through JJJJ=-10032 is shown below:

3      4      5
0      1      1
1      2      2      6
0      -30380

3      4      5
0      1      1
1      2      2      6
0      -22163

3      4      5
0      1      1
1      2      2      6
0      -15830

3      4      5
0      1      1
1      2      2      6
0      -10884

3      4      5
0      1      1
1      2      2      6
0      -10032

Above there is no rounding by hand; it is just straight copying by hand from the screen.

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and with qb64v1000-win [5], the wall-clock time through JJJJ=-10032 was three minutes.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.

References

[1] S. Abraham, S. Sanyal, M. Sanglikar (2013), Finding Numerical Solutions of Diophantine Equations Using Ant Colony Optimization. Applied Mathematics and Computation 219 (2013), Pages 11376-11387.

[2] Microsoft Corp., BASIC, Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.

[3] O. Perez, I. Amaya, R. Correa (2013), Numerical Solution of Certain Exponential and Non-linear Diophantine Systems of Equations by Using a Discrete Particles Swarm Optimization Algorithm. Applied Mathematics and Computation, Volume 225, 1 December 2013, Pages 737-746.

[4] Thomas L. Saaty, Optimization in Integers and Related Extremal Problems. McGraw-Hill, 1970.

[5] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64.

Solving Nonlinear Systems of Equations for Integer Solutions

Jsun Yui Wong

The computer program listed below seeks to find integer solutions (if any) of the following nonlinear problem:

         -141544 + X(1) ^ 3 + X(12) ^ 2 + X(3)=0,

         -424667 + X(2) ^ 3 + X(1) ^ 2 + X(4)=0,

         -861294 + X(3) ^ 3 + X(11) ^ 2 + X(2)=0,

         -683646 + X(4) ^ 3 + X(10) ^ 2 + X(5)=0,

         -196549 + X(5) ^ 3 + X(9) ^ 2 + X(8)=0,

         -517121 + X(6) ^ 3 + X(7) ^ 2 + X(6)=0,

         -359469 + X(7) ^ 3 + X(13) ^ 2 + X(9)=0,

         -319541 + X(8) ^ 3 + X(7) ^ 2 + X(8)=0,

         -52446 + X(9) ^ 3 + X(14) ^ 2 + X(12)=0,

         -101222 + X(10) ^ 3 + X(11) ^ 2 + X(14)=0,

         -241772 + X(11) ^ 3 + X(5) ^ 2 + X(6)=0,

         -26544 + X(12) ^ 3 + X(10) ^ 2 + X(13)=0,

         -68432 + X(13) ^ 3 + X(3) ^ 2 + X(4)=0,

         -76867 + X(14) ^ 3 + X(1) ^ 2 + X(2)=0,

        -142786 + X(1) ^ 3 + X(10) ^ 2 + X(11)=0,

where 0<=X(i)<=100 and X(i) are integers for i=1,2,3,...,14.

The nonlinear system above comes from Conley [5, p. 1018].


0 DEFDBL A-Z

3 DEFINT J, K, X

4 DIM X(342), A(342), L(333), K(333)

12 FOR JJJJ = -32000 TO 32000


    14 RANDOMIZE JJJJ

    16 M = -1D+317

    77 IF JJJJ > -32000 THEN GOTO 88 ELSE GOTO 91


    88 IF RND < .05 THEN GOTO 91 ELSE GOTO 128


    91 FOR KK = 1 TO 14

        94 A(KK) = FIX(RND * 81)


    95 NEXT KK


    128 FOR I = 1 TO 200000


        129 FOR K = 1 TO 14


            131 X(K) = A(K)
        132 NEXT K
        155 FOR IPP = 1 TO FIX(1 + RND * 3)

            181 B = 1 + FIX(RND * 14)


            182 REM IF RND < -.05 THEN 183 ELSE GOTO 189


            183 r = (1 - RND * 2) * A(B)
            186 X(B) = A(B) + (RND ^ 3) * r

            188 GOTO 191
            189 IF RND < .5 THEN X(B) = A(B) - FIX(1 + RND * 1.99) ELSE X(B) = A(B) + FIX(1 + RND * 1.99)


        191 NEXT IPP

        222 FOR J44 = 1 TO 14

            228 IF X(J44) > 100 THEN 1670


        233 NEXT J44


        1311 N81 = -141544 + X(1) ^ 3 + X(12) ^ 2 + X(3)


        1312 N82 = -424667 + X(2) ^ 3 + X(1) ^ 2 + X(4)


        1313 N83 = -861294 + X(3) ^ 3 + X(11) ^ 2 + X(2)


        1314 N84 = -683646 + X(4) ^ 3 + X(10) ^ 2 + X(5)

        1315 N85 = -196549 + X(5) ^ 3 + X(9) ^ 2 + X(8)


        1316 N86 = -517121 + X(6) ^ 3 + X(7) ^ 2 + X(6)


        1317 N87 = -359469 + X(7) ^ 3 + X(13) ^ 2 + X(9)


        1318 N88 = -319541 + X(8) ^ 3 + X(7) ^ 2 + X(8)


        1319 N89 = -52446 + X(9) ^ 3 + X(14) ^ 2 + X(12)

        1320 N90 = -101222 + X(10) ^ 3 + X(11) ^ 2 + X(14)


        1321 N91 = -241772 + X(11) ^ 3 + X(5) ^ 2 + X(6)


        1322 N92 = -26544 + X(12) ^ 3 + X(10) ^ 2 + X(13)


        1323 N93 = -68432 + X(13) ^ 3 + X(3) ^ 2 + X(4)


        1324 N94 = -76867 + X(14) ^ 3 + X(1) ^ 2 + X(2)


        1325 N95 = -142786 + X(1) ^ 3 + X(10) ^ 2 + X(11)

        1445 P = -ABS(N81) - ABS(N82) - ABS(N83) - ABS(N84) - ABS(N85) - ABS(N86) - ABS(N87) - ABS(N88) - ABS(N89) - ABS(N90) - ABS(N91) - ABS(N92) - ABS(N93) - ABS(N94) - ABS(N95)


        1499 IF P <= M THEN 1670
        1657 FOR KEW = 1 TO 14

            1658 A(KEW) = X(KEW)
        1659 NEXT KEW
        1661 M = P
    1670 NEXT I
    1888 IF M < 0 THEN 1999

    1917 PRINT A(1), A(2), A(3), A(4), A(5), A(6), A(7), A(8), A(9)
    1919 PRINT A(10), A(11), A(12), A(13), A(14), M, JJJJ

1999 NEXT JJJJ

This computer program was run with qb64v1000-win [12]. Copied by hand from the screen, the computer program’s complete output through
JJJJ=-31968 is shown below:

52      75      95      88      58
80      71      68      37
46      62      29      39      42
0      -32000

52      75      95      88      58
80      71      68      37
46      62      29      39      42
0      -31999

52      75      95      88      58
80      71      68      37
46      62      29      39      42
0      -31987

52      75      95      88      58
80      71      68      37
46      62      29      39      42
0      -31986

52      75      95      88      58
80      71      68      37
46      62      29      39      42
0      -31985

.
.
.

52      75      95      88      58
80      71      68      37
46      62      29      39      42
0      -31968

Above there is no rounding by hand; it is just straight copying by hand from the screen.

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and with qb64v1000-win [12], the wall-clock time through
JJJJ=-31968 was 35 seconds.

Incidentally, one can stop the computer run as soon as the first 0 (for M) appears on the screen.  For the present problem, that happens at JJJJ=-32000.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.

References
[1] R. Burden, J. Faires, A. Burden, Numerical Analysis, Tenth Edition. Cengage Learning, 2016.
[2] R. Burden, J. Faires, Numerical Analysis, Sixth Edition. Brooks/Cole Publishing Company, 1996.
[3] R. Burden, J. Faires, Numerical Analysis, Third Edition. PWS Publishers, 1985.
[4] W. Conley, Computer Optimization Techniques, Revised Edition.  Petrocelli Books, Inc., NY/Princeton, 1984.
[5] William Conley, Simulation Optimization and Correlation with Multi Stage Monte Carlo Optimization, International Journal of Systems Science, Vol.38, No. 12, Dec. 2007, pp. 1013-1019.
[6] D. Greenspan, V. Casulli, Numerical Analysis for Applied Mathematics, Science, and Engineering. Addison-Wesley Publishing Company, 1988
[7] L. W. Johnson, R. D. Riess, Numerical Analysis, Second Edition. Addison-Wesley Publishing Company, 1982
[8] Microsoft Corp. BASIC, second edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
[9] William H. Mills, A System of Quadratic Diophantine Equations, Pacific Journal of Mathematics, 3 (1953), pp. 209-220.
[10]  Thomas L.. Saaty, Optimization in Integers and Related Extremal Problems.  McGraw-Hill, 1970.
[11] Terry E. Shoup, Applied Numerical Methods for the Microcomputer, Prentice-Hall, 1984.
[12] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64.