Min Zheng.sagews

def gcd(a, b, step):
    step += 1
    
    if (a % b == 0):
        return step
    else:
        return gcd(b, a%b, step)
    
def search_max(N):
    max_step = 0
    pair_i = -1
    pair_j = -1
    for i in range(1, N+1):
        for j in range(1, N+1):
            step = 0
            if (i > j):
                step = gcd(i, j, step)
            else:
                step = gcd(j, i, step)

            if step > max_step:
                pair_i = i
                pair_j = j
                max_step = step
    print("max step length is %d， pair is %d and %d"%(max_step, pair_i, pair_j))

def average(N):
    total_step = 0

    for i in range(1, N+1):
        for j in range(1, N+1):
            step = 0
            if (i > j):
                step = gcd(i, j, step)
            else:
                step = gcd(j, i, step)
            total_step += step

    average_step = float(total_step) / (N*N)

    print("total step is %d, average step is %f"%(total_step, average_step))

def main():
    search_max(50)
    average(50)

main()

max step length is 7， pair is 21 and 34 total step is 7372, average step is 2.948800

u=mod(111,17)
u
u^111
u^111^111
((u^111))^(111^111)

9 2 2 9

5.00000000000000e124

# Question 16  (a)
def get_100_primes():
    n=0
    index = 0
    while (index < 100):
      x = 11*n +3
      n+=1
      if is_prime(x):
          index+=1
          print x,index
get_100_primes()

3 1 47 2 113 3 157 4 179 5 223 6 311 7 421 8 443 9 487 10 509 11 619 12 641 13 751 14 773 15 839 16 883 17 971 18 1103 19 1213 20 1279 21 1301 22 1367 23 1433 24 1499 25 1543 26 1609 27 1697 28 1741 29 1873 30 2027 31 2137 32 2203 33 2269 34 2357 35 2423 36 2467 37 2621 38 2687 39 2731 40 2753 41 2797 42 2819 43 3061 44 3083 45 3259 46 3347 47 3391 48 3413 49 3457 50 3677 51 3853 52 3919 53 4007 54 4051 55 4073 56 4139 57 4271 58 4337 59 4447 60 4513 61 4733 62 4799 63 4909 64 4931 65 5107 66 5261 67 5393 68 5437 69 5503 70 5569 71 5591 72 5657 73 5701 74 5987 75 6053 76 6163 77 6229 78 6317 79 6361 80 6427 81 6449 82 6581 83 6691 84 6779 85 6823 86 6911 87 6977 88 7043 89 7109 90 7219 91 7307 92 7351 93 7417 94 7549 95 7681 96 7703 97 7879 98 7901 99 8011 100

#(b)
def get_1000_primes():
    n=0
    index = 0
    while (index < 1000):
      x = 17*n +13
      n+=1
      if is_prime(x):
          index+=1
          print x,index
get_1000_primes()

