```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 ``` ```; how fermat factored integers (define (sprintf fmt . args) (define (escape cs) (define (octal? c) (char<=? #\0 c #\7)) (define (c->o c) (- (char->integer c) 48)) (cond ((null? cs) (error 'escape "incomplete")) ((not (char=? (car cs) #\\)) (values (car cs) (cdr cs))) ((null? (cdr cs)) (error 'escape "malformed")) ((char=? (cadr cs) #\b) (values #\backspace (cddr cs))) ((char=? (cadr cs) #\f) (values #\page (cddr cs))) ((char=? (cadr cs) #\n) (values #\newline (cddr cs))) ((char=? (cadr cs) #\r) (values #\return (cddr cs))) ((char=? (cadr cs) #\t) (values #\tab (cddr cs))) ((octal? (cadr cs)) (let loop ((k 3) (cs (cdr cs)) (oct 0)) (if (and (positive? k) (pair? cs) (octal? (car cs))) (loop (- k 1) (cdr cs) (+ (* oct 8) (c->o (car cs)))) (values (integer->char oct) cs)))) (else (values (cadr cs) (cddr cs))))) (define (specifier cs arg) (define (c->d c) (- (char->integer c) 48)) (define (justify str left? pad? width) (let ((len (string-length str))) (cond ((<= width len) str) (left? (string-append str (make-string (- width len) #\space))) ((and pad? (not left?)) (string-append (make-string (- width len) #\0) str)) (else (string-append (make-string (- width len) #\space) str))))) (define (rnd num prec) (if prec (/ (round (* num (expt 10 prec))) (expt 10 prec)) num)) (define (trunc num) (inexact->exact (truncate num))) (let ((cs (cdr cs)) (left? #f) (pad? #f) (width 0) (prec #f)) (when (and (pair? cs) (char=? (car cs) #\-)) (set! left? #t) (set! cs (cdr cs))) (when (and (pair? cs) (char=? (car cs) #\0)) (set! pad? #t) (set! cs (cdr cs))) (do () ((or (null? cs) (not (char-numeric? (car cs))))) (set! width (+ (* width 10) (c->d (car cs)))) (set! cs (cdr cs))) (when (and (pair? cs) (char=? (car cs) #\.)) (set! cs (cdr cs)) (set! prec 0) (do () ((or (null? cs) (not (char-numeric? (car cs))))) (set! prec (+ (* prec 10) (c->d (car cs)))) (set! cs (cdr cs)))) (if (null? cs) (error 'specifier "incomplete") (case (car cs) ((#\c) (values (justify (string (integer->char arg)) left? #f width) (cdr cs))) ((#\d) (values (justify (number->string (trunc arg)) left? pad? width) (cdr cs))) ((#\f) (values (justify (number->string (rnd arg prec)) left? pad? width) (cdr cs))) ((#\o) (values (justify (number->string (trunc arg) 8) left? pad? width) (cdr cs))) ((#\s) (values (justify (if prec (substring arg 0 prec) arg) left? #f width) (cdr cs))) ((#\x) (values (justify (number->string (trunc arg) 16) left? pad? width) (cdr cs))) (else (error 'specifier "unsupported")))))) (let loop ((cs (string->list fmt)) (args args) (out (list))) (cond ((null? cs) (if (pair? args) (error 'printf "too many arguments") (list->string (reverse out)))) ((char=? (car cs) #\\) (call-with-values (lambda () (escape cs)) (lambda (c rest) (loop rest args (cons c out))))) ((char=? (car cs) #\%) (if (null? (cdr cs)) (error 'sprintf "incomplete specifier") (if (char=? (cadr cs) #\%) (loop (cddr cs) args (cons #\% out)) (if (null? args) (error 'printf "not enough arguments") (call-with-values (lambda () (specifier cs (car args))) (lambda (str rest) (loop rest (cdr args) (append (reverse (string->list str)) out)))))))) (else (loop (cdr cs) args (cons (car cs) out)))))) (define (printf fmt . args) (display (apply sprintf fmt args))) (define limit 10000) (define squares (let ((squares (make-vector (+ limit 1)))) (do ((i 0 (+ i 1))) ((< limit i) squares) (vector-set! squares i (* i i))))) (define (isqrt n) (do ((i 1 (+ i 1))) ((< n (vector-ref squares i)) (- i 1)))) (define (in-table n) (let loop ((i 0)) (cond ((< n (vector-ref squares i)) #f) ((= n (vector-ref squares i)) i) (else (loop (+ i 1)))))) (define (digital-root n) (let loop ((n n) (r 0)) (cond ((zero? n) (if (< r 10) r (digital-root r))) ((< n 10) (loop 0 (+ r n))) (else (let ((d (modulo n 10))) (loop (/ (- n d) 10) (+ r d))))))) (define (square? n) (let* ((ones (modulo n 10)) (tens (modulo (/ (- n ones) 10) 10))) (and (or (and (= 0 ones) (zero? tens)) (and (= 1 ones) (even? tens)) (and (= 4 ones) (even? tens)) (and (= 5 ones) (= 2 tens)) (and (= 6 ones) (odd? tens)) (and (= 9 ones) (even? tens))) (member (digital-root n) '(1 4 7 9)) (in-table n)))) (define (fermat n) (if (not (< -1 n (* limit limit))) #f (if (even? n) (list 2 (/ n 2)) (let ((x (isqrt n))) (if (= (* x x) n) (list x x) (let loop ((r (- (* x x) n)) (t (+ x x 1))) (display r) (display " ") (display t) (newline) (if (not (square? r)) (loop (+ r t) (+ t 2)) (let ((x (/ (- t 1) 2)) (y (isqrt r))) (list (- x y) (+ x y)))))))))) (display (fermat 13290059)) (newline) (newline) ; print table of squares to a million (begin (define (square x) (* x x)) (define (print-header) (printf "--- ------ ------ ------ ------ ------ ------ ------ ------ ------\n") (printf " 1 2 3 4 5 6 7 8 9\n") (printf "--- ------ ------ ------ ------ ------ ------ ------ ------ ------\n")) (do ((tens 0 (+ tens 1))) ((= tens 100)) (when (zero? (modulo tens 10)) (print-header)) (printf "%3d" (* tens 10)) (do ((ones 1 (+ ones 1))) ((= ones 10)) (printf " %6d" (square (+ (* tens 10) ones)))) (printf "\n")) (print-header)) ```
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 ``` ```-4034 7291 3257 7293 10550 7295 17845 7297 25142 7299 32441 7301 39742 7303 47045 7305 54350 7307 61657 7309 68966 7311 76277 7313 83590 7315 90905 7317 98222 7319 105541 7321 112862 7323 120185 7325 127510 7327 134837 7329 142166 7331 149497 7333 156830 7335 164165 7337 171502 7339 178841 7341 186182 7343 193525 7345 200870 7347 208217 7349 215566 7351 222917 7353 230270 7355 237625 7357 244982 7359 252341 7361 259702 7363 267065 7365 274430 7367 281797 7369 289166 7371 296537 7373 303910 7375 311285 7377 318662 7379 326041 7381 (3119 4261) --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 1 2 3 4 5 6 7 8 9 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 0 1 4 9 16 25 36 49 64 81 10 121 144 169 196 225 256 289 324 361 20 441 484 529 576 625 676 729 784 841 30 961 1024 1089 1156 1225 1296 1369 1444 1521 40 1681 1764 1849 1936 2025 2116 2209 2304 2401 50 2601 2704 2809 2916 3025 3136 3249 3364 3481 60 3721 3844 3969 4096 4225 4356 4489 4624 4761 70 5041 5184 5329 5476 5625 5776 5929 6084 6241 80 6561 6724 6889 7056 7225 7396 7569 7744 7921 90 8281 8464 8649 8836 9025 9216 9409 9604 9801 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 1 2 3 4 5 6 7 8 9 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 100 10201 10404 10609 10816 11025 11236 11449 11664 11881 110 12321 12544 12769 12996 13225 13456 13689 13924 14161 120 14641 14884 15129 15376 15625 15876 16129 16384 16641 130 17161 17424 17689 17956 18225 18496 18769 19044 19321 140 19881 20164 20449 20736 21025 21316 21609 21904 22201 150 22801 23104 23409 23716 24025 24336 24649 24964 25281 160 25921 26244 26569 26896 27225 27556 27889 28224 28561 170 29241 29584 29929 30276 30625 30976 31329 31684 32041 180 32761 33124 33489 33856 34225 34596 34969 35344 35721 190 36481 36864 37249 37636 38025 38416 38809 39204 39601 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 1 2 3 4 5 6 7 8 9 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 200 40401 40804 41209 41616 42025 42436 42849 43264 43681 210 44521 44944 45369 45796 46225 46656 47089 47524 47961 220 48841 49284 49729 50176 50625 51076 51529 51984 52441 230 53361 53824 54289 54756 55225 55696 56169 56644 57121 240 58081 58564 59049 59536 60025 60516 61009 61504 62001 250 63001 63504 64009 64516 65025 65536 66049 66564 67081 260 68121 68644 69169 69696 70225 70756 71289 71824 72361 270 73441 73984 74529 75076 75625 76176 76729 77284 77841 280 78961 79524 80089 80656 81225 81796 82369 82944 83521 290 84681 85264 85849 86436 87025 87616 88209 88804 89401 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 1 2 3 4 5 6 7 8 9 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 300 90601 91204 91809 92416 93025 93636 94249 94864 95481 310 96721 97344 97969 98596 99225 99856 100489 101124 101761 320 103041 103684 104329 104976 105625 106276 106929 107584 108241 330 109561 110224 110889 111556 112225 112896 113569 114244 114921 340 116281 116964 117649 118336 119025 119716 120409 121104 121801 350 123201 123904 124609 125316 126025 126736 127449 128164 128881 360 130321 131044 131769 132496 133225 133956 134689 135424 136161 370 137641 138384 139129 139876 140625 141376 142129 142884 143641 380 145161 145924 146689 147456 148225 148996 149769 150544 151321 390 152881 153664 154449 155236 156025 156816 157609 158404 159201 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 1 2 3 4 5 6 7 8 9 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 400 160801 161604 162409 163216 164025 164836 165649 166464 167281 410 168921 169744 170569 171396 172225 173056 173889 174724 175561 420 177241 178084 178929 179776 180625 181476 182329 183184 184041 430 185761 186624 187489 188356 189225 190096 190969 191844 192721 440 194481 195364 196249 197136 198025 198916 199809 200704 201601 450 203401 204304 205209 206116 207025 207936 208849 209764 210681 460 212521 213444 214369 215296 216225 217156 218089 219024 219961 470 221841 222784 223729 224676 225625 226576 227529 228484 229441 480 231361 232324 233289 234256 235225 236196 237169 238144 239121 490 241081 242064 243049 244036 245025 246016 247009 248004 249001 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 1 2 3 4 5 6 7 8 9 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 500 251001 252004 253009 254016 255025 256036 257049 258064 259081 510 261121 262144 263169 264196 265225 266256 267289 268324 269361 520 271441 272484 273529 274576 275625 276676 277729 278784 279841 530 281961 283024 284089 285156 286225 287296 288369 289444 290521 540 292681 293764 294849 295936 297025 298116 299209 300304 301401 550 303601 304704 305809 306916 308025 309136 310249 311364 312481 560 314721 315844 316969 318096 319225 320356 321489 322624 323761 570 326041 327184 328329 329476 330625 331776 332929 334084 335241 580 337561 338724 339889 341056 342225 343396 344569 345744 346921 590 349281 350464 351649 352836 354025 355216 356409 357604 358801 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 1 2 3 4 5 6 7 8 9 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 600 361201 362404 363609 364816 366025 367236 368449 369664 370881 610 373321 374544 375769 376996 378225 379456 380689 381924 383161 620 385641 386884 388129 389376 390625 391876 393129 394384 395641 630 398161 399424 400689 401956 403225 404496 405769 407044 408321 640 410881 412164 413449 414736 416025 417316 418609 419904 421201 650 423801 425104 426409 427716 429025 430336 431649 432964 434281 660 436921 438244 439569 440896 442225 443556 444889 446224 447561 670 450241 451584 452929 454276 455625 456976 458329 459684 461041 680 463761 465124 466489 467856 469225 470596 471969 473344 474721 690 477481 478864 480249 481636 483025 484416 485809 487204 488601 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 1 2 3 4 5 6 7 8 9 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 700 491401 492804 494209 495616 497025 498436 499849 501264 502681 710 505521 506944 508369 509796 511225 512656 514089 515524 516961 720 519841 521284 522729 524176 525625 527076 528529 529984 531441 730 534361 535824 537289 538756 540225 541696 543169 544644 546121 740 549081 550564 552049 553536 555025 556516 558009 559504 561001 750 564001 565504 567009 568516 570025 571536 573049 574564 576081 760 579121 580644 582169 583696 585225 586756 588289 589824 591361 770 594441 595984 597529 599076 600625 602176 603729 605284 606841 780 609961 611524 613089 614656 616225 617796 619369 620944 622521 790 625681 627264 628849 630436 632025 633616 635209 636804 638401 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 1 2 3 4 5 6 7 8 9 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 800 641601 643204 644809 646416 648025 649636 651249 652864 654481 810 657721 659344 660969 662596 664225 665856 667489 669124 670761 820 674041 675684 677329 678976 680625 682276 683929 685584 687241 830 690561 692224 693889 695556 697225 698896 700569 702244 703921 840 707281 708964 710649 712336 714025 715716 717409 719104 720801 850 724201 725904 727609 729316 731025 732736 734449 736164 737881 860 741321 743044 744769 746496 748225 749956 751689 753424 755161 870 758641 760384 762129 763876 765625 767376 769129 770884 772641 880 776161 777924 779689 781456 783225 784996 786769 788544 790321 890 793881 795664 797449 799236 801025 802816 804609 806404 808201 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 1 2 3 4 5 6 7 8 9 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 900 811801 813604 815409 817216 819025 820836 822649 824464 826281 910 829921 831744 833569 835396 837225 839056 840889 842724 844561 920 848241 850084 851929 853776 855625 857476 859329 861184 863041 930 866761 868624 870489 872356 874225 876096 877969 879844 881721 940 885481 887364 889249 891136 893025 894916 896809 898704 900601 950 904401 906304 908209 910116 912025 913936 915849 917764 919681 960 923521 925444 927369 929296 931225 933156 935089 937024 938961 970 942841 944784 946729 948676 950625 952576 954529 956484 958441 980 962361 964324 966289 968256 970225 972196 974169 976144 978121 990 982081 984064 986049 988036 990025 992016 994009 996004 998001 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ 1 2 3 4 5 6 7 8 9 --- ------ ------ ------ ------ ------ ------ ------ ------ ------ ```