Problem Statement

Many people have heard of the Golden ratio, phi (φ). Phi is just one of a series of related ratios that are referred to as the "Metallic ratios". The Golden ratio was discovered and named by ancient civilizations as it was thought to be the most pure and beautiful (like Gold). The Silver ratio was was also known to the early Greeks, though was not named so until later as a nod to the Golden ratio to which it is closely related. The series has been extended to encompass all of the related ratios and was given the general name Metallic ratios (or Metallic means). Somewhat incongruously as the original Golden ratio referred to the adjective "golden" rather than the metal "gold". Metallic ratios are the real roots of the general form equation: where the integer b determines which specific one it is. Using the quadratic equation: Substitute in (from the top equation) 1 for a, -1 for c, and recognising that -b is negated we get: We only want the real root: When we set b to 1, we get an irrational number: the Golden ratio. With b set to 2, we get a different irrational number: the Silver ratio. When the ratio b is 3, it is commonly referred to as the Bronze ratio, 4 and 5 are sometimes called the Copper and Nickel ratios, though they aren't as standard. After that there isn't really any attempt at standardized names. They are given names here on this page, but consider the names fanciful rather than canonical. Note that technically, b can be 0 for a "smaller" ratio than the Golden ratio. We will refer to it here as the Platinum ratio, though it is kind-of a degenerate case. Metallic ratios where b > 0 are also defined by the irrational continued fractions:

So, The first ten Metallic ratios are:

There are other ways to find the Metallic ratios; one, (the focus of this task) is through successive approximations of Lucas sequences. A traditional Lucas sequence is of the form: and starts with the first 2 values 0, 1. For our purposes in this task, to find the metallic ratios we'll use the form: ( P is set to b and Q is set to -1. ) To avoid "divide by zero" issues we'll start the sequence with the first two terms 1, 1. The initial starting value has very little effect on the final ratio or convergence rate. Perhaps it would be more accurate to call it a Lucas-like sequence. At any rate, when b = 1 we get: more commonly known as the Fibonacci sequence. When b = 2:

And so on.

To find the ratio by successive approximations, divide the (n+1)th term by the nth. As n grows larger, the ratio will approach the b metallic ratio. For b = 1 (Fibonacci sequence): It converges, but pretty slowly. In fact, the Golden ratio has the slowest possible convergence for any irrational number.

For each of the first 10 Metallic ratios; b = 0 through 9: Optional, stretch goal - Show the value and number of iterations n, to approximate the Golden ratio to 256 decimal places. You may assume that the approximation has been reached when the next iteration does not cause the value (to the desired places) to change.

Let's start with the solution:

L(0) = 2, L(1) = 1, L(n) = b * L(n-1) + L(n-2) for n >= 2

#include <boost/multiprecision/cpp_dec_float.hpp>
#include <iostream>

const char* names[] = { "Platinum", "Golden", "Silver", "Bronze", "Copper", "Nickel", "Aluminium", "Iron", "Tin", "Lead" };

template<const uint N>
void lucas(ulong b) {
    std::cout << "Lucas sequence for " << names[b] << " ratio, where b = " << b << ":\nFirst " << N << " elements: ";
    auto x0 = 1L, x1 = 1L;
    std::cout << x0 << ", " << x1;
    for (auto i = 1u; i <= N - 1 - 1; i++) {
        auto x2 = b * x1 + x0;
        std::cout << ", " << x2;
        x0 = x1;
        x1 = x2;
    }
    std::cout << std::endl;
}

template<const ushort P>
void metallic(ulong b) {
    using namespace boost::multiprecision;
    using bfloat = number<cpp_dec_float<P+1>>;
    bfloat x0(1), x1(1);
    auto prev = bfloat(1).str(P+1);
    for (auto i = 0u;;) {
        i++;
        bfloat x2(b * x1 + x0);
        auto thiz = bfloat(x2 / x1).str(P+1);
        if (prev == thiz) {
            std::cout << "Value after " << i << " iteration" << (i == 1 ? ": " : "s: ") << thiz << std::endl << std::endl;
            break;
        }
        prev = thiz;
        x0 = x1;
        x1 = x2;
    }
}

int main() {
    for (auto b = 0L; b < 10L; b++) {
        lucas<15>(b);
        metallic<32>(b);
    }
    std::cout << "Golden ratio, where b = 1:" << std::endl;
    metallic<256>(1);

    return 0;
}