number theory | Eikonal Blog

2012.11.26

Generating functions

Recently I have been rereading the Herbert S. Wilf’s free online book Generatingfunctionology – http://www.math.upenn.edu/~wilf/DownldGF.html. It is choke-full of interesting results.

Definitions

For a number series ${\bf a} :\equiv \{a_n|n\in\{0,\infty\}\}$ one defines following generating functions (GFs):

Ordinary Power Series GF (OPSGF): $OPSGF[a](x) :\equiv \sum_{n=0}^\infty a_n x^n \leftrightarrow_{opsgf} {\bf a}$ ;
Exponential Series GF (EGF): $EGF[a](x) :\equiv \sum_{n=0}^\infty a_n \frac{x^n}{n!} \leftrightarrow_{egf} {\bf a}$ ;
Dirichlet GF (DGF): $DGF(x;s) :\equiv \sum_n \frac{a_n}{n^s} x^n \leftrightarrow_{dgf} {\bf a}$ ;
Lambert GF (LGF): $LGF(x) :\equiv \sum_n \frac{a_n}{1-x^n} x^n \leftrightarrow_{lgf} {\bf a}$ ;
Bell GF (BGF): $BGF(x;s) :\equiv \sum_n a_{p^n} x^n \leftrightarrow_{bgf} {\bf a}$ ;
Poisson GF (PGF): $PGF(x;s) :\equiv \sum_n \frac{a_n}{n!} x^n e^{-x} = e^{-x} EGF(x) \leftrightarrow_{pgf} {\bf a}$ ;

Simple results

