# Eikonal Blog

## 2012.11.26

### Generating functions

Recently I have been rereading the Herbert S. Wilf’s free online book Generatingfunctionologyhttp://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$.

## 2012.03.14

### Pretty little tables

Filed under: mathematics, number theory, puzzles — Tags: , — 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/

## 2011.07.06

### Derivatives of numbers

Filed under: mathematics, number theory — Tags: , , — 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 $n= \prod_{i=1}{k} {p_i}^{n_i}$ one has $n' = n \sum_{i=1}^{k} \frac{n_i}{p_i}$.
• 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
Abstract: We define the derivative of an integer to be the map sending every prime to 1 and satisfying the Leibnitz rule. The aim of the article is to consider the basic properties of this map and to show how to generalize the notion to the case of rational and arbitrary real numbers. We make some conjectures and find some connections with Goldbach’s Conjecture and the Twin Prime Conjecture. Finally, we solve the easiest associated differential equations and calculate the generating function.
• “Investigations of the number derivative” by Linda Westrick – http://web.mit.edu/lwest/www/intmain.pdf

## 2010.12.10

### The Erdos Number

Filed under: mathematics, number theory — Tags: — 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.

## 2010.11.15

### Cyclic numbers

Filed under: mathematics, number theory — Tags: , — 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:

## 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$).
• $p(n) = \oint_C \frac{dx}{2\pi i} \frac{F(x)}{x^{n+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 ($R_k(N)$) to write number $N$ as a sum of $k$ squares (i.e. $N = \sum_{i=1}^k n_i^2$) use the $k$-th potency of the function $f(x):\equiv \sum_{n=0}^\infty x^{n^2}$:
• $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)$.

## 2010.01.05

### Squares with just two different decimal digits

Filed under: mathematics, number theory, puzzles — Tags: — 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}$

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

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/

### Number theory finite concidental sums

Filed under: mathematics, number theory — Tags: — 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

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/

### Sums

Filed under: mathematics, number theory — Tags: , — 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