TOTIENT CARNIVAL

11 07 2010

Euler´s totient function: \phi(n) is defined as the number of positive integers less than or equal to n, that are coprime to n, and using Iverson bracket, \phi can be written as: (See reference [1])

\phi(n) =\sum_{i=1}^{n}{[gcd(i,n)=1]}

MULTIPLICATIVE BUT NOT COMPLETELY MULTIPLICATIVE FUNCTIONS:

The above summatory can be expressed with the aid of non completely multiplicative arithmetical funcions, using the fact that, some functions hold for inequalities similar to this one:

f(n \cdot m)  f(n) \cdot f(m); if gcd(n,m)\neq 1

And that also hold for the properties that any multiplicative function has:

f(n)> 0

f(n \cdot m) = f(n) \cdot f(m); if gcd(n,m)= 1

Then:

\phi(n)=\sum_{i=1}^{n}{\bigg\lfloor \frac{ f(i \cdot n)}{ f(i)\cdot f(n)}\bigg\rfloor}

And applying this idea to arithmetical functions of common use, we can give, for the divisor sigma functions, the Piltz divisor functions and the squarefree kernel [4], respectively:

\phi(n)=\sum_{i=1}^{n}{\bigg\lfloor \frac{\sigma_{k}(i \cdot n)}{\sigma_{k}(i)\cdot \sigma_{k}(n)}\bigg\rfloor}

\phi(n)=\sum_{i=1}^{n}{\bigg\lfloor \frac{\tau_{k}(i \cdot n)}{\tau_{k}(i)\cdot \tau_{k}(n)}\bigg\rfloor}

\phi(n)=\sum_{i=1}^{n}{\bigg\lfloor \frac{rad(i \cdot n)}{rad(i)\cdot rad(n)}\bigg\rfloor}

Or we can construct an implicit formula for the Totient function:

\phi(n)=\sum_{i=1}^{n}{\bigg\lfloor \frac {\phi(i)\cdot \phi(n)}{\phi(i \cdot n)}\bigg\rfloor}

But now we must take care that now:

f(n \cdot m) > f(n) \cdot f(m); if gcd(n,m)\neq 1

so we must invert the fraction inside the floor function.

ADDITIVE BUT NOT COMPLETELY ADDITIVE FUNCTIONS:

The same thing can be done with additive but not completely additive functions:

\phi(n)=\sum_{i=1}^{n}{\bigg\lfloor \frac{\omega(i \cdot n)}{\omega(i) + \omega(n)}\bigg\rfloor} \; (n>1)

OTHER FORMULAS:

This way of constructing new formulas, seems to be trivial and useless, but this is only an excuse to show how works the characteristic or indicator functions, that are underneath the behaviour of the arithmetical functions, and thus the basic Set Theory inside Number Theory.

And of course we can extend this collection of formulas to other functions distinct than \phi, like for example \pi the Prime Counting Function:

\pi(n)=\sum_{i=2}^{n}{\bigg\lfloor \frac{i+1}{\sigma_{1}(i)}\bigg\rfloor} \; (n>1)

\pi(n)=\sum_{i=2}^{n}{\bigg\lfloor \frac{\phi(i)}{i-1}\bigg\rfloor} \; (n>1)

\pi(n)=\sum_{i=2}^{n}{\bigg\lfloor \frac{2}{\tau(i)}\bigg\rfloor}=\sum_{i=2}^{n}{\bigg\lfloor \frac{k}{\tau_{k}(i)}\bigg\rfloor} \; (n>1)


Archives:
[a]-071210-Totient Carnival.nb


References:

[1]-Peter Luschny – OEIS-Wiki: Sequences related to Euler’s totient function.
[2]- N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences.
A000720: pi(n), the number of primes <= n. Sometimes called PrimePi(n) to distinguish it from the number 3.14159…
[3]- N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences.
A000010: Euler totient function phi(n): count numbers <= n and prime to n.
[4]- R. Muller, The On-Line Encyclopedia of Integer Sequences.
A007947: Largest squarefree number dividing n (the squarefree kernel of n)


Advertisements

Actions

Information




%d bloggers like this: