An astronomical number

[raymond]

I was toying with some math principals the other day. It's amazing how what seems to be some 'simple' input can turn out such extreme numbers.

The first part had to do with the digit sum of numbers (in the decimal system). For example, the digit sum of 31495 would be 3+1+4+9+5=22. However, there is an infinite variety of numbers having that same digit sum. The main idea was to find the smallest number having a given digit sum. In this case, the smallest one would be 499 (4+9+9=22).

The next part had to do with the Fibonacci sequence. For those not familiar with it, it starts with 0 and 1 as the first two numbers in the sequence. The next number is obtained by adding the previous two numbers, giving:
0,1,1,2,3,5,8,13,21,34,55,...
55 being the tenth one and denoted as F₁₀.

Although F₉₀ is not a small number by any means, it still fits within the 64-bit binary format. But, the smallest number which would have a digit sum equal to F₉₀ would be so big that if you wanted to print it on a strip of paper with letter-size width, 100 characters per line, 100 lines per foot, that strip of paper would reach well beyond the orbit of Pluto. AND, if you had a super fast printer which could produce at a rate of 100 feet/second, it would take some 4.5 million years to finish the job!!!

[daydreamer]

The first part had to do with the digit sum of numbers (in the decimal system). For example, the digit sum of 31495 would be 3+1+4+9+5=22. However, there is an infinite variety of numbers having that same digit sum. The main idea was to find the smallest number having a given digit sum. In this case, the smallest one would be 499 (4+9+9=22).

The next part had to do with the Fibonacci sequence. For those not familiar with it, it starts with 0 and 1 as the first two numbers in the sequence. The next number is obtained by adding the previous two numbers, giving:
0,1,1,2,3,5,8,13,21,34,55,...
55 being the tenth one and denoted as F₁₀.

are you sure,isnt all numbers that add up to 22 some factorial 1!,2!,3!,4!,5!,6!,7!,8!,9! ?
used for 21 black jack game probability ?

fibonacci
discovered they appear alot in nature,for example sunflower seeds is placed in one fibonnaci "rows" and following fibonnaci "columns",its actually curved
they had second biggest prime number finder on tv documentary about maths,he found it by have his computer crunch numbers for 5 years
but fibonnaci done with ascii,endless adc until out of memory
 

[daydreamer]

I was just curious so I tested with 128bit DECIMAL type and

Code: [Select]

139th fibonnaci 5009530124805839113932791626129 digits

[raymond]

I confirm your value for F₁₃₉, with my mega-million decimal type.

For your info (and others' as well), here's my value for the first Fibonacci number to reach 100 digits, i.e. F₄₇₆:
1344719667586153181419716641724567886890850696275767987106294472017884974410332069524504824747437757

And, F₄₇₈₂ would be the first one to reach 1000 digits.

[daydreamer]

thanks raymond
wonder how fast lots of digits fibonnaci can be made to go?

 

[daydreamer]

I made an attempt with fibonnaci ,allocate few million bytes memory,but a bug made it crash
was aiming for find the first over 1000000 fibonnaci number
so I instead went for get it right with
.data
f1 db 1024 dup("0")
cr db 0

[raymond]

Just for curiosity, F₄₇₈₄₇ would be the first one to have 10000 digits. That took an entire 0.5 second on my old laptop.

Based on previous results, my estimate would be close to F₄₇₈₄₉₅ to get the first one with 100000 digits, and may take between 30 seconds and a minute. But, going for the million digits may increase the time to well over an hour and could be just before arriving at F_4785000.

I'm tempted.


Amazing! It is actually F₄₇₈₄₉₅ being the first to reach 100000 digits, and it took 53 seconds. Now for the million!!!!

[daydreamer]

I am going for 1million,Unrolled loops
F_2100000

[raymond]

It only took a shade less than an hour and a half, about 100 times longer than for the 100,000th. F_4784969 is the first one to reach the million digits.

The leading 7 digits are 1072739 and the least significant 8 digits would be 78405156.

I don't think Hutch would appreciate a posting of the whole number in this thread!

[daydreamer]

Great raymond 
Biggest over 500000 to be able To zip here?
Biggest possible in 32bit 1billion in size?
I wanna know how to get bigger many million stack?

fibonnaci nr 2002

with two print two fibonnaci in loop

fibonnaci millis  1297

with print buffer that holds two fibonnaci nr in loop

fibonnaci millis  735

without print,only final print

fibonnaci millis  16

[jack]

@raymond
I wrote my own arbitrary precision floating point routines and calculated fibonacci(4784969) by using the formula ( ( (1+sqrt(5))/2 )^n - ( (1-sqrt(5))/2 )^n )/sqrt(5)
it took 25 minutes 18 seconds but the last 10 digits are 8405156269 I verified my result with Maple

[raymond]

Hi Jack,

Congratulations for your patience. Those Fibonacci numbers get to be pretty large pretty fast. BTW, I did mine with binary coded decimals which is 100% accurate.

Two points.

(i) Floating point computations with the given formula will only give you the eventual size of the Fibonacci number with some idea of the first few digits of that number, but certainly not any idea of the last few digits. Your accuracy would depend heavily on the accuracy of the sqrt(5) value which would need to be accurate to the 5,000,000th digit as a minimum to be used for computing F_4784969 with the required accuracy.
Remember that a computation is only accurate to the accuracy level of the least accurate of its components

(ii) Whenever you mention the value of an F number, you should always add as reference which F value you would consider equal to 3; i.e. is it F₂ (as starting with 1,2,3), F₃ (as with 1,1,2,3), or F₄) as with 0,1,1,2,3).

[jack]

hello raymond
I am an enthusiast of FreeBasic, I do most of my recreational programming it
I found a Fibonacci program on my HD created by Eric Olson, he implements basic BigNum routines to calculate the Fibonacci numbers using identities
     F(2k) = F(k)[2F(k+1)-F(k)]
   F(2k+1) = F(k+1)^2+F(k)^2
   F(2k+2) = F(k+1)[2F(k)+F(k+1)]
he later presents an optimized version that he uses in the program
     F(2k) = F(k)[2F(k+1)-F(k)]
   F(2k+1) = F(k+1)[2F(k+1)-F(k)]+(-1)^(k+1)
   F(2k+1) = F(k)[2F(k)+F(k+1)]+(-1)^(k)
   F(2k+2) = F(k+1)[2F(k)+F(k+1)]
on my PC to calculate Fibonacci(47849721) -- which gives a 10 million digits number, takes less than 6 minutes
you can find he's program in the BASIC folder at https://github.com/ZiCog/fibo_4784969 Eric's program is named fibo.bas
note that you need to change the constant nmax in line 28 to the desired precision/8 + a little extra
first 10 digits 8490335471 and the last 10 digits 8041866146
here's a zip file with the number https://u.pcloud.link/publink/show?code=XZU69rXZb6UTE84AQUQKcoikuxpQxjVjy407

an interesting read https://www.whitman.edu/documents/Academics/Mathematics/2015/Final%20Project%20-%20Shatkin.pdf

[daydreamer]

Great jack 
Thanks raymond, made me realise I might need check reciprocal constants used to speed up div replace by mul, if I lose precision with replace it with 1/constant
Interesting read about overflow exception handler,wish I could write my own that handle decimal128 overflow with add second decimal variable same way adc= add with carry

[daydreamer]

I can confirm that formula needs very accurate sqrt(5),because I tested calculate it with the usual fp types
or maybe I have a bug?
How far can you go with help of raymonds 9999 digits sqrt program ?

What works best with formula ? Round up or down?