Archive for the ‘Projecteuler’ Category
projecteuler30
コメントを残す projecteuler の 問題30は、自然数の各桁の 5 乗の和が、その自然数になるものを求め、その和を取るという問題。
だから（汗）、スクリプトは力技で、
(define (pf i)
(* i i i i i))
(let (lst)
(for (i 2 999999)
(if (= i (apply + (map pf (map int (explode (string i))))))
(push i lst -1))
)
(println lst)
(apply + lst)
) こんな感じ。
これを実行すると
(4150 4151 54748 92727 93084 194979) 443839 >
と、自然数のリストとその和が出てきます。
つまり、答えは 443839 。
以上、如何でしょうか？
projecteuler29
projecteuler の 問題29は、2 から 100 までの自然数を 2 乗から 100乗 して、同じものを除くと何個になるかという問題。
だから、スクリプトは単純、
(let (lst)
(for (i 2 100)
(for (j 2 100)
(push (apply * (cons 1L (dup i j))) lst -1)
)
)
(length (unique lst)))こんな感じ。1L を cons しているのは、大整数にするため。100 乗するには 64 ビット整数では足りないですからね（笑）
(let (lst)
(for (i 2 100)
(for (j 2 100)
(push (apply * (map bigint (dup i j))) lst -1)
)
)
(length (unique lst)))でも同じになります。
ここで bigint は整数を大整数に変換します。
また、unique は同一数値を除去してくれます。
これを実行すると
9183 >
と答えが求まります。
以上、如何でしょうか？
projecteuler28
projecteuler の 問題28は、自然数をらせん状に並べ、角の数値のみを足した和を求めるもの。といっても、一辺が 1001 になるまでですが（笑）
スクリプトは単純、
(let (i 1 j 2 lst '(1))
(while (< j 1001)
(dotimes (k 4) (++ i j) (push i lst -1))
(++ j 2))
(println lst)
(apply + lst)
) こんな感じ。一週ごとに求める自然数の間隔が2つずつ増えていくのがミソ。
これを実行すると
(1 3 5 7 9 13 17 21 25 31 37 43 49 57 65 73 81 91 101 111 121 133 145 157 169 183 ： 986049 987043 988037 989031 990025 991021 992017 993013 994009 995007 996005 997003 998001 999001 1000001 1001001 1002001) 669171001 >
答え 669171001 が求まります。
以上、如何でしょうか？
projecteuler27
projecteuler27
projecteuler の 問題27は、二次方程式
n^2 + an + b, where |a| < 1000 and |b| < 1000
において、n = 0 から素数が続く数が最大となる係数を探し出し、その積を求めるもの。
何も考えずに力ずくで求めるスクリプトは、
(define (func n a b)
(+ b (* a n) (* n n)))
(setq lst '() len 1)
(for (i -999 999)
(for (j -999 999)
(let (k 0 res '() flag true)
(while flag
(let (ans (func k i j))
(if(and (> ans 0) (= 1 (length (factor ans)))) (push (list k i j) res -1)
(setq flag nil)))
(++ k))
(when (> (length res) len) (setq len (length res)) (push res lst -1)))))
(lst -1 -1)
(apply * (1 (lst -1 -1)))これを実行すると
(lambda (n a b) (+ b (* a n) (* n n))) 1 nil (70 -61 971) -59231 >
こんな感じで答え -59231 が求まります。
この時の二次方程式は
n^2 - 61n + 971
で n = 0 ～ 70 で 71 個の素数が作られます。
実際に計算してみると、
> (map (hayashi func -61 971) (sequence 0 70)) (971 911 853 797 743 691 641 593 547 503 461 421 383 347 313 281 251 223 197 173 151 131 113 97 83 71 61 53 47 43 41 41 43 47 53 61 71 83 97 113 131 151 173 197 223 251 281 313 347 383 421 461 503 547 593 641 691 743 797 853 911 971 1033 1097 1163 1231 1301 1373 1447 1523 1601) >
こんな感じ。
ここで関数 hayashi は拙作で、（newlisp-utility.lsp にあります）
(hayashi func -61 971)
は以下の式等価です。
(fn (x) (func x -61 971))
以上、如何でしょうか？
projecteuler26
projecteuler の 問題26は、1000より小さい自然数 d で、1/d の作る循環小数が最大の長さになる d を求めよという問題。
まず、循環小数の長さを求める関数を用意します。
(define (junkan n disp)
(let (m 1 s 0 t 0 flst '() mlst '() flag true)
(while flag
(setq f (/ m n) m (% m n))
(if (find m mlst) (setq flag nil))
(push f flst -1)
(if (and (= s 0) (!= f 0) (setq s t)))
(push m mlst -1)
(if (= m 0) (setq flag nil))
(setq m (* 10 m))
(++ t)
)
(if disp (begin
(println mlst)
(println (flst 0) "." (apply append (map string (1 flst))))
(println s " " (-- t)))
(-- t))
)
) 与えらえた数値 n で 1 を割り算して、商と余りを次々に求め、それぞれをリストに保存し、余りに同じものが出たら終了して、長さを返すもの。余計な表示部分もつけてありますが、、、
さて、どうせ求める答えは素数ですから、あらかじめ素数を求め、そこから答えを探します。
(let (i 3 lst '() cc 0 res)
(while (< i 1000)
(when (= (length (factor i)) 1) (push i lst -1))
(++ i 2))
(dolist (i lst)
(let (len (junkan i))
(if (< cc len) (setq cc len res i))))
res)
こんな感じで実行すると、
>983
という答えが得られます。
実際、どれくらいの循環かというと
> (junkan 983 true) (1 10 100 17 170 717 289 924 393 981 963 783 949 643 532 405 118 197 4 40 400 68 680 902 173 747 589 975 903 183 847 606 162 637 472 788 16 160 617 272 754 659 692 39 390 951 663 732 439 458 648 582 905 203 64 640 502 105 67 670 802 156 577 855 686 962 773 849 626 362 671 812 256 594 42 420 268 714 259 624 342 471 778 899 143 447 538 465 718 299 41 410 168 697 89 890 53 530 385 901 163 647 572 805 186 877 906 213 164 657 672 822 356 611 212 154 557 655 652 622 322 271 744 559 675 852 656 662 722 339 441 478 848 616 262 654 642 522 305 101 27 270 734 459 658 682 922 373 781 929 443 498 65 650 602 122 237 404 108 97 970 853 666 762 739 509 175 767 789 26 260 634 442 488 948 633 432 388 931 463 698 99 7 70 700 119 207 104 57 570 785 969 843 566 745 569 775 869 826 396 28 280 834 476 828 416 228 314 191 927 423 298 31 310 151 527 355 601 112 137 387 921 363 681 912 273 764 759 709 209 124 257 604 142 437 438 448 548 565 735 469 758 699 109 107 87 870 836 496 45 450 568 765 769 809 226 294 974 893 83 830 436 428 348 531 395 18 180 817 306 111 127 287 904 193 947 623 332 371 761 729 409 158 597 72 720 319 241 444 508 165 667 772 839 526 345 501 95 950 653 632 422 288 914 293 964 793 66 660 702 139 407 138 397 38 380 851 646 562 705 169 707 189 907 223 264 674 842 556 645 552 605 152 537 455 618 282 854 676 862 756 679 892 73 730 419 258 614 242 454 608 182 837 506 145 467 738 499 75 750 619 292 954 693 49 490 968 833 466 728 399 58 580 885 3 30 300 51 510 185 867 806 196 977 923 383 881 946 613 232 354 591 12 120 217 204 74 740 519 275 784 959 743 549 575 835 486 928 433 398 48 480 868 816 296 11 110 117 187 887 23 230 334 391 961 763 749 609 192 937 523 315 201 44 440 468 748 599 92 920 353 581 895 103 47 470 768 799 126 277 804 176 777 889 43 430 368 731 429 358 631 412 188 897 123 247 504 125 267 704 159 607 172 737 489 958 733 449 558 665 752 639 492 5 50 500 85 850 636 462 688 982 973 883 966 813 266 694 59 590 2 20 200 34 340 451 578 865 786 979 943 583 915 303 81 810 236 394 8 80 800 136 377 821 346 511 195 967 823 366 711 229 324 291 944 593 32 320 251 544 525 335 401 78 780 919 343 481 878 916 313 181 827 406 128 297 21 210 134 357 621 312 171 727 389 941 563 715 269 724 359 641 512 205 84 840 536 445 518 265 684 942 573 815 286 894 93 930 453 598 82 820 336 411 178 797 106 77 770 819 326 311 161 627 372 771 829 426 328 331 361 661 712 239 424 308 131 327 321 261 644 542 505 135 367 721 329 341 461 678 882 956 713 249 524 325 301 61 610 202 54 540 485 918 333 381 861 746 579 875 886 13 130 317 221 244 474 808 216 194 957 723 349 541 495 35 350 551 595 52 520 285 884 976 913 283 864 776 879 926 413 198 14 140 417 238 414 208 114 157 587 955 703 149 507 155 567 755 669 792 56 560 685 952 673 832 456 628 382 871 846 596 62 620 302 71 710 219 224 274 774 859 726 379 841 546 545 535 435 418 248 514 225 284 874 876 896 113 147 487 938 533 415 218 214 174 757 689 9 90 900 153 547 555 635 452 588 965 803 166 677 872 856 696 79 790 36 360 651 612 222 254 574 825 386 911 263 664 742 539 475 818 316 211 144 457 638 482 888 33 330 351 561 695 69 690 19 190 917 323 281 844 576 845 586 945 603 132 337 421 278 814 276 794 76 760 719 309 141 427 338 431 378 831 446 528 365 701 129 307 121 227 304 91 910 253 564 725 369 741 529 375 801 146 477 838 516 245 484 908 233 364 691 29 290 934 493 15 150 517 255 584 925 403 98 980 953 683 932 473 798 116 177 787 6 60 600 102 37 370 751 629 392 971 863 766 779 909 243 464 708 199 24 240 434 408 148 497 55 550 585 935 503 115 167 687 972 873 866 796 96 960 753 649 592 22 220 234 374 791 46 460 668 782 939 543 515 235 384 891 63 630 402 88 880 936 513 215 184 857 706 179 807 206 94 940 553 615 252 554 625 352 571 795 86 860 736 479 858 716 279 824 376 811 246 494 25 250 534 425 318 231 344 491 978 933 483 898 133 347 521 295 1) 0.0010172939979654120040691759918616480162767039674465920651068158697863682604272634791454730417090539165818921668362156663275686673448626653102746693794506612410986775178026449643947100712105798575788402848423194303153611393692777212614445574771108850457782299084435401831129196337741607324516785350966429298067141403865717192268565615462868769074262461851475076297049847405900305188199389623601220752797558494404883011190233977619532044760935910478128179043743641912512716174974567650050864699898270600203458799593082400813835198372329603255340793489318413021363173957273652085452695829094608341810783316378433367243133265513733468972533062054933875890132248219735503560528992878942014242115971515768056968463886063072227873855544252288911495422177009155645981688708036622583926754832146490335707019328585961342828077314343845371312309257375381485249237029501525940996948118006103763987792472024415055951169888097660223804679552390640895218718209562563580874872838250254323499491353 3 982 982 >
こんな感じで 982 桁でした。
以上、如何でしょうか？
projecteuler25
newLISP の length を数値に適用すると、整数部分の桁数が返ります。
ということで、projecteuler の 問題25は、フィボナッチ数が 1000桁になるのは何番目かという問題。
1000桁ですから大整数の出番。そして、前述のlengthを使えば、
(silent)
(setq fibo '(1L 1L))
(while (< (length (fibo -1)) 1000)
(push (+ (fibo -2) (fibo -1)) fibo -1))
(println (length fibo))これを実行すれば
> 4782
と答えが得られます。
silent は余計な表示を抑えるための関数。なくても答えは得られます。
リストの長さが求める答えになっているので、スクリプトの最後にも length を使っています。
フィボナッチ数列は変数 fibo に入っていますから、中身を覗くと
> (0 12 fibo) (1L 1L 2L 3L 5L 8L 13L 21L 34L 55L 89L 144L) > (fibo -1) 1070066266382758936764980584457396885083683896632151665013235203375314520604694040621889147582489792657804694888177591957484336466672569959512996030461262748092482186144069433051234774442750273781753087579391666192149259186759553966422837148943113074699503439547001985432609723067290192870526447243726117715821825548491120525013201478612965931381792235559657452039506137551467837543229119602129934048260706175397706847068202895486902666185435124521900369480641357447470911707619766945691070098024393439617474103736912503231365532164773697023167755051595173518460579954919410967778373229665796581646513903488154256310184224190259846088000110186255550245493937113651657039447629584714548523425950428582425306083544435428212611008992863795048006894330309773217834864543113205765659868456288616808718693835297350643986297640660000723562917905207051164077614812491885830945940566688339109350944456576357666151619317753792891661581327159616877487983821820492520348473874384736771934512787029218636250627816L > (length (fibo -1)) 1000 >
こんな感じ。
末尾に L が付いているのは、大整数の証。
以上、如何でしょうか？
projecteuler24
projecteuler の 問題24は、辞書的順列問題。0 から 9 までの数字を組み合わせた10桁の数値を辞書的に並べ、百万番目を求めるもの。
当然一番目は 0123456789 。先頭が 0 である数は
9! ＝ 362880 個。
とすれば、
1000000 － 2*362880 ＝ 274240
となり、解答は先頭が 2 の 274240 番目。
こんな風に各桁を求めれば、解答に行く着くはず。
これを関数にすれば
(define (make-ans cnt lst, (res '()))
(-- cnt)
(while (> cnt 0)
(let (cm (apply * (sequence 1 (-- (length lst)))))
(push (pop lst (/ cnt cm)) res -1)
(setq cnt (% cnt cm))))
(apply string (if lst (append res lst) res)))実際に試すと、
> (make-ans 1 (sequence 0 9)) "0123456789" > (make-ans 362880 (sequence 0 9)) "0987654321" > (make-ans 362881 (sequence 0 9)) "1023456789" > (make-ans 1000000 (sequence 0 9)) "2783915460" >
こんな感じ。
ちなみ、例題にある 0 から 2 の三桁も
> (map (hayashi make-ans (sequence 0 2)) '(1 2 3 4 5 6))
("012" "021" "102" "120" "201" "210")
> (map (fn (x) (make-ans x (sequence 0 2))) '(1 2 3 4 5 6))
("012" "021" "102" "120" "201" "210")
>
この通り。
hayashi は拙作の関数で二番目以降の引数を curry のように扱える関数で、newlisp-utility.lsp に置いてあります。
以上、如何でしょうか？
projecteuler23
正の自然数の約数の総和が、その自然数の2倍より大きい時、その数を過剰数（abundant number） と呼ぶそうです。さらに、数理解析（mathematical analysis） によると、28123より多きい数は二つの過剰数の和で表されるとか。
そして、projecteuler の 問題23 は、二つの過剰数の和で表されない数の和を求める問題。
つまり、二つの過剰数の和で表される 28123 以下の数値がわかれば答えが求まります。
さて、まず二つの過剰数を求めます。最小の過剰数が 12 と示されているので、
(define-macro (memoize mem-func func)
(set (sym mem-func mem-func)
(letex (f func c mem-func)
(lambda ()
(or (context c (string (args)))
(context c (string (args)) (apply f (args))))))))
(define (make-sublist lst)
(clean nil? (map (fn(x) (if x $idx)) lst))
)
(memoize combination2 (lambda (n)
(if (= n 0) '()
(let (res (combination2 (-- n)))
(push (list n) res -1)
(dolist (x res (= (x 0) n))
(push (append x (list n)) res -1))
res))))
(define (divisors2 num , (res '(1)))
(let (numbers (factor num))
(if (= num 1) 1
numbers
(let (sublist (combination2 (length numbers)))
(dolist (x sublist)
(push (apply * (select numbers x)) res -1))
(unique res)))))
(setq max-num 28124 abundants '())
(for (i 2 (- max-num 12))
(let (lst (divisors2 i))
(if (> (apply + (0 -1 lst)) (lst -1)) (push i abundants -1))))
これで、計算に必要な過剰数が abundants に入ります。
中身はこんな感じ、
> (0 10 abundants) (12 18 20 24 30 36 40 42 48 54) > (-10 10 abundants) (28074 28080 28084 28086 28092 28098 28100 28104 28110 28112) > (length abundants) 6962 >
つぎに、二つの過剰数の和を求めます。
(setq lst '())
(for (i 0 (-- (length abundants)))
(if (> max-num (* 2 (abundants i)))
(push (map (curry + (abundants i)) (i abundants)) lst －１)))
(setq two-abundants (filter (fn(x) (< x max-num)) (unique (flat lst))))
さて、二つの過剰数の和の最大値と最小値は
> (apply max two-abundants) 28123 > (apply min two-abundants) 24 >
予定通りです。
あとは、1 ～ 28123 までの数値から二つの過剰数の和を取り除いて、和を取るだけ。sequence と difference を使えば、簡単（笑）
> (apply + (difference (sequence 1 (-- max-num)) two-abundants)) 4179871 >
これで答えが出ました。
ちなみに、
> (sort (difference (sequence 1 (-- max-num)) two-abundants))
(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 26 27 28 29 31 33
：
13621 13829 13879 14143 14251 14297 15371 15557 16187 17261 17891 18437 19067 20161)
> ということから、20162 以上の数値が二つの過剰数の和になるようです。
以上、如何でしょうか？
projecteuler22
projecteuler22
projecteuler の 問題22 は、names.txt にある名前をアルファベット順に並べ、全ての名前の順位と名前のアルファベットの値和と積を求め、その総量を求める問題。アルファベットの値は A, B, C,… が 1, 2, 3,… に相当。
url にあるデータは get-url で取り出し、sort でソートすれば、後は計算するだけ。繰り返しには dolist でも使いましょうか。文字列の分解には explode が使えます。
さて、コードは、
(silent)
(setq names (replace "," (parse (get-url "https://projecteuler.net/project/resources/p022_names.txt"))))
(sort names)
(let (res 0)
(dolist (n names)
(++ res (* (+ $idx 1) (apply + (map (fn (x) (- x 0x40)) (map char (explode n)))))))
(println res))
こんな感じ。これを実行すれば、
871198282
という答えが得られます。
silent 文を外せば、names.txt にある名前がすべて表示されます。お好みでどうぞ。
以上、如何でしょうか？
projecteuler21
projecteuler の 問題21 は、10000 未満の友愛数の和を求める問題。
この問題を解いていると聞いたこともない種類の数の名前が出てきます。友愛数もその一つ。
友愛数は親和数とも呼ばれ、約数から自身を除いた和が相手の数値になり、その相手の数値の約数の和が自分と同じになる組だそうです。
つまり、突き詰めれば全ての約数を求める問題。約数を求めるのは 問題12でやっているので、コード自体は、
(define-macro (memoize mem-func func)
(set (sym mem-func mem-func)
(letex (f func c mem-func)
(lambda ()
(or (context c (string (args)))
(context c (string (args)) (apply f (args))))))))
(define (make-sublist lst)
(clean nil? (map (fn(x) (if x $idx)) lst))
)
(memoize combination2 (lambda (n)
(if (= n 0) '()
(let (res (combination2 (-- n)))
(push (list n) res -1)
(dolist (x res (= (x 0) n))
(push (append x (list n)) res -1))
res))))
(define (divisors2 num , (res '(1)))
(let (numbers (factor num))
(if (= num 1) 1
numbers
(let (sublist (combination2 (length numbers)))
(dolist (x sublist)
(push (apply * (select numbers x)) res -1))
(unique res)))))
(let (res)
(for (a 2 9999)
(let (b (apply + (chop (divisors2 a))))
(if (and (> b 1) (!= a b) (= a (apply + (chop (divisors2 b)))))
(push a res -1))))
(println res)
(apply + res))
こんな感じ。これを実行すれば、
(220 284 1184 1210 2620 2924 5020 5564 6232 6368) 31626
10000 未満の友愛数とその和 31626 が出てきます。
以上、如何でしょうか？
新リスプな日々 