Friday 25 December 2009

TETRAHEDRAL NUMBERS RECIPROCALS SUM



TETRAHEDRAL NUMBERS SERIES:

This post follows with the exercises on special numbers reciprocals related series, after the blog entries about Square Pyramidal Numbers and Polygonal Numbers . In fact, this example it is not very much interesting, but I wanted to write it before to deal with more difficult problems.

$latex \displaystyle T_{n}=\frac{n(n+1)(n+2)}{6}=\binom{n+2}{3}$

$latex \displaystyle S(n)=\sum_{k=1}^{n}{\frac{1}{T_{k}}=\sum_{k=1}^{n}{\frac{6}{k(k+1)(k+2)}$

If we split the main fraction into others:

$latex \displaystyle \frac{S(n)}{6}=\sum_{k=1}^{n}{\frac{1}{k(k+1)(k+2)}}=\sum_{k=1}^{n}{\left( \frac{A}{k}+\frac{B}{k+1}+\frac{C}{k+2} \right) }$

Solving the linear system of equations it gives:

$latex \displaystyle A=\frac{1}{2} \; ; B=-1 \; ; C=\frac{1}{2};$

This three series can be summed easily with the aid of the Harmonic Numbers:

$latex \displaystyle \sum_{k=1}^{n}{\frac{1}{k}=1+\frac{1}{2}+\frac{1}{3}+ \cdots +\frac{1}{n}=H_n$

$latex \displaystyle \sum_{k=1}^{n}{\frac{1}{k+1}=\frac{1}{2}+\frac{1}{3}+ \cdots +\frac{1}{n}+\frac{1}{n+1}=H_n-1+\frac{1}{n+1}$

$latex \displaystyle \sum_{k=1}^{n}{\frac{1}{k+2}=\frac{1}{3}+\frac{1}{4}+ \cdots +\frac{1}{n}+\frac{1}{n+1}+\frac{1}{n+2}=H_n-1-\frac{1}{2} + \frac{1}{n+1}+\frac{1}{n+2}$


If we substitute everything in the expression for the reciprocals sum:


$latex \displaystyle \frac{S(n)}{6}=\frac{n}{n+1}-\frac{1}{2}-\frac{1}{4} +\frac{1}{2(n+1)}+\frac{1}{2(n+2)}$

In the previous step we can see what does exactly means to be a "telescoping series", the term $latex H_n$, has vanished and there is no need to handle Euler Mascheroni Gamma and Digamma Function:

$latex H_{n}=\gamma + \psi_{0}(n+1)$

Then the formula for the n-th partial sum is:

$latex \displaystyle S(n)=\frac{3n(3+n)}{2(1+n)(2+n)}$

And evaluating the limit we get:

$latex \displaystyle S(\infty)=\lim_{n \leftarrow \infty}{S(n)}=\frac{3}{2}$


References:

[1]-Tetrahedral Number at- Wikipedia
[2]-Weisstein, Eric W. "Tetrahedral Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/TetrahedralNumber.html
[3] A000292-Tetrahedral (or pyramidal) numbers: C(n+2,3) = n(n+1)(n+2)/6. The On-Line Encyclopedia of Integer Sequences!


Thursday 24 December 2009

SPLITTING FTA FUNCTIONS (III)

PILTZ DIVISOR FUNCTIONS (2)


THEOREM-2:

$latex \tau_{j+k}(n)=\sum_{d|n}^{}{\tau_{j}(d)\cdot\tau_{k}\left(\frac{n}{d}\right)}$

Proof:

The Piltz Divisor functions are multiplicative, so it is only necessary to prove the case $latex p^{\alpha}$

In the previous post we saw how:

$latex \tau_{k}(p^\alpha)=\binom{\alpha+k-1}{k-1}$

And if we apply $latex p^\alpha$ to second member of the problem identity, then:

$latex f(p^\alpha)=\sum_{d|p^\alpha}^{}{\tau_{j}(d)\cdot\tau_{k}\left(\frac{p^\alpha}{d}\right)}=\sum_{i=0}^{\alpha}{\tau_{j}(p^i)\cdot\tau_{k}(p^{\alpha-i})=\sum_{i=0}^{\alpha}{\binom{i+j-1}{j-1}\binom{\alpha-i+k-1}{k-1}=$

$latex =\binom{\alpha+j+k-1}{j+k-1}=\tau_{j+k}(p^\alpha)$

This proof seems easy except for the binomial identity step:

$latex \sum_{i=0}^{\alpha}{\binom{i+j-1}{j-1}\binom{\alpha-i+k-1}{k-1}=\binom{\alpha+j+k-1}{j+k-1}$

After several unfruitful tries to prove it, due to my lack of mathematical skills, I resigned myself to look for information about this problem on the bibliography, this formula look very close to the one found on reference [1] or [2], but with an additional variable, and after many reviews, I was glad to find a combinatorial version of the proof into the book of Chuan Chong Chen and Khee-Meng Koh [3]

This proof solved the problem, but it let me very much unsatisfied, and I begun to rethink about this topic again.

This problem is about Number Theory and not Combinatorics, and I had to revise the first lesson about the properties of Dirichlet Product:

Dirichlet´s functional convolution is associative: we can put the brackets wherever we want, so:

$latex \tau_{j+k}(n)=(\underbrace{I_{0}(n)*...*I_{0}(n)}_{j}) *( \underbrace{I_{0}(n)*...*I_{0}(n)}_{k})=\tau_{j}(n)*\tau_{k}(n)$

This simple line proves this trivial property of the Piltz functions that I pedanticly considered as a Theorem, and it proves, as a tip, the binomial formula. The readers of this blog (if any) may forgive me.

But after all of this mess, I´ve learned many interesting things:

1) Number Theory counts with powerful mathematical tools than can be used for many unexpected purposes, just to mention the relationship between the Piltz functions and the Jacobi polynomials.
2) The properties of arithmetical functions can be used to get elegant proofs for binomial identities. (This is the opposite way that the one I took).
3) In my effort to deal with binomial identities, I discovered some formulas for determinants of matrices with binomial coefficients. (Well, there´s many articles about this topic, but I worked without previous knowledge of them). Anyhow, I haven´t found this formula somewhere but here.


References:

[1]-Matthew Hubbard and Tom Roby - Pascal's Triangle From Top To Bottom -Catalog #: 31000005
[2]-Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: Addison-Wesley, 1994 - Concrete Mathematics - Identity (5.26)
[3]-Chuan Chong Chen,Khee-Meng Koh - Principles and techniques in combinatorics page 88-Example 2.6.2-Shortest Routes in Rectangular Grid.

Monday 21 December 2009

SPLITTING FTA FUNCTIONS (II)

PILTZ DIVISOR FUNCTIONS (1)


INTRO:

If we look for an example of "Functions that depend only on coefficients", our first idea should be the divisor function, $latex \tau_{2}(n)$ because it is multiplicative with:

$latex \tau_{2}(p^\alpha)=1+\alpha$

Here, they only appear the coefficients but not the primes.

With the help of recursive Dirichlet Convolution of the unit, $latex I_{0}(n)=1$, it is possible to construct a sequence of arithmetical functions only dependent on the coefficients of the prime factors of any number, known as Piltz Divisor Functions, $latex \tau_{k}(n)$, because they give the number of distinct solutions of the equation $latex x_{1}x_{2} \cdots x_{k}=n$, where $latex x_{1},x_{2},\cdots,x_{k}$ run indepently through the set of positive integers) or, if preferred, they give the number of ordered factorizations of $latex n$ as a product of $latex k$ terms. (References [3],[4] and [11])

DEFINITION:

$latex \displaystyle \tau_{1}(n)=I_{0}(n)=1 $

$latex \tau_{k}(n)=\sum_{d|n}^{}{\tau_{k-1}(d)\cdot I_{0}(n/d)}=\sum_{d|n}^{}{\tau_{k-1}(d)} $


This recursion can also be notated in terms of Dirichlet Product as:

$latex (f*g)(n)=\sum_{d|n}{f(d)\cdot g(n/d)}$

$latex \tau_{k}(n)=\tau_{k-1}*I_{0}(n)$




NOTES ON NOTATION:

The divisor function can be found on the literature as: $latex d(n)$, $latex \sigma_{0}(n)$, $latex \tau(n)$, and in this post as $latex \tau_{2}(n)$.

The "$latex \sigma$´s", and "$latex \tau$´s" are two different series of arithmetical functions that share one element in common: The divisor function. With the help of this two notations, it is possible to remark what kind of series we are working with.

On the other hand the "$latex d$", it is a simple notation that can be used for another purposes, were the belonging to this series of functions, does not matters.

Unfortunately, this happens not only with the divisor function, the mathematical notation on arithmetical functions related to Dirichlet convolution (or product) varies from one book to another, and not only distinct functions are named the same, but all cases of "non-biyectivity" between notations and functions can be found.

Hereinafter we are going to use:

$latex I_{k}(n)=n^{k}$ ( like in Reference [3] but with $latex I_{0}(n)=1$ and $latex I_{1}(n)=n$)

The identity element for Dirichlet´s product (or unit function), using Kronecker´s delta notation, is:

$latex \displaystyle \delta_{1n}= \bigg\lfloor \frac{1}{n} \bigg\rfloor$ (Reference [2])

$latex \omega(n)$ means the number of
distinct prime factors of $latex n$



PROPERTY:

$latex \tau_{k}(n)$ is multiplicative because $latex \tau_{k-1}(n)$, and $latex \tau_{1}(n)$ are multiplicative.

This property can also be derived from the behavior of the Dirichlet Product, but we must note that although $latex \tau_{1}(n)=I_{0}(n)=1$ is a completely multiplicative function, its convolution: $latex \tau_{2}(n)$ is multiplicative, but it is not completely multiplicative.


THEOREM-1: [1] and [4]

$latex \displaystyle \tau_{k}(n)=\prod_{i=1}^{\omega(n)}{\prod_{j=1}^{k-1}\frac{\alpha_{i}+j}{j}}=\prod_{i=1}^{\omega(n)}{\binom{\alpha_{i}+k-1}{k-1}}; \; (k \ge 1)$


Proof:

$latex \displaystyle \tau_{k}(p^\alpha)=\sum_{d|p^\alpha}^{}{\tau_{k-1}(d)}=\tau_{k-1}(1)+\tau_{k-1}(p)+\tau_{k-1}(p^2)+ \cdots +\tau_{k-1}(p^\alpha)$

$latex \displaystyle \tau_{k}(p^\alpha)= \sum_{i=0}^{\alpha}{\tau_{k-1}(p^i)} =\sum_{i=0}^{\alpha}{\binom{i+k-2}{k-2}=\binom{\alpha+k-1}{k-1}$

Lemma:

$latex \displaystyle \sum_{i=0}^{\alpha}{\binom{i+k-2}{k-2}}=\binom{\alpha+k-1}{k-1}$

Proof:

From Parallel Summation Identity (References [6] and [8]):

$latex \displaystyle \sum_{k=0}^{n}{\binom{k+r}{k}}=\binom{n+r+1}{n}$

Substituing: $latex \displaystyle n\rightarrow{\alpha}$ and $latex \displaystyle k\rightarrow{i}$

$latex \displaystyle \sum_{i=0}^{\alpha}{\binom{i+r}{i}}=\binom{\alpha+r+1}{\alpha}$

$latex \displaystyle r\rightarrow{k-2}$ and with Pascal´s Symmetry Rule [7]:

$latex \displaystyle \sum_{i=0}^{\alpha}{\binom{i+k-2}{i}}= \sum_{i=0}^{\alpha}{\binom{i+k-2}{k-2}}= \binom{\alpha+k-1}{\alpha}=\binom{\alpha+k-1}{k-1}$



Corollary-1: Values of $latex \tau_{k}(s)$, being $latex s$ a squarefree number.

If $latex s$ is squarefree then all coefficients of its factorization are $latex \displaystyle \alpha_{i}(s)=1$, then:

$latex \displaystyle \tau_{k}(s)= \prod_{i=1}^{\omega(s)}{\binom{k}{k-1}=k^{\omega(s)}$

For a prime $latex p$, $latex \displaystyle \omega(p)=1$, and $latex \displaystyle \tau_{k}(p)=k$, and if $latex s=1$, then $latex \displaystyle \omega(1)=0$ and $latex \tau_{k}(1)=1$


Corollary-2:

$latex \displaystyle \tau_{k+1}(n^k)=\tau_{k}(n^k)\cdot \tau_2(n) $

Proof:

$latex \displaystyle \tau_{k+1}(n)=\tau_{k}(n)\cdot \prod_{i=1}^{\omega(n)}{\frac{\alpha_{i}+k}{k}}$

$latex \displaystyle \tau_{k+1}(n^k)=\tau_{k}(n^k)\cdot \prod_{i=1}^{\omega(n^k)}{\frac{\alpha_{i}+k}{k}}$

Like $latex \displaystyle \omega(n^k)=\omega(n)$, and $latex \displaystyle \alpha_{i}(n^k)=k\cdot\alpha_{i}(n)$:

$latex \displaystyle \tau_{k+1}(n^k)=\tau_{k}(n^k)\cdot \prod_{i=1}^{\omega(n)}{\frac{k \cdot \alpha_i+k}{k}}=\tau_{k}(n^k)\cdot \prod_{i=1}^{\omega(n)}{(\alpha_i+1)}=\tau_{k}(n^k)\cdot \tau_2(n) $


References:

[1]-p.167-Exercise 5.b - Leveque, William J. (1996) [1977]. Fundamentals of Number Theory. New York: Dover Publications. ISBN 9780486689067
[2]-T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, pages 29 and 38
[3]-J. Sándor: On the Arithmetical Functions $latex d_{k}(n)$ and $latex d_{k}^{*}(n)$, Portugaliæ Mathematica 53, No. 1 (1996)
[4]-I.Vinogradov, Fundamentos de la Teoría de los Números, Editorial RUBIÑOS, ISBN 84-2222-210-8, Segunda Edición,chapter II, Exercise 11, page 44
[5]-J. Sándor, B. Crstici, Handbook of Number Theory (Vol II), Kluwer Academic Publishers, Springer, 2004 ISBN 1402025467, 9781402025464
[6]-Ken.J.Ward, Ken Ward's Mathematics Pages, Parellel Summation-Formula 2.2.2
[7]-Matthew Hubbard and Tom Roby - Pascal's Triangle From Top To Bottom -Catalog #: 1000001
[8]-Matthew Hubbard and Tom Roby - Pascal's Triangle From Top To Bottom - Catalog #: 1100002
[9]-A000012-The simplest sequence of positive numbers: the all 1's sequence. The On-Line Encyclopedia of Integer Sequences!
[10]-A000005-d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n. The On-Line Encyclopedia of Integer Sequences!
[11]-A007425-d_3(n), or tau_3(n), the number of ordered factorizations of n as n = rst. The On-Line Encyclopedia of Integer Sequences!

Friday 18 December 2009

NOTES ON LEGENDRE'S FORMULA

MORE FACTS ABOUT PRIME FACTORIZATION OF FACTORIALS.

In the previous post, we introduced these functions, just as a small trick to calculate the limit we were looking for, but unlikely of what they seem to be, they are less artificial than expected.

Legendre´s formula for the exponent of p in the prime factorization of n!:

$latex \displaystyle\alpha(n,p)=\sum _{i=1}^{\lfloor log_p(n)\rfloor}{ \bigg\lfloor\frac{n}{p^i} \bigg\rfloor = \sum _{i=1}^{\infty} { \bigg\lfloor\frac{n}{p^i} \bigg\rfloor$

Integer Approximation for the Legendre's formula:

$latex \displaystyle \alpha^{*}(n,p)=\bigg\lfloor \frac{n}{p-1}\bigg\rfloor = \bigg\lfloor\sum _{i=1}^{\infty}{\frac{n}{p^i}}\bigg\rfloor$

The diference between one function and its approximation is the error function.

Error Function for the Legendre's formula:

$latex \displaystyle \epsilon(n,p)=|\alpha^{*}(n,p) - \alpha(n,p) |= \alpha^{*}(n,p) - \alpha(n,p)$

$latex \displaystyle \epsilon(n,p)= \bigg\lfloor\sum _{i=1}^{\infty}{\frac{n}{p^i}}\bigg\rfloor - \sum _{i=1}^{\infty} { \bigg\lfloor\frac{n}{p^i} \bigg\rfloor $

We can use $latex \lfloor x \rfloor = x - \left\{ x \right\}$ to get another beautiful expression for the error function:

$latex \displaystyle \epsilon(n,p)= \sum _{i=1}^{\infty} { \left\{ \frac{n}{p^i} \right\} - \left\{ \sum _{i=1}^{\infty}{\frac{n}{p^i}} \right\} $

This function shows fractal behavior:



Particular Values for $latex \epsilon(n,p)$:

$latex \epsilon(n,2)=A011371(n)=n-A000120(n)$, References [1] and [2]

$latex \epsilon(2^{n},2)=1$

$latex \epsilon(2^{n}+1,2)=2$

$latex \epsilon(p^{n},p)=0; \; (p > 2)$

$latex \epsilon(p^{n}-1,p)=n$

$latex \epsilon(p^{n}+1,p)=0; \; (p > 3)$

More facts about Legendre´s $latex \alpha(n,p)$

$latex \alpha(n,2)$ gives also the number of 1's in binary expansion of $latex n$ (or the sum of all its binary digits).

And if we extend the range of this formula, been $latex b$ any number not necessarily prime, then:

$latex \displaystyle \alpha(b^{n},b)=\frac{b^{n}-1}{b-1}=R_{n}^{(b)}$

It gives the base $latex b$ repunits, and so for base $latex 2$:

$latex \alpha(2^{n},2)=2^{n}-1=M_{n}$

It gives the Mersenne Numbers.

Amazingly, this uninteresting topic, at first sight, becomes a joint between: Repunits, Mersenne numbers, Factorials, primes, fractals, counting of digits...

Number Theory is it!


References:

[1]-A011371-n minus (number of 1's in binary expansion of n). Also highest power of 2 dividing n!. The On-Line Encyclopedia of Integer Sequences!
[2]-A000120-1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n). The On-Line Encyclopedia of Integer Sequences!
[3]-Cooper, Topher and Weisstein, Eric W. "Digit Sum." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/DigitSum.html


Archives:

[a]-121809-Notes on Legendre´s Formula.nb


Saturday 12 December 2009

TRAILING ZEROS IN n!



BEHAVIOR OF THE PERCENTAJE OF TRAILING ZEROS IN THE DECIMAL EXPANSION OF n!

It was many and many a year ago, In a kingdom by the sea , I spent a very good time reading an spanish translation of Martin Gardner´s "Mathematical Magic Show" [1] , just because Annabel was not very much interested on me.

In this compilation from Scientific American, Gardner dedicated some pages to this topic in an article called "Factorial Oddities".

Gardner explained how, as $latex n$ increases, $latex n!$ is having more and more factors including the prime factor $latex 5$, that with other factors with any $latex 2$ it gives $latex 10$´s that accumulates in the decimal expansion of $latex n!$ creating a long tail of zeros [2] that fill the least significant digits of this kind of huge numbers.

As it is possible to calculate this number of trailing zeros without having to expand the whole factorial, I wondered (when I was sixteen) if this final zeros were giving very much information about the digits of the whole factorial number or not.

To answer this question, it is necessary to study the behaviour of $latex PTZ(n)$ the percentage between the trailing zeros and the total number of digits of $latex n!$ when $latex n$ tends to infinity.

Number of Digits of n!: [3]

$latex \displaystyle D_{10}(n!)=1+\lfloor log_{10}(n!) \rfloor$

Exponent of p in the prime factorization of n!: (Legendre´s formula)

$latex \displaystyle\alpha(n,p)=\sum _{i=1}^{\lfloor log_p(n)\rfloor}{ \bigg\lfloor\frac{n}{p^i} \bigg\rfloor $

Number of Trailing Zeros in n!. (See sequence [2])

$latex NTZ(n!)=\alpha(n,5) $

PTZ(n!) = Percentage of trailing zeros of the total digits in n! (%)

$latex \displaystyle PTZ(n!)=100*\frac{NTZ(n!)}{D_{10}(n!)}$

But if we want to test the limit of $latex PTZ(n)$ we need to work more handy bounds of this functions, notated with an added asterisk, and that they are going to hold for:

$latex \displaystyle D_{10}^{*}(n!) < D_{10}(n!)$ $latex \displaystyle NTZ^{*}(n!) \ge NTZ(n!)$ $latex \displaystyle PTZ^{*}(n!) > PTZ(n!)$

Approximation for the Number of Digits of n!:

We can sustitute the famous Stirling's approximation instead of $latex n!$ in the formula for $latex D_{10}(n!)$:

$latex \displaystyle n! \approx \sqrt{2\pi n} \left({\frac{n}{e}\right)}^n$

$latex \displaystyle D_{10}(n!)=\left\lfloor \frac{-n+\left(n+\frac{1}{2}\right) \log (n)+\frac{1}{2} \log (2 \pi )}{\log (10)}\right\rfloor +1 +\delta_{n,1}$

The last formula gives the exact value for the number of digits of $latex n!$, for $latex n>0$, because the error for the Stirling´s formula is $latex O\left(\frac{1}{n}\right)$

But for our purposes we must make some changes inside $latex D_{10}(n)$ to get a continuous lower bound:

$latex \displaystyle D_{10}^{*}(n!)=\frac{-n+\left(n+\frac{1}{2}\right) \log (n)+\frac{1}{2} \log (2 \pi )}{\log (10)} < D_{10}(n)$ Approximation for the Legendre's formula and for the Number of Trailing Zeros:

$latex \displaystyle\alpha(n,p)= \sum _{i=1}^{\lfloor log_p(n)\rfloor} { \bigg\lfloor\frac{n}{p^i} \bigg\rfloor = \sum _{i=1}^{\infty} { \bigg\lfloor\frac{n}{p^i} \bigg\rfloor \leq \bigg\lfloor\sum _{i=1}^{\infty}{\frac{n}{p^i}}\bigg\rfloor =\bigg\lfloor \frac{n}{p-1}\bigg\rfloor =\alpha^{*}(n,p)$

$latex NTZ^{*}(n!) =\frac{n}{4} \ge \bigg\lfloor \frac{n}{4}\bigg\rfloor = \alpha^{*}(n,5) \ge \alpha(n,5)=NTZ(n!)$

Final Result and Limit:

$latex \displaystyle PTZ(n!)\approx PTZ^{*}(n!)=100*\frac{NTZ^{*}(n!)}{D_{10}^{*}(n!)}$

$latex \displaystyle\lim_{n \to{+}\infty}{PTZ^{*}(n!)}=0$

$latex PTZ(n!)$ is always positive and it is upper bounded by a continuous function that tend to zero as $latex n$ tends to infinity.

So the number of trailing zeros of $latex n!$ is giving lesser information about the decimal digits of $latex n!$ when the more grows $latex n$

This result may not cause any surprise, but long time ago I had a lot of fun when I was able to prove and plot it.

This ideas does not finish here, but on the contrary there are many many things than can be derived from this introductory point, and that are going to be material for further development in this blog.


References:

[1]-Gardner, M. "Factorial Oddities." Ch. 4 in Mathematical Magic Show: More Puzzles, Games, Diversions, Illusions and Other Mathematical Sleight-of-Mind from Scientific American. New York: Vintage, pp. 50-65, 1978
[2]-A027868-Number of trailing zeros in n! The On-Line Encyclopedia of Integer Sequences!
[3]-A055642-Number of digits in decimal expansion of n. The On-Line Encyclopedia of Integer Sequences!
[5]-Trailing Zero @ Wikipedia
[6]-Stapel, Elizabeth. "Factorials and Trailing Zeroes." Purplemath. Available from
http://www.purplemath.com/modules/factzero.htm
[7]-A061010-Number of digits in (10^n)!. The On-Line Encyclopedia of Integer Sequences!


Archives:

[a]-121209-Number of Trailing Zeros of n!.nb


Saturday 24 October 2009

BINOMIAL MATRIX (III)

If $latex A_n$ is an square matrix with elements:

$latex \displaystyle a_{i,j}=\binom{i+j+k}{i}$

Then:

$latex \displaystyle |A_{n}|=\binom{n+k+1}{k+1}=\binom{n+k+1}{n}$

Proof:

The $latex \displaystyle A_{n}$ matrix can be decomposed as the product of a lower triangular matrix, $latex L_{n}$, and an upper triangular matrix, $latex U_{n}$:

$latex \displaystyle A_{n}=L_{n}*U_{n}$

Example:

$latex \displaystyle A_{3}=\left(\begin{array}{ccc} 2+k & 3+k & 4+k \\ \frac{1}{2} (2+k) (3+k) & \frac{1}{2} (3+k) (4+k) & \frac{1}{2} (4+k) (5+k) \\ \frac{1}{6} (2+k) (3+k) (4+k) & \frac{1}{6} (3+k) (4+k) (5+k) & \frac{1}{6} (4+k) (5+k) (6+k) \end{array}\right)$

$latex \displaystyle L_{3}= \left(\begin{array}{ccc} 1 & 0 & 0 \\ \frac{3+k}{2} & 1 & 0 \\ \frac{1}{6} (3+k) (4+k) & \frac{2 (4+k)}{3} & 1 \end{array} \right)$

$latex \displaystyle U_{3}=\left(\begin{array}{ccc} 2+k & 3+k & 4+k \\ 0 & \frac{3+k}{2} & 4+k \\ 0 & 0 & \frac{4+k}{3} \end{array} \right)$

After some trial and error puzzle, we can propose as decomposition:

$latex \displaystyle l_{i,j}=\frac{j}{i} \binom{i+k+1}{j+k+1}$

$latex \displaystyle u_{i,j}=\frac{j+k+1}{j}\binom{j}{i}$

If this decomposition is the correct one then the matrix product should be $latex a_{i,j}$:

$latex \displaystyle \sum_{r=1}^n{l_{i,r} \cdot u_{r,j}=\sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}$

Where:

$latex \displaystyle l_{i,r}=\frac{r}{i} \binom{i+k+1}{r+k+1}$

$latex \displaystyle u_{r,j}=\frac{j+k+1}{j}\binom{j}{r}$

$latex l_{i,r}\cdot u_{r,j}$, can be simplified, changing the binomial coefficient to the gamma function, as:

$latex \displaystyle l_{i,r} \cdot u_{r,j}=\frac{j+k+1}{i}\binom{j-1}{r-1}\binom{i+k+1}{r+k+1}$

$latex \displaystyle \sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}=\sum_{r=1}^{min(i,j)}{\frac{j+k+1}{i}\binom{j-1}{r-1}\binom{i+k+1}{r+k+1}} = $

$latex \displaystyle = \frac{j+k+1}{i} \cdot \sum_{r=1}^{min(i,j)}{\binom{j-1}{r-1}\binom{i+k+1}{r+k+1}} = \frac{j+k+1}{i} \cdot \binom{i+j+k}{j+k+1}=$

$latex \displaystyle=\frac{i}{i}\cdot \binom{i+j+k}{j+k}=\binom{i+j+k}{i}=a_{i,j}$

In the last part of the proof, involving binomial coefficients, we have used: (See ref [1] and [2])

1) $latex \displaystyle \sum_{r}^{}{\binom{l}{r+m} \binom{s}{r+n}}=\binom{l+s}{l-m+n}$

2) $latex \displaystyle r\binom{i}{r}=i \binom{i-1}{r-1}$


Now we can calculate easily $latex |A_n|$, because the LU-decomposition used is the so called Doolittle decomposition, where the matrix $latex L_{n}$ has all ones on its diagonal.

$latex \displaystyle |A_{n}|=\prod_{i=1}^{n}{l_{i,i} \cdot u_{i,i}}=\prod_{i=1}^{n}{u_{i,i}}=\prod_{i=1}^{n}{\frac{i+k+1}{i}}=\binom{n+k+1}{n}$

Archives:
[a]-092609-Binomial Matrix (III).nb

References:
[1]-Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: Addison-Wesley, 1994 - Concrete Mathematics - Identity (5.32) in Table 169.
[2]-Matthew Hubbard and Tom Roby - Pascal's Triangle From Top To Bottom - the binomial coefficient website- Catalog #: 3100004.


THE CLONE WARS



I´m tired of rewritting the same posts again and again due to the problems with the external $latex \LaTeX$ services that work with blogger, so I decided to make some changes in order to be the more self-sufficient as possible.

1) I´ve changed mathtex3.js, the java code that gives the blog $latex \LaTeX$ functionality (In particular some lines inside the Don't MOdify Under THis Line Unless You Know What You Are Doing !! piece of code). I hope this does not cause too much damage inside the Death Star.

2) Now, I´ve uploaded this modified java code, to my web page: (Psychedelic-mathtex.js). Now, this code, depends on me, but in the end, this java program invokes the external servers: http://www.forkosh.dreamhost.com/mathtex.cgi and http://mathcache.appspot.com/

3) With the modifications inside Psychedelic-mathtex.js, I can use the same post indistinctively in Blogger and in WordPress.

4) Now, this blog, has a clon copy in WordPress.com , under the original and unexpected name of Psychedelic Geometry

5) WordPress offers its own $latex \LaTeX$ service, so I expect some stability.

6) I´ve begun, also, another blog about technology, chemistry, and many other things I ignore, called: Psychedelic Thermodynamics

Thursday 24 September 2009

BINOMIAL MATRIX (II)

If $latex A_n$ is an square matrix with elements:

$latex \displaystyle a_{i,j}=\binom{i+k}{j}$

Then:

$latex \displaystyle |A_{n}|=\binom{n+k}{n}$


Proof:

The $latex \displaystyle A_{n}$ matrix can be decomposed as the product of a lower triangular matrix, $latex \displaystyle L_{n}$, and an upper triangular matrix, $latex \displaystyle U_{n}$:

$latex \displaystyle A_{n}=L_{n}*U_{n}$

Example:

$latex \displaystyle A_{3}=\left(\begin{array}{ccc} 1+k & \frac{1}{2} k (1+k) & \frac{1}{6} (-1+k) k (1+k) \\ 2+k & \frac{1}{2} (1+k) (2+k) & \frac{1}{6} k (1+k) (2+k) \\ 3+k & \frac{1}{2} (2+k) (3+k) & \frac{1}{6} (1+k) (2+k) (3+k) \end{array} \right)$

$latex \displaystyle L_{3}=\left(\begin{array}{ccc} 1 & 0 & 0 \\ \frac{2+k}{1+k} & 1 & 0 \\ \frac{3+k}{1+k} & \frac{2 (3+k)}{2+k} & 1 \end{array} \right)$

$latex \displaystyle U_{3}=\left( \begin{array}{ccc} 1+k & \frac{1}{2} k (1+k) & \frac{1}{6} (-1+k) k (1+k) \\ 0 & \frac{2+k}{2} & \frac{1}{3} k (2+k) \\ 0 & 0 & \frac{3+k}{3}\end{array} \right)$

After some math "plumbing", we can propose as decomposition:

$latex \displaystyle l_{i,j}=\frac{i + k}{j + k} \binom{i - 1}{j - 1}$

$latex \displaystyle u_{i,j}=\binom{j - 1}{i - 1} \binom{i + k}{j} {\binom{k + i - 1}{i - 1}}^{-1}$

If this decomposition is correct then the matrix product should be $latex \displaystyle a_{i,j}$:

$latex \displaystyle \sum_{r=1}^n{l_{i,r} \cdot u_{r,j}}=\sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}}$

Where:

$latex \displaystyle l_{i,r}=\frac{i + k}{r + k} \binom{i - 1}{r - 1}$

$latex \displaystyle u_{r,j}=\binom{j - 1}{r - 1} \binom{r + k}{j} {\binom{k + r - 1}{r - 1}}^{-1}$

$latex \displaystyle l_{i,r} \cdot u_{r,j}$, can be simplified, changing the binomial coefficient to the gamma function, as:

$latex \displaystyle l_{i,r} \cdot u_{r,j}=\frac{(i+k)\cdot r}{i \cdot j}\cdot\binom{i}{r}\binom{k}{j-r}$

$latex \displaystyle \sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}}=\sum_{r=1}^{min(i,j)}{\frac{(i+k) r}{i \cdot j}\cdot\binom{i}{r}\binom{k}{j-r}}=\\ \frac{(i+k)}{i \cdot j} \cdot \sum_{r=1}^{min(i,j)}{r\binom{i}{r}\binom{k}{j-r}}$

This last expression can be simplified, with the help of:

$latex \displaystyle r\binom{i}{r}=i \binom{i-1}{r-1}$, the Vandermonde´s convolution (see reference [2]), and the absortion formula (see reference [3]), to:

$latex \displaystyle \sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}}=\binom{i+k}{j}=a_{i,j}$

