9
\$\begingroup\$

Write some code that takes a single non-negative integer n and outputs the nth power of Phi (ϕ, the Golden Ratio, approximately 1.61803398874989) with the same number of decimal digits as the nth Fibonacci number.

Your code must produce the correct sequence of digits for all inputs up to at least 10 (55 decimal digits). The output must be human-readable decimal. You may choose whether to round the last digit to the closest value, or truncate the value. Please specify which one your code uses.

n and output, up to 10, rounding down:

 0   1
 1   1.6
 2   2.6
 3   4.23
 4   6.854
 5  11.09016
 6  17.94427190
 7  29.0344418537486
 8  46.978713763747791812296
 9  76.0131556174964248389559523684316960
10 122.9918693812442166512522758901100964746170048893169574174

n and output, up to 10, rounding to the closest value:

 0   1
 1   1.6
 2   2.6
 3   4.24
 4   6.854
 5  11.09017
 6  17.94427191
 7  29.0344418537486
 8  46.978713763747791812296
 9  76.0131556174964248389559523684316960
10 122.9918693812442166512522758901100964746170048893169574174

The 7th Fibonacci number is 13, so the output for n=7, ϕ7, has 13 decimal places. You must not truncate trailing zeros that would display too few digits; see output for 6 in the first table, which ends in a single zero to keep the decimal precision at 8 digits.

Maybe as a bonus, say what the highest number your program can correctly output is.

\$\endgroup\$
  • \$\begingroup\$ What about languages that can't handle that many decimal places? I got a 24 byte Pyth solution here that only works till n=7, since I can't display more than 15 decimal places. Should I post it anyway? \$\endgroup\$ – Denker Feb 5 '16 at 8:19
  • \$\begingroup\$ @DenkerAffe Sure, you can post it but with a note saying that it's not valid because it can't do the last three test cases. It might be inspiration for someone to add precision to your answer! \$\endgroup\$ – CJ Dennis Feb 5 '16 at 21:04
3
\$\begingroup\$

dc, 26 bytes

99k5v1+2/?^d5v/.5+0k1/k1/p

Due to the initial precision of 99 digits after the comma, this will work up yo input 11. A dynamic (or higher static) precision is possible, but would elevate the byte count.

Test cases

$ for ((i = 0; i < 11; i++)) { dc -e '99k5v1+2/?^d5v/.5+0k1/k1/p' <<< $i; }
1
1.6
2.6
4.23
6.854
11.09016
17.94427190
29.0344418537486
46.978713763747791812296
76.0131556174964248389559523684316960
122.9918693812442166512522758901100964746170048893169574174

How it works

Since the desired output is φn, we can calculate the the Fibonacci number F(n) as ⌊φn ÷ √5 + 0.5⌋ with little additional effort.

99k                         Set the precision to 99.
   5v                       Compute the square root of 5.
     1+                     Add 1.
       2/                   Divide by 2.
                            This pushes the golden ratio.
         ?                  Read the input from STDIN.
          ^                 Elevate the golden ratio to that power.
           d                Push a copy.
            5v/             Divide it by the square root of 5.
               .5+          Add 0.5.
                  0k        Set the precision to 0.
                    1/      Divide by 1, truncating to the desired precision.
                            This pushes F(n).
                      k     Set the precision to F(n).
                       1/   Divide by 1, truncating to the desired precision.
                         p  Print.
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 50 bytes

N[GoldenRatio^#,2^#]~NumberForm~{2^#,Fibonacci@#}&

Basic solution. Rounds to the nearest value. Still verifying the highest value that won't make my computer run out of memory. Input 32 works, but it takes 45 minutes and uses 16GiB of RAM. However, given infinite time and memory, this could theoretically run for any value.

\$\endgroup\$
  • 1
    \$\begingroup\$ Would you post the output please? I need to cheat and use your output to add the last few test cases. Which way are you rounding? Down or to nearest? "Infinite resources" is good enough. I don't require that you run out of memory! \$\endgroup\$ – CJ Dennis Feb 4 '16 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.