Polyglot Euler

1. Multiples of 3 and 5

1.1. C

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

apt update && apt install gcc make

4.4s

Bash

#include<stdio.h>
int main()
{
	long sum=0;
	int i;
	for(i=0;i<1000;i++)
		if(i%3==0 || i%5==0){
			sum+=i;
		}
	printf("%ld\n",sum);
}

euler001.c

make euler001 && ./euler001

0.8s

Bash

1.2. Bash

apt install bc
seq 3 3 999 > nums
seq 5 5 999 >> nums
sort -n -u nums | paste -s -d+ - | bc

2.6s

Bash

1.3. AWK

seq 999 | awk '{if ($1%3==0 || $1%5==0) sum+=$1} END{print sum}'

0.7s

Bash

1.4. Clojure

(reduce + (filter #(or (zero? (rem % 3))
                       (zero? (rem % 5)))
                  (range 1000)))

0.1s

Clojure

233168

1.5. Python

sum([i for i in range(1000) if (i % 3 == 0 or i % 5 == 0)])

0.4s

Python

233168

2. Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

2.1. C

#include <stdio.h>

int main(void)
{
  unsigned int a1 = 1, a2 = 1, a3 = 2, sum = 0;
  while (a3 < 4000000) {
    a3 = a1 + a2;
    sum += a3 * !(a3%2);
    a1 = a2;
    a2 = a3;
  }
  printf("%u\n", sum);
  return 0;
}

euler002.c

make euler002 && ./euler002

0.7s

Bash

2.2. Bash

sum=0
fib0=0
fib1=1
fibn=0
lim=${1:-4000000}
while [[ $fib0 -le $lim && $fib0 -ge 0 ]]
do
if [[ $fib0%2 -eq 0 ]]
then sum=$((sum+fib0))
fi
fibn=$((fib0+fib1))
fib0=$fib1
fib1=$fibn
done
echo $sum

0.7s

Bash

2.3. AWK

awk -v max=4000000 'BEGIN{a=1;b=1;while(b<max){r=b;b+=a;a=r;if(a%2==0)sum+=a;}printf sum;}'

0.7s

Bash

2.4. Clojure

(->> [1 1]
  (iterate
   (juxt last
         (partial apply +)))
  (map first)
  (filter even?)
  (take-while #(< % 4000000))
  (apply +))

0.1s

Clojure

4613732

2.5. Python

def fibonacci_even_sum(n):
    if n == 0: return 0
    if n == 1: return 0
    if n == 2: return 2
    sum = 2
    fib0 = 0 
    fib1 = 1
    fib2 = 2
    iter = 0
    while( fib2 <= 4000000 ):
        if( iter == 3 ):
            sum = sum + fib2
            iter = 0
        fib0 = fib1
        fib1 = fib2
        fib2 = fib0 + fib1
        iter = iter + 1
    return sum
 
fibonacci_even_sum(4000000)

0.3s

Python

4613732

3. Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

3.1. C

#include <stdio.h>

int main(void)
{
  unsigned long long n = 600851475143ULL;
  unsigned long long i;

  for (i = 2ULL; i < n; i++) {
    while (n % i == 0) {
      n /= i;
    }
  }
  printf("%llu\n", n);

  return 0;
}

euler003.c

make euler003 && ./euler003

0.7s

Bash

3.2. Bash

factor 600851475143 | awk '{print $NF}'

0.6s

Bash

3.3. AWK

awk -v m=600851475143 'BEGIN{
a[0]=2;
n=1;
for(i=3;m>2;i++){
for(j=0;j<n;j++){
if(i%a[j]==0){
break;
}}
if(j==n){a[n]=i;n++;
while(m%i==0){
printf "%d/%d=",m,i;
m/=i;
printf "%d\n",m;
}}}}'

0.7s

Bash

3.4. Clojure

