Friday, 29 November 2013

A004782(n)=A014847(n)+1



A004782



The sequence of numbers where $latex \frac{2(2n-3)!}{n!(n-1)!}$ is an integer, is closely related to numbers n such that n-th Catalan number $latex \frac{C(2n,n)}{(n+1)}$ is divisible by n.
Theorem:
A004782(n)=A014847(n) + 1
Proof:

References:
[1]- R. K. Guy, The On-Line Encyclopedia of Integer Sequences. A004782: 2(2n-3)!/n!(n-1)! is an integer.
[2]- N. J. A. Sloane., The On-Line Encyclopedia of Integer Sequences. A014847: Numbers n such that n-th Catalan number C(2n,n)/(n+1) is divisible by n.
[3]- N. J. A. Sloane., The On-Line Encyclopedia of Integer Sequences. A000984: Central binomial coefficients: C(2*n,n) = (2*n)!/(n!)^2.

Tuesday, 15 January 2013

MAX DETERMINANT

A SPECIAL MATRIX:

The determinant of $latex M_{n}$, a square matrix with elements $latex m_{i,j}= \max(i,j)$, where $latex \max$ is the maximum function, is given by sequence: A181983

This identity looks as follows:

$latex\displaystyle det{\bigg[ max(i,j) \bigg] }_{1\leq i,j \leq n} = -n \cdot {(-1)}^{n} = A181983(n)$

Proof:

A new matrix with the same determinant can be created, subtracting row i from row i+1 starting at the 2nd row, and then this determinant can be computed easily using the expansion by minors technique at element $latex m_{1,n}$

This can be better shown with an example:

We can transform:

$latex\displaystyle M_{10} = \left(\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 2 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 3 & 3 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 4 & 4 & 4 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 5 & 5 & 5 & 5 & 5 & 6 & 7 & 8 & 9 & 10 \\ 6 & 6 & 6 & 6 & 6 & 6 & 7 & 8 & 9 & 10 \\ 7 & 7 & 7 & 7 & 7 & 7 & 7 & 8 & 9 & 10 \\ 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 9 & 10 \\ 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 10 \\ 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \end{array} \right)$

Into:

$latex\ M^{*}_{10} =\left(\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \end{array} \right)$

This proof can be generalized to a very similar kind of matrices, obtaining:

$latex\displaystyle det{\bigg[ max(i,j)^k \bigg]}_{1\leq i,j \leq n} = {(-1)}^{n-1} \cdot n^{k} \cdot \prod_{s=1}^{n-1}{(s+1)^k-s^k}$

$latex\displaystyle det{\bigg[ min(i,j)^k \bigg]}_{1\leq i,j \leq n} = \prod_{s=1}^{n-1}{(s+1)^k-s^k}$



References:
[1]- N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. A051125: Table T(n,k) = max{n,k} read by antidiagonals (n >= 1, k >= 1).
[2]- Michael Somos, Apr 04 2012, The On-Line Encyclopedia of Integer Sequences. A181983: -(-1)^n * n.
[3]- Emeric Deutsch, Jun 05 2009, The On-Line Encyclopedia of Integer Sequences. A161124: Number of inversions in all fixed-point-free involutions of {1,2,...,2n}.
[4]- N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. A001147: Double factorial of odd numbers: (2*n-1)!! = 1*3*5*...*(2*n-1).

Saturday, 9 June 2012

RECYCLING HARDY & WRIGHT

AVERAGE ORDER OF DEDEKIND PSI FUNCTION