Now we can calculate easily $latex |A_n|$, because the LU-decomposition used is the so called Doolittle decomposition, where the matrix $latex L_{n}$ has all ones on its diagonal.

$latex \displaystyle |A_{n}|=\prod_{i=1}^{n}{l_{i,i}*u_{i,i}}=\prod_{i=1}^{n}{u_{i,i}}=\prod_{i=1}^{n}{\frac{i+k}{i}}=\binom{n+k}{k}=\binom{n+k}{n}$


Archives:[a]-092609-Binomial Matrix (II).nb


References:
[1]-John H. Mathews and Kurtis Fink, 2004 - Module for PA = LU Factorization with Pivoting
[2]-Matthew Hubbard and Tom Roby - Pascal's Triangle From Top To Bottom - the binomial coefficient website- Catalog #: 3100003.
[3]-Matthew Hubbard and Tom Roby - Pascal's Triangle From Top To Bottom - the binomial coefficient website- Catalog #: 2400002.



Tuesday 22 September 2009

BINOMIAL MATRIX (I)

If we use yesterday's idea, with little variations, we can create new expressions for matrices with elements related to binomial coefficients, for instance:

Let be $latex U_n$ an square matrix with elements:

$latex \displaystyle u_{i,j}=\binom{j}{i}$

$latex U_n$ is an upper triangular matrix with all its diagonal elements equal to $latex 1$, and similar to Pascal's triangle.(That I prefer to name Tartaglia's Triangle)

