Mathematics

I will collect the solution of different mathematical problems addressed in a variety of programming languages.

---

Factorization

This is a problem proposed for undergraduate students of Mathematical Sciences at the University of Buenos Aires (FCEyN, UBA). The problem has to be solved in the haskell programming language. Haskell is a purely funcional programming language, that is specially suitable for mathematical purposes.

Exercise Write a function factorizar :: Integer -> [(Integer,Integer)] that receives as a parameter an integer n >= 1 and returns a list representing the factorization of n. Formally, the list has to be structured like
[(p₁; k₁), (p₂, k₂),...,(p_m, k_m)] such that

1. p₁, p₂, . . . , p_m and k₁, k₂, . . . ,k_m are positive integers.
2. p₁, p₂, . . . , p_m are primes.
3. p₁ < p₂ < . . . < p_m.
4. p₁^k1 x p₂^k2 x . . . x p_m^km = n

For the value 1, the answer is an empty list, because it has no prime divisors.

Examples of the factorizar function

Query in terminal	Should return
factorizar 6	[(2,1),(3,1)]
factorizar 7	[(7,1)]
factorizar 81	[(3,4)]
factorizar 1176	[(2,3),(3,1),(7,2)]
factorizar 1	[ ]
factorizar 0	*** Exception: ...
factorizar -1	*** Exception: ...

Solution

While the Riemann Hypothesis remains unsolved, there is no easy way in which we can affirm that a number is prime. However, there are some recursive algorithms that let us deal with this situation. I have chosen the one called The sieve of Eratosthenes.

References

• Bernhard Riemann - On the Number of Prime Numbers less than a Given Quantity
• Sieve of Eratosthenes