Problem #14

Här kommer min lösning till problem 14. Här stötte jag på problem då mina 32-bit int's inte räckte till på min plattform. Därav uint64_t, då talet växte till ganska stora tal (dvs större än 4294967296).

#include <iostream>
#include <utility>

template <typename T>
inline T next_seq(T n)
{
  return n & 1 ? (n * 3) + 1 : n / 2;
}

template <typename T>
inline T chain_length(T n)
{
  T i;
  for (i = 1; n != 1; ++i)
    n = next_seq(n);
  return i;
}

int main(int argc, char *argv[])
{
  std::pair<int64_t, uint64_t> chain_pair;
  for (uint64_t i = 2; i < 1000000; ++i)
  {
    uint64_t len = chain_length(i);
    if (len > chain_pair.first)
      chain_pair = std::make_pair(len, i);
  }

  std::cout << "Answer is "
            << chain_pair.first
            << " for n = "
            << chain_pair.second
            << std::endl;

  return 0;
}

Det finns en ganska bra optimering att göra in chain_length() genom att ha en hashtabell med n som nyckel och längden som värde för att inte göra onödigt jobb. Men med brute force på min MacBook går det <1s så det känns ganska onödigt.

Godnatt! Snart dags för en ny arbetsvecka.