Example:

$latex U_{10}= \left( \begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 0 & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45\\ 0 & 0 & 1 & 4 & 10 & 20 & 35 & 56 & 84 & 120 \\ 0 & 0 & 0 & 1 & 5 & 15 & 35 & 70 & 126 & 210 \\ 0 & 0 & 0 & 0 & 1 & 6 & 21 & 56 & 126 & 252 \\ 0 & 0 & 0 & 0 & 0 & 1 & 7 & 28 & 84 & 210 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 8 & 36 & 120 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 9 & 45 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 10 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right)$

And, of course:

$latex |U_{n}|=1$

If we multiply this matrix by its transposed one, then we get a symmetrical matrix with:

$latex |A_{n}|=|U_{n}^{T}*U_{n}|=|U_{n}|^2=1$

Example:

$latex A_{10}=U_{10}^{T}*U_{10}$

$latex \displaystyle A_{10}=\\ \\ \left( \begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 2 & 5 & 9 & 14 & 20 & 27 & 35 & 44 & 54 & 65 \\ 3 & 9 & 19 & 34 & 55 & 83 & 119 & 164 & 219 & 285 \\ 4 & 14 & 34 & 69 & 125 & 209 & 329 & 494 & 714 & 1000 \\ 5 & 20 & 55 & 125 & 251 & 461 & 791 & 1286 & 2001 & 3002 \\ 6 & 27 & 83 & 209 & 461 & 923 & 1715 & 3002 & 5004 & 8007 \\ 7 & 35 & 119 & 329 & 791 & 1715 & 3431 & 6434 & 11439 & 19447 \\ 8 & 44 & 164 & 494 & 1286 & 3002 & 6434 & 12869 & 24309 & 43757 \\ 9 & 54 & 219 & 714 & 2001 & 5004 & 11439 & 24309 & 48619 & 92377 \\ 10 & 65 & 285 & 1000 & 3002 & 8007 & 19447 & 43757 & 92377 & 184755 \end{array}\right)$

