Interesting formulas and exercises in number theory

In this post I would like to introduce some interesting exercises in number theory, along with some curious formulas and identities for some number-theoretic functions.

The following list includes the notations used in this post: `φ(n)` is the Euler's totient function`J_k(n)` is the Jordan's totient function`σ_k(n)` is the Divisor (sigma) function`μ(n)` is the Möbius function`c_q(n)` is the Ramanujan's sum function
# Conditional Euler's totient function Given a boolean function `f(x)`, let `a(n)` be the number of integers `k` in the range `[1, n]` for which `f(gcd(n, k))` is true.

For example, if `f(x)` returns a true value only when `x=1`, then the problem reduces to the Euler's totient function: `a(n) = φ(n)`.

This is interesting, because if the prime factorization of `n` can be computed, then we can efficiently compute `φ(n)` using the following formula:

`φ(n) = n * \prod_{p|n} (1 - 1/p)`

where the product is taken over the distinct prime factors of `n`.

Now con…

Investigating the Fibonacci numbers modulo m

The Fibonacci sequence is, without doubt, one of the most popular sequences in mathematics and in popular culture, named after Italian mathematician Leonardo of Pisa (also known as Fibonacci, Leonardo Bonacci, Leonardo of Pisa, Leonardo Pisano Bigollo, or Leonardo Fibonacci), who first introduced the numbers in Western European with his book Liber Abaci, in 1202.

The sequence is elegantly defined as:

`F(0) = 0`
`F(1) = 1`
`F(n) = F(n-1) + F(n-2)`

where the first 20 terms are:

`0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181`

In this post, we investigate the Fibonacci numbers modulo a positive integer `m`. It is well known that for every positive integer `m`, the modular Fibonacci sequence, `F(n) mod m`, is eventually periodic. This period is called the Pisano period.
For example, let's take a look at `F(n) mod 4`:
0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, ...
we observe, as highlighted above in yellow, the Pisano cycle has a length of…

Representing integers as the sum of two squares

Almost 400 years ago, Pierre de Fermat stated that every odd prime of the form `4k+1` can be expressed as the sum of two squares:

`p = x^2 + y^2`

with integers `x` and `y`, if and only if

`p ≡ 1 mod 4`

Later on, around the year 1747, Leonhard Euler was able to prove Fermat's statement correct.
# Overview In this post we present a recursive algorithm for finding all the possible representations, as a sum of two squares, for any given integer that can be expressed this way.
For example, if `n=12345678910111213`, we can represent it as a sum of two squares in 4 different ways:
`12345678910111213 = 1251082^2 + 111104067^2` `12345678910111213 = 13508317^2 + 110286918^2` `12345678910111213 = 52418877^2 + 97969078^2` `12345678910111213 = 64959738^2 + 90143837^2`
If the prime factorization of a number is known, it can be verified if the number is expressible as a sum of two squares by checking each prime factor modulo 4. If a prime factor is congruent to `3 mod 4` , then its power must …

Representing integers as the difference of two squares

Most integers can be represented as the difference of two squares, where each square is a non-negative integer.

Algebraically speaking:

`n = x^2 - y^2`

for some non-negative integers `x` and `y`.

In this blog post we're going to look at a simple and elegant algorithm for finding all the possible representations for any given integer that can be represented as a difference of two squares, using its divisors.

For example, if we have `n = 12345`, we can represent it in four different ways as a difference of two non-negative integer squares:

`12345 = 419^2 - 404^2`
`12345 = 1237^2 - 1232^2`
`12345 = 2059^2 - 2056^2`
`12345 = 6173^2 - 6172^2`

# Finding solutions By writing `n` as the product of two whole numbers, `n = a*b`, we have the following identity:

`a*b = ((a+b)/2)^2 - ((a-b)/2)^2`

Then, by iterating over all the divisors of `n`, we generate all the possible representations for `n` as a difference of two non-negative squares.

In order to generate only integer solutions, we have…

Various representations for famous mathematical constants

In this unusual post, much like in the older post, The beauty of Infinity, we're listing the most famous mathematical constants as representations of infinite seriesinfinite products and limits.

The list of constants considered in this post, are:
Apéry's constant: `\zeta(3)`πmathematical constante mathematical constantEuler-Mascheroni constant: `γ`Catalan's constant: `\G` or `\beta(2)`Natural logarithm of 2: `\log(2)` Most of this representations have a very fast convergence. # Representations for Apéry's constant `\zeta(3) = 5/2 \sum_{n=1}^(\infty) ((-1)^(n - 1) (n!)^2)/(n^3 (2 n)!)`

`\zeta(3) = \sum_{n=1}^(\infty) ((30 n - 11) (n!)^4)/(4 n^3 (2 n - 1) ((2 n)!)^2)`

`\zeta(3) = π \sum_{n=1}^(\infty) ((30 n - 11) Γ(n)^2)/(n 16^n (2 n - 1)^3 Γ(n - 1/2)^2)`

` \zeta(3) = -π^2 / 3 \sum_{n=0}^(\infty) (2^(-2 n) (2 n + 5) ζ(2 n))/((2 n + 1) (2 n + 2) (2 n + 3))`

`\zeta(3) = -(4 π^2)/7 \sum_{n=0}^(\infty) (2^(-2 n) ζ(2 n))/((2 n + 1) (2 n + 2))`

`\zeta(3) = -(4 π^2)/7 [log(…

Thoughts on programming language notations

Some posts ago, we looked at what it's required in creating a new programming language. In this post we're going a little bit more into it, trying to find ways to effectively express meanings in natural ways, similar to what we can express in a natural language.

First, let's begin by considering the sentence: "GeorgelovesMaria".

We have three components: "George"   is the subject doing the action"loves"   is the action itself"Maria"   is the subject on which the action is being done
From a programming language perspective, subjects are equivalent with objects and actions are equivalent with methods.
object1 := George object2 := Maria method  := loves
In an object-oriented programming language, the sentence can be expressed as:

In general, we have:
In a natural language, like Romanian, we can express the same meaning in six different ways: O iubește, George, pe Maria.O iubește, pe Maria, Georg…