Commits

Shlomi Fish committed 8dedb22

Commit the Project Euler programs I have so far.

They were not version controlled until now.

  • Participants

Comments (0)

Files changed (138)

project-euler/1.lisp

+; This aims to be a solution for:
+; http://projecteuler.net/index.php?section=problems&id=1
+(asdf:oos 'asdf:load-op :iterate)
+(use-package :iterate)
+
+(defun sum1 (n)
+  (iter (for i from 1 to n)
+        (sum (if (or (= (mod i 3) 0) (= (mod i 5) 0)) i 0) into mysum)
+        (finally (return mysum))))
+
+(defun display-result ()
+  (format t "Total is ~A~%" (sum1 (1- 1000))))
+          
+
+

project-euler/1.rb

+#!/usr/bin/ruby
+
+sum = 0
+((1...1000).select {|i| (((i % 3) == 0) || ((i%5) == 0)) }).each {|i| sum += i}
+puts sum

project-euler/10/10-zerothorder.hs

+primes :: [Integer]
+primes = 2 : filter isPrime [3, 5 ..]
+    where
+        -- only check divisibility of the numbers less than the square root of n
+        isPrime n = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes
+        divides n p = n `mod` p == 0
+ 
+result = sum $ takeWhile (< 2000000) primes
+ 
+main = do putStrLn( show result )
+
+

project-euler/10/10.c

+/*
+ * =====================================================================================
+ *
+ *       Filename:  10.c
+ *
+ *    Description:  
+ *
+ *        Version:  1.0
+ *        Created:  28/11/09 14:08:11
+ *       Revision:  none
+ *       Compiler:  gcc
+ *
+ *         Author:  YOUR NAME (), 
+ *        Company:  
+ *
+ * =====================================================================================
+ */
+
+#include <string.h>
+#include <math.h>
+#include <stdint.h>
+#include <stdio.h>
+
+#define limit 2000000
+int8_t bitmask[(limit+1)/8];
+
+int main(int argc, char * argv[])
+{
+    int p, i;
+    int mark_limit;
+    long long sum = 0;
+
+    memset(bitmask, '\0', sizeof(bitmask));
+    mark_limit = (int)sqrt(limit);
+    
+    for (p=2 ; p <= mark_limit ; p++)
+    {
+        if (! ( bitmask[p>>3]&(1 << (p&(8-1))) ) )
+        {
+            /* It is a prime. */
+            sum += p;
+            for (i=p*p;i<=limit;i+=p)
+            {
+                bitmask[i>>3] |= (1 << (i&(8-1)));
+            }
+        }
+    }
+    for (; p <= limit; p++)
+    {
+        if (! ( bitmask[p>>3]&(1 << (p&(8-1))) ) )
+        {
+            sum += p;
+        }
+    }
+
+    printf("%lli\n", sum);
+
+    return 0;
+}

project-euler/10/10.hi

Binary file added.

project-euler/10/10.hs

+primes :: Integer -> [Integer]
+
+primes how_much = sieve [2..how_much] where
+         sieve (p:x) = 
+             p : (if p <= mybound
+                 then sieve (remove (p*p) x)
+                 else x) where
+             remove what (a:as) | what > how_much = (a:as)
+                                | a < what = a:(remove what as)
+                                | a == what = (remove (what+step) as)
+                                | a > what = a:(remove (what+step) as)
+             remove what [] = []
+             step = (if (p == 2) then p else (2*p)) 
+         sieve [] = []
+         mybound = ceiling(sqrt(fromIntegral how_much))
+
+--main = print (length (primes 1000000))
+main = print (sum (primes 2000000))

project-euler/10/10.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use Math::BigInt lib => 'GMP';
+
+my $limit = 2_000_000;
+
+my $primes_bitmask = "";
+
+my $loop_to = int(sqrt($limit));
+my $sum = 0;
+my $total_sum = Math::BigInt->new('0');
+
+for my $p (2 .. $loop_to)
+{
+    if (vec($primes_bitmask, $p, 1) == 0)
+    {
+        $sum += $p;
+
+        my $i = $p * $p;
+
+        while ($i < $limit)
+        {
+            vec($primes_bitmask, $i, 1) = 1;
+        }
+        continue
+        {
+            $i += $p;
+        }
+
+    }
+}
+
+for my $p ($loop_to .. $limit)
+{
+    if (vec($primes_bitmask, $p, 1) == 0)
+    {
+        if (($sum += $p) > (1 << 30))
+        {
+            $total_sum += $sum;
+            $sum = 0;
+        }
+    }
+}
+
+$total_sum += $sum;
+print "$total_sum\n";
+

project-euler/10/10_2.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use Math::BigInt lib => 'GMP';
+
+my $limit = 2_000_000;
+
+my $primes_bitmask = "";
+
+my $loop_to = int(sqrt($limit));
+my $sum = 0;
+my $total_sum = Math::BigInt->new('0');
+
+for my $p (2 .. $loop_to)
+{
+    if (vec($primes_bitmask, $p, 1) == 0)
+    {
+        $sum += $p;
+
+        my $i = $p * $p;
+
+        while ($i < $limit)
+        {
+            vec($primes_bitmask, $i, 1) = 1;
+        }
+        continue
+        {
+            $i += $p;
+        }
+
+    }
+}
+
+my $p = $loop_to-1;
+
+while (($p += 2) < $limit)
+{
+    if (vec($primes_bitmask, $p, 1) == 0)
+    {
+        if (($sum += $p) > (1 << 30))
+        {
+            $total_sum += $sum;
+            $sum = 0;
+        }
+    }
+}
+
+$total_sum += $sum;
+print "$total_sum\n";
+

project-euler/10/10_3.c

+/*
+ * =====================================================================================
+ *
+ *       Filename:  10.c
+ *
+ *    Description:  
+ *
+ *        Version:  1.0
+ *        Created:  28/11/09 14:08:11
+ *       Revision:  none
+ *       Compiler:  gcc
+ *
+ *         Author:  YOUR NAME (), 
+ *        Company:  
+ *
+ * =====================================================================================
+ */
+
+#include <string.h>
+#include <math.h>
+#include <stdint.h>
+#include <stdio.h>
+
+#define limit 2000000
+int8_t bitmask[(limit+1)/8];
+
+int main(int argc, char * argv[])
+{
+    int p, i;
+    int mark_limit, half_limit;
+    long long sum = 0;
+
+    memset(bitmask, '\0', sizeof(bitmask));
+    mark_limit = (int)sqrt(limit);
+    
+    for (p=2 ; p <= mark_limit ; p++)
+    {
+        if (! ( bitmask[p>>3]&(1 << (p&(8-1))) ) )
+        {
+            /* It is a prime. */
+            sum += p;
+            for (i=p*p;i<=limit;i+=p)
+            {
+                bitmask[i>>3] |= (1 << (i&(8-1)));
+            }
+        }
+    }
+
+    /* Bump to the next odd number */
+    p = p+((p&0x1)^0x1);
+
+    p >>= 1;
+
+    half_limit = (limit >> 1);
+
+    for (; p < half_limit; p++)
+    {
+        if (! ( bitmask[p>>2]&(1 << (( (p << 1) & (8-1) )+1)) ) )
+        {
+            sum += (p<<1)+1;
+        }
+    }
+
+    printf("%lli\n", sum);
+
+    return 0;
+}

project-euler/10/10_half.c

+/*
+ * =====================================================================================
+ *
+ *       Filename:  10.c
+ *
+ *    Description:  
+ *
+ *        Version:  1.0
+ *        Created:  28/11/09 14:08:11
+ *       Revision:  none
+ *       Compiler:  gcc
+ *
+ *         Author:  YOUR NAME (), 
+ *        Company:  
+ *
+ * =====================================================================================
+ */
+
+#include <string.h>
+#include <math.h>
+#include <stdint.h>
+#include <stdio.h>
+
+#define limit 2000000
+int8_t bitmask[(limit+1)/8/2];
+
+int main(int argc, char * argv[])
+{
+    int half, p, i;
+    int half_limit;
+    int loop_to;
+    long long sum = 0 + 2;
+
+    memset(bitmask, '\0', sizeof(bitmask));
+
+    loop_to=(((int)(sqrt(limit)))>>1);
+    half_limit = (limit-1)>>1;
+    
+    for (half=1 ; half <= loop_to ; half++)
+    {
+        if (! ( bitmask[half>>3]&(1 << (half&(8-1))) ) )
+        {
+            /* It is a prime. */
+            p = (half << 1)+1;
+            sum += p;
+            for (i = ((p*p)>>1) ; i < half_limit ; i+=p )
+            {
+                bitmask[i>>3] |= (1 << (i&(8-1)));
+            }
+        }
+    }
+
+    for( ; half < half_limit ; half++)
+    {
+        if (! ( bitmask[half>>3]&(1 << (half&(8-1))) ) )
+        {
+            sum += (half<<1)+1;
+        }
+    }
+
+    printf("%lli\n", sum);
+
+    return 0;
+}
+

project-euler/10/10_half.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use Math::BigInt lib => 'GMP';
+
+my $limit = 2_000_000;
+
+my $primes_bitmask = "";
+
+my $loop_to = (int(sqrt($limit)))>>1;
+my $half_limit = ($limit-1)>>1;
+
+my $sum = 0+2;
+my $total_sum = Math::BigInt->new('0');
+
+for my $half (1 .. $loop_to)
+{
+    if (vec($primes_bitmask, $half, 1) == 0)
+    {
+        my $p = (($half<<1)+1);
+        $sum += $p;
+
+        my $i = ($p * $p)>>1;
+
+        while ($i < $limit)
+        {
+            vec($primes_bitmask, $i, 1) = 1;
+        }
+        continue
+        {
+            $i += $p;
+        }
+
+    }
+}
+
+
+for my $half ($loop_to .. $half_limit)
+{
+    if (vec($primes_bitmask, $half, 1) == 0)
+    {
+        if (($sum += (($half<<1)+1)) > (1 << 30))
+        {
+            $total_sum += $sum;
+            $sum = 0;
+        }
+    }
+}
+
+$total_sum += $sum;
+print "$total_sum\n";
+

project-euler/10/10_micro_opt.c

+/*
+ * =====================================================================================
+ *
+ *       Filename:  10.c
+ *
+ *    Description:  
+ *
+ *        Version:  1.0
+ *        Created:  28/11/09 14:08:11
+ *       Revision:  none
+ *       Compiler:  gcc
+ *
+ *         Author:  YOUR NAME (), 
+ *        Company:  
+ *
+ * =====================================================================================
+ */
+
+#include <string.h>
+#include <math.h>
+#include <stdint.h>
+#include <stdio.h>
+
+#define limit 2000000
+int8_t bitmask[(limit+1)/8];
+
+int main(int argc, char * argv[])
+{
+    int p, i;
+    int mark_limit, half_limit;
+    long long sum = 0;
+
+    memset(bitmask, '\0', sizeof(bitmask));
+    mark_limit = (int)sqrt(limit);
+    
+    for (p=2 ; p <= mark_limit ; p++)
+    {
+        if (! ( bitmask[p>>3]&(1 << (p&(8-1))) ) )
+        {
+            /* It is a prime. */
+            sum += p;
+            for (i=p*p;i<=limit;i+=p)
+            {
+                bitmask[i>>3] |= (1 << (i&(8-1)));
+            }
+        }
+    }
+
+    /* Bump to the next odd number */
+    p = p+((p&0x1)^0x1);
+
+    p >>= 1;
+
+    half_limit = (limit >> 1);
+
+    for (; p < half_limit; p++)
+    {
+        if (! ( bitmask[p>>2]&(1 << (( (p << 1) & (8-1) )+1)) ) )
+        {
+            sum += (p<<1)+1;
+        }
+    }
+
+    printf("%lli\n", sum);
+
+    return 0;
+}

project-euler/10/Makefile

+TARGETS = haskell_mine haskell_zeroth c_mine c_mine_micro_opt c_mine_half
+
+all: $(TARGETS)
+
+haskell_mine: 10.hs
+	ghc -o $@ $<
+
+haskell_zeroth: 10-zerothorder.hs
+	ghc -o $@ $<
+
+c_mine: 10.c
+	gcc -O2 -o $@ -Wall $<
+
+c_mine_micro_opt: 10_micro_opt.c
+	gcc -O2 -o $@ -Wall $<
+
+c_mine_half: 10_half.c
+	gcc -O2 -o $@ -Wall $<
+
+mystrip:
+	strip $(TARGETS)
+
+clean:
+	rm -f $(TARGETS) *.o
+
+bench:
+	perl benchmark.pl 2>&1 | tee bench_results.txt

project-euler/10/bench_results.txt

+Benchmark: timing 500 iterations of c_mine, c_mine_half, c_mine_micro_opt...
+    c_mine: 15 wallclock secs ( 0.02 usr  0.13 sys + 12.20 cusr  2.37 csys = 14.72 CPU) @ 33.97/s (n=500)
+c_mine_half: 10 wallclock secs ( 0.02 usr  0.13 sys +  6.75 cusr  2.30 csys =  9.20 CPU) @ 54.35/s (n=500)
+c_mine_micro_opt: 15 wallclock secs ( 0.02 usr  0.13 sys + 11.34 cusr  2.36 csys = 13.85 CPU) @ 36.10/s (n=500)
+Benchmark: timing 20 iterations of haskell_mine, haskell_zeroth, perl-10, perl-10_half...
+haskell_mine: 135 wallclock secs ( 0.00 usr  0.00 sys + 134.71 cusr  0.70 csys = 135.41 CPU) @  0.15/s (n=20)
+haskell_zeroth: 310 wallclock secs ( 0.00 usr  0.01 sys + 307.61 cusr  1.15 csys = 308.77 CPU) @  0.06/s (n=20)
+   perl-10: 95 wallclock secs ( 0.00 usr  0.01 sys + 94.14 cusr  0.30 csys = 94.45 CPU) @  0.21/s (n=20)
+perl-10_half: 73 wallclock secs ( 0.00 usr  0.00 sys + 71.34 cusr  0.36 csys = 71.70 CPU) @  0.28/s (n=20)

project-euler/10/benchmark.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use Benchmark qw(:all) ;
+
+sub get_c_prog_kv
+{
+    my $prog = shift;
+    my $cmd = "./$prog > /dev/null";
+
+    return ($prog => sub { system($cmd); });
+}
+
+sub get_perl_prog_kv
+{
+    my $prog = shift;
+    my $cmd = "perl $prog.pl > /dev/null";
+
+    return ("perl-$prog" => sub { system($cmd); });
+}
+
+timethese(
+    500,
+    {
+        (
+            map { get_c_prog_kv($_) } 
+            (qw(
+                c_mine c_mine_micro_opt c_mine_half 
+            ))
+        ),
+    }
+);
+
+timethese(
+    20,
+    {
+        (
+            map { get_c_prog_kv($_) } 
+            qw(haskell_mine haskell_zeroth)
+        ),
+        (
+            map { get_perl_prog_kv($_) }
+            (qw(10 10_half))
+        ),
+    },
+);

project-euler/11.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+use List::Util (qw(max));
+
+my $grid_string = <<'EOF';
+08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
+49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
+81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
+52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
+22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
+24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
+32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
+67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
+24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
+21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
+78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
+16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
+86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
+19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
+04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
+88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
+04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
+20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
+20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
+01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
+EOF
+
+my @g = (map { [split(/\s+/, $_ )] } split(/\n+/, $grid_string));
+
+my $max = 0;
+
+sub product
+{
+    my (@coords) = @_;
+    my $p = 1;
+    foreach my $c (@coords)
+    {
+        foreach my $d (@$c)
+        {
+            if (($d < 0) || ($d >= 20))
+            {
+                return 0;
+            }
+        }
+        $p *= $g[$c->[0]][$c->[1]];
+    }
+    return $p;
+}
+
+sub p_v
+{
+    my ($x, $y, $dx, $dy) = @_;
+
+    return product(map { [$x + $dx*$_ , $y + $dy*$_] } (0 .. 3));
+}
+
+foreach my $x (0 .. 19)
+{
+    foreach my $y (0 .. 19)
+    {
+        $max = 
+            max(
+                $max, 
+                map {
+                    p_v($x,$y,@$_)
+                } ([0,1],[1,0],[1,1],[1,-1])
+            );
+    }
+}
+print "$max\n";

project-euler/12.lisp

+; This aims to be a solution for:
+; http://projecteuler.net/index.php?section=problems&id=5
+(asdf:oos 'asdf:load-op :iterate)
+(use-package :iterate)
+
+; a^2 + b^2 = c^2
+; a + b + c = 1000
+; ===>
+; a^2 + b^2 = (1000-(a+b))^2
+; a^2 + b^2 = 1000^2 + (a+b)^2 - 2000(a+b)
+; 0 = 1000^2 + 2ab - 2000a - 2000b
+; 1e6+2ab = 2000(a+b)
+
+(defun factorize-using-factor (num factor)
+  (if (not (= (mod num factor) 0))
+    0
+    (1+ (factorize-using-factor (/ num factor) factor))))
+
+(defun factorize (num)
+  (iter (for factor from 2)
+        (until (= num 1))
+        (let ((e (factorize-using-factor num factor)))
+          (if (not (= e 0))
+            (progn (collect (cons factor e))
+                   (setq num (/ num (expt factor e))))))))
+
+(defun num-divisors (num)
+  (apply #'* 
+          (mapcar #'(lambda (pair) (1+ (cdr pair))) (factorize num))))
+
+(defun myfind ()
+  (iter (for i from 1)
+        (sum i into num)
+        (until (> (num-divisors num) 500))
+        (finally (return num))))

project-euler/14.lisp

+; This aims to be a solution for:
+; http://projecteuler.net/index.php?section=problems&id=5
+(asdf:oos 'asdf:load-op :iterate)
+(use-package :iterate)
+
+(defun calc-seq-rank (n)
+  (if (= n 1)
+    0
+    (1+ (calc-seq-rank (if (= 0 (mod n 2)) (/ n 2) (1+ (* 3 n)))))))
+
+(defun myfind ()
+  (iter (for i from 2 to 999999)
+        (reducing (cons i (calc-seq-rank i)) 
+                  by #'(lambda (m n) (if (> (cdr m) (cdr n)) m n))
+                  initial-value (cons 1 0))))

project-euler/15.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+use Math::BigInt qw(:constant);
+
+sub fact
+{
+    my $n = shift;
+    my $prod = 1;
+    for my $i (1 .. $n)
+    {
+        $prod *= $i;
+    }
+    return $prod;
+}
+
+printf "%s\n", (fact(40)/(fact(20)*fact(20)));

project-euler/16.lisp

+; This aims to be a solution for:
+; http://projecteuler.net/index.php?section=problems&id=5
+(asdf:oos 'asdf:load-op :iterate)
+(use-package :iterate)
+
+(defun digits-sum (num)
+  (labels
+    ((helper (n sum) 
+        (if (zerop n)
+          sum
+          (helper (floor (/ n 10)) (+ sum (mod n 10))))))
+    (helper num 0)))
+    
+(defun myfind ()
+  (digits-sum (expt 2 1000)))
+

project-euler/17.lisp

+(defun string-list-len (l)
+  (apply #'+ (mapcar #'length l)))
+
+(defun f-up-to-nine () 
+  (list "one" "two" "three" "four" "five" "six" "seven" "eight" "nine"))
+
+(defun f-ten-to-19 ()
+  (list "ten" "eleven" "twelve" "thirteen" "fourteen" "fifteen" 
+        "sixteen" "seventeen" "eighteen" "nineteen"))
+
+(defun f-tens ()
+  (list "twenty" "thirty" "forty" "fifty" "sixty" "seventy" "eighty" "ninety"))
+
+(defun f-hundreds ()
+  (mapcar (lambda (s) (concatenate 'string s "hundred")) (f-up-to-nine)))
+
+(defun total ()
+  (let ((up-to-nine (string-list-len (f-up-to-nine)))
+        (ten-to-19 (string-list-len (f-ten-to-19)))
+        (tens (string-list-len (f-tens)))
+        (hundreds (string-list-len (f-hundreds)))
+        )
+
+    (+ (* up-to-nine 9 10) ; the digits of the non-teens
+       (* ten-to-19 10) ; the digits of the teens
+       (* tens 10 10) ; the digits of the tens 
+       (* hundreds 100) ; the digits of the hundreds.
+       (* (length "and") 99 9) ; the digits of the "and" of the hundreds"
+       (length "onethousand")
+       )))
+

project-euler/18.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+use List::Util qw(max);
+
+my $triangle_str = <<'EOF';
+75
+95 64
+17 47 82
+18 35 87 10
+20 04 82 47 65
+19 01 23 75 03 34
+88 02 77 73 07 63 67
+99 65 04 28 06 16 70 92
+41 41 26 56 83 40 80 70 33
+41 48 72 33 47 32 37 16 94 29
+53 71 44 65 25 43 91 52 97 51 14
+70 11 33 28 77 73 17 78 39 68 17 57
+91 71 52 38 17 14 91 43 58 50 27 29 48
+63 66 04 68 89 53 67 30 73 16 69 87 40 31
+04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
+EOF
+
+my @lines = (map { [split(/\s+/, $_)] } split(/\n/, $triangle_str));
+
+my @totals_lines = ([ @{$lines[0]} ]);
+
+for my $i (1 .. $#lines)
+{
+    my $last = $totals_lines[-1];
+    my $this = $lines[$i];
+    push @totals_lines,
+        [
+            map
+            { 
+                $this->[$_] +
+                max(
+                  (($_ > 0) ? ($last->[$_-1]) : ()),
+                  (($_ < $#{$this}) ? ($last->[$_]) : ())
+                )
+            } (0 .. $#{$this})
+        ];
+}
+
+printf "Max is %i\n", max(@{$totals_lines[-1]});
+

project-euler/19.lisp

+(asdf:oos 'asdf:load-op :iterate)
+(use-package :iterate)
+
+(defun is-in (num lst)
+  (> (count-if #'(lambda (i) (= i num)) lst) 0))
+
+(defun div-by (num modulo)
+  (= (mod num modulo) 0))
+
+(defun month-len (y m)
+  (cond ((is-in m '(4 6 9 11)) 30)
+        ((= m 2) (+ 28 (if (or (div-by y 400) 
+                               (and (div-by y 4) (not (div-by y 100))))
+                         1 0)))
+        (t 31)))
+
+(defmacro-clause (sum7 expr &optional into var initial-value init-val)
+    `(reducing ,expr by #'(lambda (m n) (mod (+ m n) 7)) 
+               into ,var initial-value ,init-val))
+
+(defun calc ()
+  (iter year-iter 
+        (for year from 1900 to 2000)
+        (iter (for month from 1 to 12)
+              (in year-iter (sum7 (month-len year month) into day-of-week 
+                                  initial-value 2))
+              (format t "DW=~A~%" day-of-week)
+              (in year-iter (sum (if (and (>= year 1901) 
+                                          (= day-of-week 1)) 1 0)
+                                 into mycount
+                                 )))
+        (finally (return-from year-iter mycount))
+        ))
+

project-euler/2.lisp

+; This aims to be a solution for:
+; http://projecteuler.net/index.php?section=problems&id=1
+(asdf:oos 'asdf:load-op :iterate)
+(use-package :iterate)
+
+(defun sum1 (n)
+  (iter (for f1 initially 1 then f2 and
+             f2 initially 2 then (+ f1 f2))
+        (until (> f1 n))
+        (format t "Foo = ~A,~A~%" f1 f2)
+        (sum f1 into mysum)
+        (finally (return mysum))))
+
+(defun display-result ()
+  (format t "Total is ~A~%" (sum1 1e6)))
+          
+
+

project-euler/2.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+my ($i, $j) = (1,2);
+
+my $sum;
+while ($i < 1e6)
+{
+    if ($i % 2 == 0)
+    {
+        $sum += $i;
+    }
+}
+continue
+{
+    ($i, $j) = ($j, $i+$j);
+}
+print "$sum\n";

project-euler/2.rb

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+my ($i, $j) = (1,2);
+
+my $sum;
+while ($i < 1e6)
+{
+    if ($i % 2 == 0)
+    {
+        $sum += $i;
+    }
+}
+continue
+{
+    ($i, $j) = ($j, $i+$j);
+}
+print "$sum\n";

project-euler/20.lisp

+; This aims to be a solution for:
+; http://projecteuler.net/index.php?section=problems&id=5
+(asdf:oos 'asdf:load-op :iterate)
+(use-package :iterate)
+
+(defun digits-sum (num)
+  (labels
+    ((helper (n sum) 
+        (if (zerop n)
+          sum
+          (helper (floor (/ n 10)) (+ sum (mod n 10))))))
+    (helper num 0)))
+
+(defun factorial (num)
+  (labels
+    ((helper (n prod)
+             (if (= n 0) prod (helper (1- n) (* prod n)))))
+    (helper num 1)))
+ 
+(defun myfind ()
+  (digits-sum (factorial 100)))
+

project-euler/21.lisp

+; This aims to be a solution for:
+; http://projecteuler.net/index.php?section=problems&id=5
+(asdf:oos 'asdf:load-op :iterate)
+(use-package :iterate)
+
+; a^2 + b^2 = c^2
+; a + b + c = 1000
+; ===>
+; a^2 + b^2 = (1000-(a+b))^2
+; a^2 + b^2 = 1000^2 + (a+b)^2 - 2000(a+b)
+; 0 = 1000^2 + 2ab - 2000a - 2000b
+; 1e6+2ab = 2000(a+b)
+
+(defun factorize-using-factor (num factor)
+  (if (not (= (mod num factor) 0))
+    0
+    (1+ (factorize-using-factor (/ num factor) factor))))
+
+(defun factorize (num)
+  (iter (for factor from 2)
+        (until (= num 1))
+        (let ((e (factorize-using-factor num factor)))
+          (if (not (= e 0))
+            (progn (collect (cons factor e))
+                   (setq num (/ num (expt factor e))))))))
+
+(defun num-divisors (num)
+  (reduce #'* 
+          (mapcar #'(lambda (pair) (1+ (cdr pair))) (factorize num))
+          :initial-value 1))
+
+(defun sum-divisors (num)
+  (iter (for div from 1 to (floor (/ num 2)))
+        (if (zerop (mod num div))
+          (sum div))))
+
+(defun myfind ()
+  (iter (for i from 1 to (1- 10000))
+        (format t "~A~%" i)
+        (let ((d-i (sum-divisors i)))
+          (if (and (/= i d-i)
+                   (< d-i 10000)
+                   (= i (sum-divisors d-i)))
+            (sum i)))))

project-euler/22.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+use IO::All;
+use List::Util qw(sum);
+
+my $text = io("names.txt")->slurp();
+
+my @names = sort { $a cmp $b } (lc($text) =~ m{"([a-z]+)"}g);
+
+my $sum = 0;
+for my $i (0 .. $#names)
+{
+    $sum += ($i+1) * sum(map { ord($_)-ord("a")+1 } split(//, $names[$i]));
+}
+
+print "$sum\n";

project-euler/23.lisp

+; This aims to be a solution for:
+; http://projecteuler.net/index.php?section=problems&id=5
+(asdf:oos 'asdf:load-op :iterate)
+(use-package :iterate)
+
+(asdf:oos 'asdf:load-op :memoize)
+(use-package :memoize)
+
+; a^2 + b^2 = c^2
+; a + b + c = 1000
+; ===>
+; a^2 + b^2 = (1000-(a+b))^2
+; a^2 + b^2 = 1000^2 + (a+b)^2 - 2000(a+b)
+; 0 = 1000^2 + 2ab - 2000a - 2000b
+; 1e6+2ab = 2000(a+b)
+
+(defun factorize-using-factor (num factor)
+  (if (not (= (mod num factor) 0))
+    0
+    (1+ (factorize-using-factor (/ num factor) factor))))
+
+(defun factorize (num)
+  (iter (for factor from 2)
+        (until (= num 1))
+        (let ((e (factorize-using-factor num factor)))
+          (if (not (= e 0))
+            (progn (collect (cons factor e))
+                   (setq num (/ num (expt factor e))))))))
+
+(defun num-divisors (num)
+  (reduce #'* 
+          (mapcar #'(lambda (pair) (1+ (cdr pair))) (factorize num))
+          :initial-value 1))
+
+(defun sum-divisors (num)
+  (iter (for div from 1 to (floor (/ num 2)))
+        (if (zerop (mod num div))
+          (sum div))))
+
+(defun is-abundant (n)
+  (> (sum-divisors n) n))
+
+(memoize-function 'is-abundant)
+
+(defun is-abundant-sum (num)
+  (iter (for part from 1 to (floor (/ num 2)))
+        (if (and (is-abundant part) (is-abundant (- num part)))
+            (return t))
+        (finally (return nil))))
+
+(defun myfind ()
+  (iter (for i from 1 to 28123)
+        (if (not (is-abundant-sum i))
+          (sum i))))

project-euler/24.lisp

+; This aims to be a solution for:
+; http://projecteuler.net/index.php?section=problems&id=5
+(asdf:oos 'asdf:load-op :iterate)
+(use-package :iterate)
+
+(defun factorial (num)
+  (labels
+    ((helper (n prod)
+             (if (= n 0) prod (helper (1- n) (* prod n)))))
+    (helper num 1)))
+
+(defun form-perm (remaining bit-vec)
+  (
+  (+ 5 6))
+    
+    

project-euler/24.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+sub factorial
+{
+    my $n = shift;
+
+    if ($n <= 1)
+    {
+        return $n;
+    }
+    else
+    {
+        return $n * factorial($n-1);
+    }
+}
+
+my $perm = 1_000_000 - 1;
+my @digits = (0 .. 9);
+
+my $place = 9;
+my @result;
+
+while ($perm)
+{
+    my $f = factorial($place);
+    my $p = int ($perm / $f);
+    
+    push @result, splice(@digits,$p,1);
+
+    $perm %= $f;
+    $place--;
+}
+push @result, @digits;
+print join("",@result), "\n";

project-euler/25.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+use Math::BigInt lib => 'GMP', ':constant';
+
+my $f1 = 1;
+my $f2 = 1;
+
+my $i1 = 1;
+while (length("$f1") != 1000)
+{
+    ($f1, $f2) = ($f2, $f1+$f2);
+    $i1++;
+}
+print "$i1\n";
+

project-euler/26.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+use List::Util qw(reduce);
+
+sub find_cycle
+{
+    my $n = shift;
+
+    my %states;
+
+    my $r = 1;
+    my $count;
+    while (!exists($states{"$r"}))
+    {
+        $states{"$r"} = $count++;
+        $r = +($r * 10) % $n;
+    }
+    return $count - $states{"$r"};
+}
+
+my $pair = 
+    reduce { $a->[1] > $b->[1] ? $a : $b } 
+    map { [$_,find_cycle($_)] } 
+    (2 .. 999)
+    ;
+
+print join(",", @$pair), "\n";

project-euler/27.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+sub is_prime
+{
+    my ($n) = @_;
+
+    if ($n <= 1)
+    {
+        return 0;
+    }
+
+    my $top = int(sqrt($n));
+
+    for my $i (2 .. $top)
+    {
+        if ($n % $i == 0)
+        {
+            return 0;
+        }
+    }
+
+    return 1;
+}
+
+my ($max_a, $max_b, $max_iter);
+
+$max_iter = 0;
+for my $b_coeff (0 .. 999)
+{
+    for my $a_coeff ((-$b_coeff+1) .. 999)
+    {
+        my $n = 0;
+        while (is_prime($b_coeff+$n*($n+$a_coeff)))
+        {
+            $n++;
+        }
+        $n--;
+        if ($n > $max_iter)
+        {
+            ($max_a, $max_b, $max_iter) = ($a_coeff, $b_coeff, $n);
+        }
+    }
+}
+printf("a = %d ; b = %d ; n = %d\n", ($max_a, $max_b, $max_iter));
+

project-euler/28.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+my $sum = 0;
+
+my $num = 1;
+
+$sum += $num;
+
+my $step = 0;
+foreach my $square (grep { $_ % 2 == 1 } 3 .. 1001)
+{
+    $step += 2;
+
+    foreach my $side (0 .. 3)
+    {
+        $num += $step;
+        $sum += $num;
+    }
+}
+print "Sum = $sum\n";

project-euler/29.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+use Math::BigInt lib => 'GMP', ':constant';
+
+my %numbers;
+
+for my $base (2 .. 100)
+{
+    for my $expt (2 .. 100)
+    {
+        my $r = Math::BigInt->new($base) ** Math::BigInt->new($expt);
+        $numbers{"$r"}++;
+    }
+}
+
+print keys(%numbers);

project-euler/30.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+use List::Util qw(sum);
+
+my $n = 10;
+
+my $sum = 0;
+while (1)
+{
+    if (sum(map { $_ ** 5 } split(//, $n)) == $n)
+    {
+        $sum += $n;
+        print "$n : $sum\n"
+    }
+    $n++;
+}

project-euler/31.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+my @coins = (1,2,5,10,20,50,100,200);
+
+my @r_coins = (reverse(@coins));
+
+my %cache = ();
+
+sub calc
+{
+    my ($max_idx, $sum) = @_;
+
+    if (exists($cache{"$max_idx,$sum"}))
+    {
+        return $cache{"$max_idx,$sum"}
+    }
+    else
+    {
+        my $ret;
+        if ($max_idx == $#r_coins)
+        {
+            $ret = 1;
+        }
+        elsif ($sum < $r_coins[$max_idx])
+        {
+            $ret = calc($max_idx+1, $sum);
+        }
+        else
+        {
+            $ret = calc($max_idx+1, $sum)+calc($max_idx, $sum-$r_coins[$max_idx]);
+        }
+        return $cache{"$max_idx,$sum"} = $ret;
+    }
+}
+
+print calc(0, 200), "\n";

project-euler/32.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+use List::Util qw(sum);
+
+use Data::Dumper;
+
+sub gen_perms
+{
+    my ($set) = @_;
+
+    if (@$set < 5)
+    {
+        return [[]];
+    }
+
+    my $elem;
+    my @prev_elems;
+    my @perms;
+    while ($elem = shift(@$set))
+    {
+        push @perms, (map { [$elem,@{$_}] } @{gen_perms([@prev_elems,@$set])});
+        push @prev_elems, $elem;
+    }
+
+    return \@perms;
+}
+
+my %products;
+my $good = join("K", 1..9);
+foreach my $p (@{gen_perms([1..9])})
+{
+    {
+        my $result = join("", @$p[0..1]) * join("", @$p[2..4]);
+        if (join("K", sort { $a <=> $b } (@$p,split(//, $result))) eq $good)
+        {
+            $products{$result}++;
+        }
+    }
+    {
+        my $result = join("", @$p[0]) * join("", @$p[1..4]);
+        if (join("K", sort { $a <=> $b } (@$p,split(//, $result))) eq $good)
+        {
+            $products{$result}++;
+        }
+    }
+}
+
+print sum(keys(%products)), "\n";

project-euler/33.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+use Math::BigInt;
+use Math::BigRat;
+
+my %h = ();
+
+foreach my $numer (11 .. 99)
+{
+    if ($numer % 10 == 0)
+    {
+        next;
+    }
+
+    foreach my $denom (($numer+1)..99)
+    {
+        my $get_my = sub {
+            my $digit = shift;
+            my ($n, $d) = ($numer, $denom);
+            if (
+                    ($d =~ s{$digit}{})
+                 && ($n =~ s{$digit}{})
+                 && ($d * $numer == $n * $denom)
+             )
+            {
+                 return ($n, $d);
+            }
+            else
+            {
+                return ();
+            }
+        };
+
+        foreach my $digit ($numer%10,int($numer/10))
+        {
+            if (my ($n, $d) = $get_my->($digit))
+            {
+                my $gcd = Math::BigInt::bgcd($n, $d);
+                $n /= "$gcd";
+                $d /= "$gcd";
+
+                print "$n/$d\n";
+                $h{"$n/$d"}++;
+            }
+        }
+    }
+}
+
+print keys(%h), "\n"
+

project-euler/34.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+use List::Util (qw(sum));
+
+sub factorial
+{
+    my $n = shift;
+
+    if ($n <= 1)
+    {
+        return 1;
+    }
+    else
+    {
+        return $n * factorial($n-1);
+    }
+}
+
+my @facts = (map { factorial($_) } (0 .. 9));
+
+my $total;
+foreach my $n (3 .. 1e7)
+{
+    if ($n % 1e5 == 0)
+    {
+        print "$n\n";
+    }
+    if (sum(@facts[split//,$n]) == $n)
+    {
+        $total += $n;
+    }
+}
+print "$total\n";

project-euler/35.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+sub is_prime
+{
+    my ($n) = @_;
+
+    if ($n <= 1)
+    {
+        return 0;
+    }
+
+    my $top = int(sqrt($n));
+
+    for my $i (2 .. $top)
+    {
+        if ($n % $i == 0)
+        {
+            return 0;
+        }
+    }
+
+    return 1;
+}
+
+sub is_circ_prime
+{
+    my $n = shift;
+    if ($n =~ /0/)
+    {
+        return;
+    }
+    else
+    {
+        my $l = length($n);
+        for my $i (1 .. $l)
+        {
+            if (!is_prime($n))
+            {
+                return;
+            }
+            $n = substr($n,1) . substr($n,0,1);
+        }
+        return 1;
+    }
+}
+
+my $count;
+foreach my $n (2 .. 1_000_000)
+{
+    if (is_circ_prime($n))
+    {
+        $count++;
+    }
+}
+print "$count\n";

project-euler/36.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+my $count;
+my $sum = 0;
+foreach my $n (1 .. 999_999)
+{
+    if (    ($n&0x1)
+         && (scalar(reverse($n)) eq $n)
+    )
+    {
+        my $b = sprintf("%b", $n);
+        if (scalar(reverse($b)) eq $b)
+        {
+            $count++;
+            $sum += $n;
+        }
+    }
+}
+print "$count <=> $sum\n";

project-euler/37.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+use List::Util qw(sum);
+sub is_prime
+{
+    my ($n) = @_;
+
+    if ($n <= 1)
+    {
+        return 0;
+    }
+
+    my $top = int(sqrt($n));
+
+    for my $i (2 .. $top)
+    {
+        if ($n % $i == 0)
+        {
+            return 0;
+        }
+    }
+
+    return 1;
+}
+
+my @trunc_primes = ();
+
+N_LOOP: 
+for(my $n = 11; @trunc_primes < 11 ; $n += 2)
+{
+    foreach my $i (1 .. length($n))
+    {
+        if (is_prime(substr($n, 0, $i))
+                &&
+            is_prime(substr($n, -$i))
+        )
+        {
+            # Do nothing
+        }
+        else
+        {
+            next N_LOOP;
+        }
+    }
+    push @trunc_primes, $n;
+    print "Found " . join(",", @trunc_primes) . "\n";
+    print "Sum = " . sum(@trunc_primes) . "\n";
+}

project-euler/38.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+my $max = -1;
+INT_LOOP:
+for my $int (9, 91..99, 911..999, 9111..9999)
+{
+
+    if ($int =~ /0/)
+    {
+        next INT_LOOP;
+    }
+
+    my $n = 1;
+    my $pan = "";
+    while (length($pan) < 9)
+    {
+        $pan .= $int * $n++;
+    }
+    if (length($pan) == 9)
+    {
+        if (join("", sort { $a <=> $b } split(//, $pan)) eq "123456789")
+        {
+            # $pan is a pan-digital number.
+            if ($pan > $max)
+            {
+                $max = $pan;
+            }
+        }
+    }
+}
+print "max = $max\n";
+

project-euler/39.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+my %p_counts;
+
+for my $bb (2 .. 500)
+{
+    A_LOOP:
+    for my $aa (1 .. $bb)
+    {
+        my $sq = $bb*$bb+$aa*$aa;
+        my $cc = int(sqrt($sq));
+        my $p = $aa+$bb+$cc;
+        if ($p >= 1000)
+        {
+            last A_LOOP;
+        }
+        elsif ($cc*$cc == $sq)
+        {
+            $p_counts{$p}++;
+        }
+    }
+}
+
+print map { "$_ => $p_counts{$_}\n" } 
+    sort { $p_counts{$a} <=> $p_counts{$b} } keys(%p_counts)
+    ;

project-euler/4.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+my $max = 0;
+for my $i (100 .. 999)
+{
+    for my $j (100 .. 999)
+    {
+        my $n = $i*$j;
+        if ($n == scalar(reverse($n)) && ($n > $max))
+        {
+            $max = $n;
+        }
+    }
+}
+print "$max\n";
+

project-euler/40.txt

+d[1] = 1
+
+123456789
+
+d[10] = 1
+
+10,11,12,13,14,...
+^
+|
+10
+   12 14 16
+
+10+90/2 = 55
+
+d[100] = 5
+
+------------------
+
+End of the two-digits (first digit of 100):
+
+(99-10+1)*2 + 10 = 190
+
+100,101,102,103,104
+^
+190 ^
+    193 ^
+        196
+
+100 + (1000-190)/3 = 100 + 810/3 = 100 + 270 = 370
+
+d[1000] = 3
+
+-------------------------
+
+End of the three digits (first digit of 1000):
+
+(999-100+1)*3 + 190 = 900*3 + 190 = 2700 + 190 = 2890
+
+1000,1001,1002
+
+^
+2890 ^
+     2894 ^
+          2898
+
+1000+(10,000-2890)/4 = 3500 - 2890/4 = 3500 - 700 - 90/4 = 2800 - 90/4 = 
+2800 - 22 - 2/4 = 2800-23+2/4 = 2777+2/4
+
+d[10,000] = 7
+
+--------------------------------------
+
+End of the four digits (first digit of 10,000):
+
+(9,999-1,000+1)*4 + 2,890 = 9,000*4+2,890 = 36,000 + 2,890 = 38,890
+
+10,000 ; 10,001 ; 10,002 ; 10,003
+
+^
+38,890   ^
+         38,895   ^
+                  38,900
+
+10,000 + (100,000 - 38,890)/5 = 10,000 + 20,000 - 3,889 * 2 = 
+30,000 - 3,900 * 2 + 2*11 = 30,000 - 7,800 + 22 = 22,200 + 22 = 22,222
+
+d[100,000] = 2
+
+-------------------
+
+End of the five digits (first digit of 100,000):
+
+(99,999 - 10,000+1)*5 + 38,890 = 90,000*5 + 38,890 = 450,000 + 38,890 =
+488,890
+
+100,000 ; 100,001 ; 100,002 ; 100,003
+
+^
+488,890   ^
+          488,896   ^
+                    488,902
+
+100,000 + (1,000,000 - 488,890)/6 = 100,000 + 511,110/6
+>>>>
+     85,185  
+    --------
+    511,110|6
+    48
+    --
+     31
+     30
+     --
+      1,1
+        6
+      ---
+        51
+        48
+        --
+         30
+<<<<
+
+100,000 + 85,185  = 185,185
+
+d[1,000,000] = 1
+

project-euler/41.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+package Permutations::Iterator;
+
+sub new
+{
+    my $class = shift;
+
+    my $self = {};
+    bless $self, $class;
+
+    $self->_init(@_);
+
+    return $self;
+}
+
+
+sub _init
+{
+    my ($self, $set) = @_;
+
+    $self->{stack} = 
+        [ {prefix => [], set => [@$set], elem => undef, prev => []} ];
+
+    $self->{lim} = (@$set + 1);
+
+    return 0;
+}
+
+sub next
+{
+    my $self = shift;
+
+    my $stack = $self->{stack};
+    my $limit = $self->{lim};
+    while (@$stack)
+    {
+        my $s = $stack->[-1];
+
+        if (@$stack == $limit)
+        {
+            pop(@$stack);
+            return $s->{prefix};
+        }
+        else
+        {
+            if (defined($s->{elem}))
+            {
+                push @{$s->{prev}}, $s->{elem};
+            }
+
+            if ($s->{elem} = shift(@{$s->{set}}))
+            {
+                push @$stack, 
+                    {
+                        prefix => [@{$s->{prefix}}, $s->{elem}],
+                        set => [@{$s->{prev}}, @{$s->{set}}],
+                        elem => undef(),
+                        prev => [],
+                    };
+            }
+            else
+            {
+                pop(@$stack);
+            }
+        }
+    }
+
+    return;
+}
+
+use Data::Dumper;
+
+my $set = [1, 22, 303, 4400, 51, 607, 789];
+
+my $self = Permutations::Iterator->new($set);
+
+while (defined(my $p = $self->next()))
+{
+    print join(",", @$p), "\n";
+}

project-euler/42.pl

+#!/usr/bin/perl 
+
+use strict;
+use warnings;
+
+use IO::All;
+use List::Util qw(sum);
+use POSIX;
+
+sub is_triangle
+{
+    my $n = shift()*2;
+
+    my $i = int(sqrt($n));
+
+    if ($i * $i == $n)
+    {
+        return 0;
+    }
+    else
+    {
+        return ($n == $i * ($i+1));
+    }
+}
+
+my $text = io("/home/shlomi/words.txt")->slurp();
+
+my @words = ($text =~ m{([A-Z]+)}g);
+print scalar(grep { is_triangle(sum(map { ord($_) - ord('A')+1 } split //, $_)) }@words), "\n";

project-euler/43.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+package Permutations::Iterator;
+
+sub new