Project Euler

(Below the Catalan version, you can find an extended version with examples in English)

Leonhard_Euler

Leonhard Euler (CC) Source: https://commons.wikimedia.org/

[CAT] A https://projecteuler.net/ hi trobem tota una sèrie de problemes matemàtics en tots els rangs de dificultat, la majoria dels quals són pensats per ser resolts amb un ordinador. Els problemes estan destinats a totes aquelles persones a qui els encanta les matemàtiques i resoldre problemes de programació de forma eficient amb el llenguatge de programació que més els agradi.

La gran varietat de problemes que trobem a la web dóna a tots als seus usuaris l’oportunitat d’aprendre més d’un tipus de llenguatge de programació perquè no es requereix l’ús d’un únic llenguatge per resoldre els problemes. De fet, d’entre els 88 llenguatges diferents que fan servir els més de 500.000 usuaris registrats a tot arreu del món, hi trobem llenguatges tant variats com Haskell, C/C++, Python, Java, Ocaml, Perl i fins i tot Prolog.

Registrar-se a la web és una bona oportunitat per a estudiants de totes les edats, ja sigui per aprendre coses curioses sobre les matemàtiques o per aprendre a programar o totes dues coses.


Leonhard_Euler_2

Leonhard Euler (CC) Source: https://commons.wikimedia.org/

[EN] At https://projecteuler.net/ one can find a large number of mathematical problems in all range of difficulty, most of which are meant to be solved with a computer. Project Euler is for all those people who love Maths and solving problems efficiently with the programming language they like most.

       The great variety of problems that are found at the web, though, give its users the opportunity to learn more than one kind of programming language because the use of a single programming language is not required. In fact, among the 88 different languages used by more than 500,000 users of Project Euler all over the world one can find a really varied collection of languages like Haskell, C/C++, Python, Java, Ocaml, Perl and even Prolog. Signing up on the web is a great opportunity for students of all ages for learning curious things about Maths or learning to program or both.

       As an example, one of the problems at the web will be solved with two different programming languages: Haskell and C++. The problem solved is the problem # 35 Circular Primes:

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

This is a good example to show how using a language like Haskell helps solving a fundamental part of the problem very easily: obtaining all rotations of the digits, and how C++ helps improving the performance using dynamic programming, where in Haskell would be something quite tedious.

This is a possible solution using Haskell:

digitToInteger :: Char -> Integer
digitToInteger '0' = 0
digitToInteger '1' = 1
digitToInteger '2' = 2
digitToInteger '3' = 3
digitToInteger '4' = 4
digitToInteger '5' = 5
digitToInteger '6' = 6
digitToInteger '7' = 7
digitToInteger '8' = 8
digitToInteger '9' = 9

isPrimeRec :: Integer -> Integer -> Bool
isPrimeRec n d
    | mod n d == 0 = False
    | d*d > n = True
    | otherwise = isPrimeRec n (d + 2)

isPrime :: Integer -> Bool
isPrime n
    | n <= 1 = False
    | n <= 3 = True
    | even n = False
    | otherwise = isPrimeRec n 3

rotations :: String -> Integer -> [String]
rotations _ 0 = []
rotations (x:xs) n = [(x:xs)] ++ (rotations (xs ++ [x]) (n - 1))

stringToNumeric :: String -> Integer -> Integer
stringToNumeric [] n = n
stringToNumeric (x:xs) n = stringToNumeric xs (10*n + (digitToInteger x))

isCircular :: Integer -> Bool
isCircular n = all (\s -> isPrime (stringToNumeric s 0)) (rotations numString len)
    where
        len = fromIntegral $ length numString
        numString = show n

candidateCircular :: Integer -> Bool
candidateCircular 1 = False
candidateCircular 2 = True
candidateCircular n = all (\x -> mod (digitToInteger x) 2 /= 0) $ show n

problem35 = (l, length l)
    where l = [x | x <- [2..1000000], candidateCircular x, isCircular x]

We can find the computation of all rotations of the digits in the function rotations. It is fairly easy to understand how it works: the n rotations of a n-digit number is the number itself plus the n – 1 rotations of that number rotated once. At each rotation step the highest-weight digit is placed at the beginning, so that it becomes the digit with least weight.

A possible solution in C++ could be this one:

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n%2 == 0) return false;
    int d = 3;
    while (d*d <= n) {
        if (n%d == 0) return false;
        d += 2;
    }
    return true;
}

void rotations(string s, int n, vector& r) {
    if (n == 0) {
        r = vector();
        return;
    }
    r.push_back(s);

    s.push_back(s[0]);
    s.erase(0,1);

    vector rr;
    rotations(s, n - 1, rr);
    for (int i = 0; i < rr.size(); ++i) r.push_back(rr[i]);
}

string intToString(int k) {
    string d;
    if (k < 10) {
        d.push_back(k + '0');
        return d;
    }
    d = intToString(k/10);
    d.push_back(k%10 + '0');
    return d;
}

bool allPrimes(const vector& s, vector& primes) {
    for (int i = 0; i < s.size(); ++i) {
        primes[i] = atoi(s[i].c_str());
        if (!isPrime(primes[i])) return false;
    }
    return true;
}

bool isCandidateCircular(int n) {
    while (n >= 10) {
        if ((n%10)%2 == 0) return false;
        n /= 10;
    }
    return true;
}

int main() {
    int lim = 1000000;
    vector isCircular(lim, false);
    int nCircular = 0; 

    for (int i = 0; i < lim; ++i) {
        if (not isCircular[i] and isCandidateCircular(i) and isPrime(i)) {
            string k = intToString(i);
            vector s;
            rotations(k, k.size(), s);
            
            vector primes(s.size());
            if (allPrimes(s, primes)) {
                for (int j = 0; j < primes.size(); ++j) {
                    if (!isCircular[primes[j]]) ++nCircular;
                    isCircular[primes[j]] = true;
                }
            }
        }
    }
    cout << "Number of circular primes: " << nCircular << endl;
}

We find the computation of all rotations of the digits in the function rotations. The main difference we can see from the C++ and the Haskell version of this function is that in C++ one  has to be much more careful when computing this rotations. But C++ is much more efficient due to the possibility of using a dynamic programming technique which consists in not repeating computations: if x is a circular prime then, all of its rotations are also circular primes, therefore we can store which numbers are circular and which are not in an array, as found in the main procedure.

With these examples we can see that the choice of the language is quite important when deciding how to solve a problem: using one language or another might help in solving the problem very easily but that might turn out to be an inefficient solution.

But, where is all this learning? What if somebody found the solution to the problem but the program took 30 minutes to find it? Once the solution to the problem is found, one may discuss their solution with other users that have also solved that problem in the forum and learn how to make their program more efficient by learning new programming skills or new mathematical stuff.

quadrat magic gaudi
Lluís Alemany, computer science student, interested in maths and classical music and WhatIf’s collaborator.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s