Shlomi Fish avatar Shlomi Fish committed a8a4570

#108: made progress with the analysis.

Comments (0)

Files changed (1)

project-euler/108/euler-108.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+=head1 DESCRIPTION:
+
+In the following equation x, y, and n are positive integers:
+
+1/x + 1/y = 1/n
+
+For n = 4 there are exactly three distinct solutions:
+
+* 1/5 + 1/20 = 1/4
+
+* 1/6 + 1/12 = 1/4
+
+* 1/8 + 1/8 = 1/4
+
+What is the least value of n for which the number of distinct solutions exceeds one-thousand?
+
+=head1 ANALYSIS
+
+ny + nx = xy
+
+n (x+y) = xy
+
+n = xy / (x+y)
+
+x,y > n
+
+1/y = 1/n-1/x = (x-n)/nx
+
+y = nx/(x-n)
+
+If t = x-n ; x = t + n
+
+y = n*(t+n) / t = n + [ n^2 / t ]
+
+t \in [1 .. n]
+
+2*3
+=cut
+
+# use Math::GMP ':constant';
+
+use integer;
+
+for (my $n = 1_000; ;$n++)
+{
+    my $count = 0;
+    my $n_sq = $n * $n;
+
+    for my $t (1 .. $n)
+    {
+        if (! ($n_sq % $t))
+        {
+            $count++;
+        }
+    }
+    print "Reached $n [$count]\n";
+    if ($count > 1_000)
+    {
+        print "N = $n\n";
+        exit(0);
+    }
+}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.