 |
CS 3723 Programming Languages |
Factor Fibonacci Numbers
| |
| Successive Fibonacci Numbers and Their Prime Factorization | |
|---|---|
| Python Program | |
# fibfact.py: succ fib #'s and factors
import sys
import math # for sqrt
def bound(k): # best bound
return int(math.sqrt(k))
def fib_fact(m):
f = 1 # F(2)
g = 2 # F(3)
n = 3 # index of fib #, init 3
while m - n: # keep going through m fib #s
sys.stdout.write(str(n) + "\t" + str(g) + "\t")
j = g # init g = F(3), then iter through fib #s
# based on value of g, set x so that x*x > g,
# or, x > sqrt(g). Only check factors up to x
x = bound(j)
d = 2 # initial trial divisor, after mults by 2,
# will switch to 3, then use 3, 5, 7, 9, etc
t = 1 # means d is a trial divisor
while t:
if j % d:
e = 0
else:
e = 1
while e: # d is a divisor, divide it out
j = j/d
# did a division, recalculate magic x
x = bound(j)
sys.stdout.write(str(d) + ' ')
if j% d:
e = 0
else:
e = 1
if j - 1: # keep going until j is 1
t = 1
else:
t = 0
if d - 2:
if d < x: # inside bound
d = d + 2
else:
d = j # terminate
else:
d = 3
# if d is 2, change d to 3, else incr d by 2
# eventually d == j, so d divides into j,
# and will have last factor.
# j == 1 will set t == 0, which terms while
# above also checks for bound. d = j termis
sys.stdout.write("\n")
n = n + 1 # next index
h = f + g # next fib number
f = g # adjusting previous fib #s
g = h # ditto
m = raw_input( "-->" )
fib_fact(int(m))
| 3 2 2 4 3 3 5 5 5 6 8 2 2 2 7 13 13 8 21 3 7 9 34 2 17 10 55 5 11 11 89 89 12 144 2 2 2 2 3 3 13 233 233 14 377 13 29 15 610 2 5 61 16 987 3 7 47 17 1597 1597 18 2584 2 2 2 17 19 19 4181 37 113 20 6765 3 5 11 41 21 10946 2 13 421 22 17711 89 199 23 28657 28657 24 46368 2 2 2 2 2 3 3 7 23 25 75025 5 5 3001 26 121393 233 521 27 196418 2 17 53 109 28 317811 3 13 29 281 29 514229 514229 30 832040 2 2 2 5 11 31 61 31 1346269 557 2417 32 2178309 3 7 47 2207 33 3524578 2 89 19801 34 5702887 1597 3571 35 9227465 5 13 141961 36 14930352 2 2 2 2 3 3 3 17 19 107 37 24157817 73 149 2221 38 39088169 37 113 9349 39 63245986 2 233 135721 40 102334155 3 5 7 11 41 2161 41 165580141 2789 59369 42 267914296 2 2 2 13 29 211 421 43 433494437 433494437 44 701408733 3 43 89 199 307 45 1134903170 2 5 17 61 109441 46 1836311903 139 461 28657 47 2971215073 2971215073 48 4807526976 2 2 2 2 2 2 3 3 7 23 47 1103 49 7778742049 13 97 6168709 50 12586269025 5 5 11 101 151 3001 51 20365011074 2 1597 6376021 52 32951280099 3 233 521 90481 53 53316291173 953 55945741 54 86267571272 2 2 2 17 19 53 109 5779 55 139583862445 5 89 661 474541 56 225851433717 3 7 7 13 29 281 14503 57 365435296162 2 37 113 797 54833 58 591286729879 59 19489 514229 59 956722026041 353 2710260697 |
60 1548008755920 2 2 2 2 3 3 5 11 31 41 61 2521 61 2504730781961 4513 555003497 62 4052739537881 557 2417 3010349 63 6557470319842 2 13 17 421 35239681 64 10610209857723 3 7 47 1087 2207 4481 65 17167680177565 5 233 14736206161 66 27777890035288 2 2 2 89 199 9901 19801 67 44945570212853 269 116849 1429913 68 72723460248141 3 67 1597 3571 63443 69 117669030460994 2 137 829 18077 28657 70 190392490709135 5 11 13 29 71 911 141961 71 308061521170129 6673 46165371073 72 498454011879264 2 2 2 2 2 3 3 3 7 17 19 23 107 103681 73 806515533049393 9375829 86020717 74 1304969544928657 73 149 2221 54018521 75 2111485077978050 2 5 5 61 3001 230686501 76 3416454622906707 3 37 113 9349 29134601 77 5527939700884757 13 89 988681 4832521 78 8944394323791464 2 2 2 79 233 521 859 135721 79 14472334024676221 157 92180471494753 80 23416728348467685 3 5 7 11 41 47 1601 2161 3041 81 37889062373143906 2 17 53 109 2269 4373 19441 82 61305790721611591 2789 59369 370248451 83 99194853094755497 99194853094755497 84 160500643816367088 2 2 2 2 3 3 13 29 83 211 281 421 1427 85 259695496911122585 5 1597 9521 3415914041 86 420196140727489673 6709 144481 433494437 87 679891637638612258 2 173 514229 3821263937 88 1100087778366101931 3 7 43 89 199 263 307 881 967 89 1779979416004714189 1069 1665088321800481 90 2880067194370816120 2 2 2 5 11 17 19 31 61 181 541 109441 91 4660046610375530309 13 13 233 741469 159607993 92 7540113804746346429 3 139 461 4969 28657 275449 93 12200160415121876738 2 557 2417 4531100550901 94 19740274219868223167 2971215073 6643838879 95 31940434634990099905 5 37 113 761 29641 67735001 96 51680708854858323072 2 2 2 2 2 2 2 3 3 7 23 47 769 1103 2207 3167 97 83621143489848422977 193 389 3084989 361040209 98 135301852344706746049 13 29 97 6168709 599786069 99 218922995834555169026 2 17 89 197 19801 18546805133 100 354224848179261915075 3 5 5 11 41 101 151 401 3001 570601 101 573147844013817084101 743519377 770857978613 102 927372692193078999176 2 2 2 919 1597 3469 3571 6376021 103 1500520536206896083277 519121 5644193 512119709 104 2427893228399975082453 3 7 103 233 521 90481 102193207 105 3928413764606871165730 2 5 13 61 421 141961 8288823481 106 6356306993006846248183 953 55945741 119218851371 107 10284720757613717413913 1247833 8242065050061761 108 16641027750620563662096 2 2 2 2 3 3 3 3 17 19 53 107 109 5779 11128427 109 26925748508234281076009 827728777 32529675488417 110 43566776258854844738105 5 11 11 89 199 331 661 39161 474541 111 70492524767089125814114 2 73 149 2221 1459000305513721 112 114059301025943970552219 3 7 7 13 29 47 281 14503 10745088481 113 184551825793033096366333 677 272602401466814027129 114 298611126818977066918552 2 2 2 37 113 229 797 9349 54833 95419 115 483162952612010163284885 5 1381 28657 2441738887963981 116 781774079430987230203437 3 59 347 19489 514229 1270083883 117 1264937032042997393488322 2 17 233 29717 135721 39589685693 118 2046711111473984623691759 353 709 8969 336419 2710260697 119 3311648143516982017180081 13 1597 159512939815855788121 120 5358359254990966640871840 2 2 2 2 2 3 3 5 7 11 23 31 41 61 241 2161 2521 20641 | |