$\{a_n=n\} \leftrightarrow_{opsgf} f(x) = \frac{x}{(1-x)^2}$ .
$\{a_n=n^2\} \leftrightarrow_{opsgf} f(x) = \frac{x(x+1)}{(1-x)^3}$ .
$\{a_n=b^n\} \leftrightarrow_{opsgf} f(x) = \frac{1}{1-b x}$ .
$\{a_n=n\} \leftrightarrow_{egf} f(x) = x e^{x}$ .
$\{a_n=n^2\} \leftrightarrow_{egf} f(x) = x(x+1)e^{x}$ .
$\{a_n=b^n\} \leftrightarrow_{egf} f(x) = e^{b x}$ .
For Fibonacci numbers $\{F_n|F_{n+1} = F_n + F_{n-1} | f_0 = F_1 = 1\}$ one has: $OPSGF(x) = \frac{x}{1-x-x^2}$ , leading to $F_n = \frac{r_+^n-(r_-^n}{\sqrt{5}}$ ( $r_\pm = \frac{1\pm\sqrt{5}}{2}$ ).
$\{a_n|a_{n+1}=2 a_n + 1| a_0=0\} \leftrightarrow_{opsgf} OPSGF = \frac{x}{(1-x)(1-2x)} = \frac{1}{1-2x} - \frac{1}{1-x}$ ; which leads to $a_n=2^n - 1$ .
For $a_{n+1} = 2 a_n + n$ , $alatex _0=1$ one has: $OPSGF = \frac{2}{1-2x} - \frac1{(1-x)^2}$ leading to
$a_n = 2^{n-1} - n - 1$ .

Define $[x^n]f(x)$ as the coefficient next to $x^n$ in power series $f(x)$ . Examples and properties:

$[x^n] e^x = \frac1{n!}$ ,
$[x^n] \frac1{1-ax} = a^n$ ,
$[x^n] (1+x)^s = \binom{s}{n}$ ,
$[x^n] \{x^m f(x)\} = [x^{n-m}] f(x)$ ,
$[\lambda x^n] f(x) = \frac1{\lambda} [x^n]f(x)$ ,
$\left[\frac{x^n}{n!}\right] e^x = 1$ .

For binomial coeficients:

$\sum_{k=0}^{\infty} \binom{n}{k} x^k = (1+x)^n$ ,
$\sum_{n=0}^{\infty} \binom{n}{k} y^n = \frac{y^k}{(1-y)^{k+1}}$ ,
$\binom{n}{k} = [x^k y^n] \frac1{1 - y (1+x)}$ .

Some orthogonal polynomials:

Tchebitshev polynomials generating function: $\sum_{n=0}^\infty \frac{z^n}{n!} T_n(x) = e^{zx}\cos(z\sqrt{1-x^2})$ .
Legendre polynomials generating function: $\frac1{(1-2tz+z^2)^{\frac12}} = \sum_{n=0}^\infty P_n(t)z^n$ .
Generating function for associated Legendre polynomials: $(1-2tc+t^2)^{\alpha} = |1-t e^{i\theta}|^{2\alpha} = \sum_{n=0}^\infty t^n P_n^{\alpha}(c)$ .

Dirichlet series generating functions

For $a_n=1$ : $DGF = \zeta(s)$ .
For $a_n=\mu(n)$ (the Moebius function): $DGF = \frac1{\zeta(s)}$ .
For $a_n=d(n)=\sigma_0(n)$ (the zeroth-order divisor function): $DGF = \zeta(s)^2$ .
For $a_n=\sigma_k(n)$ (the $k$ th-order divisor function): $DGF = \zeta(s)\zeta(s-k)$ .
For $a_n=\phi(n)$ (the totient function): $DGF = \frac{\zeta(s-1)}{\zeta(s)}$ .
For $a_n=H(n)$ (the number of ordered factorizations): $DGF = \frac{1}{2 - \zeta(s)}$ .
For $a_n=\frac12 [1-(-1)^n]$ : $DGF = \lambda(s)$ (the Dirichlet lambda function).

Moebius inversion formula:

If two DGF series $A(s)$ and $B(s)$ have coefficient relation $a_n = \sum_{d|n} b_d$ , then $A(s) = B(s) \zeta(s)$ , and $b_n = \sum_{d|n} \mu\left(\frac{n}{d}\right) a_d$ .
If $a_n = \sum_{d|n} b_d$ , then $b_n = \sum_{d|n} \mu\left(\frac{n}{d}\right) a_d$ .

Leave a Comment

2012.03.14

Pretty little tables

Filed under: mathematics, number theory, puzzles — Tags: math wonders, trivial math relations — sandokan65 @ 14:59

Recently I have seen in an math forum this:

and just a few days later this one, too:

Pretty little tables, aren’t they? How could they be so regular? Can they be generalized somehow?

Answers are: yes, you will see, and yes.

Wonder #1

Let’s first take a look at the first table:

Table 1

$1 \times 8 + 1 = 9$ ,
$12 \times 8 + 2 = 98$ ,
$123 \times 8 + 3 = 987$ ,
$1,234 \times 8 + 4 = 9,876$ ,
$12,345 \times 8 + 5 = 98,765$ ,
$123,456 \times 8 + 6 = 987,654$ ,
$1,234,567 \times 8 + 7 = 9,876,543$ ,
$12,345,678 \times 8 + 8 = 98,765,432$ ,
$123,456,789 \times 8 + 9 = 987,654,321$ ,

In order to understand it one has to work not with the specific numbers (digits), but with their abstract representations. For this, we will work with a number system of base $B$ ( $\in {\Bbb N}$ ), which in the orginal tables is $B=10$ . Then we can rewrite several first members of the Table 1 as follows:

$1 \cdot B^0 \times (B-2) + 1 = (B-1) B^0$ ,
$(1 \cdot B^1 + 2 B^0) \times (B-2) + 2 = (B-1) B^1 + (B-2)B^0$ ,
$(1 \cdot B^2 + 2 B^1 + 3 B^0) \times (B-2) + 3 = (B-1)B^2 + (B-2)B^1 + (B-3)B^0$ ,
etc

Ok, we see some regularity here. To proceed further, rewrite the $n^{th}$ row of that table in the form a mathematical equation $y_n :\equiv x_n \cdot \hbox{some number} + \hbox{some other number}$ , transforming the first beautifully looking number ( $x_n$ ) into second beautifully looking number $y_n$ .

Here the series $\{x_n\}$ is:

$x_1 = 1_B = 1\times B^0$ ,
$x_2 = 12_B = 1\times B^1 + 2 \times B^0$ ,
$x_3 = 123_B = 1\times B^2 + 2 \times B^1 + 3 \times B^0$ ,
…
$x_n = 123...n_B = 1\times B^{n-1} + 2 \times B^{n-2} + \cdots + n \times B^0 = \sum_{k=1}^n k B^{n-k}$ .

A side note:
Note that $x_n = \sum_{s=0}^{n-1} (n-s) B^s$ . It can be explicitly summarized as follows:

$x_ n = (n- B \partial_B) \sum_{s=0}^{n-1} B^s = (n-B\partial_B) \frac{B^n-1}{B-1} = \frac{B(B^n-1)-n(B-1)}{(B-1)^2}$

For example, for $B=10$ that formula yields $x_n = \frac{10(10^n-1)-9n}{81}$ : $x_1 = 1$ , $x_2 = 12$ , …, $x_5 = 12345$ , etc.

Let’s go back to the main line of discussion.

Now we are interested in the following derivative series $y_n :\equiv x_n \cdot (B-2) + n$ . The straightforward manipulation leads to the anticipated result:

$y_ n = B^n + \sum_{s=1}^{n-1} (s+1-n)B^s - n$

$= (B-1)B^{n-1} + B^{n-1} + \sum_{s=1}^{n-2} (s+1-n)B^s - n$

$= (B-1)B^{n-1} + (B-2) B^{n-2} + \sum_{s=1}^{n-3} (s+1-n)B^s - n$

$\cdots$

$= \sum_{r=1}^{m} (B-r)B^{n-r} + B^{n-m} + \sum_{s=1}^{n-m-1} (s+1-n)B^s - n$

$\cdots$

$= \sum_{r=1}^{n-2} (B-r)B^{n-r} + B^{2} + \sum_{s=1}^{1} (s+1-n)B^s - n$
$= \sum_{r=1}^{n-2} (B-r)B^{n-r} + B^{2} + (2-n)B^1 - n$
$= \sum_{r=1}^{n-1} (B-r)B^{n-r} + B^{1} - n$
$= \sum_{r=1}^{n} (B-r)B^{n-r}$ .

i.e. $y_n = (B-1)(B-2)...(B-n+2)(B-n+1)(B-n)_B$ . The initial pyramid of simple results holds for every base $B$ .

Example: for $B=5$ we have $x_n = \frac{5(5^n-1)-4n}{16}$ , so $x_1 = \frac{5\cdot 4 - 4 \cdot 1}{16} = 1$ , $x_2 = \frac{5\cdot 24 - 4 \cdot 2}{16} = 7_{10} = 12_5$ , etc. Then, for example $y_2 = x_2 \cdot 3 + 2 = 7\cdot 3 + 2 = 21 + 2 = 23_{10} = 43_5$ .

Wonder #2

Let’s look at the Table 2:

Table 2

$1 \times 9 + 2 = 11$ ,
$12 \times 9 + 3 = 111$ ,
$123 \times 9 + 4 = 1,111$ ,
$1,234 \times 9 + 5 = 11,111$ ,
$12,345 \times 9 + 6 = 111,111$ ,
$123,456 \times 9 + 7 = 1,111,111$ ,
$1,234,567 \times 9 + 8 = 11,111,111$ ,
$12,345,678 \times 9 + 9 = 111,111,111$ ,
$123,456,789 \times 9 + 10 = 1,111,111,111$ ,

Here the first (i.e. the independent) variable $x_n$ is the exactly same as the one used for Table 1. The second (i.e. the dependent) variable $z_n$ is new one, determined by defining equation:

$x_n = \sum_{s=0}^{n-1}(n-s)B^s$

Then, using steps similar to these used in analysis of the Table 1, we get:

$z_n :\equiv x_b \cdot (B-1) + (n+1) =$

$= \sum_{s=0}^{n-1} (n-s) B^{s+1} - \sum_{s=0}^{n-1} (n-s) B^s + (n+1) =$

$= \sum_{s=1}^{n} (n+1-s) B^{s} - \sum_{s=0}^{n-1} (n-s) B^s + (n+1) =$

$= B^n + \sum_{s=1}^{n-1} (n+1-s - n +s) B^{s} - n + (n+1) =$

$= B^n + \sum_{s=1}^{n-1} B^{s} +1 =$

$= \sum_{s=0}^{n} B^{s} =$

$= 1\cdots 1_B$

where there are $(n+1)$ copies of digit 1.

Nice. Easy.

Wonder #3

Table 3

$9 \times 9 + 7 = 88$ ,
$98 \times 9 + 6 = 888$ ,
$987 \times 9 + 5 = 8,888$ ,
$9,876 \times 9 + 4 = 88,888$ ,
$98,765 \times 9 + 3 = 888,888$ ,
$987,654 \times 9 + 2 = 8,888,888$ ,
$9,876,543 \times 9 + 1 = 88,888,888$ ,
$98,765,432 \times 9 + 0 = 888,888,888$ ,

That series of relations has form $v_n = u_n \cdot 9 + (8-n)$ where the dependent variable is
$v_n = \underbrace{8\cdots8}_{n+1}$ in the normal decimal system ( $B=10$ ).

For general basis $B$ this generalizes to the:
$v_n = u_n \cdot (B-1) + (B - n -2)$ . Here the independent variable $u_n$ is

$u_n = \sum_{k=1}^n (B-k) B^{n-k} =$

$= \sum_{s=0}^{n-1} (B- n -s) B^s =$

$= (B - n + B \partial_B) \sum_{s=0}^{n-1}B^s =$

$= (B - n + B \partial_B)\frac{B^n-1}{B-1} =$

$= \frac{B(B-2)(B^n-1)+n (B-1)}{(B-1)^2}$

Now

$v_ n :\equiv u_n (B-1) + (B-n-2) =$

$= (B-1) B^n - \sum_{s=1}^{n-1} B^s - 2 =$

$= (B-2) B^n + (B-1) B^{n-1} - \sum_{s=1}^{n-2} B^s - 2 =$

$= (B-2) B^n + (B-2) B^{n-1} + (B-1)B^{n-2} - \sum_{s=1}^{n-3} B^s - 2 =$

$\cdots$

$= (B-2) B^n + \cdots + (B-2) B^{n-m+1} + (B-1)B^{n-m} - \sum_{s=1}^{n-m-1} B^s - 2 =$

$\cdots$

$= (B-2) B^n + \cdots + (B-2) B^{3} + (B-1)B^{2} - B^1 - 2 =$
$= (B-2) B^n + \cdots + (B-2) B^{3} + (B-2)B^{2} + B^2 - B^1 - 2 =$
$= (B-2) B^n + \cdots + (B-2) B^{2} + (B-1)B^{1} - 2 =$
$= (B-2) B^n + \cdots + (B-2) B^{1} + B - 2 =$
$= \sum_{r=0}^{n} (B-2) B^r$ .

For $B=10$ that covers all examples in the Table 3.

Note: Even more, we can add two more members to it, corresponding to $n=9$ and $n=10$ :

$u_9 = 987,654,321$ corresponds to $v_9 = x_9 \cdot 9 + (-1) = 8,888,888,888$ ,
$u_{10} = 9,876,543,210$ corresponds to $v_{10} = x_{10} \cdot 9 + (-2) = 88,888,888,888$ .

Also, the $u_0=0$ provides one more line, which is prepended to this more complete table 3:

Table 3*

$0 \times 9 + 8 = 8$ ,
$9 \times 9 + 7 = 88$ ,
$98 \times 9 + 6 = 888$ ,
$987 \times 9 + 5 = 8,888$ ,
$9,876 \times 9 + 4 = 88,888$ ,
$98,765 \times 9 + 3 = 888,888$ ,
$987,654 \times 9 + 2 = 8,888,888$ ,
$9,876,543 \times 9 + 1 = 88,888,888$ ,
$98,765,432 \times 9 + 0 = 888,888,888$ ,
$987,654,321 \times 9 - 1 = 8,888,888,888$ ,
$9,876,543,210 \times 9 - 2 = 88,888,888,888$ .

Wonder #4

Table 4

$1^2 = 1$ ,
$11^2 = 121$ ,
$111^2 = 12,321$ ,
$1,111^2 = 1,234,321$ ,
$11,111^2 = 123,454,321$ ,
$111,111^2 = 1,2345,654,321$ ,
$1,111,111^2 = 1,234,567,654,321$ ,
$11,111,111^2 = 123,456,787,654,321$ ,
$111,111,111^2 = 12,345,678,987,654,321$ .

Here the independent variable is

$p_n :\equiv 1\cdot B^{n} + 1\cdot B^{n-1} + \cdots + 1\cdot B^0 = \sum_{i=0}^n B^i = \frac{B^{n+1}-1}{B-1}$

The resulting variable is

$r_n :\equiv p_n^2 = \sum_{i=0}^n \sum_{j=0}^n B^{i+j} =$

$= \sum_{k=0}^{2n} (\sum_{i=0}^n \sum_{j=0}^n \delta_{i+j,k}) B^k$

Now the sum in brackets can be transformed as follows:

$\sum_{i=0}^n \sum_{j=0}^n \delta_{i+j,k} = \sum_{i=0}^n \Theta(0 \le k-i \le n) =$

$= \sum_{i=0}^n \Theta(k-n \le i \le k) = \sum_{i=\hbox{max}(0,k-n)}^{\hbox{min}(n,k)} 1 =$

$= \hbox{min}(n,k) - \hbox{max}(0,k-n) + 1 = *$

which has three posible simplifications:

$* = k - 0 + 1 = k + 1$ for $k < n$ ,
$* = n + 1$ for $k = n$ ,
$* = n - (k-n) + 1 = 2n - k + 1$ for $k > n$ .

So, now we can write the final form for $r_n$ as following:

$r_n = \sum_{k=0}^{n-1} (k+1) B^k + (n+1) B^n + \sum_{k=n+1}^{2n} (2n-k+1) B^k =$

$= 1\cdot B^0 + 2\cdot B^1 + 3\cdot B^2 + \cdots + (n+1) B^n + \cdots 2\cdot B^{2n-1} + 1\cdot B^{2n} =$

$= 123\cdots(n+1)\cdots321_B$

That is it.

Note that one can get some regularities for degrees higher than 2. For example, for degree 3 one has:

$1^3 = 1$

$11^3 = 1,331$

$111^3 = 135,531$

$1,111^3 = 13,577,531$

$11,111^3 = 1,357,997,531$

$111,111^3 = 135,79b,b97,531$

$1,111,111^3 = 13,579,bdd,b97,531$

$\cdots$

${\underbrace{1\cdots1}_{[B'/2]+1}}^3 = 1357\cdots B'B'\cdots 7531$ .

up to the last member (of that series) where the two central digits are the highest single-digit number $B'$ allowed in the number system of base $B$ (i.e. $B'=B-2$ if $B$ is odd, and $B'=B-1$ if $B$ is even).

Note: Here $a = 10_{10}$ , $b = 11_{10}$ , $c = 12_{10}$ , $d = 13_{10}$ , $e = 14_{10}$ , $f = 15_{10}$ , $g = 16_{10}$ , $h = 17_{10}$ , $i = 18_{10}$ , etc.

For the degree 4 the similar pyramid/table is:

$1^4 = 1$

$11^4 = 14,641$

$111^4 = 1,48a,841$

$1,111^4 = 1,48a,cec,841$

$\cdots$

Here one can also work some more (and I did not do that work yet) to establish which is the last member of that table (as a function of the base $B$ ), and what is the innermost digit in that last member.
This could be a homework for you. 🙂

For the degree 5:

$1^5 = 1$

$11^5 = 15885$

$111^5 = 15ciic51$

$\cdots$

Similar here: More simple math wonders – https://eikonal.wordpress.com/2012/03/14/more-simple-math-wonders/ | Mental calculation of cube root of a six-digit number – https://eikonal.wordpress.com/2010/01/14/mental-calculation-of-cube-root-of-a-two-digit-number/ | Squares with just two different decimal digits – https://eikonal.wordpress.com/2010/01/05/squares-with-just-two-different-decimal-digits/ | Number theory finite concidental sums – https://eikonal.wordpress.com/2010/01/05/number-theory-finite-considental-sums/

Comments (3)

2011.07.06

Derivatives of numbers

Filed under: mathematics, number theory — Tags: Åhlander, number differentials, Ufnarovski — sandokan65 @ 23:45

Definitions:

$p'=1$ for every prime number $p$
$(a b)' = a' b + a b'$ (Leibnitz rule) for every two natural numbers $a, b \in {\Bbb N}$

Concequences:

$1' = 0$ .
$(p^n)' = n \cdot p^{n-1}$
for any natural number one has .
- Eg: $40' = (2^3 \cdot 5)' = 3 \cdot 2^2 \cdot 5 + 2^3 = 68$ .
in general $(a+b)' \ne a' + b'$
$\left(\frac{a}{b}\right)' = \frac{a' b - a b'}{b^2}$
$(p^p)' = p^p$ for any prime number $p$ is equivalent of the exponential function’s property that its derivative is itself.
If $n = p^p \cdot m$ for prime $p$ and natural $m>1$ , then $n' = p^p (m+m') > n$ , $n^{(k)} \ge n+k$ , and $\lim_{k\rightarrow \infty} n^{(k)} = \infty$ .
For infinitely many natural numbers $n$ there exist suitable $k$ s/t $n^{(k)}=0$
Ufnarovski and Åhlander give following conjecture: for every natural $n$ , as we observe its derivatives $n^{(k)}$ (as $k$ grows to infinity), the limit will be either $0$ , $\infty$ , or $n$ itself (if $n=p^p$ for some prime $p$ ).
If $n'=0$ , then $n=1$ .
If $n'=1$ , then $n = p$ (for all possible primes).

Sources:

“Deriving the Structure of Numbers” by Ivars Peterson (Ivars Peterson’s MathTrek) – http://www.maa.org/mathland/mathtrek_03_22_04.html
“How to differentiate a number” by Ufnarovski, V., and B. Åhlander (Journal of Integer Sequences 6; 2003.09.17) – http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Ufnarovski/ufnarovski.html
“Investigations of the number derivative” by Linda Westrick – http://web.mit.edu/lwest/www/intmain.pdf

Leave a Comment

2010.12.10

The Erdos Number

Filed under: mathematics, number theory — Tags: Erdos Number — sandokan65 @ 15:52

A simple metric on the space of the publishing mathematicians. That space consists of the discrete nodes that represent each publishing mathematician. For each jointly publication there is a link between the two nodes representing authors of that publication. If two authors have N common publications, the link connecting them has weight N. A distance between two nodes (x and y) is defined as the shortest number of steps from x to y. The Erdos Number is the distance (metric) of x to the one specific node (Paul Erdos). Majority of the nodes in the space belong to a one extremely large cluster/graph (a dominant/principal component). Still, there are many solitary nodes.

The Erdos Number Project – http://www.oakland.edu/enp/

Leave a Comment

2010.11.15

Cyclic numbers

Filed under: mathematics, number theory — Tags: 142857, cyclic numbers — sandokan65 @ 14:14

Definition: (source: [3]) A number with n digits, which, when multiplied by 1, 2, 3, …, n produces the same digits in a different order. For example, 142857 is a cyclic number: 142857 × 2 = 285714; 142857 × 3 = 428571; 142857 × 4 = 571428; 142857 × 5 = 714285; 142857 × 6 = 857142, and so on. It has been conjectured, but not yet proven, that an infinite number of cyclic numbers exist.

Properties:

$142,857 X 1 = 142,857$
$142,857 X 2 = 285,714$
$142,857 X 3 = 428,571$
$142,857 X 4 = 571,428$
$142,857 X 5 = 714,285$
$142,857 X 6 = 857,142$
$142,857 X 7 = 999,999$
$142 + 857 = 999$
$14 + 28 + 57 = 99$
from [2]: … Multiplication by an integer greater than 7: adding the lowest six digits (ones through hundred thousands) to the remaining digits and repeat this process until you have only the six digits left, it will result in a cyclic permutation of 142857. Example:
- $142,857 X 142,857 = 20,408,122,449$
- $20,408 + 122,449 = 142,857$

Sources:

[1] 142857 is an Interesting Number – http://swik.net/Unix/My+SysAd+Blog/142857+is+an+Interesting+Number/czm43
[2] 142857 @ WikiPedia – http://en.wikipedia.org/wiki/142857_%28number%29
[3] cyclic numbers defined @ The Internet Encyclopedia of Science – http://www.daviddarling.info/encyclopedia/C/cyclic_number.html
[4] cyclic numbers defined @ PlanetMath.org – http://planetmath.org/encyclopedia/CyclicNumber.html
[5]Douglas Twitchell 142857 calculator (online) – http://www.douglastwitchell.com/142857calculator.asp
- “My Pet Number – 142857” by Douglas Twitchell – http://www.articlesforeducators.com/dir/mathematics/number_fun/pet_number_142857.asp
Eye Gate 142857 gallery – http://www.eyegate.com/showgal.php?id=297

Leave a Comment

2010.11.02

Readings in number theory

Filed under: mathematics, number theory — Tags: Circle Method, Goldbach's conjecture, Lagrange's conjecture, modular form, modular forms, number theory, Partition function, ramanujan, Ramanujan's congruences, tau function, Waring's problem — sandokan65 @ 11:17

Partition function $p(n)$

Definition: The partition function $p(n):{\Bbb N}\rightarrow{\Bbb N}_0$ is defined by

$p(n) = \hbox{number of partitions of } n$

Examples: The partitions of 5:

$5 = 5$ ,
$5 = 4+1$ ,
$5 = 3+2$ ,
$5 = 3+1+1$ ,
$5 = 2+2+1$ ,
$5 = 2+1+1+1$ ,
$5 = 1+1+1+1+1$ .

i.e. $p(5)= 7$ .

Properties:

$p(1)=1$ , $p(2)=2$ , $p(3)=3$ , $p(4)=5$ , $p(5)=7$ , $p(6)=11$ , $p(7)=15$ , $p(8)=22$ , $p(9)=30$ , $p(10)=42$ , … $p(100)=190,569,292$ , … $p(200)=3,972,999,029,388$ , … $p(1,000)=24,061,467,864,032,622,473,692,149,727,991$ , …
An asymptotic formula: $p(n) \sim \frac{e^{\pi \sqrt{\frac{2n}3}}}{4n\sqrt{3}}$ .
Generating function: $F(x) :\equiv \prod_{m=1}^\infty \frac1{(1-x^m)} = \sum_{n=0}^\infty p(n) x^n$ (where $|x|<1$ ).
- … [the] main contributions [to this integral] come from poles of $F(x)$ , [and] these lie at every root of $1$ .
- Circle Method: using the function $T_q(n)$ that estimates the contribution [to the above integral] from the poles on the circle ${\cal C}$ that are near the q-th roots of unity. The main formula of the method is: $p(n) = \sum_{q=1}^\infty T_q(n)$ . Taking the finite number of terms in that sum gives surprisingly good results, due to the fact that the estimated function has integer values.

Some applications of Circle Method:

Lagrange’s conjecture: Each natural number can be expressed as the sum of at most four squares.
Waring’s problem: Every sufficiently large natural number can be expressed as the sum of at most $w(k)$ k-th powers.
Example: To calculate the exact expression for the number of ways () to write number as a sum of squares (i.e. ) use the -th potency of the function :
- $f(x)^k = \sum_{N=0}^\infty R_k(N) x^N$ ,
- and, therefore: $R_k(N) = \oint_C \frac{dx}{2\pi i} \frac{f(x)^k}{x^{n+1}}$

Goldbach’s conjecture:

Every even number greater than two can be represented as a sum of two primes.
Every odd number greater than five can be represented as a sum of three primes.

Congruences for $p(n)$

Ramanujan’s congruences:

$p(5n+4) \equiv 0 (mod \ 5)$ ,
$p(7n+5) \equiv 0 (mod \ 7)$ ,
$p(11n+6) \equiv 0 (mod \ 11)$ .

Congruences found in 1960s:

$p(A n + B) \equiv 0 (mod \ l^k)$

for $l = 13, 17, 19, 23, 29, 31$ .

Example: $p(13^2\cdot 97^3 \cdot 103^3 \cdot n - 6,950,975,499,605) \equiv 0 (mod \ 13^2)$ .

Theorem (Ono, 2000): For prime $l \ge 5$ there exist infinitely many congruences of the form $p(A n + B) \equiv 0 (mod \ l)$ .

Theorem (Ahlgren, 2000): For prime $l \ge 5$ and a positive integer $m$ there exist infinitely many congruences of the form $p(A n + B) \equiv 0 (mod \ l^m)$ .

Modular forms

Definition: Ramanujan’s tau-function:

$\sum_{n=1}^\infty \tau(n) q^n :\equiv q \prod_{m=1}^\infty (1-q^m)^{24} = q -24 q^2 +252 q^3 - 1,472 q^4 + 4,830 q^5 - - 6,048 q^6 - 16,744 q^7 + 84,480 q^8 - 113,643 q^9 - 115,920 q^{10} + \cdots$

Definition: $\Delta(z) :\equiv \sum_{n=1}^\infty \tau(n) q^n :\equiv q \prod_{m=1}^\infty (1-q^m)^{24}$ for $q :\equiv e^{2\pi i z}$ (with $\Im{z}>0$ ).

The $\Delta(z)$ has modular symmetries: $\Delta\left(\frac{az+b}{cz+d}\right) = (cz+d)^{12} \Delta(z)$ ( $\forall z$ ) for any integer $M= \begin{pmatrix}a & b \\ c & d\end{pmatrix}$ that is unimodular ( $\det M = 1$ ). In another words, $\Delta(z)$ is a modular form of weight 12.

Definition: The function $f:{\Bbb C}\rightarrow{\Bbb C}$ is a modular form of weight $k$ if it satisfies the modularity equation $f\left(\frac{az+b}{cz+d}\right) = (cz+d)^{k} f(z)$ ( $\forall z$ , ( $\forall M\in{\Bbb Z}^{2\times2}/\{\det M=1\}$ )).

The $\Delta(z)$ is a prototype of all modular functions. Some other examples are:

$\theta(z) :\equiv \sum_{n\in{\Bbb Z}} q^{n^2}$ ,
$E(z) :\equiv 1+ 240 \sum_{n=1}^\infty (\sum_{d|n} d^3) q^{n}$ .

Some properties of $\tau(n)$ :

$\tau(n) \tau(m) = \tau(nm)$ if $gcd(n,m)=1$ .
Ramanujan’s conjecture: $|\tau(p)| \le 2 p^{11/2}$ for every prime $p$ .
Generalized Ramanujan’s conjecture: if $f(z) = \sum_{n=1}^\infty a(n) q^n$ has weight $k$ , then $|a(p)| \le 2 p^{{k-1}/2}$ for all primes $p$ .

Congruences for $\tau$ function:

$\tau(p) \equiv 1+ p^{11} \ (\hbox{mod} \ 691)$ for every prime $p$ .
$\tau(p) \equiv 1+p^{11} \ (\hbox{mod} \ 2^5)$ for $p\ne 2$ .
$\tau(p) \equiv 1+p \ (\hbox{mod} \ 3)$ for $p\ne 3$ .
$\tau(p) \equiv p^{30}+p^{-41} \ (\hbox{mod} \ 5^3)$ for $p\ne 5$ .
$\tau(p) \equiv p+p^4 \ (\hbox{mod} \ 7)$ for $p\ne 7$ .
These are the only congruences of the form $\tau(p) \equiv p^a + p^{11-a} \ (\hbox{mod} \ l^k)$ .

Sources

[1] “Ramanujan’s Legacy in Number Theory” by Scott Ahlgren (2001.08.05).
[2] Online partitions calculator (Java applet) by Henry Bottomley (2004) – http://www.btinternet.com/~se16/js/partitions.htm

Modular forms (Vivatsgasse 7 blog; 2007.07.23) – http://vivatsgasse7.wordpress.com/2007/07/23/modular-forms/

Comments (1)

2010.01.05

Squares with just two different decimal digits

Filed under: mathematics, number theory, puzzles — Tags: math — sandokan65 @ 16:00

I used to state here

There exist only finitely many squares with just two decimal digits” providing a really short list

$38^2 = 1,444$
$88^2 = 7,744$
$109^2 = 11,881$
$173^2 = 29,929$
$212^2 = 44,944$
$235^2 = 55,255$
$3,114^2 = 9,696,996$

plus infinite classes:

$10^{2n}$ ,
$4\cdot 10^{2n}$ ,
$9\cdot 10^{2n}$ .

This is not correct. Thanks to Bruno Curfs for pointing this out, as well as for finding the reference [2] cited below.

Namely, one can see that squares of all single digit numbers satisfy targeted condition:
- $1^2 = 01$ ,
- $2^2 = 04$ ,
- $3^2 = 09$ ,
- $4^2 = 16$ ,
- $5^2 = 25$ ,
- $6^2 = 36$ ,
- $7^2 = 49$ ,
- $8^2 = 64$ ,
- $9^2 = 81$ ,
Then, there are squares of following two-digit numbers:
- $10^2 = 100$ ,
- $11^2 = 121$ ,
- $12^2 = 144$ ,
- $15^2 = 225$ ,
- $20^2 = 400$ ,
- $21^2 = 441$ ,
- $22^2 = 484$ ,
- $26^2 = 676$ ,
- $30^2 = 900$ ,
- $38^2 = 1,444$ ,
- $88^2 = 7,744$ ,
For squares of 3-digit numbers one finds:
- $100^2 = 10,000$ ,
- $109^2 = 11,881$
- $173^2 = 29,929$
- $212^2 = 44,944$
- $235^2 = 55,255$
- $264^2 = 69,696$ (thanks to Bruno Curfs)

Of the higher cases, there are known only infinitely long classes:

$10^{2n}$
$4\cdot 10^{2n}$
$9\cdot 10^{2n}$

and following two “sporadic” occurrences:

$3,114^2 = 9,696,996$
$81,619^2 = 6,661,661,161$ .

Author of page “1. Squares of 2 different digits” (http://www.asahi-net.or.jp/~KC2H-MSM/mathland/math02/three01.htm) provides an implementation of the algorithm to perform exhaustive check. According to his numerical experiments, there are no other sporadic occurrences up to at least $y=10^{48}$ (i.e. $x=10^{24}$ ).

Reference:

[1] T1277
[2] “1. Squares of 2 different digits” (http://www.asahi-net.or.jp/~KC2H-MSM/mathland/math02/three01.htm

Comments (4)

Number theory finite concidental sums

Filed under: mathematics, number theory — Tags: math — sandokan65 @ 15:43

$1+3+3^n+3^{n+1}+3^{2n} = (2+3^n)^2$

$1+3^n+3^{n+1}+3^{2n} +3^{2n+1}= (1+2 \cdot 3^n)^2$

$1+7+7^2+7^3=20^2$

$1+12^2+12^3+12^4+12^5=521^2$

Reference: T1277

Comments (2)

Sums

Filed under: mathematics, number theory — Tags: series, sums — sandokan65 @ 15:39

$\sum_{k=1}^\infty \frac1{k^k} = 1.291,285,997,...$ (see Prudnikov 5.1.30.1)

$\sum_{k=1}^\infty \frac{(-)^k}{k} = -0.783,430,051,...$

$\sum_{k=1}^\infty \frac{k!}{k^k} = 1.879,853,86...$

$\sum_{k=1}^\infty \frac{(-)^k k!}{k^k} = -0.655,831,60...$

Reference: T1277

Leave a Comment

2012.11.26

Definitions

Simple results

Dirichlet series generating functions

2012.03.14

Wonder #1

Wonder #2

Wonder #3

Wonder #4

2011.07.06

2010.12.10

2010.11.15

2010.11.02

Partition function

Congruences for

Modular forms

Sources

More

2010.01.05

Categories

Archives

Email Subscription

Recent Posts

art and fun

Blogroll

free thinkers

health

infosec & privacy

it

knowledge management

life

mathematics & physics & astro, oh my!

mind & brain

past

science

skils & hacks

society & technology

unix

Partition function $p(n)$

Congruences for $p(n)$