So we have constructed a new matrix with determinant equal to one:

$latex \displaystyle a_{i,j}=\sum_{r=1}^n{u_{i,r}^{*} \cdot u_{r,j}}=\sum_{r=1}^{min(i,j)}{u_{r,i} \cdot u_{r,j}}$

$latex \displaystyle a_{i,j}=\sum_{r=1}^{min(i,j)}{\binom{i}{r} \binom{j}{r}}=-1+\sum_{r=0}^{i}{\binom{i}{r} \binom{j}{r}}=\binom{i+j}{i}-1=\binom{i+j}{j}-1$

Note(i): For a proof on binomial identity see references [1] or [2]

OEIS Related Sequences:




Row/Column


Sequence
1 A000027
2 A000096
3 A062748
4 A063258
5 A062988
6 A124089
7 A124090
8 A165618
9 A035927
10 -


References:
[1]-Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: Addison-Wesley, 1994 - Concrete Mathematics - Identity (5.32) in Table 169.
[2]-Matthew Hubbard and Tom Roby - Pascal's Triangle From Top To Bottom - the binomial coefficient website- Catalog #: 3100004.

Monday 21 September 2009

BETA FUNCTION MATRIX DETERMINANT



If $latex A_n$ is an square matrix of order $latex n$, whose elements are defined as:

$latex \displaystyle a_{i,j}=\frac{1}{\beta(i,j)}$, where $latex \beta$ is the beta function. Then:

$latex |A_{n}|=n!$


Proof:

If we use Cholesky method, we can decompose this matrix as:

$latex A_{n}=U_{n}^{T}*U_n$

Where $latex U_n$ is an upper triangular matrix.

But instead of applying the algorithm to a generic case, we are going to propose a factorization, and after we will check that this decomposition generates the appropriate matrix. This mean to use software to speed up the proof, like:

$latex \displaystyle A_{5}=\left(\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 6 & 12 & 20 & 30 \\ 3 & 12 & 30 & 60 & 105 \\ 4 & 20 & 60 & 140 & 280 \\ 5 & 30 & 105 & 280 & 630 \end{array} \right)= U_{n}^{T}* \left( \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 0 & \sqrt{2} & 3 \sqrt{2} & 6 \sqrt{2} & 10 \sqrt{2} \\ 0 & 0 & \sqrt{3} & 4 \sqrt{3} & 10 \sqrt{3} \\ 0 & 0 & 0 & 2 & 10 \\ 0 & 0 & 0 & 0 & \sqrt{5} \end{array} \right)$

The elements of $latex U_n$, seems to be:

$latex \displaystyle u_{i,j}=\sqrt{i}\cdot \binom{j}{i}$

$latex U_{n}^T$ is the transpose of $latex U_n$, so:

$latex \displaystyle u_{i,j}^{*}=u_{j,i}=\sqrt{j} \cdot \binom{i}{j}$

If we multiply both triangular matrices:

$latex \displaystyle a_{i,j}=\sum_{r=1}^n{u_{i,r}^{*} \cdot u_{r,j}} =\sum_{r=1}^n{r \cdot \binom{i}{r} \binom{j}{r}}=\sum_{r=1}^{min(i,j)}{r \cdot \binom{i}{r} \binom{j}{r}}$

This last binomial expression, can be added to a closed form, equal to the reciprocal of beta function, (See proof on reference [1])

$latex \displaystyle a_{i,j}=i \cdot \binom{i+j-1}{j-1}=\frac{1}{\beta(i,j)}$

Now, that we have found this decomposition, for $latex A_n$, then it is unique and $latex A_n$ is Hermitian and positive definite.

$latex \displaystyle |A_{n}|=|U_{n}^{T}*U_{n}|=|U_{n}|^{2}=\left(\prod_{i=1}^{n}{u_{i,i}}\right)^{2}=\prod_{i=1}^{n}{u_{i,i}^2}=\prod_{i=1}^{n}{\left(\sqrt{i}\cdot\binom{i}{i}\right)^2}=\prod_{i=1}^{n}{i}=n!$

Archives:[a]-092109-Beta Determinant.nb


References:
[1]-Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: Addison-Wesley, 1994 - Concrete Mathematics - page 181 Problem 5
[2]-A000142-Factorial numbers: n! The On-Line Encyclopedia of Integer Sequences!

Tuesday 8 September 2009

CURIOUS SERIES-002

This is the Dirichlet convolution of $latex \displaystyle \omega*1$:

$latex \displaystyle a(n)=\sum_{d|n}{\omega(d)}$

Where $latex \displaystyle \omega$ is the number of distinct prime factors function.

This function, $latex \displaystyle \omega(n)$ is an additive function:

$latex \displaystyle \omega(n)=\omega(d \cdot n/d ) \leq \omega(d)+\omega(n/d)$

Where the equal symbol holds iff $latex GCD(n/d,d)=1$

If we sum over all divisors:

$latex \displaystyle \sum_{d|n}{\omega(n)} \leq \sum_{d|n}{\bigg(\omega(d)+\omega(n/d)\bigg)}=\sum_{d|n}{\omega(d)}+\sum_{d|n}{\omega(n/d)}=2 \sum_{d|n}{\omega(d)} $

$latex \displaystyle \omega(n)\cdot \sum_{d|n}{1}=\omega(n)\cdot\tau_{2}(n) \leq 2 \sum_{d|n}{\omega(d)}=2\cdot a(n)$

If $latex s$ is a squarefree number and if $latex d|s$ then $latex GCD(d,d/s)=1$ and, the number of divisors , $latex \displaystyle \tau_{2}(s)=2^{\omega(s)}$, then:

$latex \displaystyle a(s)=\omega(s)\cdot 2^{\omega(s)-1}$

For every number $latex n>1$:

$latex \displaystyle a(n)=\sum_{d|n}{\omega(d)} \leq \sum_{d|n \; d\neq 1}{\omega(n)}= \omega(n) \cdot \sum_{d|n \; d\neq 1}{1}= \omega(n)\cdot(\tau_{2}(n)-1) $

$latex \displaystyle \omega(n)\cdot(\tau_{2}(n)-1) \geq a(n) \geq \bigg\lceil \frac{\omega(n)\cdot \tau_{2}(n)}{2} \bigg\rceil$


NOTE: Sequences in OEIS:

$latex a(n)=A062799(n)$

$latex \omega(n)=A001221(n)$

$latex \tau_{2}(n)=A000005(n)$

References:

[1]-A062799-Inverse Moebius transform of A001221, the number of distinct prime factors of n The On-Line Encyclopedia of Integer Sequences!
[2]-A001221-Number of distinct primes dividing n (also called omega(n)). The On-Line Encyclopedia of Integer Sequences!
[3]-A000005-d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n.. The On-Line Encyclopedia of Integer Sequences!


Friday 28 August 2009

SPLITTING FTA FUNCTIONS (I)

The Fundamental Theorem of Arithmetic (FTA) grants every natural number, $latex n>1$, a unique factorization of the form:

$latex \displaystyle n=p_1^{\alpha_1}p_2^{\alpha_2}...p_{\omega(n)}^{\alpha_{\omega(n)}} = \prod_{i=1}^{\omega(n)} p_i^{\alpha_i}$

Where $latex \omega(n)$ is the number of distinct prime factors of n.

The arithmetical functions can be evaluated once the factorization of $latex n$ is known, (although there are many of them that can be calculated without factorization)

In fact, the only way to "express some arithmetical property of $latex n$" is that the function, must be dependant on the primes, $latex p_i$ and (or) on the coefficients, $latex \alpha_i$

So the arithmetical functions can be classified, in a psychedelic and unorthodox way of course, in:

1) Functions that depend only on coefficients.

2) Functions that depend only on primes.

3) Functions that depend both on primes and coefficients.

This classification, mathematically speaking, seems to be useless, but it is only an alternative to the alphabetical order, when it comes to deal with this topic.


References:

[1]-D. Joyner, R. Kreminski, J. Turisco @ Applied Abstract Algebra The Fundamental Theorem of Arithmetic
[2]-Arithmetic Function @ Wikipedia Arithmetic Function
[3]-Prime Factor @ Wikipedia Prime Factor

Thursday 27 August 2009

COROLLARY TO EULER´S COROLLARY



It is sure that, after a very short fraction of a second, the first time Euler saw (despite he was one-eyed and partially blind) Gauss´s Gamma Function Multiplication Formula:

$latex \displaystyle \prod _{k=0}^{n-1} \Gamma \left(\frac{k}{n}+z\right)=(2 \pi )^{\frac{n-1}{2}} n^{\frac{1}{2}-n z}\Gamma (n z)$

Euler tested the expresion with $latex \displaystyle z=\frac{1}{n}$ to get his corollary:

$latex \displaystyle \prod _{k=1}^{n-1} \Gamma \left(\frac{k}{n}\right)=\frac{(2 \pi )^{\frac{n-1}{2}}}{\sqrt{n}}$

Or maybe was Gauss who generalized, Legendre´s Gamma Duplication Formula with Euler´s ideas, I haven´t found anything about the real history.

Anyway, if we multiply Euler´s corollary by the Gamma Formula with $latex \displaystyle z=1$, and if we practice the "good habit" of multiplying things by $latex 1$:

$latex \displaystyle \Gamma \left(\frac{n}{n}\right)=\Gamma(1)=\Gamma \left(\frac{2n}{n}\right)=\Gamma(2)=1$

Then we get:

$latex \displaystyle \prod_{k=1}^{2n} \Gamma \left(\frac{k}{n}\right)=\frac{(2 \pi )^{n-1}}{n^n}\Gamma(n)$

References:

[1]-Xavier Gourdon and Pascal Sebah, Introduction to the Gamma Function
[2]-Gamma Function @ Wikipedia Gamma Function

Sunday 16 August 2009

CURIOUS SERIES-001

Curious Series 001

There´s a very common finite series, that use to be, at the begining on every book:

$latex \displaystyle S_{n}(z)=\sum _{k=0}^n z^k =\frac{z^{n+1}-1}{z-1}$

Where $latex z$ can be real or complex.

There is a, very well known, particular case of this series where $latex z=2$:

$latex \displaystyle S_{n-1}(2)=\sum _{k=0}^{n-1} 2^{k} =2^{n}-1=M_n$

$latex \displaystyle M_n$ are the Mersenne Numbers, and due to this sum, is easy to see that the Mersenne numbers consist of all 1s in base-2 (they are base 2 repunits)

But this entry is about another particular case of this finite sum:

$latex \displaystyle S_{n}(\textbf{i})=\sum _{k=0}^{n} \textbf{i}^k$

Where: $latex \textbf{i}=\sqrt{-1}$, is the complex unit.

$latex \displaystyle S_{n}( \textbf{i} ) =\frac{1}{2}(1+\textbf{i}) \left(1-\textbf{i}^{n+1}\right)$

This sum shows periodical behaviour with a period of $latex 4$, and its values changes from one vertex to another in a square of side equal to $latex 1$, if we plot them in the complex plane:

$latex \displaystyle S_{n}( \textbf{i} )=\{1,1+\textbf{i},\textbf{i},0,1,1+\textbf{i},\textbf{i},...\}$

$latex \displaystyle S_{n}(\textbf{i})=1\;$ if $latex \;n\equiv 0\;mod\;4$

$latex \displaystyle S_{n}(\textbf{i})=1+\textbf{i}\;$ if $latex \;n\equiv 1\;mod\;4$

$latex \displaystyle S_{n}(\textbf{i})=\textbf{i}\;$ if $latex \;n\equiv 2\;mod\;4$

$latex \displaystyle S_{n}(\textbf{i})=0\;$ if $latex \;n\equiv 3\;mod\;4$

If we take a look at the real part of the complex number $latex S_{n}(\textbf{i})$:

$latex \displaystyle Re\bigg(\sum _{k=0}^{n} \textbf{i}^k\bigg)=\{1,1,0,0,1,1,0,0,...\}$

Then we had just found the sequence A133872 from OEIS, and then we can construct another expressions for this sequence, and also for the problem series:

$latex \displaystyle A133872(n)=Re\bigg(\sum _{k=0}^{n} \textbf{i}^k\bigg)$

$latex \displaystyle A133872(n)=\frac{1}{2}\bigg(\sum _{k=0}^{n} \textbf{i}^k + \sum _{k=0}^{n} \textbf{i}^{-k}\bigg)$

$latex \displaystyle A133872(n)=\frac{1}{2}+\frac{1}{2} \text{cos}\left(\frac{n \pi }{2}\right)+\frac{1}{2} \text{sin}\left(\frac{n \pi }{2}\right)$

Then, if we expand to trigonometrical functions $latex S_{n}( \textbf{i} )$:

$latex \displaystyle S_{n}( \textbf{i} ) =\left(\frac{1}{2}+\frac{1}{2} \text{cos}\left(\frac{n \pi }{2}\right)+\frac{1}{2} \text{sin}\left(\frac{n \pi }{2}\right)\right) + \textbf{i} \left( \frac{1}{2}-\frac{1}{2} \text{cos}\left(\frac{n \pi }{2}\right)+\frac{1}{2} \text{sin}\left(\frac{n \pi }{2}\right)\right)$

And finally using the information inside OEIS:

$latex \displaystyle S_{n}( \textbf{i} )= \text{mod}\left(\bigg\lfloor\frac{n+2}{2}\bigg\rfloor,2\right)+ \textbf{i}\cdot \text{mod}\left(\bigg\lfloor\frac{n+1}{2}\bigg\rfloor,2\right)\cdot \textbf{i}$


References:[1]-A133872-Period 4: repeat 1,1,0,0. The On-Line Encyclopedia of Integer Sequences!


Sunday 9 August 2009

SUMMERTIME CHANGES


Now that the Fish are jumpin' and the cotton is high: the $latex \LaTeX$ code renderer this blog was using, is not working in the same way it was.

I´ve discovered today, that some older posts with tables and floor function symbols, are not been displayed properly. As far as I know, the server from http://yourequations.com/ has exceeded its files quota, and they have made some changes that are causing this kind of problems.

So I´ve added a new script that provides very good quality $latex \LaTeX$ rendering:

http://www.watchmath.com

with the added advantage that the code is easier to be included inside any page.

I´ve also updated my Mathematica´s version from 5.2 to 6.0 with some files I´ve found "somewhere" on the internet.

Saturday 18 July 2009

INTEGRATING ROUNDING FUNCTIONS (IV)



FLOOR AND INTEGER PART PRODUCT DEFINITE INTEGRAL:
$latex \displaystyle I_4= \int_0^x \lfloor x \rfloor \left\{x\right\} dx $ $latex \displaystyle x^2=(\lfloor x \rfloor + \left\{x\right\})^2 = {\lfloor x \rfloor}^{2} +2 \lfloor x \rfloor \left\{x\right\} + \left\{x\right\}^2 $
$latex \displaystyle \lfloor x \rfloor \left\{x\right\}=\frac{1}{2}(x^2 - \left\{x\right\}^2 - {\lfloor x \rfloor}^{2} )$
$latex \displaystyle I_4=\frac{1}{2} ( \frac{x^3}{3} - I_3 - I_1)$
$latex \displaystyle I_4=\frac{1}{2} ( \lfloor x \rfloor \left\{x\right\}^2 +\frac{{\lfloor x \rfloor}^{2}-\lfloor x \rfloor}{2}) $

The same result can be derived just adding the areas under the curve.

Saturday 11 April 2009

SQUARE PYRAMIDAL NUMBERS RECIPROCALS SUM


This post continues with the work on some special sets of integers related series:

The square pyramidal numbers expression can be found on [1] and it is:

$latex \displaystyle P(n)=\sum_{k=1}^n{k^2}=\frac{n(n+1)(2n+1)}{6}$

The Square pyramidal numbers reciprocal finite serie is:

$latex \displaystyle S(n)=\sum_{k=1}^n{\frac{6}{k(k+1)(2k+1)}}$

Splitting the main fraction into others:

$latex \displaystyle \frac{S(n)}{6}=\sum_{k=1}^n{\frac{1}{k(k+1)(2k+1)}}=\sum_{k=1}^n{\frac{A}{k}+\frac{B}{k+1}+\frac{C}{2k+1}}$

Solving the equations gives:

$latex \displaystyle A=1 ;\; B=1;\; C=-4;$

Substituing the series (ii), and the expression for the Harmonic Numbers (i):

$latex \displaystyle \frac{S(n)}{6}= \sum_{k=1}^n {\frac{1}{k}}+\sum_{k=1}^n{\frac{1}{k+1}}-4\sum_{k=1}^n{\frac{1}{2k+1}}=2H_n-\frac{n}{n+1}-4\sum_{k=1}^n{\frac{1}{2k+1}}$

Taking into account the expressions: (i),(iv) and (vi), for the digamma function:

$latex \displaystyle \frac{S(n)}{6}= 2\gamma+2\psi_{0}(n+1)-\frac{n}{n+1}-4\sum_{k=1}^n{\frac{1}{2k+1}}$

$latex \displaystyle S(n)=6[ 2\gamma+2\psi_{0}(n+1) -\frac{n}{n+1}-2[\psi_{0}(n+\frac{3}{2})+\gamma+2\log{2}-2]]$

$latex \displaystyle S(n)=6[2\psi_{0}(n+1)-2\psi_{0}(n+\frac{3}{2})-\frac{n}{n+1} -4\log{2}+4]$

Calculating the limit, and using (vii):

$latex \displaystyle S(\infty)= \lim_{x \to{+}\infty}{S(n)}= 6(3-4\log{2})=18-24\log{2}\approx 1.3644676665...$

(see reference [4])





NOTES:

(i) Harmonic Numbers and Digamma Function at integer values:

$latex \displaystyle H_{n}=\sum_{k=1}^n {\frac{1}{k}}=\gamma+\psi_{0}(n+1)$

(ii) Changing series into Harmonic Numbers:

$latex \displaystyle \sum_{k=1}^n{\frac{1}{k+1}} =\sum_{k=1}^n{\frac{1}{k}}-1+\frac{1}{n+1}=H_{n}-\frac{n}{n+1}$

(iii) Changing one series into another:

$latex \displaystyle \sum_{k=1}^n{\frac{1}{2k-1}} -\sum_{k=1}^n{\frac{1}{2k+1}}=1-\frac{1}{2n+1}$

(iv) Digamma function at half-integer values:

$latex \displaystyle \psi_{0}(n+\frac{1}{2})= -\gamma-2\log{2}+2\sum_{k=1}^n{\frac{1}{2k-1}}$

(v) A Digamma function property:

$latex \displaystyle \psi_{0}(z+1)= \psi_{0}(z)+\frac{1}{z}$

(vi) Another expression for Digamma function at half-integer values:

Using (iii), (iv) and (v):

$latex \displaystyle \psi_{0}(n+\frac{3}{2}) = \psi_{0}(n+\frac{1}{2}) +\frac{1}{n+\frac{1}{2}}=\psi_{0}(n+\frac{1}{2})+\frac{2}{2n+1}=$
$latex = -\gamma-2\log{2} +2(1-\frac{1}{2n+1}+\sum_{k=1}^n{\frac{1}{2k+1}} )= -\gamma-2\log{2}+2+2\sum_{k=1}^n{\frac{1}{2k+1}} $

(vii) Limit for Digamma function at half-integer values:

$latex \displaystyle L_{1}(\infty)=\lim_{x \to{+}\infty}{L_{1}(n)}= \lim_{x \to{+}\infty}{[\psi_{0}(n+1)-\psi_{0}(n+\frac{3}{2})] }$

$latex \displaystyle L_{1}(n)=\psi_{0}(n+1)-\psi_{0}(n+\frac{3}{2})=2\log{2} + \sum_{k=1}^n {\frac{1}{k}}-2 \sum_{k=1}^n {\frac{1}{2k-1}}$

$latex \displaystyle L_{1}(n)=2\log{2}-\sum_{k=1}^n {\frac{1}{k(2k-1)}}$

The last serie limit can be derived from the Mercator-Mengoli infinite series for $latex \displaystyle \log{2}\;$. See [3].
This proof is interesting enough for another entry on the blog.

$latex \displaystyle \log{2}=\sum_{k=1}^\infty {\frac{1}{2k(2k-1)}}$

So:

$latex \displaystyle L_{1}(\infty)=0$



References:
[1]-Square Pyramidal Numbers @ Wikipedia Square Pyramidal Numbers
[2]-Weisstein, Eric W. "Digamma Function." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/DigammaFunction.html
[3]-Collection of formulae for log 2-Numbers Constants and Computation-Xavier Gourdon and Pascal Sebah.
[4]-A159354-Decimal expansion of 18-24*log(2) The On-Line Encyclopedia of Integer Sequences!
[5]-A000330-Square pyramidal numbers The On-Line Encyclopedia of Integer Sequences!


Archives:
[a]-041109-SQUARE PYRAMIDAL NUMBERS RECIPROCALS SUM.nb

Tuesday 24 March 2009

INTEGRATING ROUNDING FUNCTIONS-(III)

SQUARE FLOOR FUNCTION DEFINITE INTEGRAL:

$latex \displaystyle I_3= \int_0^x \lfloor x \rfloor^2 dx = \int_0^{\lfloor x \rfloor} \lfloor x \rfloor^2 dx+ \int_{{\lfloor x \rfloor}}^ {x} \lfloor x \rfloor^2 dx $

$latex \displaystyle I_3=\sum_{k=1}^{ \lfloor x \rfloor-1}{k^2} + \left\{{x}\right\}\lfloor x \rfloor^2 $

$latex \displaystyle I_3=P(\lfloor x \rfloor-1) + \left\{{x}\right\}\lfloor x \rfloor^2 $

Where: $latex \displaystyle P(n)$ gives the n-th Square Pyramidal Number.

$latex \displaystyle P(n) =\frac{n(n+1)(2n+1)}{6} $

POWER FLOOR FUNCTION DEFINITE INTEGRAL:

$latex \displaystyle I_4= \int_0^x \lfloor x \rfloor^n dx = \sum_{k=1}^{ \lfloor x \rfloor-1}{k^n} + \left\{{x}\right\}\lfloor x \rfloor^n$

$latex \displaystyle S(n,m)=\sum_{k=1}^{m}{k^n} \;\;\;\;$ is the Faulhaber's formula.

If $latex \displaystyle n=1$ , the formula gives the Triangular Numbers.

And if $latex \displaystyle n=2$ , the formula gives the Square Pyramidal Numbers.

Monday 23 March 2009

INTEGRATING ROUNDING FUNCTIONS-(II)

SQUARE FRACTIONAL PART DEFINITE INTEGRAL:

For any $latex \displaystyle x\geq 0$:

$latex \displaystyle I_1= \int_0^x \left\{{x}\right\}^2 dx = \int_0^{\lfloor x \rfloor} \left\{{x}\right\}^2 dx+ \int_{{\lfloor x \rfloor}}^ {x} \left\{{x}\right\}^2 dx $

The function $latex \displaystyle \left\{{x}\right\}^2$ has a periodical behaviour, so the limits can be reduced to the first period:

$latex \displaystyle I_1= \lfloor x \rfloor \int_0^{1} {\left\{{x}\right\}^2 dx}+ \int_0^{\left\{{x}\right\}}{ \left\{{x}\right\}^2 dx} = \lfloor x \rfloor \int_0^1 x^2 dx+ \int_0^{\left\{{x}\right\}} {x^2 dx}$

$latex \displaystyle I_1= \frac{ \lfloor x \rfloor + \left\{{x}\right\}^3}{3} $

$latex \displaystyle I_1= \int_0^x \left\{{x}\right\}^2 dx= \frac{x+ \left\{{x}\right\}^{3}-\left\{{x}\right\}}{3}$

POWER FRACTIONAL PART DEFINITE INTEGRAL:

The same formula can be extended to any given positive integer power:

$latex \displaystyle I_2= \int_0^x \left\{{x}\right\}^n dx= \frac{x+ \left\{{x}\right\}^{n+1}-\left\{{x}\right\}}{n+1}$

$latex \displaystyle I_2= \frac{ \lfloor x \rfloor + \left\{{x}\right\}^{n+1}}{n+1} $