(def primes
  (concat 
   [2 3 5 7]
   (lazy-seq
    (let [primes-from
      (fn primes-from [n [f & r]]
        (if (some #(zero? (rem n %))
                  (take-while #(<= (* % %) n) primes))
          (recur (+ n f) r)
          (lazy-seq (cons n (primes-from (+ n f) r)))))
      wheel (cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6  4  2
                    6 4 6 8 4 2 4 2 4 8 6 4 6 2  4  6
                    2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10])]
      (primes-from 11 wheel)))))

(defn prime-factors-of [^long n]
  (let [q (long (Math/sqrt n))]
    (loop [n n
           p primes
           res nil]
      (let [d (long (first p))]
        (cond
          (or (> d q) (= n d)) (cons n res)
          (zero? (rem n d))    (recur (quot n d) p (cons d res))
          :else                (recur n (next p) res))))))
          
(first (prime-factors-of 600851475143))

0.2s

Clojure

6857

3.5. Python

def largest_prime_factor(n):
    largest_factor = 1
    # remove any factors of 2 first
    while n % 2 == 0:
        largest_factor = 2
        n = n/2
    # now look at odd factors
    p = 3
    while n != 1:
        while n % p == 0:
            largest_factor = p
            n = n/p
        p += 2
    return largest_factor

largest_prime_factor(600851475143)

0.4s

Python

6857

4. Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

4.1. C

#include <stdio.h>

static int is_palindromic(unsigned int n);

int main(void)
{
  unsigned int i, j, max = 0;
  for (i = 100; i <= 999; i++) {
    for (j = 100; j <= 999; j++) {
      unsigned int p = i*j;
      if (is_palindromic(p) && p > max) {
        max = p;
      }
    }
  }
  printf("%u\n", max);
  return 0;
}

int is_palindromic(unsigned int n)
{
  unsigned int reversed = 0, t = n;

  while (t) {
    reversed = 10*reversed + (t % 10);
    t /= 10;
  }
  return reversed == n;
}

euler004.c

make euler004 && ./euler004

0.9s

Bash

4.2. Bash

20.2s

Bash

A=900
B=900
C=0    
PALINDROME=
FACTOR1=
FACTOR2=

while true
do
{
 
# C = A * B
 
C=$(( $A * $B ))
TEST1=`echo $C | rev` # Flip C and store it in TEST1
 
# echo $C $TEST1
 
# {Is C a palindrome AND bigger than PALINDROME?}
# Yes: C becomes the new value for PALINDROME
 
if [ "$C" -eq "$TEST1" ]
then
{
        #echo $C
        PALINDROME=$C
        FACTOR1=$A
        FACTOR2=$B
}
fi
 
# No: Increment the value of B
 
let "B = B + 1"
 
# {Is B = 1000?}
# Yes: reset B to 900 and add 1 to A
if [ "$B" -eq 1000 ]
then
{
        B=900
        let "A = A + 1"
}
fi
 
# {Keep doing the above until A = 1000}
if [ "$A" -eq 1000 ]
then
        break
fi
 
} done
 
echo "$PALINDROME is the largest palindromic number that is a product of two three-digit numbers ($FACTOR1 and $FACTOR2)."

20.2s

Bash

4.3. AWK

awk 'BEGIN{for(i=100;i<=999;i++)for(j=i+1;j<=999;j++) printf "%d %d %d\n",i,j,i*j;}'| awk '{k=$3; m=0;do{ N=k; k=int(N/10);a[m]=N-(k*10);m++;}while(k>0);
if (m==5) if (a[0]==a[4] && a[1]==a[3]) {printf "%d %d %d\n",$1,$2,$3; p=($3>p)?$3:p;} 
if (m==6) if (a[0]==a[5] && a[1]==a[4] && a[2]==a[3]) {printf "%d %d %d\n",$1,$2,$3; p=($3>p)?$3:p;} 
}END{printf "\nThe largest palindrome is %d\n",p;}'

0.9s

Bash

4.4. Clojure

(defn palindrome? [s]
  (= (reverse (str s) ) (seq (str s))))

(apply max
       (filter palindrome?
               (for
                   [a (range 100 1000)
                    b (range 100 1000)]
                 (* a b))))

1.1s

Clojure

906609

4.5. Python

def is_palindrome(n):
    n = str(n)
    return n == n[::-1]


def project_euler_004(first, last):
    given_range = range(first, last + 1)
    products = list(set([a * b for a in given_range for b in given_range]))
    palindromes = [n for n in products if is_palindrome(n)]
    solution = max(palindromes)
    print(solution)

project_euler_004(100, 999)

1.0s

Python