$latex \psi(n)= n \cdot \prod_{p|n}{\left( 1 + \frac{1}{p} \right)$

Dedekind psi function called my attention, when I was trying to find trivial properties and formulas related to Jordan's totient functions, that are indeed just generalizations of Euler's totient function. At that time I realize that values in range of psi had similarities to those of divisor sigma, because trivially: $latex \sigma_{1}(n) - \psi(n) \geq 0$, (inequality that holds for squarefree numbers). So, It seems reasonable to look for an alternate inequality to Robin's criterion but with Dedekind psi instead of divisor function.

Fortunately, this question was settled, before my discovery of gunpowder, by true mathematicians like Patrick Sole and Michel Planat ([1] and [2]).

Riemann Hypothesis (RH) is true if and only:

$latex \frac{\psi(n)}{n} < e^{\gamma} \;log{log{\;n}}$, for $latex n>30$.

After I found these papers on the internet, my interest on Dedekind psi function became huge, and then I begun to look for more and more information about this arithmetical function inside my library. But the real thing is that psi is never given the importance on every Number Theory book that it deserves. This was good to me because it gave me the opportunity to populate The On-Line Encyclopedia of Integer Sequences with my trivialities related to this function. This the modest mission of this blog: to create math not in the books.

As I'm a copycat and Euler's totient is first cousin of Dedekind psi, the idea is to turn $latex \varphi$ formulas into $latex \psi$ with a small retouch, for example if:

$latex \frac{n}{\varphi(n)}=\sum_{d|n}{\frac{{\mu(d)}^2}{\varphi(d)}}$

Then you can discover the unpublished:

$latex \frac{n}{\psi(n)}=\sum_{d|n}{\frac{\mu(d)}{\psi(d)}}$

The same thing can be done "recycling" the analytic theorems about the average order of number theoretical functions that came on the most cited book on the topic: Hardy and Wright's An Introduction to the Theory of Numbers, particularly Theorem 330 on the average order of Euler's Totient can be easily rewritten to get, the not so easy to find, average order of Dedekind psi, just implementing the following expressions along theorem development:

$latex \psi(n)= n \cdot \sum_{d|n}{ \frac{|\mu(d)|}{d} $

(Taken from [4])

and

$latex \sum_{d=1}^{\infty}{\frac{|\mu(d)|}{d^{2}}} = \frac{15}{{\pi}^{2}}$

(See [6])

Proof:
$latex \Psi(n) = \sum_{m=1}^{n}{\psi(m)} = m \cdot \sum_{d|m}{ \frac{|\mu(d)|}{d} =$

$latex \sum_{d \cdot d^{\prime} \leq n}{d^{\prime} \cdot |\mu(d)|} = \sum_{d=1}^{n}{|\mu(d)| \cdot \sum_{d^{\prime}=1}^{\lfloor \frac{n}{d} \rfloor}{d^{\prime}} = $


$latex \frac{1}{2} \sum_{d=1}^{n}{|\mu(d)| \bigg( \bigg\lfloor \frac{n}{d} \bigg\rfloor^{2} + \bigg\lfloor \frac{n}{d} \bigg\rfloor \bigg) = $


$latex \frac{1}{2} \sum_{d=1}^{n}{|\mu(d)| \bigg\{ \frac{n^{2}}{d^{2}} + O \bigg( \frac{n}{d} \bigg) \bigg\} } = $

$latex \frac{n^2}{2} \sum_{d=1}^{n}{ \frac{|\mu(d)|}{d^2} + O \bigg( n \sum_{d=1}^{n}{ \frac{1}{d} \bigg) } = $

$latex \frac{n^2}{2} \sum_{d=1}^{n}{ \frac{|\mu(d)|}{d^2} + O \bigg( n^{2} \sum_{n+1}^{\infty}{ \frac{1}{d^2} \bigg) + O(n \cdot \log{n}) =$

$latex \frac{15n^{2}}{2{\pi}^2} + O(n) + O(n \cdot \log{n}) = \frac{15n^{2}}{2{\pi}^2} + O(n \cdot \log{n})$


$latex \Psi(n) = \frac{15n^{2}}{2{\pi}^2} + O(n \cdot \log{n})$

Then the average order of $latex \psi(n)$ is $latex \frac{2}{n} \cdot \frac{15n^2}{{2\pi}^2} = \frac{15n}{\pi^2}$

Archives:
[a]-JordanTotientFunction.m


References:
[1]-Patrick Sole and Michel Planat, Extreme values of the Dedekind Psi function, to appear in Journal of Combinatorics and Number Theory, arXiv:1011.1825v2
[2]-Michel Planat, Riemann hypothesis from the Dedekind psi function, arXiv:1010.3239v2
[3]-G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1979, 5th Edition pp 268, Theorem 330.
[4]- N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. A001615: Dedekind psi function: n * Product_{p|n, p prime} (1 + 1/p)
[5]- Jonathan Vos Post, Feb 15 2010, The On-Line Encyclopedia of Integer Sequences. A173290: Partial sums of A001615.
[6]- N. J. A. Sloane, May 09 2003, The On-Line Encyclopedia of Integer Sequences. A082020: Decimal expansion of 15/Pi^2.

Saturday, 31 July 2010

ADDING HELP TO OEIS SEQUENCES

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

Sunday, 11 July 2010

TOTIENT CARNIVAL


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)

Thursday, 13 May 2010

A SMALL FIBONACCI SUM

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

Sunday, 14 February 2010

BibTeX AUTOMATIC OEIS CITATIONS



I've programmed 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.