Commits

Lars Viklund committed 342c694

Solved problem #104.

Comments (0)

Files changed (5)

Windows/Windows.vcxproj

     <ClInclude Include="..\src\095.h" />
     <ClInclude Include="..\src\099.h" />
     <ClInclude Include="..\src\102.h" />
+    <ClInclude Include="..\src\104.h" />
     <ClInclude Include="..\src\112.h" />
     <ClInclude Include="..\src\061.h" />
     <ClInclude Include="..\src\bignum.h" />

Windows/Windows.vcxproj.filters

     <ClInclude Include="..\src\080.h">
       <Filter>Header Files\Problems</Filter>
     </ClInclude>
+    <ClInclude Include="..\src\104.h">
+      <Filter>Header Files\Problems</Filter>
+    </ClInclude>
   </ItemGroup>
   <ItemGroup>
     <ClCompile Include="..\src\main.cc">
+#include "problem.h"
+
+template <>
+void Problem<104>()
+{
+	mpz_class Fs[3] = { 1, 1, 0 };
+	mpz_class* F = Fs + 0;
+	mpz_class* F_1 = Fs + 1;
+	mpz_class* F_2 = Fs + 2;
+	mpz_class mod("1000000000");
+	mpz_class rem;
+	int k = 1;
+	while (true)
+	{
+		++k;
+		if (k % 1000 == 0)
+			std::cerr << k << std::endl;
+		*F = *F_1 + *F_2;
+		rem = *F % mod;
+		std::string s = rem.get_str();
+		if (s.size() >= 9)
+		{
+			std::set<char> digits(s.begin(), s.begin() + 9);
+			if (digits.size() == 9 && *digits.begin() == '1' && *digits.rbegin() == '9')
+			{
+				s = F->get_str();
+				digits.clear();
+				digits.insert(s.begin(), s.begin() + 9);
+				if (digits.size() == 9 && *digits.begin() == '1' && *digits.rbegin() == '9')
+				{
+					break;
+				}
+			}
+		}
+		std::swap(F, F_1);
+		std::swap(F, F_2);
+	}
+	std::cout << "F_" << k << " is the number." << std::endl;
+}
-#include "080.h"
+#include "104.h"
 
 int main()
 {
-	Problem<80>();
+	Problem<104>();
 }
 #include <boost/format.hpp>
 using namespace boost::assign;
 
-#include "stopwatch.h"
+#include "stopwatch.h"
+#include "primes.h"