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

    Wonder #1

and just a few days later this one, too:

    Wonders 1-4

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:

2010.11.02

Readings in number theory

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

Sources


More

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}

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:


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

Create a free website or blog at WordPress.com.