BibTeX AUTOMATIC OEIS CITATIONS

14 02 2010

I’ve been programming a small web application in PHP to get automatically the BibTeX citation of any sequence in the The On-Line Encyclopedia of Integer Sequences.

If you follow this link: OEIS2BibTeX or just click on the above image, then you must enter the desired sequence ID to get the BibTeX citation data, that you can easily copy to your .bib file.

As I begun to learn PHP yesterday´s evening, and this is my first PHP programming, you can guess that this code must have more than one bug.

The citation is done using the @MISC BibTeX entry, that uses as Required fields: none, and as Optional fields: AUTHOR, TITLE, HOWPUBLISHED, MONTH, YEAR, NOTE.

The AUTHOR field contains the OEIS Sequence Author.

HOWPUBLISHED contains the url to the sequence in the OEIS Wiki, and it is assumed to be used with the \LaTeX hyperref packages

MONTH and YEAR are not yet used, and the field NOTE includes the Description of the sequence.

If this small application is used in combination with the BibTeX2HTML it is very fast to reuse the same bibliography data in your web, or in your \LaTeX document.

All the PHP archives can be downloaded and changed if desired.

The reference [1] is an example of how does the Plain format works.


References and Archives:
[1] Clark Kimberling. The On-Line Encyclopedia of Integer Sequences. A045051. Numbers n with property that in base 4 representation the numbers of 0’s and 2’s are 2 and 4, respectively.
[2] Andrew Roberts. Bibtex entry and field types.
www.andy-roberts.net/misc/latex/sessions/bibtex/bibentries.pdf.
[3] Psychedelic Geometry.PHP file. OEIS2BibTeX.php.
[4] Psychedelic Geometry.PHP file. default.php, feb 2010.
[5] Psychedelic Geometry. OEIS2BibTeX web site. http://www.oeis2bibtex.netai.net/, feb 2010.


Advertisements




NOTES ON LEGENDRE´S FORMULA

18 12 2009

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!:

\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:

\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:

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

\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 \lfloor x \rfloor = x - \left\{ x \right\} to get another beautiful expression for the error function:

\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 \epsilon(n,p):

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

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

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

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

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

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

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

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

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

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

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

\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






BINOMIAL MATRIX (III)

24 10 2009

If A_n is an square matrix with elements:

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

Then:

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


Proof:

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

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

Example:

A_{3}=

\displaystyle \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)

\displaystyle L_{n}=\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)

\displaystyle U_{n}=\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:

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

\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 a_{i,j}:

\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:

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

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

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

\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}

\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}} =

\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}=

\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) \displaystyle \sum_{r}^{}{\binom{l}{r+m} \binom{s}{r+n}}=\binom{l+s}{l-m+n}

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

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

\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

24 10 2009

I´m tired of rewritting the same posts again and again due to the problems with the external \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 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 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






BINOMIAL MATRIX (II)

24 09 2009

If A_n is an square matrix with elements:

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

Then:

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


Proof:

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

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

Example:

\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)

\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)

\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:

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

\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 \displaystyle a_{i,j}:

\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:

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

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

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

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

\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:

\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:

\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 |A_n|, because the LU-decomposition used is the so called Doolittle decomposition, where the matrix L_{n} has all ones on its diagonal.

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





BINOMIAL MATRIX (I)

22 09 2009

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 U_n an square matrix with elements:

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

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

Example:

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:

|U_{n}|=1

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

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

Example:

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

\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:

\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}}

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






BETA FUNCTION MATRIX DETERMINANT

21 09 2009

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

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

|A_{n}|=n!


Proof:

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

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

Where U_n is an upper triangular matrix.

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

\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 U_n, seems to be:

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

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

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

If we multiply both triangular matrices:

\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])

\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 A_n, then it is unique and A_n is Hermitian and positive definite.

\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!