Tuesday, 17 February 2009

MERSENNE NUMBERS TREASURE MAP

The Mersenne generating function splits the integer set in some subsets:

$latex \displaystyle \mathbb{N}\longrightarrow\mathbb{N}$

$latex \displaystyle f(n)\longrightarrow{2^{n}-1=M_n}$

1-INTEGERS PARTITION SET

$latex \displaystyle Composites =\{4,6,8,9,10,12,...\}; \;[2]$

$latex \displaystyle Primes =\{2,3,5,7,11,13,...\}; \;[3]$

$latex \displaystyle Square Free =\{1,2,3,5,6,7,10,...\}; \;[4]$

$latex \displaystyle Integers =\{0,1,2,3,4,5,6,...\}=\mathbb{N}$

$latex \displaystyle \{0,1\} \cup Primes \cup Composites=Integers$

$latex \displaystyle Primes \subset Square Free$

$latex \displaystyle (Square Free-Primes-\{1\}) \subset Composites$

$latex \displaystyle Primes \cap Composites =\emptyset \\$

2-RANGE PARTITION SET

$latex \displaystyle f(0)=0$

$latex \displaystyle f(1)=1$

$latex \displaystyle f(Primes)\cap f(Composites) = \emptyset$

$latex \displaystyle f(Primes) \subset (Square Free \; \cup$ Composite factors of unknown Wieferich Primes $latex )$

$latex \displaystyle f(Primes) \cap Primes = \textrm{Prime Mersenne Numbers}$

$latex \displaystyle f(Composites)\subset Composites$

$latex \displaystyle f(Composites)\cap Primes=\emptyset$

$latex \displaystyle f(Square Free)\subset (Composites \cup \{ 1 \} )$

If $latex \displaystyle n=a*b$ is a composite number, then $latex \displaystyle M_{n}=M_{a*b}$ is also composite, because:
$latex \displaystyle M_{a*b}=2^{a*b}-1=(2^{a}-1)\cdot (1+2^a+2^{2a}+\dots+2^{(b-1)a})=$

$latex \displaystyle M_{a}*\sum_{i=1}^b{2^{(b-i)\cdot a}}$
And also if $latex \displaystyle d|n$ , and if $latex \displaystyle M_d$ , is not squarefree, then $latex M_n$, can not be squarefree [8].

The only known Wieferich primes are 1093 and 3511, but they can not be prime factors of a Mersenne prime, see [6] and [7].

Note: See $latex \displaystyle \frac{M_{n^2}}{M_n}=\sum_{i=1}^n{2^{(n-i)\cdot n}}$ on link [5]

Archives:

References:
[1]- N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences.
A000225: 2^n - 1. (Sometimes called Mersenne numbers, although that name is usually reserved for A001348.)
[2]- N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences.
A002808: The composite numbers: numbers n of the form x*y for x > 1 and y > 1.
[3]- N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences.
A000040: The prime numbers.
[4]- N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences.
A005117: Squarefree numbers: numbers that are not divisible by a square greater than 1.
[5]- Leroy Quet Apr 19 2007, The On-Line Encyclopedia of Integer Sequences.
A128889: a(n) = (2^(n^2) -1) /(2^n -1).
[6]- Labos E., The On-Line Encyclopedia of Integer Sequences.
A049094: 2^n - 1 is divisible by a square >
[7]-Wieferich primes and Mersenne primes Miroslav Kures, Wieferich@Home - search for Wieferich prime.
[8]-Pacific J. Math. Volume 22, Number 3 (1967), 563-564 Henry G. Bray and Leroy J. Warren.

Monday, 16 February 2009

FERMAT AND MERSENNE NUMBERS CONJECTURE-(3)

(2)-CONSTRUCTING SOME FUNCTION ZEROS (ii)

(2.5) POWERS OF A PRIME * ODD SQUAREFREE:

$latex \displaystyle f(N)=f(p_{1}^{k}*M)=f(p_{1}^{k}*p_2*...*p_n)=0\;\rightarrow (k+1)|p_{1}^{k-1}* \phi\left(\frac{N}{p_{1}^{k-1}}\right)$, then the zeros can fall into two cases:

(2.5.1) Case: $latex \displaystyle (k+1)| \phi\left(\frac{N}{p_{1}^{k-1}}\right)$

Then if $latex \displaystyle d_i| \phi\left(\frac{N}{p_{1}^{k-1}}\right)$, $latex \displaystyle f(p_{1}^{d_{i}-1}*M)=0$, and we can built $latex \displaystyle \sigma_{0} \left(\frac{N}{p_{1}^{k-1}}\right)$, zeros,

one for every divisor of the product applied to every distinct prime factor

