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.