### Partial sums of arithmetical functions

In this post I would like to present some interesting generalized formulas for computing the partial sums of some arithmetical functions.

By
Daniel Șuteu

Reactions:

By
Daniel Șuteu

Prime factorization of composite integers has many applications in number theory, especially in computing some important arithmetic functions for large inputs.

One such function is the Euler's totient function `φ(n)`, which it's practically impossible to compute for very large composite values of `n`, if the prime factorization of `n` is not known.

This led to the creation of public-key cryptography systems (such as the RSA algorithm), which are systems responsible for secure communication online and rely on the assumption that it's very hard to factorize a large integer `n` that is the product of two large random prime numbers.

The publication of the RSA algorithm led to an increasing interest in factoring large integers, which also resulted in the creation of several new factorization algorithms, none of which, however, is able to efficiently factorize an RSA modulo of more than `1024` bits.

One such function is the Euler's totient function `φ(n)`, which it's practically impossible to compute for very large composite values of `n`, if the prime factorization of `n` is not known.

This led to the creation of public-key cryptography systems (such as the RSA algorithm), which are systems responsible for secure communication online and rely on the assumption that it's very hard to factorize a large integer `n` that is the product of two large random prime numbers.

The publication of the RSA algorithm led to an increasing interest in factoring large integers, which also resulted in the creation of several new factorization algorithms, none of which, however, is able to efficiently factorize an RSA modulo of more than `1024` bits.

Reactions:

By
Daniel Șuteu

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

Reactions:

By
Daniel Șuteu

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.

Reactions:

By
Daniel Șuteu

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.

`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.

Reactions:

By
Daniel Șuteu

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 series, infinite products and limits.

Reactions:

By
Daniel Șuteu

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.

Reactions:

By
Daniel Șuteu

Named after the great symbolist poet, George Bacovia, I created this library to symbolically manipulate mathematical expressions in a simple and elegant way.

Reactions:

By
Daniel Șuteu

The Mandelbrot set and its complex beauty.

# Formula At its simplest, the Mandelbrot set is defined iteratively by the following formula:

`z_(n+1) = (z_n)^2 + c`

# Generation The rules for generating the Mandelbrot set are surprisingly simple; we begin by defining the following three constants:

`W` = the width of the plane`H` = the height of the plane`Z` = the zoom factor

Then for each value of `x={1,2,...,W}` and `y={1,2,...,H}`, we create a complex number `c` as following:

`c = (2x - W) / (W*Z) + ((2y - H) / (H*Z))i`

The value of `c` is then assigned to a new variable, called `z_1`, as:

`z_1 = c`

Then we define a new constant, called `I`, which represents the total number of iterations that we want to perform (usually, in the range `[30,150]`).

`I = 100`

Then we choose a limit `L`, which will stop the iteration early if a certain value `|z_n|` (where `1 <= n <= I`) exceeds the value of `L`.

`L = 2`

Now we can begin the iteration, with `n={1,2,...,I}`.

`z_(n+1) = (z_n)^2 + c`

A…

# Formula At its simplest, the Mandelbrot set is defined iteratively by the following formula:

`z_(n+1) = (z_n)^2 + c`

# Generation The rules for generating the Mandelbrot set are surprisingly simple; we begin by defining the following three constants:

`W` = the width of the plane`H` = the height of the plane`Z` = the zoom factor

Then for each value of `x={1,2,...,W}` and `y={1,2,...,H}`, we create a complex number `c` as following:

`c = (2x - W) / (W*Z) + ((2y - H) / (H*Z))i`

The value of `c` is then assigned to a new variable, called `z_1`, as:

`z_1 = c`

Then we define a new constant, called `I`, which represents the total number of iterations that we want to perform (usually, in the range `[30,150]`).

`I = 100`

Then we choose a limit `L`, which will stop the iteration early if a certain value `|z_n|` (where `1 <= n <= I`) exceeds the value of `L`.

`L = 2`

Now we can begin the iteration, with `n={1,2,...,I}`.

`z_(n+1) = (z_n)^2 + c`

A…

Reactions:

By
Daniel Șuteu

RSA is a practical public-key cryptographic algorithm, which is widely used on modern computers to communicate securely over large distances.

The acronym of the algorithm stands for Ron Rivest, Adi Shamir and Leonard Adleman, which first published the algorithm in 1978.

# Algorithm overviewChoose `p` and `q` as distinct prime numbersCompute `n` as `n = p*q`Compute `\phi(n)` as `\phi(n) = (p-1) * (q-1)`Choose `e` such that `1 < e < \phi(n)` and `e` and `\phi(n)` are coprimeCompute the value of `d` as `d ≡ e^(-1) mod \phi(n)`Public key is `(e, n)`Private key is `(d, n)`The encryption of `m` as `c`, is `c ≡ m^e mod n`The decryption of `c` as `m`, is `m ≡ c^d mod n`

# Generating `p` and `q` In order to generate a public and a private key, the algorithm requires two distinct prime numbers `p` and `q`, which are randomly chosen and should have, roughly, the same number of bits. By today standards, it is recommended that each prime number to have at least 2048 bits.

In Perl, there is a…

The acronym of the algorithm stands for Ron Rivest, Adi Shamir and Leonard Adleman, which first published the algorithm in 1978.

# Algorithm overviewChoose `p` and `q` as distinct prime numbersCompute `n` as `n = p*q`Compute `\phi(n)` as `\phi(n) = (p-1) * (q-1)`Choose `e` such that `1 < e < \phi(n)` and `e` and `\phi(n)` are coprimeCompute the value of `d` as `d ≡ e^(-1) mod \phi(n)`Public key is `(e, n)`Private key is `(d, n)`The encryption of `m` as `c`, is `c ≡ m^e mod n`The decryption of `c` as `m`, is `m ≡ c^d mod n`

# Generating `p` and `q` In order to generate a public and a private key, the algorithm requires two distinct prime numbers `p` and `q`, which are randomly chosen and should have, roughly, the same number of bits. By today standards, it is recommended that each prime number to have at least 2048 bits.

In Perl, there is a…

Reactions: