hacker.org

Posted: **Tue Jan 11, 2011 7:58 am**

Anyone remember how they did this one? I forgot.

Posted: **Tue Jan 11, 2011 8:23 am**

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

Posted: **Tue Jan 11, 2011 8:43 am**

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

Posted: **Tue Jan 11, 2011 9:21 am**

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

Posted: **Tue Jan 11, 2011 7:45 pm**

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]

Posted: **Fri Mar 11, 2011 11:26 pm**

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

Posted: **Thu Oct 06, 2011 4:35 pm**

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

Posted: **Fri Oct 07, 2011 7:23 am**

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

Posted: **Sat Oct 08, 2011 12:20 am**

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

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

Posted: **Sat Oct 08, 2011 10:40 am**

cakeeatinghaxxor wrote:
laz0r wrote: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!

Posted: **Sat Jun 29, 2013 5:12 pm**

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)?

Posted: **Tue Apr 01, 2014 10:35 am**

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)));
		}
	}

Posted: **Mon Feb 29, 2016 11:58 am**

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.
*/

Posted: **Wed Mar 02, 2016 10:20 am**

sinan wrote:PARI/GP code

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

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

Posted: **Wed Mar 02, 2016 6:42 pm**

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.

hacker.org

Big Fib

Big Fib

I like Ruby.