$latex \displaystyle \prod_{i=1}^{i=n}{ (p_{i}-1)}$ of $latex \displaystyle N$

Note that, in the particular case:

$latex \displaystyle (k+1)=(p_{i}-1) \rightarrow{k=p_{i}-2}\rightarrow{f(p_{1}^{p_{i}-2}*M)=0}$.

And $latex \displaystyle f(p_{1}^{p_{1}-1}*M)=Mod(p_{1}^{p_{1}-2}*\phi\left(\frac{N}{p_{1}^{k-1}}\right),p_{1})=0$.

(2.5.2) Case: $latex \displaystyle (k+1)|p_{1}^{k-1}$

$latex \displaystyle f(p_{1}^{p_{1}^{n}-1})=0$

Saturday, 14 February 2009

FERMAT AND MERSENNE NUMBERS CONJECTURE-(2)

(2)-CONSTRUCTING SOME FUNCTION ZEROS

$latex f(n)=Mod( \phi(n),\sigma_0(n))$

(2.1) PRIMES:

$latex \displaystyle f(p)=Mod(p-1,2)=0$, holds for every odd prime $latex p \in \mathbb{P} -\{2\}$.

$latex f(2)=1$

(2.2) PRODUCT OF DISTINCT PRIMES NOT 2:

$latex \displaystyle f(p_1*p_2*...*p_n)=0$, because $latex \displaystyle \sigma_0(p_i)|\phi(p_i) \rightarrow {2 |(p_i-1)}$, always holds if $latex \displaystyle p_{i} \neq 2$

With $latex \displaystyle k$, distinct primes, none of them equal two, it is possible to combine them in $latex \displaystyle 2^n$, products to find $latex \displaystyle 2^n$ zeros.

This set of zeros can be described as odd squarefree numbers [1].

(2.3) POWERS OF 2:

$latex \displaystyle f(2^k)=0\;\rightarrow (k+1)|2^{k-1}$, so $latex \displaystyle k+1=2^n$ must be a power of 2:

$latex \displaystyle k=2^n-1=M_n$
A power of 2, is a function zero, iff the exponent is a Mersenne number.

$latex \displaystyle f(2^{M_n})=f(2^{2^{n}-1})=0$

(2.4) POWERS OF A PRIME:

$latex \displaystyle f(p^k)=0\;\rightarrow (k+1)|(p-1)*p^{k-1}$, then the zeros can fall into two cases:

(2.4.1) Case: $latex \displaystyle (k+1)|(p-1)$

Then if $latex \displaystyle d|(p-1)$, $latex \displaystyle f(p^{d-1})=0$, and we can built $latex \displaystyle \sigma_{0}(p-1)$, zeros, one for every divisor of $latex \displaystyle (p-1)$.

Note that, in the particular case:

$latex \displaystyle (k+1)=(p-1) \rightarrow{k=p-2}\rightarrow{f(p^{p-2})=0}$.

And $latex \displaystyle f(p^{p-1})=Mod((p-1)*p^{p-2},p)=0$.

(2.4.2) Case: $latex \displaystyle (k+1)|p^{k-1}$

This is more general than (2.3):

$latex \displaystyle f(p^{p^{n}-1})=0$

Archives:

References:
[1]-CRCGreathouse at My Math Forum/Number Theory: Mersenne and Fermat Numbers congruence

Sunday, 8 February 2009

FERMAT AND MERSENNE NUMBERS CONJECTURE-(1)

(1)-INITIAL IDEAS:

Playing, like always, with my computer, I´ve been plotting this function, that includes the Euler totient function, and the Divisor function.

$latex \displaystyle f(n)=Mod( \phi(n),\sigma_0(n))\: , \; n\in\mathbb{N_{*}^{+}}$

The first 25 values of $latex \displaystyle f(n)$, (not in OEIS) are:

$latex \displaystyle \{0, 1, 0, 2, 0, 2, 0, 0, 0, 0, 0, 4, 0, 2, 0, 3, 0, 0, 0, 2, 0, 2, 0, 0, 2,...\}$

Applying $latex \displaystyle f(x)$ to the Fermat Numbers, $latex \displaystyle F_n=2^{2^{n}}+1$, and to the Mersenne Numbers, $latex \displaystyle M_n=2^n-1$, we can conjecture the following congruences:

(1) $latex \displaystyle \phi(F_n) \equiv 0\; (mod \; \sigma_0(F_n))$

(2) $latex \displaystyle \phi(F_n-2) \equiv 0\; (mod \; \sigma_0(F_n-2))$

(3) $latex \displaystyle \phi(M_n) \equiv 0\; (mod \; \sigma_0(M_n))$

(4) $latex \displaystyle \phi(M_n+2) \equiv 0\; (mod \; \sigma_0(M_n+2))$

