Commits

Shlomi Fish committed 0f9184f

A faster algorithm.

Courtesy of the Encyclopedia of Integer Sequences and the Wikipedia. Still
not fast enough.

Comments (0)

Files changed (1)

project-euler/78/78-2.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use IO::Handle;
+
+no warnings 'recursion';
+
+use 5.010;
+
+use List::Util qw(sum min);
+use Math::BigInt (":constant", lib => 'GMP');
+
+STDOUT->autoflush(1);
+
+my @p;
+
+sub p_k_n
+{
+    my ($k, $n) = @_;
+
+    if ($k > $n)
+    {
+        return 0;
+    }
+    elsif ($k == $n)
+    {
+        return 1;
+    }
+    else
+    {
+        return ($p[$n][$k] ||= (p_k_n($k+1, $n) + p_k_n($k,$n-$k)));
+    }
+}
+
+my $n = 2;
+N_LOOP:
+while (1)
+{
+    my $p = p_k_n(1, $n);
+    print "N = $n ; V = $p\n";
+    if ($p % 1_000_000 == 0)
+    {
+        last N_LOOP;
+    }
+}
+continue
+{
+    $n++;
+}
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.