project-euler

https://projecteuler.net/
Log | Files | Refs | README

Euler_64.cpp (1737B)

      1 //#include <boost/multiprecision/cpp_dec_float.hpp>
      2 
      3 #include "Euler.h"
      4 
      5 //namespace mp = boost::multiprecision;
      6 //
      7 //typedef mp::number<mp::cpp_dec_float<500>> cpp_dec_float_500;
      8 //
      9 //int Euler::OddPeriodSquareRoots()
     10 //{
     11 //    int count = 0;
     12 //
     13 //    for (cpp_dec_float_500 i = 1; i <= 10000; ++i)
     14 //    {
     15 //        int sequenceLength = 0;
     16 //
     17 //        cpp_dec_float_500 value = mp::sqrt(i);
     18 //        cpp_dec_float_500 floor = mp::floor(value);
     19 //
     20 //        if (!EulerUtility::isPerfectSquare(i.convert_to<int>()))
     21 //        {
     22 //            bool sequenceDetermined = false;
     23 //            bool sequenceIsOdd = false;
     24 //
     25 //            while (!sequenceDetermined)
     26 //            {
     27 //                value = 1.0 / (value - mp::floor(value));
     28 //
     29 //                if (mp::floor(value) == 2 * floor)
     30 //                {
     31 //                    sequenceDetermined = true;
     32 //                    sequenceIsOdd = sequenceLength + 1 & 1;
     33 //                }
     34 //                else
     35 //                {
     36 //                    ++sequenceLength;
     37 //                }
     38 //            }
     39 //
     40 //            if (sequenceIsOdd)
     41 //            {
     42 //                ++count;
     43 //            }
     44 //        }
     45 //    }
     46 //
     47 //    return count;
     48 //}
     49 
     50 int period(int n)
     51 {
     52     double n2 = sqrtl(n);
     53     int a = n2, p = 0, q = 1, length = 0;
     54 
     55     do
     56     {
     57         length++;
     58         p = a * q - p;
     59         q = ( n - p * p ) / q;
     60         a = ( p + n2 ) /q;
     61     } while ( q != 1 );
     62 
     63     return length;
     64 }
     65 
     66 int Euler::OddPeriodSquareRoots()
     67 {
     68     int odds = 0;
     69 
     70     for (int n = 1; n <= 10000; n++)
     71     {
     72         int n2 = sqrt(n);
     73 
     74         if (n2 * n2 != n)
     75         {
     76             if (period(n) & 1)
     77             {
     78                 odds++;
     79             }
     80         }
     81     }
     82 
     83     return odds;
     84 }