Fibonacci Numbers

Post Reply New Topic

9809463517264670023038788649658295091956272699959366635620342487725314342549664567

15872045382336327044129125268014971913825377475586919838578035057243596666433462105

15872 045382 336327 044129 125268 014971 913825 377475 586919 838578 035057 243596 666433 462105 =
5 x 157 x 1 472561 x 92 180471 494753 x 148953 605644 242840 431762 356563 438185 533394 886582 362797 645241

Number of divisors: 32

25681508899600997067167913917673267005781650175546286474198377544968911008983126672

41553554281937324111297039185688238919607027651133206312776412602212507675416588777

15 minutes into factoring....
Factoring 41553 554281 937324 111297 039185 688238 919607 027651 133206 312776 412602 212507 675416 588777 (83 digits)

Limit (B1=1000000; B2=100000000) Curve 335
Digits in factor: >= 15 >= 20 >= 25 >= 30 >= 35 >= 40
Probability: 100% 100% 91% 19% 2% 0%

Aborted after 30 minutes....

67235063181538321178464953103361505925388677826679492786974790147181418684399715449

Looks more and more like I'll have to write a factorization program. My next little programming job when I've got a few minutes spare. Looks like run time could be a serious problem though unless there are way to optimise the analysis? My guess would be to start with a pre-generated list of prime numbers and just iterate through those testing for exact division for each one.

108788617463475645289761992289049744844995705477812699099751202749393926359816304226

108788 617463 475645 289761 992289 049744 844995 705477 812699 099751 202749 393926 359816 304226 =
2 x 13 x 37 x 113 x 421 x 797 x 3457 x 42293 x 54833 x 351 301301 942501 x
1059 009573 400125 529504 166094 598642 626708 730201

Number of divisors: 2048

This is what I am using... http://www.alpertron.com.ar/ECM.HTM

Trial and error division by primes will take forever and a day.

The program on that site will crunch through numbers FAR larger than are being worked with in this thread, it's just that when it is confronted with a huge composite with, let's say, two 40-50 digit prime factors, it will take some time to do that crunching.

BTW, that first one that he bailed on crunched down to (note, I changed it on mine to show five-digit grouping):

49292 54182 06236 09906 58330 25380 07088 75532 65330 87070 10411 58018 62234
83798 54264 29697 = 16 39241 x 15318 50844 38107 74614 61960 36434 86769 x
19630 07348 39095 06000 33407 90295 13730 73993

Number of divisors: 8

Sum of divisors: 49292 57189 09682 51495 95906 03328 05134 48621 77716 27800
47561 45574 71864 87671 88781 89960

Euler's Totient: 49292 51175 02789 68317 20754 47432 09043 02443 92205 91673
53140 58678 68649 84436 20110 69440

Moebius: -1

Sum of squares: a^2 + b^2
a = 61333 42757 84542 00143 91335 27021 50625 79456
b = 34168 18466 85022 87016 68140 48204 52886 74431

(using an Intel Mac-Mini running MacOSX 10.4.11)

Mike

176023680645013966468226945392411250770384383304492191886725992896575345044216019675

Yes, maybe it would take too long to just use prime division. I'd have to write an algorithm too to handle the long numbers as they are way beyond the normal mathematical operations available in .Net. Writing an algorithm to perform addition of numbers of unlimited size was easy but I can't think of an easy way to program division of such big numbers. In the good old days of assembly programming I had some bright ideas for shortcuts with mathematical operations, so for example to multiply by 10 I'd shift the bits left three times (ROL) then once with the orginal number then add the results and the answer would drop out really fast. 10 x = x * 8 + x * 2

284812298108489611757988937681460995615380088782304890986477195645969271404032323901....Finally found something on OEIS

284812 298108 489611 757988 937681 460995 615380 088782 304890 986477 195645 969271 404032 323901 =
13 885829 x 20511 004284 187109 877126 452996 177685 582573 434310 785829 998805 054825 748557 857369

Number of divisors: 4

460835978753503578226215883073872246385764472086797082873203188542544616448248343576

745648276861993189984204820755333242001144560869101973859680384188513887852280667477

1206484255615496768210420703829205488386909032955899056732883572731058504300529011053

1952132532477489958194625524584538730388053593825001030592563956919572392152809678530

85 digits?

3158616788092986726405046228413744218774962626780900087325447529650630896453338689583

5110749320570476684599671752998282949163016220605901117918011486570203288606148368113

8269366108663463411004717981412027167937978847386801205243459016220834185059487057696