PSYCHEDELIC GEOMETRY

ADDING HELP TO OEIS SEQUENCES

2010-07-31T20:14:00.058+02:00

As I´m working on more than one small projects of programming sequences from The On-Line Encyclopedia of Integer Sequences, and as I always try to document my code the best I can: I like to add comments and help information to it, but after many hours of “copy and paste”, and being aware that when you are trying to do something with a computer: if you feel that everything is repetitive and boring, then it is for sure, that you are using the wrong procedure, so then, I decided to create a very simple tools to make my life easier.

The PHP code of these two on-line applications is almost the same than the one of OEIS2BibTeX, but this time changed to provide the help code for PARI/GP or Mathematica OEIS sequences functions.

Both applications can be used in two different ways:

* Entering the Sequence Id number with a HTML form: in a POST METHOD, or
* With the Id Number supplied to the PHP code within the link, using ?sequence=valid_ID

1) PARI/GP

1.1) HTML POST Method:
http://oeis2bibtex.netai.net/helpPARI_GP/

1.2) PHP Parameter:
http://oeis2bibtex.netai.net/helpPARI_GP/OEIS-PARI_GP-Help.php?sequence=A000200
Here you can change A000200 for the desired Sequence Id Number:

2) WOLFRAM MATHEMATICA

2.1) HTML POST Method:
http://oeis2bibtex.netai.net/helpMathematica/

2.2) PHP Parameter:
http://oeis2bibtex.netai.net/helpMathematica/OEIS-Mathematica-Help.php?sequence=A000200

2.3) Mathematica Code using Import:

As Mathematica can access on-line data, these functions can do the job too inside any Mathematica Notebook or Package:

OEISSequenceDescription[seq_String]:=Module[{dataloaded = StringJoin[Import["http://oeis.org/classic/?q=id%3a" <> seq <> "&fmt=3","Data"]], first, last},
first = Flatten[StringPosition[dataloaded, "%N"], 1][[2]];
last = Select[StringPosition[dataloaded, "%"][[All, 1]], # > first&][[1]];
StringReplace[StringTake[dataloaded, {first + 10, last - 1}], "  " ~~ _ -> ""]]


OEISAddHelp[seq_String]:=ToExpression[StringJoin[seq, "::usage=\"",seq, ": ", OEISSequenceDescription[seq], "\""]]

Archives:
[a]-073110-Adding Help to OEIS Sequences.nb

References:

[1]-PARI/GP Development Headquarters - Programming in GP: other specific functions-addhelp
[2]-http://formatmysourcecode.blogspot.com/
[3]-Wolfram Mathematica Documentation Center: Import
[4]-E.Pérez Herrero-OEIS Utilities Page@ OEIS Wiki

TOTIENT CARNIVAL

2010-07-11T13:30:00.072+02:00

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

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

MULTIPLICATIVE BUT NOT COMPLETELY MULTIPLICATIVE FUNCTIONS:

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

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

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

$latex f(n)>0$

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

Then:

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

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

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

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

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

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

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

But we must take care that now:

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

so we must invert the fraction inside the floor function.

ADDITIVE BUT NOT COMPLETELY ADDITIVE FUNCTIONS:

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

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

OTHER FORMULAS:

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

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

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

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

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

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

References:

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

A SMALL FIBONACCI SUM

2010-05-13T21:36:00.009+02:00

If $latex F_{n}$ is the nth Fibonacci Number then:

$latex \displaystyle \sum_{i=0}^{n}{i \cdot F_{2i}} = n \cdot F_{2n+1} - F_{2n}$

This identity can be easily proved using the method of induction with the basic recurrence relation of Fibonacci Numbers.

How can we find methods for constructing new identities like this one?

References:

[1]-Wikipedia - Fibonacci number
[2]-Chandra, Pravin and Weisstein, Eric W. "Fibonacci Number." From MathWorld--A Wolfram Web Resource - http://mathworld.wolfram.com/FibonacciNumber.html

BibTeX AUTOMATIC OEIS CITATIONS

2010-02-14T10:49:00.051+01:00

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

READER'S CORNER (I)

2010-01-17T18:56:00.036+01:00

A BINOMIAL PLAY:

Our contributor Raymond Rogers has sent an alternate proof for:

$latex \displaystyle det{\bigg[ \binom{i+j+k}{i} \bigg]}_{0\leq i,j \leq n} =\binom{n+k+1}{k+1}$

This expression is identical to the one found in the post Binomial Matrix (III), but here the matrices are indexed from zero instead of one.

The proof is entitled A BINOMIAL DETERMINATE,A VERY SHORT PLAY IN THREE ACTS, and it is based on Vandermonde's identity.

Thank you Raymond.

Archives:
[a]-120510-Binomial-Play-R.Rogers.pdf

Links:
[1]-Raymond Rogers, Lamm´s Equation, Confluent Hypergeometric Equations- Lamm´s Equation Blogspot

BINARY BISECTION

2010-01-09T10:14:00.006+01:00

INTRO:

The Bisection Method is a very well known root-finding algorithm that always comes at the very beginning of every book on Numerical Analysis.

The algorithmn searches for a root in the interval, $latex [a_{0},b_{0}]$ in whose endpoints the continous problem function, $latex f(x)$, takes opposite signs:

$latex f(a_{0})f(b_{0})<0$

The Bisection Method is based on Bolzano´s Intermediate Value Theorem, and it can give, also, an alternative proof for it. (Reference [1])

Here, it does not matter the function values: The algorithm does not use any other information from $latex f(x)$, other than its sign changes.

There are excelent pages on the internet that treat this topic, (references [1], [2] and [3] for example), and it would be useless to add more redundant and, for sure, worse presented summary about this numerical method.

I just want to take out something hidden inside the computer software, a small piece of math inside the programming area.

THE LOST FUNCTION

The core of the Bisection Method is the conditional IF... THEN... sentence, where the algorithm chooses in which half of the interval is the desired root.

This conditional evaluation can be converted into a decision function, Let´s say $latex \delta_i$, that gives $latex 0$ if the root is on the left half interval and $latex 1$, otherwise.

Now the iterative sequence can be written using this function, $latex \delta_i$, where:

$latex m_{i}$ is the midpoint of the search interval:

$latex \displaystyle m_{i}=\frac{a_{i}+b_{i}}{2}$

$latex \delta_{i}$ is the decision function, and the $latex \delta(i,j)$, in the second member, is the Kronecker´s delta:

$latex \delta_i=\delta(sgn(f(m_{i})),sgn(f(a_{i})))$

Then:

$latex \delta_{i} = \left\{ \begin{array}{ll} 1 & \mbox{if } (sgn(f(m_{i})=sgn(f(a_{i})) \\\\ 0 & \mbox{if } (sgn(f(m_{i})\neq sgn(f(a_{i})) \end{array}$

The endpoints of the search interval must be:

$latex {[a_{i+1}, b_{i+1}]} = \left\{ \begin{array}{ll} {[m_{i},b_{i}]} & \mbox{if }(\delta_{i}=0) \\\\ {[a_{i},m_{i}]} & \mbox{if } (\delta_{i}=1) \end{array}$

Then, they can be expressed with the aid of $latex \delta_{i}$, as:

$latex a_{i+1}=a_{i}+\delta_{i}\cdot (m_{i}-a_{i})$

$latex b_{i+1}=b_{i}+(1-\delta_{i})\cdot (m_{i}-b_{i})$

Note:
If $latex f(x)$, has only a single root in the interval $latex [a_{0},b_{0}]$, then it is possible to use an alternate version of the decision function:

$latex \delta_i=\delta(sgn(f(m_{i})),sgn(f(a_{0})))$

with the advantage that then it is not necessary to evaluate $latex f(a_{i})$ in the main loop of the algorithm: this implies an improvement in performance.

LENGTHS RATIO:

We can name the ratio of lengths between the intervals $latex [a_{0},a_{i}]$, and $latex [a_{0},b_{0}]$, as the parameter:

$latex \theta_{i}=\frac{a_{i}-a_{0}}{b_{0}-a_{0}}$

If $latex \theta_{i}$ is expressed in function of $latex \delta_{i}$:

$latex \displaystyle \theta_{i}=\sum_{k=0}^{i-1} \frac{\delta_{k}}{2^{k+1}}$

The sequence formed by the distinct values of the decision function, $latex \delta_{i}$, matches up with the binary expansion (or the binary digits) of $latex \theta_{i}$

Then the midpoint and the endpoints of the interval in function of $latex \theta_{i}$, are:

$latex a_{i}=a_{0}+(b_{0}-a_{0})\cdot \theta_{i}$

$latex \displaystyle m_{i}=a_{0}+(b_{0}-a_{0})\cdot \left(\theta_{i}+\frac{1}{2^{i+1}}\right)$

$latex \displaystyle b_{i}=a_{0}+(b_{0}-a_{0})\cdot \left(\theta_{i}+\frac{1}{2^{i}}\right)$

HACKING BISECTION METHOD:

The connection between $latex \delta_{i}$ and $latex \theta_{i}$ can be used to convert the Bisection Method into a method for finding the binary expansion for a root of any function that holds the conditions that this method demands.

For example if we take:

$latex f(x)=x^2-x_{0}$, where $latex x_{0}>0$

with $latex a_{0}=0$ and $latex b_{0}=2^{k}$, where $latex 2^{k-1} < \sqrt{x_{0}} < 2^{k}$, then:

$latex \sqrt{x_{0}}=\lim_{i \to +\infty}{\theta_{i}}$

and the sequence of $latex \delta_{i}$ gives the binary digits of $latex \sqrt{x_{0}}$

Archives:
[a]-010910-Binary Bisection.nb

References:

[1]-Mohamed A. Khamsi, Helmut Knaust - SOSMATH - The Bisection Method
[2]-John H. Mathews - California State Univ. Fullerton - Module for The Bisection Method
[3]-Holistic Numerical Methods Institute- - Bisection Method: Nonlinear Equations

TETRAHEDRAL NUMBERS RECIPROCALS SUM

2009-12-25T11:51:00.021+01:00

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 sustitute 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 the Euler Mascheroni Gamma and the 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 taking 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!

SPLITTING FTA FUNCTIONS (III)

2009-12-24T20:14:00.008+01:00

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.

SPLITTING FTA FUNCTIONS (II)

2009-12-21T10:30:00.005+01:00

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!

NOTES ON LEGENDRE´S FORMULA

2009-12-18T17:49:00.006+01:00

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

TRAILING ZEROS IN n!

2009-12-12T23:17:00.016+01:00

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

BINOMIAL MATRIX (III)

2009-10-24T21:08:00.013+02:00

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_{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)$

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

$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

2009-10-24T19:00:00.019+02:00

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

BINOMIAL MATRIX (II)

2009-09-24T22:01:00.069+02:00

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.

BINOMIAL MATRIX (I)

2009-09-22T20:45:00.034+02:00

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.

BETA FUNCTION MATRIX DETERMINANT

2009-09-21T21:33:00.049+02:00

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

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

CURIOUS SERIES-002

2009-09-08T20:48:00.049+02:00

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!

SPLITTING FTA FUNCTIONS (I)

2009-08-28T22:10:00.027+02:00

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

COROLLARY TO EULER´S COROLLARY

2009-08-27T15:53:00.034+02:00

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

CURIOUS SERIES-001

2009-08-16T18:00:00.059+02:00

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!

SUMMERTIME CHANGES

2009-08-09T23:04:00.006+02:00

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.

INTEGRATING ROUNDING FUNCTIONS (IV)

2009-07-18T21:48:00.029+02:00

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.

SQUARE PYRAMIDAL NUMBERS RECIPROCALS SUM

2009-04-11T14:33:00.078+02:00

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

INTEGRATING ROUNDING FUNCTIONS-(III)

2009-03-24T16:08:00.019+01:00

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.

INTEGRATING ROUNDING FUNCTIONS-(II)

2009-03-23T19:27:00.024+01:00

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

INTEGRATING ROUNDING FUNCTIONS-(I)

2009-03-22T21:17:00.038+01:00

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

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

The Triangular Numbers function is used to get shorter expresions.

$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

INVERSE POLYGONAL NUMBERS SERIES-Notes

2009-03-19T22:31:00.036+01:00

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

INVERSE POLYGONAL NUMBERS SERIES

2009-03-10T00:37:00.063+01:00

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

MERSENNE NUMBERS TREASURE MAP

2009-02-17T18:35:00.077+01:00

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.

FERMAT AND MERSENNE NUMBERS CONJECTURE-(3)

2009-02-16T21:57:00.029+01:00

(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$

FERMAT AND MERSENNE NUMBERS CONJECTURE-(2)

2009-02-14T22:25:00.062+01:00

(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

FERMAT AND MERSENNE NUMBERS CONJECTURE-(1)

2009-02-08T21:29:00.045+01:00

(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

SUMS INSIDE POWER SET

2009-02-06T22:33:00.081+01:00

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 take a look, at the figure, to the right, 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.

n! ARITHMETIC FUNCTIONS

2009-02-02T22:31:00.063+01:00

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

EUCLINACCI - [1]

2009-02-01T15:57:00.191+01:00

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

FRONT COVER 270109

2009-01-27T12:42:00.011+01:00