13 1 47 2 149 3 251 4 353 5 421 6 523 7 557 8 659 9 727 10 761 11 829 12 863 13 1033 14 1237 15 1373 16 1543 17 1747 18 1951 19 2053 20 2087 21 2393 22 2699 23 2767 24 2801 25 2903 26 2971 27 3209 28 3413 29 3583 30 3617 31 3719 32 3821 33 3889 34 3923 35 4093 36 4127 37 4229 38 4297 39 4603 40 4637 41 4909 42 4943 43 5011 44 5113 45 5147 46 5351 47 5419 48 5521 49 5623 50 5657 51 5827 52 5861 53 6133 54 6269 55 6337 56 6473 57 6779 58 6949 59 6983 60 7187 61 7459 62 7561 63 7867 64 7901 65 8377 66 8513 67 8581 68 8819 69 8887 70 9091 71 9227 72 9397 73 9431 74 9533 75 9601 76 9839 77 9907 78 9941 79 10009 80 10111 81 10247 82 10723 83 10859 84 11131 85 11369 86 11437 87 11471 88 11743 89 11777 90 11981 91 12049 92 12253 93 12457 94 12491 95 12763 96 12899 97 12967 98 13001 99 13103 100 13171 101 13477 102 13613 103 13681 104 14293 105 14327 106 14633 107 14939 108 15313 109 15551 110 15619 111 15823 112 15959 113 16061 114 16231 115 16333 116 16673 117 16741 118 16843 119 16979 120 17047 121 17183 122 17387 123 17489 124 17659 125 17761 126 17863 127 18169 128 18679 129 18713 130 18917 131 19087 132 19121 133 19427 134 19597 135 19699 136 19801 137 19937 138 20107 139 20549 140 20719 141 20753 142 21059 143 21433 144 21467 145 21569 146 21739 147 21773 148 21841 149 21943 150 21977 151 22079 152 22147 153 22283 154 22453 155 22691 156 22861 157 22963 158 23099 159 23167 160 23201 161 23269 162 23371 163 23473 164 23609 165 23677 166 23813 167 24391 168 24527 169 24697 170 24799 171 25037 172 25309 173 25343 174 25411 175 25717 176 25819 177 26227 178 26261 179 26431 180 26669 181 26737 182 26839 183 27043 184 27077 185 27179 186 27281 187 27689 188 27791 189 27893 190 27961 191 28097 192 28403 193 28573 194 28607 195 28879 196 29287 197 29389 198 29423 199 30103 200 30137 201 30307 202 30341 203 30817 204 30851 205 31123 206 31259 207 31327 208 31531 209 31667 210 31769 211 31973 212 32143 213 32381 214 32653 215 32687 216 32789 217 32993 218 33469 219 33503 220 33809 221 33911 222 34183 223 34217 224 34319 225 34421 226 34591 227 34693 228 34897 229 35339 230 35407 231 35509 232 35543 233 35747 234 35951 235 36529 236 36563 237 36767 238 37039 239 37243 240 37277 241 37379 242 37447 243 37549 244 37889 245 37957 246 37991 247 38501 248 38569 249 38603 250 38671 251 38977 252 39079 253 39113 254 39181 255 39317 256 39419 257 39521 258 39623 259 39827 260 39929 261 40031 262 40099 263 40507 264 40609 265 40813 266 40847 267 40949 268 41017 269 41051 270 41221 271 41357 272 41969 273 42071 274 42139 275 42649 276 42683 277 42751 278 42853 279 42989 280 43159 281 43261 282 43397 283 43499 284 43669 285 44111 286 44179 287 44281 288 44383 289 44417 290 44519 291 44587 292 44621 293 44893 294 44927 295 45131 296 45233 297 45403 298 45641 299 46049 300 46219 301 46457 302 46559 303 46831 304 46933 305 47137 306 47681 307 48157 308 48259 309 48463 310 48497 311 48871 312 48973 313 49109 314 49177 315 49211 316 49279 317 49789 318 49823 319 49891 320 49993 321 50129 322 50231 323 50333 324 50503 325 50707 326 50741 327 51047 328 51217 329 51421 330 51659 331 51829 332 52067 333 52237 334 52543 335 52747 336 52883 337 52951 338 53087 339 53189 340 53359 341 53597 342 53699 343 54277 344 54311 345 54413 346 54583 347 54617 348 54787 349 55127 350 55229 351 55331 352 55399 353 55501 354 55603 355 55807 356 56113 357 56249 358 56453 359 56827 360 56929 361 56963 362 57269 363 57847 364 57881 365 58153 366 58391 367 58901 368 59207 369 59377 370 59513 371 59581 372 59887 373 59921 374 60091 375 60397 376 60601 377 60703 378 60737 379 61043 380 61417 381 61519 382 61553 383 61723 384 61757 385 61927 386 61961 387 62131 388 62233 389 62539 390 62743 391 62981 392 63389 393 63559 394 64171 395 64579 396 64613 397 64783 398 64817 399 64919 400 65089 401 65123 402 65293 403 65327 404 65497 405 65599 406 65633 407 65701 408 65837 409 66041 410 66109 411 66347 412 66449 413 66653 414 66721 415 66959 416 67061 417 67129 418 67231 419 67537 420 67741 421 67843 422 67979 423 68489 424 68659 425 68863 426 68897 427 69067 428 69203 429 70019 430 70121 431 70223 432 70393 433 70529 434 70937 435 71039 436 71209 437 71413 438 71549 439 71719 440 71821 441 72161 442 72229 443 72467 444 72671 445 72739 446 72977 447 73079 448 73181 449 73351 450 73453 451 73589 452 74099 453 74167 454 74201 455 74507 456 74609 457 74779 458 75017 459 75289 460 75323 461 75391 462 75527 463 75629 464 75731 465 75833 466 76003 467 76207 468 76343 469 76649 470 76717 471 76819 472 77023 473 77261 474 77431 475 77839 476 78179 477 78553 478 78791 479 78893 480 79063 481 79301 482 79777 483 79811 484 80287 485 80491 486 80627 487 80831 488 80933 489 81001 490 81239 491 81307 492 81409 493 81647 494 81749 495 81817 496 81919 497 81953 498 82021 499 82361 500 82463 501 82531 502 82633 503 82837 504 82939 505 83177 506 83449 507 83653 508 83857 509 83891 510 84061 511 84163 512 84299 513 84401 514 84503 515 84673 516 84809 517 84979 518 85081 519 85523 520 85829 521 85931 522 85999 523 86441 524 86509 525 86951 526 87121 527 87223 528 87257 529 87359 530 87427 531 87631 532 87767 533 87869 534 88379 535 88651 536 89399 537 89501 538 89603 539 89671 540 89909 541 89977 542 90011 543 90793 544 90997 545 91099 546 91303 547 91541 548 91711 549 91813 550 92051 551 92119 552 92153 553 92221 554 92357 555 92459 556 92867 557 93139 558 93241 559 93377 560 93479 561 93581 562 93683 563 93887 564 94057 565 94261 566 94397 567 94771 568 94873 569 94907 570 95009 571 95111 572 95213 573 95383 574 95621 575 95723 576 95791 577 96097 578 96199 579 96233 580 97117 581 97151 582 97423 583 97729 584 97967 585 98443 586 98953 587 99089 588 99191 589 99259 590 99497 591 99667 592 99871 593 100109 594 100279 595 100313 596 100483 597 100517 598 100823 599 101027 600 101197 601 101333 602 101503 603 101537 604 101741 605 102013 606 102149 607 102217 608 102251 609 102523 610 102761 611 102829 612 102931 613 103067 614 103237 615 103577 616 103951 617 104053 618 104087 619 104393 620 104597 621 104801 622 104869 623 104971 624 105107 625 105277 626 105379 627 106297 628 106331 629 106433 630 106501 631 106637 632 106739 633 107351 634 107453 635 107827 636 108439 637 108541 638 108643 639 108677 640 108881 641 108949 642 109357 643 109391 644 109663 645 110479 646 110581 647 110819 648 110921 649 110989 650 111091 651 111227 652 111431 653 111533 654 112111 655 112213 656 112247 657 112349 658 112621 659 112757 660 112859 661 112927 662 113063 663 113131 664 113233 665 113437 666 113539 667 113777 668 113947 669 114083 670 114593 671 114661 672 114797 673 114967 674 115001 675 115613 676 115783 677 115987 678 116089 679 116191 680 116293 681 116531 682 116803 683 117041 684 117109 685 117517 686 117619 687 117721 688 117959 689 118061 690 118163 691 118571 692 118673 693 118843 694 119047 695 119183 696 119489 697 119557 698 119591 699 119659 700 120067 701 120577 702 120713 703 120917 704 121019 705 121189 706 121291 707 121631 708 121937 709 122039 710 122209 711 122651 712 122719 713 122753 714 122957 715 123059 716 123127 717 123229 718 123433 719 123637 720 124147 721 124181 722 124249 723 124351 724 124759 725 124793 726 125201 727 125269 728 125303 729 125371 730 125507 731 125711 732 125813 733 126323 734 126493 735 127037 736 127139 737 127207 738 127241 739 127343 740 127649 741 127717 742 127819 743 127921 744 128159 745 128431 746 128669 747 128873 748 128941 749 129281 750 129553 751 129587 752 129757 753 129893 754 130199 755 130267 756 130369 757 130811 758 130981 759 131321 760 131627 761 131797 762 131899 763 131933 764 132001 765 132103 766 132137 767 132409 768 132511 769 132647 770 132749 771 132817 772 132851 773 132953 774 133157 775 133327 776 133633 777 133769 778 134177 779 134789 780 134857 781 135197 782 135367 783 135469 784 135571 785 135911 786 135979 787 136013 788 136217 789 136319 790 136421 791 136523 792 136693 793 136727 794 136897 795 136999 796 137339 797 137713 798 137849 799 138053 800 138427 801 138461 802 138563 803 138869 804 138937 805 139753 806 139787 807 139991 808 140263 809 140297 810 140603 811 140773 812 140909 813 140977 814 141079 815 141181 816 141283 817 141623 818 141793 819 142031 820 142099 821 142609 822 142711 823 142949 824 143357 825 143527 826 143629 827 143833 828 144037 829 144071 830 144139 831 144173 832 144241 833 144479 834 144751 835 144887 836 145091 837 145193 838 145601 839 145703 840 145771 841 146009 842 146077 843 146213 844 146383 845 146417 846 146519 847 146893 848 147029 849 147097 850 147607 851 147709 852 147743 853 147811 854 148151 855 148457 856 148627 857 148763 858 148933 859 149069 860 149239 861 149341 862 149579 863 149749 864 149953 865 150089 866 150497 867 150769 868 151007 869 151279 870 151381 871 151483 872 151517 873 151687 874 152027 875 152197 876 152231 877 152639 878 152809 879 152843 880 153319 881 153353 882 153421 883 153523 884 153557 885 154067 886 154339 887 154373 888 154543 889 154747 890 154849 891 154883 892 155087 893 155291 894 155461 895 155699 896 155801 897 156719 898 157127 899 157229 900 157433 901 157637 902 157739 903 157841 904 158113 905 158351 906 158419 907 158657 908 158759 909 159167 910 159337 911 159473 912 159541 913 159779 914 160357 915 160663 916 160697 917 160969 918 161071 919 161309 920 161377 921 161411 922 161683 923 161717 924 161921 925 162091 926 162499 927 162601 928 162703 929 162839 930 162907 931 163417 932 163621 933 163859 934 163927 935 164233 936 164267 937 164471 938 164743 939 165049 940 165083 941 165287 942 165457 943 165559 944 166273 945 166409 946 166613 947 166783 948 166919 949 166987 950 167021 951 167191 952 167429 953 167633 954 168109 955 168143 956 168211 957 168347 958 168449 959 169129 960 169639 961 169843 962 170047 963 170081 964 170353 965 170557 966 170761 967 171169 968 171203 969 171271 970 171679 971 171713 972 171917 973 172223 974 172427 975 172597 976 172801 977 173039 978 173141 979 173209 980 173549 981 173617 982 173651 983 173923 984 174263 985 174331 986 174467 987 174569 988 174637 989 174773 990 174943 991 175079 992 175453 993 175691 994 175759 995 175963 996 176201 997 176303 998 176507 999 176609 1000

