fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <stdint.h>
  4. #include <limits>
  5.  
  6. class Collatz
  7. {
  8.   private:
  9.     typedef unsigned short elem_t;
  10.     typedef std::vector<elem_t> vector_t;
  11.     static const elem_t MAX = 65535;
  12.     uint64_t s;
  13.     vector_t v;
  14.   public:
  15.     Collatz(vector_t::size_type s) : s(s), v(s + 1, MAX) { v[1] = 0; }
  16.     uint64_t get_at_f(uint64_t i)
  17.     {
  18.       bool inrange = i <= s;
  19.       if (inrange && (v[i] != MAX))
  20.       {
  21.         return v[i];
  22.       }
  23.       else
  24.       {
  25.         auto result = get_at_f( ((i % 2 == 0) ? i : 3 * i + 1) / 2 ) + 1;
  26.         if (inrange)
  27.         {
  28.           v[i] = result;
  29.         }
  30.         return result;
  31.       }
  32.      }
  33. };
  34.  
  35. int main()
  36. {
  37.   const std::size_t size = 1000000;
  38.   Collatz x(size);
  39.   uint64_t cur_max = 0;
  40.   uint64_t cur_max_i = 0;
  41.   for (uint64_t i = 1; i <= size; ++i)
  42.   {
  43.     auto result = x.get_at_f(i);
  44.     if (result >= cur_max)
  45.     {
  46.       cur_max = result;
  47.       cur_max_i = i;
  48.     }
  49.   }
  50.   std::cout << cur_max_i << ' ' << cur_max << std::endl;
  51. }
Success #stdin #stdout 0.03s 2888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
837799 329
https://ideone.com/MxeFl
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!