¿How do they can be proved? [1]

Archives:

References:

[1]-My Math Forum/Number Theory: Mersenne and Fermat Numbers congruence

Friday, 6 February 2009

SUMS INSIDE POWER SET

Let's consider the set of integers less or equal than a given one:

$latex \displaystyle A=\{1,2,3,...,n\}\:\:n\in\mathbb{N}$

If we add all the elements in this set, we have:

$latex \displaystyle S=\sum_{i\in A}{i}=\sum_{i=1}^n{i}=\frac{n^2+n}{2}$

If we look, at the figure, we can see how the sum ,is equal to the area below the "ladder" plotted:

$latex \displaystyle S=S_{(i)}+S_{(ii)}$

Where $latex S_{(i)}$ is the area formed for $latex n$ small triangles, with a $latex \displaystyle \frac{1}{2}$ area, each one; And $latex S_{(ii)}$ is the area of an isosceles triangle with an equal base and height of $latex n$.

$latex \displaystyle S_{(i)}=\frac{1}{2}\cdot n;\quad S_{(ii)}=\frac{1}{2}\cdot n \cdot n;$

And if the aim, of this blog, where to be rigurous instead of, to give simple ideas, an induction proof, should fit here, perfectly [1].
To extend this result, to the sum of all the elements, in the subsets included, in the Power Set of integers less or equal to a given one:

$latex \displaystyle P(A) = \{X:X\subseteq A=\{1,2,3,...,n\}\}$

There are $latex 2^n$ subsets in $latex \displaystyle P(A)$, (see [3] and [4]):

$latex \displaystyle |P(A)| = 2^{|A|} =2^n$

If $latex \displaystyle i\in A$, then this element is in half of the subsets of $latex \displaystyle P(A)$ (observe the relation between the binary digits and the power set [3]): $latex \displaystyle 2^{n-1}$
To get the final result, it is only necessary to multiply both expresions [2]:

$latex \displaystyle h(n)=\sum_{i\in X\subseteq P(A)}{i}= \frac{n^2+n}{2} \cdot 2^{n-1}=(n^2+n) \cdot 2^{n-2}$

NOTE:

$latex \displaystyle h(n)=A001788(n)$

$latex \displaystyle\lim_{x \to{+}\infty}{\frac{h(n+1)}{h(n)}}\displaystyle\lim_{x \to{+}\infty}{2+\frac{4}{x}}=2$
Archives:
References:

[1]-A000217 The On-Line Encyclopedia of Integer Sequences!
[2]-A001788 The On-Line Encyclopedia of Integer Sequences!
[3]-Powerset Construction Algorithm Shriphani Palakodety.
[4]-Course Notes 8: Size of the Power Set. Chris Nowlin.

Monday, 2 February 2009

n! ARITHMETIC FUNCTIONS

Theorem:
If $latex p_j$ is prime, then $latex \displaystyle \alpha_j(n)=\sum_{i=1}^\infty \bigg\lfloor\frac{n}{p_j^i}\bigg\rfloor$ is the exponent of $latex p_j$ appearing in the prime factorization of $latex n!$

Proof: (see [1] page 104, and [3])

But the infinity summation is applied to a infinity of zeros, because when $latex \displaystyle \frac{n}{p_j^i}<1$, the terms vanish.

So the bigger exponent, $latex m_j$, that makes the terms not null is:
$latex \displaystyle \\n{<}p_j^{m_j}; \rightarrow \frac{\log{n}}{\log{p_j}}{<}m_j; \rightarrow m_j=\bigg\lfloor\frac{\log{n}}{\log{p_j}}\bigg\rfloor; (m_j\in\mathbb{N})$

$latex \displaystyle \alpha_{j}(n)=\sum_{i=1}^{\big\lfloor\frac{\log{n}}{\log{p_j}}\big\rfloor}{\bigg\lfloor\frac{n}{p_j^i}\bigg\rfloor};$

Now we can calculate any arithmetic function, like, e.g., the divisor sigma:

$latex \displaystyle \sigma_{0}(n!)=\prod_{j=1}^{\pi(n)} (\alpha_j(n)+1)$

References:

[1]-Number Theory George E. Andrews - Courier Dover Publications, 1994 - ISBN 0486682528, 9780486682525
[2]-ASYMPTOTIC ORDER OF THE SQUARE-FREE PART OF N! Kevin A. Broughan - Department of Mathematics, University of Waikato, Hamilton, New Zealand
[3]-FUNDAMENTOS DE LA TEORÍA DE LOS NÚMEROS - I. Vinogradov - Editorial MIR

Sunday, 1 February 2009

EUCLINACCI - [1]

