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 桁でした。

 以上、如何でしょうか?

広告

No comments yet

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。