Project Euler Forum

Posted: **Mon Oct 11, 2010 11:00 pm**

The very short solutions are the pure math solutions. The longer ones are the usual programming solutions.

Here's the thing though: they are short because some clever mathematician made all the needed reductions by himself, not by a compiler.

He's also aware of many (perhaps obscure) numerical methods that are probably out of hand for the typical programmer. The tools most readily available to programmers are iteration and branching. With them, they are able to quickly hack away a solution that, while not as bright nor elegant nor as fast as the math one, will do its job. The math solution typically demands far greater knowledge of math and more time to elaborate. I'd say most brute-force programming solutions take far less time to code and run than a mathematician factorizing his formulas by hand. Final result looks shorter, but demanded far more time to produce...

what do you think?

Posted: **Mon Oct 11, 2010 11:05 pm**

Well, I would argue that for this problem, the math approach is fairly well known - certainly at least most programmers will have heard of the Fibonacci series, unlike many of the concepts in the later problems. There are probably also clever programming approaches to this problem, but why bother? You'd be better off posting them on the problems that really need them, and don't have any simple mathematical reductions.

Posted: **Tue Apr 19, 2011 6:08 am**

The problem definition contains a contradiction:

F1 = 1 and F2 = 1

...but later:

F1 = 1
F2 = 1

This caused my solution to be off by one until I spotted the mistake

Posted: **Tue Apr 19, 2011 6:22 am**

And what's the mistake?

Posted: **Wed May 11, 2011 3:40 am**

stijn263 wrote:put in the index number

Wow I totally thought it was the 1000-digit number itself, not the index. I literally spent hours trying to do this in C (having already solved it in Perl), by trying to use 1000-character strings to store the numbers and adding it. What a stupid waste of time!

Posted: **Tue May 31, 2011 8:13 pm**

Hi, I've been having problems with this one... I set up my code. It correctly calculated that the first term to hit 2 digits was the 7th term,
the first to hit 3 digits was the 12th term,
the first to hit 4 digits was the 17th term,
the first to hit 5 digits was the 21th term,
and the first to hit 6 digits was the 26th term;

all of which I verified by hand. The data is set up as an array of digits, so I can exceed size limitations of integers. The digit it lists as the first to have 1000 digits has 1000 digits with no leading zeroes. I don't see why mine could possibly be wrong, so I can only assume that 38,000 others were. But, putting my large ego aside for a second, I very well could be wrong. What do you guys think went wrong?

Posted: **Sun Jun 05, 2011 10:07 pm**

tinkles, have you checked that you're putting the index, not the number itself? Those first five results of yours are correct and there's no way 38,000+ people were wrong...

Posted: **Sat Jul 13, 2013 10:04 am**

Hi,

I have been solving Problem 25 just a few minutes ago and I noticed two things that, I believe, could be improved in its text.

1) it is said that F1=1 and F2=2, but just after, in the example, F1=F2=1 so F12 is the first 3-digits terms instead of F11. Maybe some consistency could be added.

2) the question itself: "What is the first term in the Fibonacci sequence to contain 1000 digits?" does not seem that clear (this may be because english is not my mother tong, though) and I first gave the value of the first 1000-digits term rather than its number.

By the way, thanks a lot for the website, I discovered it a few days ago and I like it very much.

Posted: **Sat Jul 13, 2013 6:39 pm**

@Lowije

We realize you are new to this forum. You should have noticed the **Clarifications on Project Euler Problems** subject and anything related to such problems should be included in there. Your post has thus been moved accordingly. Also please note that problem numbers under 100 are padded with leding 0s to make them 3-digit numbers.

Back to your comments,

it is said that F1=1 and F2=2, but just after, in the example, F1=F2=1 ...

I don't know where you got your problem description but mine dates back many many years and states F1=1 and F2=1. You will notice that someone else made a post previously suggesting he made the same interpretation mistake as you may have made.

... and I first gave the value of the first 1000-digits term rather than its number.

How did you ever succeed in entering 1001 digits in that small answer box?

Posted: **Mon Jul 15, 2013 2:06 pm**

Thanks for the answers, and sorry for having originaly posted my message in the wrong place.

rayfil wrote:
... and I first gave the value of the first 1000-digits term rather than its number.
How did you ever succeed in entering 1001 digits in that small answer box?

I just copy/pasted it... maybe not all the digits have been taken into account, I don't know.

Posted: **Fri Apr 24, 2015 4:47 am**

