hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Big Fib
Goto page 1, 2, 3  Next
 
Reply to topic    hacker.org Forum Index » Challenges View previous topic
View next topic
Big Fib
Author Message
rmplpmpl



Joined: 26 Oct 2008
Posts: 113
Location: Germany

Post Big Fib Reply with quote
Ok, another problem I have - I want to believe I got the correct number and the answer but it is not accepted.

Anyway, could please someone tell me if the number I have is correct, starting with 11742003035506558... and ending with ...32895630172796932853738956168354898000000

the six zeros at the end tell me that I might have a glitch in my computation...
Sun Nov 02, 2008 1:01 am View user's profile Send private message
MerickOWA



Joined: 07 Apr 2008
Posts: 182

Post Re: Big Fib Reply with quote
rmplpmpl wrote:
Ok, another problem I have - I want to believe I got the correct number and the answer but it is not accepted.

Anyway, could please someone tell me if the number I have is correct, starting with 11742003035506558... and ending with ...32895630172796932853738956168354898000000

the six zeros at the end tell me that I might have a glitch in my computation...


Can't be a prime and end in zeros Wink It would trivially be divisible by 2 or 5 Wink
Sun Nov 02, 2008 2:05 am View user's profile Send private message
the_impaler



Joined: 30 Apr 2008
Posts: 61

Post Re: Big Fib Reply with quote
[quote="MerickOWA"]

Can't be a prime and end in zeros ;) It would trivially be divisible by 2 or 5 ;)[/quote]
How do you know that it "can't be a prime" ? 13 is prime and so is 233 and there are more.
Of course you know because you have found it but off the bat it's hard to say.
That would probably give adum another crazy number crunching idea like "find the prime fib that has last 100 digits matching pi in reverse"
Sun Nov 02, 2008 2:28 am View user's profile Send private message
sigi



Joined: 26 Oct 2008
Posts: 37

Post Reply with quote
I have no idea what Merick is talking about... anyway: you're supposed to give every 20,000th digit of the 1.5 millionth Fibonacci number -- and your answer is having a string of zeroes at the end. I would like to say that it's extremely unlikely that you answer is correct.

I'm not a number theorist but I'm guessing that the answer to this challenge pretty much amounts to a random number -- meaning that every digit is roughly equally likely.

There's not that much that can go wrong with this challenge (or the coding involved). Just re-check your code.
Sun Nov 02, 2008 6:50 am View user's profile Send private message
rmplpmpl



Joined: 26 Oct 2008
Posts: 113
Location: Germany

Post Reply with quote
sigi wrote:
I have no idea what Merick is talking about... anyway: you're supposed to give every 20,000th digit of the 1.5 millionth Fibonacci number -- and your answer is having a string of zeroes at the end. I would like to say that it's extremely unlikely that you answer is correct.

I'm not a number theorist but I'm guessing that the answer to this challenge pretty much amounts to a random number -- meaning that every digit is roughly equally likely.

There's not that much that can go wrong with this challenge (or the coding involved). Just re-check your code.


Yupp, I know that 20,000th digit part and I could extract THAT part easily, but since I obviously got the wrong number, the resulting digits were wrong, too. Bah, back to computation.


Thumbs up to these challenges who make me learning stuff!
Sun Nov 02, 2008 10:53 am View user's profile Send private message
gfoot



Joined: 05 Sep 2007
Posts: 269
Location: Brighton, UK

Post Reply with quote
I just recalculated it - I get the same ending as you, but a different beginning. Maybe you calculated the 1499999th instead. Smile
Sun Nov 02, 2008 11:34 am View user's profile Send private message
MerickOWA



Joined: 07 Apr 2008
Posts: 182

Post Re: Big Fib Reply with quote
the_impaler wrote:
How do you know that it "can't be a prime" ? 13 is prime and so is 233 and there are more.
Of course you know because you have found it but off the bat it's hard to say.
That would probably give adum another crazy number crunching idea like "find the prime fib that has last 100 digits matching pi in reverse"


It can't be prime if the last digit is a zero. Any number that ends in zero is divisible by 10, and thus NOT prime.

Same way I can trivially prove that every prime (except 2 and 5) must end with either 1, 3, 7 or 9. If it ended in 0,2,4,6,8 it would be even and thus divisible by 2. If it ends in 0 or 5 its divisible by 5.
Mon Nov 03, 2008 5:58 am View user's profile Send private message
MerickOWA



Joined: 07 Apr 2008
Posts: 182

Post Reply with quote
Ok ignore me, I was thinking of a different problem were you have to calculate a big prime number Wink fibonacci numbers are different sorry Wink
Mon Nov 03, 2008 6:02 am View user's profile Send private message
eike42



Joined: 26 Oct 2008
Posts: 15

Post Reply with quote
I have the same value... either its correct, or we're using the same codebase:

Used this one: http://www.bigzaphod.org/fibonacci/

My own perl script was too damn slow and I was to lazy to write C code Wink
Mon Nov 03, 2008 8:23 am View user's profile Send private message
rmplpmpl



Joined: 26 Oct 2008
Posts: 113
Location: Germany

Post Reply with quote
eike42 wrote:
I have the same value... either its correct, or we're using the same codebase:

Used this one: http://www.bigzaphod.org/fibonacci/

My own perl script was too damn slow and I was to lazy to write C code Wink


hm, I used another tool (Formula One IDE) for computation of the number and a generic tool to extract the digits asked for. Length of "my" number is 67170, so the solution had four digits.
Mon Nov 03, 2008 10:43 am View user's profile Send private message
snibril



Joined: 26 Oct 2008
Posts: 31

Post Reply with quote
fib(1500000) can be computed in under 5min on a Phenom 9850 with bc under linux and has more than 300000 digits.
Mon Nov 03, 2008 12:14 pm View user's profile Send private message
hoki



Joined: 28 Oct 2008
Posts: 5

Post Reply with quote
I'm kinda stuck here. First I computed what I thought was the right number using bc. Then I noticed it asked for the 1,500,000th member of the Fibonacci sequence instead of fib(1.5m), so I recalculated. Still my solutions don't seem to be correct.

My number starts with "19768781" and ends with "345698". It has 313481 digits.

Did I get it right that you want the first digit, then take a 20,000-step, that digit (20001th) and so on? Or do you want the first and the k*20,0000th digits, with k = 1,2,...

Bye,
hoki
Wed Nov 05, 2008 2:51 pm View user's profile Send private message
snibril



Joined: 26 Oct 2008
Posts: 31

Post Reply with quote
It starts with 129... and ends with ...000
Wed Nov 05, 2008 3:00 pm View user's profile Send private message
brazzy



Joined: 07 Nov 2008
Posts: 14
Location: Munich, Germany

Post Reply with quote
I think one reason why many people are having problems is that some definitions of the Fibonacci sequence have it start with 0 and 1, and others start with 1 and 1, so that the numbering is one off between those two definitions.
Thu Dec 04, 2008 6:29 pm View user's profile Send private message Visit poster's website
abc



Joined: 02 Nov 2008
Posts: 12

Post Fib 1 = 1 Reply with quote
Hi!
I think everybody should know that the first fib=1 in this challenge. (not 0)
Still got the same problems...

abc
Fri Dec 05, 2008 7:57 pm View user's profile Send private message
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Challenges All times are GMT
Goto page 1, 2, 3  Next
Page 1 of 3

 
Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.