# HG changeset patch # User Shlomi Fish # Date 1344883617 -10800 # Node ID b7cdd3901768da38cbbb5def4a93330737f4666b # Parent 60b53c6cbd0f18c1c8791495a45f761ec44fb2d4 Solved Euler Project problem #139. diff --git a/project-euler/75/75-take3.pl b/project-euler/139/139-take1.pl copy from project-euler/75/75-take3.pl copy to project-euler/139/139-take1.pl --- a/project-euler/75/75-take3.pl +++ b/project-euler/139/139-take1.pl @@ -5,22 +5,18 @@ =head1 DESCRIPTION -It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples. +Let (a, b, c) represent the three sides of a right angle triangle with integral length sides. It is possible to place four such triangles together to form a square with length c. -12 cm: (3,4,5) -24 cm: (6,8,10) -30 cm: (5,12,13) -36 cm: (9,12,15) -40 cm: (8,15,17) -48 cm: (12,16,20) +For example, (3, 4, 5) triangles can be placed together to form a 5 by 5 square with a 1 by 1 hole in the middle and it can be seen that the 5 by 5 square can be tiled with twenty-five 1 by 1 squares. -In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles. +However, if (5, 12, 13) triangles were used then the hole would measure 7 by 7 and these could not be used to tile the 13 by 13 square. -120 cm: (30,40,50), (20,48,52), (24,45,51) +Given that the perimeter of the right triangle is less than one-hundred million, how many Pythagorean triangles would allow such a tiling to take place? +=cut -Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed? +=head1 Keywords -Note: This problem has been changed recently, please check that you are using the right parameters. +Pythagoras, Euler's Formula, Hypoteneuse =cut @@ -36,17 +32,18 @@ return gcd(\$m,\$n % \$m); } -my \$limit = 1_500_000; +my \$limit = 100_000_000; my \$half_limit = (\$limit >> 1); -my \$verdicts = ""; - my \$hypotenuse_lim = int(\$limit/2); my \$major_side_limit = int(\$limit/2); # Euclid's formula my \$m_limit = int(sqrt(\$hypotenuse_lim)); + +my \$count = 0; + for my \$m (2 .. \$m_limit) { if (\$m % 1000 == 0) @@ -66,17 +63,11 @@ last N_LOOP; } - if (vec(\$verdicts, \$half_sum, 2) != 2) + my (\$aa, \$bb, \$cc) = (\$m*\$m-\$n*\$n, 2*\$m*\$n, \$m*\$m+\$n*\$n); + + if (\$cc % abs(\$bb-\$aa) == 0) { - my \$sum_product = 0; - - while ((\$sum_product += \$half_sum) < \$half_limit) - { - if (vec(\$verdicts, \$sum_product, 2) != 2) - { - vec(\$verdicts, \$sum_product, 2)++; - } - } + \$count += int( \$half_limit / \$half_sum ); } } } @@ -86,14 +77,5 @@ } } -my \$count = 0; -foreach my \$sum_idx ((12>>1) .. (\$limit>>1)) -{ - if (vec(\$verdicts, \$sum_idx, 2) == 1) - { - \$count++ - } -} - print "Count = \$count\n";