Sunday 22 March 2009

INTEGRATING ROUNDING FUNCTIONS-(I)


Integer Rounding Functions can be found in many Number Theory texts, but I wasn´t able to find something about its integrals.

The following expressions can be derived just from their plots, adding and subtracting areas. They hold if $latex \displaystyle \;x\geq 0$

The Triangular Numbers function is used to get shorter expressions.

$latex \displaystyle T(n)=\frac{n^{2}+n}{2} $


FLOOR FUNCTION DEFINITE INTEGRAL:

$latex \displaystyle \int_0^x \lfloor x \rfloor dx = \left\{{x}\right\}\lfloor x \rfloor +T(\lfloor x \rfloor-1)$

FRACTIONAL PART FUNCTION DEFINITE INTEGRAL:

$latex \displaystyle \int_0^x \left\{{x}\right\} dx = \frac{x}{2}- \left\{{x}\right\} +T( \left\{{x}\right\} ) $

$latex \displaystyle \int_0^x \left\{{x}\right\} dx = \frac{x}{2} +T( \left\{{x}\right\}-1 ) $

$latex \displaystyle \int_0^x \left\{{x}\right\} dx =\frac{x+ \left\{{x}\right\}^{2}-\left\{{x}\right\}}{2}$

CEILING FUNCTION DEFINITE INTEGRAL:

$latex \displaystyle \int_0^x \lceil x \rceil dx = \lceil x \rceil (x-\lceil x \rceil)+T(\lceil x \rceil)$

All these formulas can be changed using the relations between them:

$latex \displaystyle \left\{{x}\right\}=x- \lfloor x \rfloor $

This topic doesn't finish here it's going to be used on incoming posts.


Archives:

[a]-032209-INTEGRATING INTEGER ROUNDING FUNCTIONS-(I).nb
[b]-032309-CheckIntegratingIntegerRoundingFunctions.pdf


References:


[1]-Štefan Porubský:Retrieved 2009/3/22 from Interactive Information Portal for Algorithmic Mathematics, Institute of Computer Science of the Czech Academy of Sciences, Prague, Czech Republic http://www.cs.cas.cz/portal/AlgoMath/NumberTheory/ArithmeticFunctions/IntegerRoundingFunctions.htm
[2]-Greg Gamble: The University of Western Australia SCHOOL OF MATHEMATICS & STATISTICS The Floor or Integer Part function

Thursday 19 March 2009

INVERSE POLYGONAL NUMBERS SERIES-Notes




The final result, in the preceeding post, can not be derived from a telescoping series [3], if $latex \displaystyle k$ is not integer (See comments at reference [1]).

$latex \displaystyle \sum_{n=1}^\infty \frac{1}{n(n+k)}=\frac{H_k}{k} $

This lack of generality, can be avoided, if we consider a more general definition for the Harmonic Numbers [4], extended to the complex plane, using the function:

$latex \displaystyle H_z=\gamma+\psi_0(z+1) $


Where $latex \displaystyle \psi_0 \;$ is the so called digamma function, and $latex \displaystyle \;\gamma\;$ is the Euler-Mascheroni constant.

If you take a look at the expresion (15), in the reference [2] : We can find that one asymptotic expansion for the digamma function is:

$latex \displaystyle \psi_0(k+1)=-\gamma+\sum_{n=1}^\infty{\frac{k}{n(n+k)} $

This is why the Polygonal Numbers Series sum is working:

$latex \displaystyle H_k=\gamma-\gamma+ \sum_{n=1}^\infty{\frac{k}{n(n+k)} $

$latex \displaystyle \frac{H_k}{k}=\sum_{n=1}^\infty{\frac{1}{n(n+k)}=\frac{\gamma+\psi_0(k+1)}{k} $

And the polygonal numbers infinite sum, can be expressed (if $latex \displaystyle \;s\neq4\;$) as:

$latex \displaystyle S_{\infty}(s)=\frac{2}{4-s}*(\gamma+\psi_{0}\left(\frac{2}{s-2}\right)) $

This expresion works for all $latex \displaystyle s>2$, as well as for all nonreal $latex \displaystyle s$, It also works for all $latex \displaystyle s<2$, except if $latex \displaystyle s<2$, and $latex \displaystyle s$ is $latex \displaystyle \;\;0, 1, 4/3, 6/4, 8/5, 10/6, ... \;$, because $latex \displaystyle \;\psi_0\;$ is not defined for negative integers (See reference) [1]


References:


[1]-Charles R Greathouse IV - Comments @ My Math Forum Inverse Polygonal Series
[2]-Weisstein, Eric W. "Digamma Function." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/DigammaFunction.html
[3]-Telescoping Series @ Wikipedia Telescoping Series
[4]-Sondow, Jonathan and Weisstein, Eric W. "Harmonic Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/HarmonicNumber.html
[5]-Photo Martin Gardner, Mathematical Games, Scientific American, 211(5):126-133, taken from http://bit-player.org/2007/hung-over

Tuesday 10 March 2009

INVERSE POLYGONAL NUMBERS SERIES



Let there be $latex \displaystyle P(n,s)$ the n-th Polygonal Number [4] of s sides, then:

$latex \displaystyle P(n,s)=\frac{ (s-2)*n^{2}-(s-4)*n }{2}$

For s=3, we get the formula for Triangular Numbers

$latex \displaystyle P(n,3)=\frac{n^{2}+n}{2}=T_n$

and with s=4 then we get the Squares:

$latex \displaystyle P(n,4)=n^{2}$

Polygonal numbers hold for the next identity:

$latex \displaystyle P(n,s+1)=P(n,s)+ P(n-1,3)=P(n,s)+ T_{n-1}$

The sum of the inverse of the first k polygonal numbers with side s, is:

$latex \displaystyle S_{k}(s)=\sum_{n=1}^k{} \frac{1}{P(n,s)}$

And its infinite series sum:
$latex \displaystyle S_{\infty}(s)=\sum_{n=1}^{\infty{}} \frac{1}{P(n,s)}$

Than this infinite series is convergent, can be proved, using some convergence test:

Raabe's convergence Test:

$latex \displaystyle \rho=\displaystyle\lim_{n \to{+}\infty}{n*\left(\frac{P(n+1,s)}{P(n,s)}-1\right) }=2>1$

A series with a lower number of sides, upper bounds, series with higher sides: So the convergence in triangular numbers, implies the convergence of the remaining polygonal numbers series:

If $latex \displaystyle s_1>s_2 \longrightarrow{} \frac{1}{P(n,s_1)}<\frac{1}{P(n,s_2)} \longrightarrow{} S_{\infty}(s_1)$

The inverse series with Triangular numbers is a telescoping series [3]:

$latex \displaystyle S_{\infty}(3)=2\cdot\sum_{n=1}^{\infty{}} \frac{1}{n\cdot(n+1)}= 2$

The squares sum is the so called Basel Problem, [1] [2], related with the Riemann Zeta Function:

$latex \displaystyle S_{\infty}(4)=\sum_{n=1}^{\infty{}} \frac{1}{n^2}=\zeta(2)=\frac{\pi^2}{6}$

If $latex \displaystyle s\neq4$, then:

The series is a more general case of a telescoping series [3], related with the Harmonic Numbers.

$latex \displaystyle S_{\infty}(s)=2\cdot \sum_{n=1}^{\infty{}} \frac{1}{(s-2)\cdot n^{2}-(s-4)*n}=\frac{2}{s-2}\cdot\sum_{n=1}^{\infty{}}\frac{1}{n\cdot(n+\frac{4-s}{s-2})}$

$latex \displaystyle \sum_{n=1}^{\infty{}} \frac{1}{n*(n+k)}=\frac{H_k}{k} $

$latex \displaystyle S_{\infty}(s)= \frac{2}{4-s}\cdot H_{\frac{4-s}{s-2}}$

Example: In the hexagonal numbers case:

$latex \displaystyle S_{\infty}(6)= -H_{-\frac{1}{2}} \approx 1.38629$


Archives:

[a]-031009-INVERSE POLYGONAL NUMBERS SERIES.nb


References:

[1]-Estimating Basel Problem@ MAA Online How Euler did it, Ed.Sandifer
[2]-Basel Problem @ Wikipedia Basel Problem
[3]-Telescoping Series @ Wikipedia Telescoping Series
[4]-Polygonal Numbers @ Wikipedia Polygonal Number

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:

[a]-021709-MERSENNE NUMBERS TREASURE MAP.ppt


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:
[a]- 021409-FERMAT AND MERSENNE NUMBER CONJECTURE-(2).nb


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:

[a]-020809-FERMAT AND MERSENNE NUMBER CONJECTURE-(1).nb


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:

[a]-020609-SUMSINSIDEPOWERSET.nb


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