Forbidden number in Fibonacci

Computer Science Level 3

Let F n = F n − 1 + F n − 2 F_n = F_{n-1}+ F_{n-2} be the n th n^\text{th} Fibonacci number ( n > 0 ) (n>0) , where F 1 = 1 F_1=1 and F 2 = 1 F_2=1 .

If we consider the last 3 digits of the Fibonacci numbers, not all numbers from 0 to 999 appear in the sequence.

\quad 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 597, 584, 181, ...

What is the largest integer from 0 to 999 that doesn't appear in this sequence?

Inspiration .


The answer is 998.

Chan Lye Lee by Chan Lye Lee , 44, Singapore

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Not the Best but works 

 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
 
public class Main {
    public static int large=1000000;
    public static int fibb(int a, int b){
        int c=0;
        c=a+b;
        return c;
    }
    public static void main(String[] args) {
        int[] numbers = new int[large];
        int i,j, old_number=1, present_number=1, new_number=2;
        int[] fibb_number = new int[large];
        fibb_number[0]=1;
        fibb_number[1]=1;
        for(i=0;i<1000;i++) {
            numbers[i] = i;
        }
        for(i=2; i< large; i++) {
            fibb_number[i]=fibb(old_number,present_number);
            old_number=present_number;
            present_number=new_number;
            new_number=fibb(old_number,present_number);
        }
        for(i=0;i<large;i++){
            for(j=0;j<1000;j++){
                if(fibb_number[i]%1000==numbers[j]||fibb_number[i]%100==numbers[j]||fibb_number[i]%10==numbers[j]){
                    numbers[j]=0;
                }
            }
        }
        for (i=0;i<1000;i++){
            if(numbers[i]!=0) {
                System.out.println(numbers[i]);
            }
        }
    }
}

2 Helpful 0 Interesting 0 Brilliant 0 Confused
Alex Li
May 24, 2017 
 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
 
public class ForbidenFibonacci {
    public static void main(String[] args) {
        int a = 1;//Initial values of Fib numbers.
        int b = 1;
        Set<Integer> first3Digits = new TreeSet<Integer>();
        first3Digits.add(1);
        //I iterated through 1,000,000 or 1000 * 1000 because that way,
        //we are guaranteed to have a pair a,b who have the same last 3 digits.
        //at this point, the pattern will repeat.
        for (int i = 0; i < 1000000; i++) {
            //Setting a and b to their next values.
            a += b;
            b = a-b;
            //taking only the last 3 digits as numbers after these won't affect the last 3 digits.
                   //this improves performance and ensures ints don't get too large.
            a%=1000;
            b%=1000;
            //adding the last 3 digits to a set.
            first3Digits.add(a%1000);
        }
        System.out.println(first3Digits.toString());
        //Scrolling through the output, you can quickly find the min. value
        //(Treelists are automatically sorted and only contain 1 of each value (: )
    }
}

2 Helpful 0 Interesting 0 Brilliant 0 Confused
Jonathan Quarrie
May 16, 2017

It seemed a shame to not have a solution on this problem, but I appreciate the (im)practicality of writing a comprehensive solution.

So I generated the last 3 Fibonacci digits into a table, alongside n n (associative), an index from 0 to 999 (which has been reversed to prevent having to scroll most of the way down the page to see the answer - this column is not associative with the Fibonacci digits on the same row), and the number of times that each index from 0 to 999 occurs (associative only with the Index on the same row).

Fortunately, the last 3 digits of the Fibonacci sequence repeats, but (unfortunately) at n=1500.

Sorry for the massive table.

. . . . . . .

