Big Fib

[DaymItzJack]

Anyone remember how they did this one? I forgot.

[CodeX]

you could use a closed expression function to get the answer or just use mathematica/wolfram alpha

[DaymItzJack]

I've been trying to use wolframalpha to get the answer again, it's not working.

[CodeX]

you could drop mathematica code into wolfram alpha to get the answer completely but I found it gave me both a closed expression function for the Fibonacci sequence and also the value of F1500000 which happens to be 313482 digits

[laz0r]

Mathematica code, somewhat bloated...

Code: Select all

ToString/@(IntegerDigits[Fibonacci[1500000]][[#]]&/@Select[Range[313481],Mod[#,20000]==1&])//StringJoin

the simple explanation being:
Find the digits which give 1 in mod 20000
Take this digit of Fibonacci[1500000]
Convert these to strings
Join them up

Unfortunately, this code is too complex for WolframAlpha. On my computer, this code takes almost two seconds; a couple of optimisations like precomputing Fibonacci[1500000] gives a speed increase to 0.000131 seconds.

Code: Select all

With[{n = Fibonacci[1500000] // IntegerDigits}, 
 ToString /@ (n[[#]] & /@ Range[1, 313481, 20000]) // StringJoin]

[gsjfoe]

i find that fib in python...
it took 15 minutes...

[cakeeatinghaxxor]

Took approx. 199.827814006 s with Ruby.

Code: Select all

def fibn(m)
	if m==0
		out=0 
	else
		n=1    
		fibn=1
		fibnMinus1=0
		while n<m do
			n=n+1
			h=fibn+fibnMinus1
			fibnMinus1=fibn
			fibn=h
		end
		out=fibn
	end
	return out
 end

def efind x
	k=fibn(x).to_s
	s=""
	for i in 0..k.length-1
		if i%20000==0 then
			s+=k[i].to_s
		end
	end
	return s
end

puts efind 1500000

Using some Fib-identities can shorten run time even more: http://en.wikipedia.org/wiki/Fibonacci_ ... identities

[laz0r]

Actually,
StringTake[ToString@Fibonacci[1500000], {1, -1, 20000}]
is more concise

[cakeeatinghaxxor]

Actually,
StringTake[ToString@Fibonacci[1500000], {1, -1, 20000}]
is more concise

Using Mathematica/Wolfram Alpha always looks like kind of cheating to me :p

[laz0r]

Actually,
StringTake[ToString@Fibonacci[1500000], {1, -1, 20000}]
is more concise

Using Mathematica/Wolfram Alpha always looks like kind of cheating to me :p

I suppose it sort of is a command like Solve or Integrate is far too powerful for us mere mortals!

[Ingrater]

Isn't the challange description wrong?

It says it wants the 1500000th member of the fibonaci sequence. Because the fibonaci sequence starts at zero that would be fib(1499999) but the correct answer is fib(1500000)?

[Hippo]

omitting mult ... standard matrix 2x2 multiplication

Code: Select all

	private static void fibcalc(){
		Result [0][0]=BigInteger.ONE; Result [0][1]=BigInteger.ZERO;
		Result [1][0]=BigInteger.ZERO; Result [1][1]=BigInteger.ONE;
		PowerTwo [0][0]=BigInteger.ZERO; PowerTwo [0][1]=BigInteger.ONE;
		PowerTwo [1][0]=BigInteger.ONE; PowerTwo [1][1]=BigInteger.ONE;
		int power = 1500000;
		int powertwo = 1;
		while (powertwo<=power) {
			if ((power&powertwo)!=0) {
				mult(Result,PowerTwo);
			}
			powertwo<<=1;
			mult(PowerTwo,PowerTwo);
		}
		String resultstr = Result[0][1].toString();
		for(int i=0;i<resultstr.length();i+=20000) {
			write("fib2.txt",String.valueOf(resultstr.charAt(i)));
		}
	}

[sinan]

PARI/GP code took less than a second:

Code: Select all

big_fib(N=30,STEP=7)=
{
	local(n=fibonacci(N),d,nd=ceil(log(n)/log(10)),nt=nd\STEP,ynd,str="");
	ynd=STEP*nt+1;
	n\=10^(nd-ynd);
	forstep(i=1,ynd,STEP,
		d=n%10;
		n\=10^STEP;
		str=concat(Str(d),str);
	);
	str
}

/*
? big_fib(1500000,20000)
%53 = "1161269686625383"
? ##
  ***   last result computed in 920 ms.
*/

[AMindForeverVoyaging]

PARI/GP code

Never heard of that before. Good to know it exists, could be quite useful.

https://en.wikipedia.org/wiki/PARI/GP

[eulerscheZahl]

pari/gp is great for calculating with big numbers - I even solved bigger fib directly with pari.

Another program is sage (sagemath.org): it's actually python, but with math related library functions like equation solving, integral, ... It uses pari for some calculations.

Code: Select all

fibonacci(1500000).str()[::20000]

Gives the answer in a few milliseconds.