Commits

Lars Viklund  committed 6dcc4ad

Solved #75, #80.

  • Participants
  • Parent commits ae06db4

Comments (0)

Files changed (6)

File Windows/Windows.vcxproj

     <ClInclude Include="..\src\072.h" />
     <ClInclude Include="..\src\073.h" />
     <ClInclude Include="..\src\074.h" />
+    <ClInclude Include="..\src\075.h" />
     <ClInclude Include="..\src\076.h" />
     <ClInclude Include="..\src\077.h" />
     <ClInclude Include="..\src\078.h" />
     <ClInclude Include="..\src\079.h" />
+    <ClInclude Include="..\src\080.h" />
     <ClInclude Include="..\src\081.h" />
     <ClInclude Include="..\src\082.h" />
     <ClInclude Include="..\src\083.h" />

File Windows/Windows.vcxproj.filters

     <ClInclude Include="..\src\066.h">
       <Filter>Header Files\Problems</Filter>
     </ClInclude>
+    <ClInclude Include="..\src\075.h">
+      <Filter>Header Files\Problems</Filter>
+    </ClInclude>
+    <ClInclude Include="..\src\080.h">
+      <Filter>Header Files\Problems</Filter>
+    </ClInclude>
   </ItemGroup>
   <ItemGroup>
     <ClCompile Include="..\src\main.cc">
+#include "problem.h"
+#include "primes.h"
+
+struct FBox
+{
+	mpz_class q, q_, p, p_;
+};
+
+std::ostream& operator << (std::ostream& os, FBox const& box)
+{
+	return os << "[" << box.q << " " << box.q_ << "; " << box.p << " " << box.p_ << "]";
+}
+
+void resolveParent(FBox& box)
+{
+	box.q = (box.p_ - box.q_) / 2;
+	box.p = box.q_ + box.q;
+}
+
+// [q q'; p p']
+// [0 x; 0 y] -> [0 x; y 0], [x y; 0 0], [y x; 0 0]
+
+void generateChildren(FBox root, FBox& c1, FBox& c2, FBox& c3)
+{
+	c1.q_ = c2.q = c3.q_ = root.q_;
+	c1.p = c2.q_ = c3.q = root.p_;
+	c1.q = c1.p - c1.q_;
+	c1.p_ = c1.q + c1.p;
+	c2.p = c2.q + c2.q_;
+	c2.p_ = c2.p + c2.q;
+	c3.p = c3.q + c3.q_;
+	c3.p_ = c3.p + c3.q;
+}
+
+enum { LIMIT = 1500000 };
+std::vector<unsigned char> lookup(LIMIT+1);
+
+void update(int a, int b, int c)
+{
+	//std::cerr << boost::format("%d = %d, %d, %d") % (a + b + c) % a % b % c << std::endl;
+	auto& el = lookup[a+b+c];
+	if (el == 0)
+		el = 1;
+	else if (el == 1)
+		el = 2;
+}
+
+bool coprime(int a, int b)
+{
+	static SievedPrimes sp(1000000);
+	std::deque<int> ap, bp;
+	primeFactors(sp, ap, a);
+	primeFactors(sp, bp, b);
+	std::deque<int> common;
+	std::set_intersection(ap.begin(), ap.end(), bp.begin(), bp.end(), std::back_inserter(common));
+	return common.empty();
+}
+
+template <>
+void Problem<75>()
+{
+	mpz_class a, b, c;
+	using namespace boost::assign;
+	mpz_class const limit = LIMIT;
+	int singular = 0;
+#if 1
+	for (int m = 2; m * m < LIMIT; ++m)
+	{
+		for (int n = 1; n < m; ++n)
+		{
+			int a = m * m - n * n;
+			int b = 2 * m * n;
+			int c = m * m + n * n;
+			if (coprime(m, n) && (m % 2) != (n % 2))
+			{
+				for (int k = 1; ; ++k)
+				{
+					if (k * (a + b + c) > limit)
+						break;
+					update(a * k, b * k, c * k);
+				}
+			}
+		}
+	}
+	singular = std::count(lookup.begin(), lookup.end(), 1);
+#else
+#if 1
+	FBox root = { 0, 1, 0, 3 };
+	resolveParent(root);
+	std::deque<FBox> work(1, root);
+	while (work.size())
+	{
+		FBox box = work.front();
+		a = 2 * box.q * box.p;
+		b = box.q_ * box.p_;
+		c = box.q * box.p_ + box.q_ * box.p;
+
+		if (a + b + c <= limit)
+		{
+			update(a.get_ui(), b.get_ui(), c.get_ui());
+		}
+
+		if (box.p < limit || box.p_ < limit || box.q < limit || box.q_ < limit)
+		{
+			FBox c1, c2 ,c3;
+			generateChildren(work.front(), c1, c2, c3);
+			
+			work += c1, c2, c3;
+		}
+
+		work.pop_front();
+	}
+	std::cerr << std::count(lookup.begin(), lookup.end(), 1) << std::endl;
+#else
+	mpz_class lhs, rhs;
+	mpz_class a, b, c;
+	for (mpz_class per = 12; per <= limit; ++per)
+	{
+		if (per % 1000 == 0)
+			std::cerr << (per / limit.get_d()) << std::endl;
+		int count = 0;
+		for (a = 1; a < per - 2; ++a)
+		{
+			for (b = a; a + b < per; ++b)
+			{
+				c = per - b - a;
+				if (a + b < c)
+					continue;
+				lhs = a*a + b*b;
+				rhs = c*c;
+				auto cmp = mpz_cmp(lhs.get_mpz_t(), rhs.get_mpz_t());
+				if (cmp == 0)
+				{
+					++count;
+					if (count > 1)
+						break;
+				}
+				if (cmp > 0)
+					break;
+			}
+			if (count > 1)
+				break;
+		}
+		if (count == 1)
+			++singular;
+	}
+#endif
+#endif
+	std::cout << "There are " << singular << " perimeters with one PPT for perimiters <= " << limit << "." << std::endl;
+}
+#include "problem.h"
+#include "primes.h"
+
+template <>
+void Problem<80>()
+{
+	mpf_set_default_prec(10000);
+	mpf_class n;
+	mpz_class sum;
+	for (int i = 1; i <= 100; ++i)
+	{
+		n = mpf_class(i, 100000);
+		n = i;
+		mpf_sqrt(n.get_mpf_t(), n.get_mpf_t());
+		if (mpf_integer_p(n.get_mpf_t()))
+			continue;
+		mp_exp_t ex;
+		std::string s = n.get_str(ex, 10, 103);
+		s.resize(100);
+		std::cerr << s << " " << s.size() << std::endl;
+		std::for_each(s.begin(), s.end(), [&sum](char ch)
+		{
+			sum += ch - '0';
+		});
+	}
+	std::cerr << "The sum is: " << sum << "." << std::endl;
+}
-#include "066.h"
+#include "080.h"
 
 int main()
 {
-	Problem<66>();
+	Problem<80>();
 }

File src/problem.h

 #include <vector>
 
 #include <boost/assign.hpp>
+#include <boost/format.hpp>
+using namespace boost::assign;
 
 #include "stopwatch.h"