n Fibonacci (3-Digits) | 0-999 Index (Reversed) Index Occurrences
n=1 001 | 999 1
n=2 001 | 998 \boxed{998} 0
n=3 002 | 997 3
n=4 003 | 996 0
n=5 005 | 995 1
n=6 008 | 994 2
n=7 013 | 993 3
n=8 021 | 992 2
n=9 034 | 991 1
n=10 055 | 990 0
n=11 089 | 989 3
n=12 144 | 988 0
n=13 233 | 987 1
n=14 377 | 986 2
n=15 610 | 985 3
n=16 987 | 984 2
n=17 597 | 983 1
n=18 584 | 982 0
n=19 181 | 981 3
n=20 765 | 980 0
n=21 946 | 979 1
n=22 711 | 978 2
n=23 657 | 977 3
n=24 368 | 976 2
n=25 025 | 975 1
n=26 393 | 974 0
n=27 418 | 973 3
n=28 811 | 972 0
n=29 229 | 971 1
n=30 040 | 970 2
n=31 269 | 969 3
n=32 309 | 968 2
n=33 578 | 967 1
n=34 887 | 966 0
n=35 465 | 965 3
n=36 352 | 964 0
n=37 817 | 963 1
n=38 169 | 962 2
n=39 986 | 961 3
n=40 155 | 960 2
n=41 141 | 959 1
n=42 296 | 958 0
n=43 437 | 957 3
n=44 733 | 956 0
n=45 170 | 955 1
n=46 903 | 954 2
n=47 073 | 953 3
n=48 976 | 952 2
n=49 049 | 951 1
n=50 025 | 950 0
n=51 074 | 949 3
n=52 099 | 948 0
n=53 173 | 947 1
n=54 272 | 946 2
n=55 445 | 945 3
n=56 717 | 944 2
n=57 162 | 943 1
n=58 879 | 942 0
n=59 041 | 941 3
n=60 920 | 940 0
n=61 961 | 939 1
n=62 881 | 938 2
n=63 842 | 937 3
n=64 723 | 936 2
n=65 565 | 935 1
n=66 288 | 934 0
n=67 853 | 933 3
n=68 141 | 932 0
n=69 994 | 931 1
n=70 135 | 930 2
n=71 129 | 929 3
n=72 264 | 928 2
n=73 393 | 927 1
n=74 657 | 926 0
n=75 050 | 925 3
n=76 707 | 924 0
n=77 757 | 923 1
n=78 464 | 922 2
n=79 221 | 921 3
n=80 685 | 920 2
n=81 906 | 919 1
n=82 591 | 918 0
n=83 497 | 917 3
n=84 088 | 916 0
n=85 585 | 915 1
n=86 673 | 914 2
n=87 258 | 913 3
n=88 931 | 912 2
n=89 189 | 911 1
n=90 120 | 910 0
n=91 309 | 909 3
n=92 429 | 908 0
n=93 738 | 907 1
n=94 167 | 906 2
n=95 905 | 905 3
n=96 072 | 904 2
n=97 977 | 903 1
n=98 049 | 902 0
n=99 026 | 901 3
n=100 075 | 900 0
n=101 101 | 899 1
n=102 176 | 898 2
n=103 277 | 897 3
n=104 453 | 896 2
n=105 730 | 895 1
n=106 183 | 894 0
n=107 913 | 893 3
n=108 096 | 892 0
n=109 009 | 891 1
n=110 105 | 890 2
n=111 114 | 889 3
n=112 219 | 888 2
n=113 333 | 887 1
n=114 552 | 886 0
n=115 885 | 885 3
n=116 437 | 884 0
n=117 322 | 883 1
n=118 759 | 882 2
n=119 081 | 881 3
n=120 840 | 880 2
n=121 921 | 879 1
n=122 761 | 878 0
n=123 682 | 877 3
n=124 443 | 876 0
n=125 125 | 875 1
n=126 568 | 874 2
n=127 693 | 873 3
n=128 261 | 872 2
n=129 954 | 871 1
n=130 215 | 870 0
n=131 169 | 869 3
n=132 384 | 868 0
n=133 553 | 867 1
n=134 937 | 866 2
n=135 490 | 865 3
n=136 427 | 864 2
n=137 917 | 863 1
n=138 344 | 862 0
n=139 261 | 861 3
n=140 605 | 860 0
n=141 866 | 859 1
n=142 471 | 858 2
n=143 337 | 857 3
n=144 808 | 856 2
n=145 145 | 855 1
n=146 953 | 854 0
n=147 098 | 853 3
n=148 051 | 852 0
n=149 149 | 851 1
n=150 200 | 850 2
n=151 349 | 849 3
n=152 549 | 848 2
n=153 898 | 847 1
n=154 447 | 846 0
n=155 345 | 845 3
n=156 792 | 844 0
n=157 137 | 843 1
n=158 929 | 842 2
n=159 066 | 841 3
n=160 995 | 840 2
n=161 061 | 839 1
n=162 056 | 838 0
n=163 117 | 837 3
n=164 173 | 836 0
n=165 290 | 835 1
n=166 463 | 834 2
n=167 753 | 833 3
n=168 216 | 832 2
n=169 969 | 831 1
n=170 185 | 830 0
n=171 154 | 829 3
n=172 339 | 828 0
n=173 493 | 827 1
n=174 832 | 826 2
n=175 325 | 825 3
n=176 157 | 824 2
n=177 482 | 823 1
n=178 639 | 822 0
n=179 121 | 821 3
n=180 760 | 820 0
n=181 881 | 819 1
n=182 641 | 818 2
n=183 522 | 817 3
n=184 163 | 816 2
n=185 685 | 815 1
n=186 848 | 814 0
n=187 533 | 813 3
n=188 381 | 812 0
n=189 914 | 811 1
n=190 295 | 810 2
n=191 209 | 809 3
n=192 504 | 808 2
n=193 713 | 807 1
n=194 217 | 806 0
n=195 930 | 805 3
n=196 147 | 804 0
n=197 077 | 803 1
n=198 224 | 802 2
n=199 301 | 801 3
n=200 525 | 800 2
n=201 826 | 799 1
n=202 351 | 798 0
n=203 177 | 797 3
n=204 528 | 796 0
n=205 705 | 795 1
n=206 233 | 794 2
n=207 938 | 793 3
n=208 171 | 792 2
n=209 109 | 791 1
n=210 280 | 790 0
n=211 389 | 789 3
n=212 669 | 788 0
n=213 058 | 787 1
n=214 727 | 786 2
n=215 785 | 785 3
n=216 512 | 784 2
n=217 297 | 783 1
n=218 809 | 782 0
n=219 106 | 781 3
n=220 915 | 780 0
n=221 021 | 779 1
n=222 936 | 778 2
n=223 957 | 777 3
n=224 893 | 776 2
n=225 850 | 775 1
n=226 743 | 774 0
n=227 593 | 773 3
n=228 336 | 772 0
n=229 929 | 771 1
n=230 265 | 770 2
n=231 194 | 769 3
n=232 459 | 768 2
n=233 653 | 767 1
n=234 112 | 766 0
n=235 765 | 765 3
n=236 877 | 764 0
n=237 642 | 763 1
n=238 519 | 762 2
n=239 161 | 761 3
n=240 680 | 760 2
n=241 841 | 759 1
n=242 521 | 758 0
n=243 362 | 757 3
n=244 883 | 756 0
n=245 245 | 755 1
n=246 128 | 754 2
n=247 373 | 753 3
n=248 501 | 752 2
n=249 874 | 751 1
n=250 375 | 750 0
n=251 249 | 749 3
n=252 624 | 748 0
n=253 873 | 747 1
n=254 497 | 746 2
n=255 370 | 745 3
n=256 867 | 744 2
n=257 237 | 743 1
n=258 104 | 742 0
n=259 341 | 741 3
n=260 445 | 740 0
n=261 786 | 739 1
n=262 231 | 738 2
n=263 017 | 737 3
n=264 248 | 736 2
n=265 265 | 735 1
n=266 513 | 734 0
n=267 778 | 733 3
n=268 291 | 732 0
n=269 069 | 731 1
n=270 360 | 730 2
n=271 429 | 729 3
n=272 789 | 728 2
n=273 218 | 727 1
n=274 007 | 726 0
n=275 225 | 725 3
n=276 232 | 724 0
n=277 457 | 723 1
n=278 689 | 722 2
n=279 146 | 721 3
n=280 835 | 720 2
n=281 981 | 719 1
n=282 816 | 718 0
n=283 797 | 717 3
n=284 613 | 716 0
n=285 410 | 715 1
n=286 023 | 714 2
n=287 433 | 713 3
n=288 456 | 712 2
n=289 889 | 711 1
n=290 345 | 710 0
n=291 234 | 709 3
n=292 579 | 708 0
n=293 813 | 707 1
n=294 392 | 706 2
n=295 205 | 705 3
n=296 597 | 704 2
n=297 802 | 703 1
n=298 399 | 702 0
n=299 201 | 701 3
n=300 600 | 700 0
n=301 801 | 699 1
n=302 401 | 698 2
n=303 202 | 697 3
n=304 603 | 696 2
n=305 805 | 695 1
n=306 408 | 694 0
n=307 213 | 693 3
n=308 621 | 692 0
n=309 834 | 691 1
n=310 455 | 690 2
n=311 289 | 689 3
n=312 744 | 688 2
n=313 033 | 687 1
n=314 777 | 686 0
n=315 810 | 685 3
n=316 587 | 684 0
n=317 397 | 683 1
n=318 984 | 682 2
n=319 381 | 681 3
n=320 365 | 680 2
n=321 746 | 679 1
n=322 111 | 678 0
n=323 857 | 677 3
n=324 968 | 676 0
n=325 825 | 675 1
n=326 793 | 674 2
n=327 618 | 673 3
n=328 411 | 672 2
n=329 029 | 671 1
n=330 440 | 670 0
n=331 469 | 669 3
n=332 909 | 668 0
n=333 378 | 667 1
n=334 287 | 666 2
n=335 665 | 665 3
n=336 952 | 664 2
n=337 617 | 663 1
n=338 569 | 662 0
n=339 186 | 661 3
n=340 755 | 660 0
n=341 941 | 659 1
n=342 696 | 658 2
n=343 637 | 657 3
n=344 333 | 656 2
n=345 970 | 655 1
n=346 303 | 654 0
n=347 273 | 653 3
n=348 576 | 652 0
n=349 849 | 651 1
n=350 425 | 650 2
n=351 274 | 649 3
n=352 699 | 648 2
n=353 973 | 647 1
n=354 672 | 646 0
n=355 645 | 645 3
n=356 317 | 644 0
n=357 962 | 643 1
n=358 279 | 642 2
n=359 241 | 641 3
n=360 520 | 640 2
n=361 761 | 639 1
n=362 281 | 638 0
n=363 042 | 637 3
n=364 323 | 636 0
n=365 365 | 635 1
n=366 688 | 634 2
n=367 053 | 633 3
n=368 741 | 632 2
n=369 794 | 631 1
n=370 535 | 630 0
n=371 329 | 629 3
n=372 864 | 628 0
n=373 193 | 627 1
n=374 057 | 626 2
n=375 250 | 625 3
n=376 307 | 624 2
n=377 557 | 623 1
n=378 864 | 622 0
n=379 421 | 621 3
n=380 285 | 620 0
n=381 706 | 619 1
n=382 991 | 618 2
n=383 697 | 617 3
n=384 688 | 616 2
n=385 385 | 615 1
n=386 073 | 614 0
n=387 458 | 613 3
n=388 531 | 612 0
n=389 989 | 611 1
n=390 520 | 610 2
n=391 509 | 609 3
n=392 029 | 608 2
n=393 538 | 607 1
n=394 567 | 606 0
n=395 105 | 605 3
n=396 672 | 604 0
n=397 777 | 603 1
n=398 449 | 602 2
n=399 226 | 601 3
n=400 675 | 600 2
n=401 901 | 599 1
n=402 576 | 598 0
n=403 477 | 597 3
n=404 053 | 596 0
n=405 530 | 595 1
n=406 583 | 594 2
n=407 113 | 593 3
n=408 696 | 592 2
n=409 809 | 591 1
n=410 505 | 590 0
n=411 314 | 589 3
n=412 819 | 588 0
n=413 133 | 587 1
n=414 952 | 586 2
n=415 085 | 585 3
n=416 037 | 584 2
n=417 122 | 583 1
n=418 159 | 582 0
n=419 281 | 581 3
n=420 440 | 580 0
n=421 721 | 579 1
n=422 161 | 578 2
n=423 882 | 577 3
n=424 043 | 576 2
n=425 925 | 575 1
n=426 968 | 574 0
n=427 893 | 573 3
n=428 861 | 572 0
n=429 754 | 571 1
n=430 615 | 570 2
n=431 369 | 569 3
n=432 984 | 568 2
n=433 353 | 567 1
n=434 337 | 566 0
n=435 690 | 565 3
n=436 027 | 564 0
n=437 717 | 563 1
n=438 744 | 562 2
n=439 461 | 561 3
n=440 205 | 560 2
n=441 666 | 559 1
n=442 871 | 558 0
n=443 537 | 557 3
n=444 408 | 556 0
n=445 945 | 555 1
n=446 353 | 554 2
n=447 298 | 553 3
n=448 651 | 552 2
n=449 949 | 551 1
n=450 600 | 550 0
n=451 549 | 549 3
n=452 149 | 548 0
n=453 698 | 547 1
n=454 847 | 546 2
n=455 545 | 545 3
n=456 392 | 544 2
n=457 937 | 543 1
n=458 329 | 542 0
n=459 266 | 541 3
n=460 595 | 540 0
n=461 861 | 539 1
n=462 456 | 538 2
n=463 317 | 537 3
n=464 773 | 536 2
n=465 090 | 535 1
n=466 863 | 534 0
n=467 953 | 533 3
n=468 816 | 532 0
n=469 769 | 531 1
n=470 585 | 530 2
n=471 354 | 529 3
n=472 939 | 528 2
n=473 293 | 527 1
n=474 232 | 526 0
n=475 525 | 525 3
n=476 757 | 524 0
n=477 282 | 523 1
n=478 039 | 522 2
n=479 321 | 521 3
n=480 360 | 520 2
n=481 681 | 519 1
n=482 041 | 518 0
n=483 722 | 517 3
n=484 763 | 516 0
n=485 485 | 515 1
n=486 248 | 514 2
n=487 733 | 513 3
n=488 981 | 512 2
n=489 714 | 511 1
n=490 695 | 510 0
n=491 409 | 509 3
n=492 104 | 508 0
n=493 513 | 507 1
n=494 617 | 506 2
n=495 130 | 505 3
n=496 747 | 504 2
n=497 877 | 503 1
n=498 624 | 502 0
n=499 501 | 501 3
n=500 125 | 500 0
n=501 626 | 499 1
n=502 751 | 498 2
n=503 377 | 497 3
n=504 128 | 496 2
n=505 505 | 495 1
n=506 633 | 494 0
n=507 138 | 493 3
n=508 771 | 492 0
n=509 909 | 491 1
n=510 680 | 490 2
n=511 589 | 489 3
n=512 269 | 488 2
n=513 858 | 487 1
n=514 127 | 486 0
n=515 985 | 485 3
n=516 112 | 484 0
n=517 097 | 483 1
n=518 209 | 482 2
n=519 306 | 481 3
n=520 515 | 480 2
n=521 821 | 479 1
n=522 336 | 478 0
n=523 157 | 477 3
n=524 493 | 476 0
n=525 650 | 475 1
n=526 143 | 474 2
n=527 793 | 473 3
n=528 936 | 472 2
n=529 729 | 471 1
n=530 665 | 470 0
n=531 394 | 469 3
n=532 059 | 468 0
n=533 453 | 467 1
n=534 512 | 466 2
n=535 965 | 465 3
n=536 477 | 464 2
n=537 442 | 463 1
n=538 919 | 462 0
n=539 361 | 461 3
n=540 280 | 460 0
n=541 641 | 459 1
n=542 921 | 458 2
n=543 562 | 457 3
n=544 483 | 456 2
n=545 045 | 455 1
n=546 528 | 454 0
n=547 573 | 453 3
n=548 101 | 452 0
n=549 674 | 451 1
n=550 775 | 450 2
n=551 449 | 449 3
n=552 224 | 448 2
n=553 673 | 447 1
n=554 897 | 446 0
n=555 570 | 445 3
n=556 467 | 444 0
n=557 037 | 443 1
n=558 504 | 442 2
n=559 541 | 441 3
n=560 045 | 440 2
n=561 586 | 439 1
n=562 631 | 438 0
n=563 217 | 437 3
n=564 848 | 436 0
n=565 065 | 435 1
n=566 913 | 434 2
n=567 978 | 433 3
n=568 891 | 432 2
n=569 869 | 431 1
n=570 760 | 430 0
n=571 629 | 429 3
n=572 389 | 428 0
n=573 018 | 427 1
n=574 407 | 426 2
n=575 425 | 425 3
n=576 832 | 424 2
n=577 257 | 423 1
n=578 089 | 422 0
n=579 346 | 421 3
n=580 435 | 420 0
n=581 781 | 419 1
n=582 216 | 418 2
n=583 997 | 417 3
n=584 213 | 416 2
n=585 210 | 415 1
n=586 423 | 414 0
n=587 633 | 413 3
n=588 056 | 412 0
n=589 689 | 411 1
n=590 745 | 410 2
n=591 434 | 409 3
n=592 179 | 408 2
n=593 613 | 407 1
n=594 792 | 406 0
n=595 405 | 405 3
n=596 197 | 404 0
n=597 602 | 403 1
n=598 799 | 402 2
n=599 401 | 401 3
n=600 200 | 400 2
n=601 601 | 399 1
n=602 801 | 398 0
n=603 402 | 397 3
n=604 203 | 396 0
n=605 605 | 395 1
n=606 808 | 394 2
n=607 413 | 393 3
n=608 221 | 392 2
n=609 634 | 391 1
n=610 855 | 390 0
n=611 489 | 389 3
n=612 344 | 388 0
n=613 833 | 387 1
n=614 177 | 386 2
n=615 010 | 385 3
n=616 187 | 384 2
n=617 197 | 383 1
n=618 384 | 382 0
n=619 581 | 381 3
n=620 965 | 380 0
n=621 546 | 379 1
n=622 511 | 378 2
n=623 057 | 377 3
n=624 568 | 376 2
n=625 625 | 375 1
n=626 193 | 374 0
n=627 818 | 373 3
n=628 011 | 372 0
n=629 829 | 371 1
n=630 840 | 370 2
n=631 669 | 369 3
n=632 509 | 368 2
n=633 178 | 367 1
n=634 687 | 366 0
n=635 865 | 365 3
n=636 552 | 364 0
n=637 417 | 363 1
n=638 969 | 362 2
n=639 386 | 361 3
n=640 355 | 360 2
n=641 741 | 359 1
n=642 096 | 358 0
n=643 837 | 357 3
n=644 933 | 356 0
n=645 770 | 355 1
n=646 703 | 354 2
n=647 473 | 353 3
n=648 176 | 352 2
n=649 649 | 351 1
n=650 825 | 350 0
n=651 474 | 349 3
n=652 299 | 348 0
n=653 773 | 347 1
n=654 072 | 346 2
n=655 845 | 345 3
n=656 917 | 344 2
n=657 762 | 343 1
n=658 679 | 342 0
n=659 441 | 341 3
n=660 120 | 340 0
n=661 561 | 339 1
n=662 681 | 338 2
n=663 242 | 337 3
n=664 923 | 336 2
n=665 165 | 335 1
n=666 088 | 334 0
n=667 253 | 333 3
n=668 341 | 332 0
n=669 594 | 331 1
n=670 935 | 330 2
n=671 529 | 329 3
n=672 464 | 328 2
n=673 993 | 327 1
n=674 457 | 326 0
n=675 450 | 325 3
n=676 907 | 324 0
n=677 357 | 323 1
n=678 264 | 322 2
n=679 621 | 321 3
n=680 885 | 320 2
n=681 506 | 319 1
n=682 391 | 318 0
n=683 897 | 317 3
n=684 288 | 316 0
n=685 185 | 315 1
n=686 473 | 314 2
n=687 658 | 313 3
n=688 131 | 312 2
n=689 789 | 311 1
n=690 920 | 310 0
n=691 709 | 309 3
n=692 629 | 308 0
n=693 338 | 307 1
n=694 967 | 306 2
n=695 305 | 305 3
n=696 272 | 304 2
n=697 577 | 303 1
n=698 849 | 302 0
n=699 426 | 301 3
n=700 275 | 300 0
n=701 701 | 299 1
n=702 976 | 298 2
n=703 677 | 297 3
n=704 653 | 296 2
n=705 330 | 295 1
n=706 983 | 294 0
n=707 313 | 293 3
n=708 296 | 292 0
n=709 609 | 291 1
n=710 905 | 290 2
n=711 514 | 289 3
n=712 419 | 288 2
n=713 933 | 287 1
n=714 352 | 286 0
n=715 285 | 285 3
n=716 637 | 284 0
n=717 922 | 283 1
n=718 559 | 282 2
n=719 481 | 281 3
n=720 040 | 280 2
n=721 521 | 279 1
n=722 561 | 278 0
n=723 082 | 277 3
n=724 643 | 276 0
n=725 725 | 275 1
n=726 368 | 274 2
n=727 093 | 273 3
n=728 461 | 272 2
n=729 554 | 271 1
n=730 015 | 270 0
n=731 569 | 269 3
n=732 584 | 268 0
n=733 153 | 267 1
n=734 737 | 266 2
n=735 890 | 265 3
n=736 627 | 264 2
n=737 517 | 263 1
n=738 144 | 262 0
n=739 661 | 261 3
n=740 805 | 260 0
n=741 466 | 259 1
n=742 271 | 258 2
n=743 737 | 257 3
n=744 008 | 256 2
n=745 745 | 255 1
n=746 753 | 254 0
n=747 498 | 253 3
n=748 251 | 252 0
n=749 749 | 251 1
n=750 000 | 250 2
n=751 749 | 249 3
n=752 749 | 248 2
n=753 498 | 247 1
n=754 247 | 246 0
n=755 745 | 245 3
n=756 992 | 244 0
n=757 737 | 243 1
n=758 729 | 242 2
n=759 466 | 241 3
n=760 195 | 240 2
n=761 661 | 239 1
n=762 856 | 238 0
n=763 517 | 237 3
n=764 373 | 236 0
n=765 890 | 235 1
n=766 263 | 234 2
n=767 153 | 233 3
n=768 416 | 232 2
n=769 569 | 231 1
n=770 985 | 230 0
n=771 554 | 229 3
n=772 539 | 228 0
n=773 093 | 227 1
n=774 632 | 226 2
n=775 725 | 225 3
n=776 357 | 224 2
n=777 082 | 223 1
n=778 439 | 222 0
n=779 521 | 221 3
n=780 960 | 220 0
n=781 481 | 219 1
n=782 441 | 218 2
n=783 922 | 217 3
n=784 363 | 216 2
n=785 285 | 215 1
n=786 648 | 214 0
n=787 933 | 213 3
n=788 581 | 212 0
n=789 514 | 211 1
n=790 095 | 210 2
n=791 609 | 209 3
n=792 704 | 208 2
n=793 313 | 207 1
n=794 017 | 206 0
n=795 330 | 205 3
n=796 347 | 204 0
n=797 677 | 203 1
n=798 024 | 202 2
n=799 701 | 201 3
n=800 725 | 200 2
n=801 426 | 199 1
n=802 151 | 198 0
n=803 577 | 197 3
n=804 728 | 196 0
n=805 305 | 195 1
n=806 033 | 194 2
n=807 338 | 193 3
n=808 371 | 192 2
n=809 709 | 191 1
n=810 080 | 190 0
n=811 789 | 189 3
n=812 869 | 188 0
n=813 658 | 187 1
n=814 527 | 186 2
n=815 185 | 185 3
n=816 712 | 184 2
n=817 897 | 183 1
n=818 609 | 182 0
n=819 506 | 181 3
n=820 115 | 180 0
n=821 621 | 179 1
n=822 736 | 178 2
n=823 357 | 177 3
n=824 093 | 176 2
n=825 450 | 175 1
n=826 543 | 174 0
n=827 993 | 173 3
n=828 536 | 172 0
n=829 529 | 171 1
n=830 065 | 170 2
n=831 594 | 169 3
n=832 659 | 168 2
n=833 253 | 167 1
n=834 912 | 166 0
n=835 165 | 165 3
n=836 077 | 164 0
n=837 242 | 163 1
n=838 319 | 162 2
n=839 561 | 161 3
n=840 880 | 160 2
n=841 441 | 159 1
n=842 321 | 158 0
n=843 762 | 157 3
n=844 083 | 156 0
n=845 845 | 155 1
n=846 928 | 154 2
n=847 773 | 153 3
n=848 701 | 152 2
n=849 474 | 151 1
n=850 175 | 150 0
n=851 649 | 149 3
n=852 824 | 148 0
n=853 473 | 147 1
n=854 297 | 146 2
n=855 770 | 145 3
n=856 067 | 144 2
n=857 837 | 143 1
n=858 904 | 142 0
n=859 741 | 141 3
n=860 645 | 140 0
n=861 386 | 139 1
n=862 031 | 138 2
n=863 417 | 137 3
n=864 448 | 136 2
n=865 865 | 135 1
n=866 313 | 134 0
n=867 178 | 133 3
n=868 491 | 132 0
n=869 669 | 131 1
n=870 160 | 130 2
n=871 829 | 129 3
n=872 989 | 128 2
n=873 818 | 127 1
n=874 807 | 126 0
n=875 625 | 125 3
n=876 432 | 124 0
n=877 057 | 123 1
n=878 489 | 122 2
n=879 546 | 121 3
n=880 035 | 120 2
n=881 581 | 119 1
n=882 616 | 118 0
n=883 197 | 117 3
n=884 813 | 116 0
n=885 010 | 115 1
n=886 823 | 114 2
n=887 833 | 113 3
n=888 656 | 112 2
n=889 489 | 111 1
n=890 145 | 110 0
n=891 634 | 109 3
n=892 779 | 108 0
n=893 413 | 107 1
n=894 192 | 106 2
n=895 605 | 105 3
n=896 797 | 104 2
n=897 402 | 103 1
n=898 199 | 102 0
n=899 601 | 101 3
n=900 800 | 100 0
n=901 401 | 099 1
n=902 201 | 098 2
n=903 602 | 097 3
n=904 803 | 096 2
n=905 405 | 095 1
n=906 208 | 094 0
n=907 613 | 093 3
n=908 821 | 092 0
n=909 434 | 091 1
n=910 255 | 090 2
n=911 689 | 089 3
n=912 944 | 088 2
n=913 633 | 087 1
n=914 577 | 086 0
n=915 210 | 085 3
n=916 787 | 084 0
n=917 997 | 083 1
n=918 784 | 082 2
n=919 781 | 081 3
n=920 565 | 080 2
n=921 346 | 079 1
n=922 911 | 078 0
n=923 257 | 077 3
n=924 168 | 076 0
n=925 425 | 075 1
n=926 593 | 074 2
n=927 018 | 073 3
n=928 611 | 072 2
n=929 629 | 071 1
n=930 240 | 070 0
n=931 869 | 069 3
n=932 109 | 068 0
n=933 978 | 067 1
n=934 087 | 066 2
n=935 065 | 065 3
n=936 152 | 064 2
n=937 217 | 063 1
n=938 369 | 062 0
n=939 586 | 061 3
n=940 955 | 060 0
n=941 541 | 059 1
n=942 496 | 058 2
n=943 037 | 057 3
n=944 533 | 056 2
n=945 570 | 055 1
n=946 103 | 054 0
n=947 673 | 053 3
n=948 776 | 052 0
n=949 449 | 051 1
n=950 225 | 050 2
n=951 674 | 049 3
n=952 899 | 048 2
n=953 573 | 047 1
n=954 472 | 046 0
n=955 045 | 045 3
n=956 517 | 044 0
n=957 562 | 043 1
n=958 079 | 042 2
n=959 641 | 041 3
n=960 720 | 040 2
n=961 361 | 039 1
n=962 081 | 038 0
n=963 442 | 037 3
n=964 523 | 036 0
n=965 965 | 035 1
n=966 488 | 034 2
n=967 453 | 033 3
n=968 941 | 032 2
n=969 394 | 031 1
n=970 335 | 030 0
n=971 729 | 029 3
n=972 064 | 028 0
n=973 793 | 027 1
n=974 857 | 026 2
n=975 650 | 025 3
n=976 507 | 024 2
n=977 157 | 023 1
n=978 664 | 022 0
n=979 821 | 021 3
n=980 485 | 020 0
n=981 306 | 019 1
n=982 791 | 018 2
n=983 097 | 017 3
n=984 888 | 016 2
n=985 985 | 015 1
n=986 873 | 014 0
n=987 858 | 013 3
n=988 731 | 012 0
n=989 589 | 011 1
n=990 320 | 010 2
n=991 909 | 009 3
n=992 229 | 008 2
n=993 138 | 007 1
n=994 367 | 006 0
n=995 505 | 005 3
n=996 872 | 004 0
n=997 377 | 003 1
n=998 249 | 002 2
n=999 626 | 001 3
n=1000 875 |
n=1001 501 |
n=1002 376 |
n=1003 877 |
n=1004 253 |
n=1005 130 |
n=1006 383 |
n=1007 513 |
n=1008 896 |
n=1009 409 |
n=1010 305 |
n=1011 714 |
n=1012 019 |
n=1013 733 |
n=1014 752 |
n=1015 485 |
n=1016 237 |
n=1017 722 |
n=1018 959 |
n=1019 681 |
n=1020 640 |
n=1021 321 |
n=1022 961 |
n=1023 282 |
n=1024 243 |
n=1025 525 |
n=1026 768 |
n=1027 293 |
n=1028 061 |
n=1029 354 |
n=1030 415 |
n=1031 769 |
n=1032 184 |
n=1033 953 |
n=1034 137 |
n=1035 090 |
n=1036 227 |
n=1037 317 |
n=1038 544 |
n=1039 861 |
n=1040 405 |
n=1041 266 |
n=1042 671 |
n=1043 937 |
n=1044 608 |
n=1045 545 |
n=1046 153 |
n=1047 698 |
n=1048 851 |
n=1049 549 |
n=1050 400 |
n=1051 949 |
n=1052 349 |
n=1053 298 |
n=1054 647 |
n=1055 945 |
n=1056 592 |
n=1057 537 |
n=1058 129 |
n=1059 666 |
n=1060 795 |
n=1061 461 |
n=1062 256 |
n=1063 717 |
n=1064 973 |
n=1065 690 |
n=1066 663 |
n=1067 353 |
n=1068 016 |
n=1069 369 |
n=1070 385 |
n=1071 754 |
n=1072 139 |
n=1073 893 |
n=1074 032 |
n=1075 925 |
n=1076 957 |
n=1077 882 |
n=1078 839 |
n=1079 721 |
n=1080 560 |
n=1081 281 |
n=1082 841 |
n=1083 122 |
n=1084 963 |
n=1085 085 |
n=1086 048 |
n=1087 133 |
n=1088 181 |
n=1089 314 |
n=1090 495 |
n=1091 809 |
n=1092 304 |
n=1093 113 |
n=1094 417 |
n=1095 530 |
n=1096 947 |
n=1097 477 |
n=1098 424 |
n=1099 901 |
n=1100 325 |
n=1101 226 |
n=1102 551 |
n=1103 777 |
n=1104 328 |
n=1105 105 |
n=1106 433 |
n=1107 538 |
n=1108 971 |
n=1109 509 |
n=1110 480 |
n=1111 989 |
n=1112 469 |
n=1113 458 |
n=1114 927 |
n=1115 385 |
n=1116 312 |
n=1117 697 |
n=1118 009 |
n=1119 706 |
n=1120 715 |
n=1121 421 |
n=1122 136 |
n=1123 557 |
n=1124 693 |
n=1125 250 |
n=1126 943 |
n=1127 193 |
n=1128 136 |
n=1129 329 |
n=1130 465 |
n=1131 794 |
n=1132 259 |
n=1133 053 |
n=1134 312 |
n=1135 365 |
n=1136 677 |
n=1137 042 |
n=1138 719 |
n=1139 761 |
n=1140 480 |
n=1141 241 |
n=1142 721 |
n=1143 962 |
n=1144 683 |
n=1145 645 |
n=1146 328 |
n=1147 973 |
n=1148 301 |
n=1149 274 |
n=1150 575 |
n=1151 849 |
n=1152 424 |
n=1153 273 |
n=1154 697 |
n=1155 970 |
n=1156 667 |
n=1157 637 |
n=1158 304 |
n=1159 941 |
n=1160 245 |
n=1161 186 |
n=1162 431 |
n=1163 617 |
n=1164 048 |
n=1165 665 |
n=1166 713 |
n=1167 378 |
n=1168 091 |
n=1169 469 |
n=1170 560 |
n=1171 029 |
n=1172 589 |
n=1173 618 |
n=1174 207 |
n=1175 825 |
n=1176 032 |
n=1177 857 |
n=1178 889 |
n=1179 746 |
n=1180 635 |
n=1181 381 |
n=1182 016 |
n=1183 397 |
n=1184 413 |
n=1185 810 |
n=1186 223 |
n=1187 033 |
n=1188 256 |
n=1189 289 |
n=1190 545 |
n=1191 834 |
n=1192 379 |
n=1193 213 |
n=1194 592 |
n=1195 805 |
n=1196 397 |
n=1197 202 |
n=1198 599 |
n=1199 801 |
n=1200 400 |
n=1201 201 |
n=1202 601 |
n=1203 802 |
n=1204 403 |
n=1205 205 |
n=1206 608 |
n=1207 813 |
n=1208 421 |
n=1209 234 |
n=1210 655 |
n=1211 889 |
n=1212 544 |
n=1213 433 |
n=1214 977 |
n=1215 410 |
n=1216 387 |
n=1217 797 |
n=1218 184 |
n=1219 981 |
n=1220 165 |
n=1221 146 |
n=1222 311 |
n=1223 457 |
n=1224 768 |
n=1225 225 |
n=1226 993 |
n=1227 218 |
n=1228 211 |
n=1229 429 |
n=1230 640 |
n=1231 069 |
n=1232 709 |
n=1233 778 |
n=1234 487 |
n=1235 265 |
n=1236 752 |
n=1237 017 |
n=1238 769 |
n=1239 786 |
n=1240 555 |
n=1241 341 |
n=1242 896 |
n=1243 237 |
n=1244 133 |
n=1245 370 |
n=1246 503 |
n=1247 873 |
n=1248 376 |
n=1249 249 |
n=1250 625 |
n=1251 874 |
n=1252 499 |
n=1253 373 |
n=1254 872 |
n=1255 245 |
n=1256 117 |
n=1257 362 |
n=1258 479 |
n=1259 841 |
n=1260 320 |
n=1261 161 |
n=1262 481 |
n=1263 642 |
n=1264 123 |
n=1265 765 |
n=1266 888 |
n=1267 653 |
n=1268 541 |
n=1269 194 |
n=1270 735 |
n=1271 929 |
n=1272 664 |
n=1273 593 |
n=1274 257 |
n=1275 850 |
n=1276 107 |
n=1277 957 |
n=1278 064 |
n=1279 021 |
n=1280 085 |
n=1281 106 |
n=1282 191 |
n=1283 297 |
n=1284 488 |
n=1285 785 |
n=1286 273 |
n=1287 058 |
n=1288 331 |
n=1289 389 |
n=1290 720 |
n=1291 109 |
n=1292 829 |
n=1293 938 |
n=1294 767 |
n=1295 705 |
n=1296 472 |
n=1297 177 |
n=1298 649 |
n=1299 826 |
n=1300 475 |
n=1301 301 |
n=1302 776 |
n=1303 077 |
n=1304 853 |
n=1305 930 |
n=1306 783 |
n=1307 713 |
n=1308 496 |
n=1309 209 |
n=1310 705 |
n=1311 914 |
n=1312 619 |
n=1313 533 |
n=1314 152 |
n=1315 685 |
n=1316 837 |
n=1317 522 |
n=1318 359 |
n=1319 881 |
n=1320 240 |
n=1321 121 |
n=1322 361 |
n=1323 482 |
n=1324 843 |
n=1325 325 |
n=1326 168 |
n=1327 493 |
n=1328 661 |
n=1329 154 |
n=1330 815 |
n=1331 969 |
n=1332 784 |
n=1333 753 |
n=1334 537 |
n=1335 290 |
n=1336 827 |
n=1337 117 |
n=1338 944 |
n=1339 061 |
n=1340 005 |
n=1341 066 |
n=1342 071 |
n=1343 137 |
n=1344 208 |
n=1345 345 |
n=1346 553 |
n=1347 898 |
n=1348 451 |
n=1349 349 |
n=1350 800 |
n=1351 149 |
n=1352 949 |
n=1353 098 |
n=1354 047 |
n=1355 145 |
n=1356 192 |
n=1357 337 |
n=1358 529 |
n=1359 866 |
n=1360 395 |
n=1361 261 |
n=1362 656 |
n=1363 917 |
n=1364 573 |
n=1365 490 |
n=1366 063 |
n=1367 553 |
n=1368 616 |
n=1369 169 |
n=1370 785 |
n=1371 954 |
n=1372 739 |
n=1373 693 |
n=1374 432 |
n=1375 125 |
n=1376 557 |
n=1377 682 |
n=1378 239 |
n=1379 921 |
n=1380 160 |
n=1381 081 |
n=1382 241 |
n=1383 322 |
n=1384 563 |
n=1385 885 |
n=1386 448 |
n=1387 333 |
n=1388 781 |
n=1389 114 |
n=1390 895 |
n=1391 009 |
n=1392 904 |
n=1393 913 |
n=1394 817 |
n=1395 730 |
n=1396 547 |
n=1397 277 |
n=1398 824 |
n=1399 101 |
n=1400 925 |
n=1401 026 |
n=1402 951 |
n=1403 977 |
n=1404 928 |
n=1405 905 |
n=1406 833 |
n=1407 738 |
n=1408 571 |
n=1409 309 |
n=1410 880 |
n=1411 189 |
n=1412 069 |
n=1413 258 |
n=1414 327 |
n=1415 585 |
n=1416 912 |
n=1417 497 |
n=1418 409 |
n=1419 906 |
n=1420 315 |
n=1421 221 |
n=1422 536 |
n=1423 757 |
n=1424 293 |
n=1425 050 |
n=1426 343 |
n=1427 393 |
n=1428 736 |
n=1429 129 |
n=1430 865 |
n=1431 994 |
n=1432 859 |
n=1433 853 |
n=1434 712 |
n=1435 565 |
n=1436 277 |
n=1437 842 |
n=1438 119 |
n=1439 961 |
n=1440 080 |
n=1441 041 |
n=1442 121 |
n=1443 162 |
n=1444 283 |
n=1445 445 |
n=1446 728 |
n=1447 173 |
n=1448 901 |
n=1449 074 |
n=1450 975 |
n=1451 049 |
n=1452 024 |
n=1453 073 |
n=1454 097 |
n=1455 170 |
n=1456 267 |
n=1457 437 |
n=1458 704 |
n=1459 141 |
n=1460 845 |
n=1461 986 |
n=1462 831 |
n=1463 817 |
n=1464 648 |
n=1465 465 |
n=1466 113 |
n=1467 578 |
n=1468 691 |
n=1469 269 |
n=1470 960 |
n=1471 229 |
n=1472 189 |
n=1473 418 |
n=1474 607 |
n=1475 025 |
n=1476 632 |
n=1477 657 |
n=1478 289 |
n=1479 946 |
n=1480 235 |
n=1481 181 |
n=1482 416 |
n=1483 597 |
n=1484 013 |
n=1485 610 |
n=1486 623 |
n=1487 233 |
n=1488 856 |
n=1489 089 |
n=1490 945 |
n=1491 034 |
n=1492 979 |
n=1493 013 |
n=1494 992 |
n=1495 005 |
n=1496 997 |
n=1497 002 |
n=1498 999 |
n=1499 001 |
n=1500 000 |

