Commits

Shlomi Fish committed e953dbd

Add problem No. 80.

  • Participants
  • Parent commits c96b691

Comments (0)

Files changed (3)

File project-euler/80/Euler80.pm

+package Euler80;
+
+use strict;
+use warnings;
+
+=head1 Project Euler 80 Problem
+
+It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.
+
+The square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475.
+
+For the first one hundred natural numbers, find the total of the digital sums
+of the first one hundred decimal digits for all the irrational square roots.
+
+=cut
+
+use Math::BigInt (":constant", lib => 'GMP');
+
+my $required_digits = 100;
+
+my $margin = 10;
+my $req_digits_with_margin = $required_digits + $margin;
+
+sub square_root
+{
+    my $n = shift;
+
+    my $n_with_digits = $n * (10 ** ($req_digits_with_margin*2));
+
+    my $min = 0;
+    my $max = $n_with_digits;
+    my $mid = (($max+$min) >> 1);
+
+    my $epsilon = $n_with_digits / (10 ** $req_digits_with_margin);
+
+    while (1)
+    {
+        my $square = $mid * $mid;
+
+        # print "Mid = $mid\n";
+        # print "Sq = $square\n";
+
+        if (abs($square - $n_with_digits) <= $epsilon)
+        {
+            return $mid;
+        }
+        elsif ($square > $n_with_digits)
+        {
+            $max = $mid;
+            $mid = (($max+$min) >> 1);
+        }
+        else
+        {
+            $min = $mid;
+            $mid = (($max+$min) >> 1);
+        }
+    }
+}
+
+# print "Result == ", square_root(2), "\n";
+
+1;
+

File project-euler/80/euler-80.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use List::Util qw(sum);
+
+use Euler80;
+
+sub square_root_digits_sum
+{
+    my $n = shift;
+
+    my $result = Euler80::square_root($n);
+    my $first_100 = substr("$result", 0, 100);
+    return sum(split //, $first_100);
+}
+
+my %squares = (map { ($_ * $_) => 1 } (1 .. 100));
+my $total_sum = 0;
+
+for my $n (1 .. 100)
+{
+    print "Reached $n\n";
+    if (! exists($squares{$n}))
+    {
+        $total_sum += square_root_digits_sum($n);
+    }
+    print "Total sum = $total_sum\n";
+}
+print $total_sum, "\n";

File project-euler/80/test88.t

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use Test::More tests => 1;
+
+use List::Util qw(sum);
+
+use Euler80;
+
+{
+    my $result = Euler80::square_root(2);
+    my $first_100 = substr("$result", 0, 100);
+    my $sum = sum(split//, $first_100);
+
+    # TEST
+    is ($sum, 475, "Sum of square root 2 is 475");
+}