This contest is about calculating Fibonacci numbers via simple arithmetic operations as quickly as possible.
Fibonacci Numbers
The sequence 0,1,1,2,3, 5, 8, 13, 21, 34, 55 ... is formed by adding the first two numbers (0,1) to get 1, then repeatedly adding the current last two numbers to get the next in the sequence. 1+1 =2, 2+1 =3, 3+ 2 = 5, 5+3 = 8 etc. If you continue this a very long time, the ratio of two Fibonacci numbers n and n+ 1 fn+1/fn converges i.e. gets closer to the value 1.61804 known as phi. Interestingly if you subtract 1 from it, you get the same as phi-1. i.e. phi-1 = 1/phi).
Phi also crops up as the value for the golden mean. If a painting canvas has the proportions 1 to phi (ie 10 cm on one side and 16.18-04 along the other) it is considered the most pleasing ratio! Phi also occurs in nature a lot.
However the Fibonacci sequence jumps a lot of numbers so what if we started with different digits at the start say 2,2 or 3,4. So in this challenge there are five Fibonacci numbers that your entry must find as fast as possible using any means necessary. After that you must locate the nearest prime number to each of the calculated Fibonacci numbers. The prime number can be greater or smaller if the number itself is not a prime number.
Each number is defined as a,b,c where a,b,c are all positive ints. a and b are the first two digits and c is the ordinal i.e. the number in the sequence. E.g. where a is the first, b is the second. Eg for a=0, b= 1, c = 6 gives the value 5 because the 6th number in that sequence is 5. 0,1,1,2,3,5. 5 is also prime so it's the answer. For a=3,b=4, c= 7 gives the value 43 because it's the 7th number in that sequence. 3,4,7,11,18,29,47. 47 is also a prime number so it would be the correct answer.
- 11,26,999
- 3,6,705
- 2,5,456
- 3,7,234
- 3,8,80
The Output
Output a file output.txt in the same location as your exe. It should contain 5 lines with each line holding the value of the prime number nearest the Fibonacci number. The sixth line should be the average time taken (see below)
Timing Code
Please time from the start of the calculation until just before the output file is opened for writing then output the five values and then the time taken as the very first line of the output file. If your code is very fast then repeat it in a loop enough times so the total elapsed time is between 1 and 5 seconds. If your program did 500 iterations in 2 seconds then the average time would be 2/500 secs.
Intermediate Results
Stole wins by less than a 10th of a second. One other entry had a flaw and the author asked me to withdraw it.
- St0le - C# Time(secs) = 2.631 St0le
- Reid and Jeff (USA, 22) - C# Time(secs) = 2.72832760036538
Rules
This is for glory only. About.com does not permit prizes to be given.Please submit your source code and the output file to the cplus.guide@about.com?subject=Programming Challenge 36 email address with the subject line Programming Challenge 36.
It must compile with Open Watcom, Microsoft Visual C++ 2005/2008 Express Edition/Microsoft Visual Studio 2003/2005/2008 or Borland Turbo C++ Explorer, Microsoft Visual C# 2005/2008 Express Edition or GCC/G++. If it doesn't compile, it can't be run so is automatically disqualified.
Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is June 30 2010.
The top ten entries will be listed, judged purely on points. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.
Past Programming Contests
- An index of Every Past Programming Contest on this site