.

2 Helpful 0 Interesting 0 Brilliant 0 Confused

I'd love to be able to create a permalink to the comments section.

Jonathan Quarrie - 4 years ago
Micah Wood
Nov 13, 2017 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
 
# Initialize values
a = 1
b = 1
L = {0,1}

# The values were initialize as if we are at 2nd iteration
# Loop until we get to the iteration where the value
# of a and b are same as "first" iteration.
while a!=0 or b!=1:
    a, b = b, (a+b)%1000
    L = L | {b} # add the element to the L if it's not in L.

# Here, it is guarantee that the set L
# will not change at all if we continue the loop indefinitely.

# Find largest value under 1000 that is not in set L.
print(max(set(range(1000))-L))

1 Helpful 0 Interesting 0 Brilliant 0 Confused

Nice and simple, but how did you know the pair (1,1) would appear again in the fibonacci sequence? Couldn't it have been possible, that some other pairs of numbers had formed a cycle? If this was the case, your while loop would have been infinite.

One of the integer pairs must appear twice in the sequence, as there are only 1 000 000 pairs.

Tarmo Taipale - 3 years, 5 months ago

Log in to reply

Good point. How to show mathematically that (1,1) must be part of the cycle is the separate question. It's first pair I "begun" with and it terminated so I don't have a reason to go further.

Micah Wood - 3 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...