Admin please consider rewording this question. It's not ambiguous, it's simply wrong. It quite clearly gives many examples of terms and then asks for a term which means the 1000 digit number. The only way to work out that you need to put in its index is by trial and error.

Posted: **Fri Apr 24, 2015 12:38 pm**

nmarkroberts wrote:Admin please consider rewording this question. It's not ambiguous, it's simply wrong. It quite clearly gives many examples of terms and then asks for a term which means the 1000 digit number. The only way to work out that you need to put in its index is by trial and error.

"... for a term which means the 1000 digit number"

The problem asks which is the first term in the Fibonacci sequence to contain 1000 digits.

If by "trial and error" you mean:
"look at F₁₃ Does it contain 1000 digits?
"look at F₁₄ Does it contain 1000 digits?
"look at F₁₅ Does it contain 1000 digits?

and so forth, then one could describe the problem as trial and error.

However, I pictured the problem as "run out the Fibonacci sequence and find the first term to contain 1000 digits."

Generating the terms in the Fibonacci sequence is an easy task. Thus, one might consider the programming problem to be one of finding a way to deal with very large numbers.

In any event, the problem is not ambiguous, not is it wrong.

Tom

Posted: **Fri Apr 24, 2015 2:15 pm**

I can see where the perception of ambiguity might come from, but don't think anything needs to change.

On its own, the question "What is the first term in the Fibonacci sequence to contain 1000 digits" might reasonably be interpreted as asking for the value of that term.

But the preceding sentence says "The 12th term, F12, is the first term to contain three digits". I think that makes it clear that in the context of this problem, the expected answer to questions of this form is the index, not the value.

Posted: **Fri Apr 24, 2015 3:34 pm**

The index ## is not such a term, F## would be such a term.

Posted: **Sat Apr 25, 2015 9:47 pm**

The problem statement has been updated.

Posted: **Mon Jun 06, 2022 9:51 am**

I noticed something. If we consider how many Fibonacci numbers are made of n digits, there seem to be a pattern:

Code: Select all

1 2 3 5 8 		1-digit, 5 number
13 21 34 55 89 		2-digits, 5 numbers
144 233 377 610 				3-digits, 5 numbers
987 1597 2584 4181 6765 				4-digits, 4 numbers
10946 17711 28657 46368 75025 		5-digits, 5 numbers
121393 196418 317811 514229 832040 			6-digits, 5 numbers
1346269 2178309 3524578 5702887 9227465 			7-digits, 5 numbers
14930352 24157817 39088169 63245986 					8-digits, 4 numbers
102334155 165580141 267914296 433494437 701408733 		9-digits, 5 numbers
1134903170 1836311903 2971215073 4807526976 7778742049 		10-digits, 5 numbers
12586269025 20365011074 32951280099 53316291173 86267571272 		11-digits, 5 numbers
139583862445 225851433717 365435296162 591286729879 956722026041 		12-digits, 5 numbers
1548008755920 2504730781961 4052739537881 6557470319842 		13-digits, 4 numbers
10610209857723 17167680177565 27777890035288 44945570212853 72723460248141 			14-digits, 5 numbers
117669030460994 190392490709135 308061521170129 498454011879264 806515533049393 		15-digits, 5 numbers
1304969544928657 2111485077978050 3416454622906707 5527939700884757 8944394323791464 		16-digits, 5 numbers
14472334024676221 23416728348467685 37889062373143906 61305790721611591 99194853094755497 		17-digits, 5 numbers
160500643816367088 259695496911122585 420196140727489673 679891637638612258 		18-digits, 4 numbers
1100087778366101931 1779979416004714189 2880067194370816120 4660046610375530309 
7540113804746346429			19-digits, 5 numbers

Does anyone know if this is a real mathematical thing?

Posted: **Mon Jun 06, 2022 11:18 am**

@Liquid25677, I don't see a way to answer that question which doesn't include a major spoiler for this problem, so I suggest that you solve the problem and then see whether the discussion thread which you unlock answers your question.

Project Euler Forum

Problem 025

Re: Problem 025

Re: Problem 025

Re: Problem 025

Re: Problem 025

Re: problem 25

Re: Problem 025

Re: Problem 025

Some remarks on Problem 25

Re: Some remarks on Problem 25

Re: Problem 025

Re: Problem 025

Re: Problem 025

Re: Problem 025

Re: Problem 025

Re: Problem 025

Re: Problem 025

Re: Problem 025