Maybe the roughest lesson, someone can ever receive, is this:

$latex 1+1=2$

The implications related to that simple line, can fill a whole library: One of them, is the, so called, Fibonacci sequence:

$latex \{0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...\}$

Defined as:

$latex \displaystyle f_n = \left\{ \begin{array}{lcr} f_0=0;\\ f_1=1;\\ f_n=f_{n-1}+f_{n-2}; \left n \ge 2\\ \end{array}$

Tabulating the ratio between two consecutive terms of the sequence, appear on insight, two properties:

1) This ratio has a finite limit.
2) Two consecutive Fibonacci numbers are
relatively prime.

$latex \begin{array}{rrc} \hline {n} & f_n & f_{n}/f_{n-1} \\ \hline 0 & 0 & -\\ 1 & 1 & -\\ 2 & 1 & 1.0000 \\ 3 & 2 & 2.0000 \\ 4 & 3 & 1.5000 \\ 5 & 5 & 1.6667 \\ 6 & 8 & 1.6000 \\ 7 & 13 & 1.6250 \\ 8 & 21 & 1.6154 \\ 9 & 34 & 1.6190 \\ 10 & 55 & 1.6176 \\ 11 & 89 & 1.6182 \\ 12 & 144 & 1.6180 \\ 13 & 233 & 1.6181 \\ 14 & 377 & 1.6180 \\ 15 & 610 & 1.6180 \\ 16 & 987 & 1.6180 \\ \hline \end{array}$

To prove the first property, we have:
$latex \displaystyle I = \lim_{x \to +\infty} \frac{f_n}{f_{n-1}} = \lim_{x \to +\infty} \frac{f_{n-1}+f_{n-2}}{f_{n-1}} = \\ 1 + \lim_{x \to +\infty} \frac{f_{n-2}}{f_{n-1}} = 1 + \lim_{x \to +\infty} \frac{f_{n-1}}{f_n}; I=1+\frac{1}{I} \Rightarrow I=1+\frac{1}{I}$

With positive solution, equal to the golden ratio.

$latex \displaystyle I=\frac{1+\sqrt{5}}{2}=\Phi$

The proof, of this second property, used to be by induction or contradiction [2], but this can also be proved using the oldest procedure designed to calculate de greatest common divisor, GCD, of two integers, known as The Euclidean Algorithm
The Euclidean method constructs a decreasing sequence of integers who share the same GCD.

$latex (a,b)=(r_0,r_1)=(r_2,r_3)=...=(r_{n-1},r_n)=r_n$

$latex \left \{ \begin{array}{l} a=r_0; \\ b=r_1; \\ r_{i+1}=r_{i-1}-r_i*\bigg \lfloor\frac{r_{i-1}}{r_i}\bigg\rfloor;\\ \end{array}$

if $latex r_{i+1}=0$ then $latex (a,b)=r_i$

Where the function $latex \displaystyle \lfloor x \rfloor$ is the Floor Function, see [3].

Proof:

$latex \displaystyle (f_{n},f_{n-1})=(r_0,r_1)$

$latex \displaystyle r_2=r_0-r_1*\bigg\lfloor\frac{r_0}{r_1}\bigg\rfloor$

$latex \displaystyle r_2=f_n-f_{n-1}*\bigg\lfloor\frac{f_n}{f_{n-1}}\bigg\rfloor=f_n-f_{n-1}*\bigg\lfloor\frac{f_{n-1}+f_{n-2}}{f_{n-1}} \bigg\rfloor$

$latex \displaystyle r_2=f_n-f_{n-1}*\bigg\lfloor 1+\frac{f_{n-2}}{f_{n-1}}\bigg\rfloor =f_n-f_{n-1}*\bigg(1+\bigg\lfloor\frac{f_{n-2}}{f_{n-1}}\bigg\rfloor\bigg)$

$latex \displaystyle f_{n-2}\le f_{n-1} \implies \bigg\lfloor\frac{f_{n-2}}{f_{n-1}}\bigg\rfloor=0$

$latex \displaystyle r_2=f_n-f_{n-1}=f_{n-2}$

$latex \displaystyle(f_{n},f_{n-1})=(r_0,r_1)=(r_1,r_2)=(f_{n-1},f_{n-2})=...=(2,1)=1$

The Euclidean Algorithm reproduces all Fibonacci´s sequence and proves that two consecutive terms are relatively prime.

References:

[1]-Fundamentals of Number Theory William J. LeVeque - Courier Dover Publications, 1996 - ISBN 0486689069, 9780486689067
[2]-Consecutive Fibonacci Numbers Relatively Prime - The Math Forum@Drexel
[3]Weisstein, Eric W. "Floor Function." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/FloorFunction.html