# (c)
def  distribute_until (n):
    index_1=0
    index_2=0
    index_3=0
    index_4=0
    for x in range(1,n+1):
        if is_prime(x):
            if x % 5 ==1:
                index_1 +=1
            elif x % 5 ==2:
                index_2 +=1
            elif x % 5 ==3:
                index_3 +=1
            elif x % 5 ==4:
                index_4 +=1
    print index_1,index_2,index_3,index_4

distribute_until(10000000)


# (d)
n=100
primes=prime_range(3,n)
count1=0
count3=0
for p in primes:
    if mod(p,4)==1:
        count1 +=1
        count3 +=1
    else:
        count3+=1
    print p,count1,count3


#
from the result, we can see that the number of primes congruent to 3 mod 4 dominates

166104 166212 166230 166032 3 0 1 5 1 2 7 1 3 11 1 4 13 2 5 17 3 6 19 3 7 23 3 8 29 4 9 31 4 10 37 5 11 41 6 12 43 6 13 47 6 14 53 7 15 59 7 16 61 8 17 67 8 18 71 8 19 73 9 20 79 9 21 83 9 22 89 10 23 97 11 24

#question 14
index = 1000000
for x in range(1,index):
    y = x*(x+1)/2
    if is_square(y):
        print x,y,sqrt(y)

1 1 1 8 36 6 49 1225 35 288 41616 204 1681 1413721 1189 9800 48024900 6930 57121 1631432881 40391 332928 55420693056 235416

n = 23423423423423423431111111
12.is_prime()
n=1
for n in range(1,100):
    k = 210*n + 6
    if k.is_prime():
        n=n+1
        print k,n

False

bin = binomial(10,2)
print bin

45

1105.is_prime()

False

continued_fraction((3+sqrt(15))/3)

[2; 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, ...]

continued_fraction(pi)

[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, ...]

continued_fraction((5+sqrt(15))/2)

[4; 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, ...]

continued_fraction(e)

[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, ...]

Error in lines 1-1 Traceback (most recent call last): File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 995, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> NameError: name 'continued_fractions' is not defined

continued_fraction(pi)

[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, ...]