Leonetti Paolo

31 December 2016

5th Oliforum Contest

Filed under: Math problems — Paolo @ 12:59

Hello guys,

There will be in nearly one month the 5th edition of the Oliforum contest. It is an individual and telematic contest, with some training problems at national/imo level. Maybe it can be useful to someone around here. 🙂

Some details below:

1- The contest is made by a unique round, starting in the early afternoon of Tuesday 31 January and ending at 23:59 of Sunday 05 February (Rome meridian +1GTM) (in practice, 5.5 days).

2- Every problem will have some points, from 0 to 7. One additional point could be given for each clear, correct, and original solution.

3- There are no age contraints.

4- Non-olympic arguments could be used, even if it is preferred to not do it.

5- It is enough to send the solutions by mail, at the address that you can find below. Enrollment is not necessary.

6- Time of incoming solutions will be considered only for ex-aequo positions.

7- How to send solutions.

– You need to send solutions to the following mail: $\text{ leonetti.paolo (AT) gmail.com }$.
– Solutions need to be attached in a unique attached .pdf file with a reasonable size.
– The .pdf file must be written with Latex or in a way that can be easily understood.
– You have to rename the .pdf file with the nickname that you have here on MathLinks.
– Try to be clear everytime.

Previous editions: { Ed. 2008, round 1, round 2, round 3 } , { Ed. 2009, round 1, round 2 }, { Ed. 2012 round 1 }, { Ed. 2013 round 1 }.

(Italian version here)

28 November 2016

A sum-product estimate

Filed under: Math problems — Paolo @ 01:51

The following result, due to Burgain (2005), aims to provide a meaning to the fact that a large subset of a finite field usually is not a proper subfield.

Theorem. Let $F$ be a finite field and $A\subseteq F\setminus \{0\}$ a subset such that $|A|>|F|^{3/4}$. Then $3(A\cdot A)=F$.

Proof. Let $f: F\to \mathbf{R}$ be the function defined by

$x\mapsto \mathbf{E}_{a \in A}1_{a\cdot A}(x):=\frac{1}{|A|}\sum_{a \in A}1_{a\cdot A}(x).$

At this point, observe that $\mathrm{supp}(f)=A\cdot A$, so that, denoting with $*$ the usual convolution, we have $\mathrm{supp}(f*f*f)=3(A\cdot A)$. Denoting with $\hat{f}$ the Fourier transform of $f$, we obtain

$\hat{f}(\xi)=\mathbf{E}_{a \in A}\hat{1_A}(\xi/a).$

Lastly, note that $\hat{f}(0)=|A|/|F|$ and, if $\xi\neq 0$, then using the Cauchy-Schwartz inequality we have

$|\hat{f}(\xi)| \le \frac{1}{|A|^{1/2}} \frac{|A|^{1/2}}{|F|^{1/2}}=|F|^{-1/2}.$

Fix $x \in F$. Then the real-valued convolution $f*f*f$, evaluated at $x$ is equal, by Fourier inversion formula, to

$\mathrm{Re}(\sum_{\xi \in F} \hat{f}(\xi)^3 e^{2\pi i \xi \cdot x}),$

which is at least

$\mathrm{Re}\hat{f}(0)^3-\sum_{\xi \in F\setminus \{0\}}|\hat{f}(\xi)|^3.$

In turn, this is lower bounded by

$\frac{|A|^3}{|F|^3}-|F|^{-1/2}\sum_{\xi \in F}|\hat{f}(\xi)|^2.$

In other words, we have shown that

$f*f*f(x) \ge \frac{|A|^3}{|F|^3}-|F|^{-1/2}\frac{|A|}{|F|},$

which is strictly positive by hypothesis. The conclusion follows from the arbitrariness of $x \in F$.

18 March 2016

Finite Partially Exchangeable Laws are Signed Mixtures of Product Laws

Filed under: Math problems — Paolo @ 11:04

Given a partition $\{I_1,\ldots,I_k\}$ of $\{1,\ldots,n\}$, let $X_1,\ldots,X_n$ be random variables taking values in a separable Banach space $(S,\mathscr{S})$ such that the joint law of $(X_1,\ldots,X_n)$ is invariant under finite permutations of the indexes within each class $I_j$. Then, it is shown that there exists a bounded signed measure $\eta$ on $S^k$ such that, for all $A_1 \in \mathscr{S}^{n_1},\ldots,A_k \in \mathscr{S}^{n_k}$, it holds

$\mathrm{Pr}\left((X_i: i \in I_j) \in A_j, j=1,\ldots,k\right)=\int \nu_{\theta_1}^{n_1}(A_1) \cdots \nu_{\theta_k}^{n_k}(A_k) \,\eta (\mathrm{d}\theta_1,\ldots,\mathrm{d}\theta_k),$

where $n_j$ stands for the cardinality of $I_j$ and each $\nu_{\theta_j}$ is a probability measure on $S$ depending measurably on the parameter $\theta_j$. In other words, the joint laws of partially exchangeable sequences are signed mixtures of independent laws and identically distributed within each class. The representation is unique if and only if the set of these signed measures is weakly compact.

If the directing measure $\eta$ is nonnegative, the representation provides a justification for the use of priors in Bayesian parametric. In this respect, we obtain a necessary condition for the existence of such probability measure $\eta$. This is related with the notions of infinite extendibility and reinforcement. As a complementary result, we prove a determinant analogue of the Cauchy–Schwarz’s inequality.

In the special case where $(X_1,\ldots,X_n)$ is an exchangeable sequence of $\{0,1\}$-valued random variables, then $\eta$ can be chosen nonnegative if and only if two effectively computable matrices are positive semi-definite.

ArXiv version

9 March 2016

A Cauchy-Schwarz integral analogue

Filed under: Math problems — Paolo @ 00:43

Let $(\Omega, \mathscr{F},\mu)$ be a probability space and $f,g: \Omega \to \mathbf{R}$ be real-valued measurable and bounded functions. Fix also nonnegative integers $a\le b\le c\le d$ such that $a+d=b+c$. Then

$\displaystyle \int_\Omega f^bg \,\mathrm{d}\mu \int_\Omega f^cg \,\mathrm{d}\mu \le \int_\Omega f^ag \,\mathrm{d}\mu \int_\Omega f^dg \,\mathrm{d}\mu.$

Corollary: Given two positive and bounded measurable functions $\Omega \to \mathbf{R}$, set $f=h/k$, $g=k^2$, and $(a,b,c,d)=(0,1,1,2)$. Then we get that $\int hk \mathrm{d}\mu$ is at most the geometric mean of $\int h^2 \mathrm{d}\mu$ and $\int k^2 \mathrm{d}\mu$.

11 October 2015

The number of distinct prime factors of sum of n-th powers

Filed under: Math problems — Paolo @ 23:53

A result about the number of distinct prime factors of $x_1^n+\cdots+x_k^n$, where $x_1,\ldots,x_k$ are some given integers; the following estimate holds:

Theorem. Let $x_1,\ldots,x_k$ be positive integers. Then, there exist a constant $c>2$ and infinitely many positive integer $n$ for which the number of distinct prime factors of $x_1^n+\cdots+x_k^n$ is greater than the super-logarithm $\text{slog}_c(n)$ if and only if the numbers $x_1,\ldots,x_k$ are not all equal.

In particular, they are bounded if and only if all $x_1=\cdots=x_k$.

This is related to several known results in number theory, e.g., Zsigmondy’s theorem, Kobayashi’s theorem, and cases of integer-valued sequences raising from the solution of non-degenerate linear recurrence equations with integer coefficients.

ArXiV preprint w/ Salvatore Tringali.

27 September 2015

A conjecture

Filed under: Math problems — Paolo @ 12:57

Conejcture: Let $\alpha,\beta$ be positive integers, $k$  a nonzero integer, and $a,b$ be distinct reals greater than $1$. Then there exist infinitely many positive integer pairs $(n,m)$ for which $\alpha \lfloor n^a\rfloor-\beta\lfloor m^b\rfloor=k$ if and only if $\mathrm{gcd}(\alpha,\beta)$ divides $k$.

Any idea?

12 May 2015

Filed under: Math problems — Paolo @ 18:27

Why do we need to study numbers which do not belong to the real world?

Of course, we all know that the thesis is wrong as far as there are some examples where the use of complex variable functions simplify the solutions considerably. The drawback of all them is the assumption of some knowledge from students. So we would be happy to see an elementary example which may convince ourself in the usefulness of complex numbers and functions in complex variable. Here there’s a number theoretic example.

Problem. Let $p \ge 3$ be a prime. Show that

$\displaystyle \biggl(\frac2p\biggr)=(-1)^{(p^2-1)/8}.$

Solution. In the ring $\mathbb Z+\mathbb Zi=\Bbb Z[i]$, the binomial formula implies that $(1+i)^p\equiv1+i^p\pmod p$. On the other hand,

$\displaystyle (1+i)^p=\bigl(\sqrt2e^{\pi i/4}\bigr)^p=2^{p/2}\biggl(\cos\frac{\pi p}4+i\sin\frac{\pi p}4\biggr)$

and

$\displaystyle 1+i^p=1+(e^{\pi i/2})^p=1+\cos\frac{\pi p}2+i\sin\frac{\pi p}2=1+i\sin\frac{\pi p}2.$

Comparing the real parts implies that

$2^{p/2}\cos\frac{\pi p}4\equiv1\pmod p,$

hence from $\sqrt2\cos(\pi p/4)\in \{+1,-1\}$ modulo p, we conclude that

$2^{(p-1)/2}\equiv\sqrt2\cos\frac{\pi p}4\pmod p.$

It remains to apply Fermat’s theorem, so that:

$\biggl(\frac2p\biggr)\equiv2^{(p-1)/2}\equiv\sqrt2\cos\frac{\pi p}4=\begin{cases}1 & \text{if } p\equiv\pm1\pmod8, \cr-1 & \text{if } p\equiv\pm3\pmod8,\end{cases}$

which is exactly twhat we wanted to show []

11 May 2015

Using CLT to evaluate a limit

Filed under: Math problems — Paolo @ 22:37

Problem. Show that

$\displaystyle \lim\limits_{n\to\infty}\frac{1}{e^n\sqrt{n}}\sum\limits_{k=0}^{\infty}\frac{n^k}{k!}|n-k|=\sqrt{2/\pi}$

Solution (due to Jack D’Aurizio): Given a sequence of random variables $(X_n)_{n \in \mathbf{N}_+}$, each one distributed with Poisson distribution with parameter $n$, we are essentially computing

$\displaystyle \lim\limits_{n\to\infty}\frac{\mathbf{E}\left[|X-\mathbf{E}[X]|\right]}{\sqrt{n}}.$

According to the central limit theorem, we obtain that if $X_1,X_2,....$ are i.i.d. with the same distribution of $X$ then the following convergence in distribution holds

$\displaystyle \left(\frac{X_1+\cdots+X_n}{n}-\mathbf{E}[X_1]\right)_{n \in \mathbf{N}_+} \overset{d}{\to}\mathcal{N}(0,1),$

therefore we conclude that the original limit is equal to

$\displaystyle \frac{1}{\sqrt{n}}\cdot\frac{1}{\sqrt{2\pi n}}\int_{\mathbf{R}}|x-n|\exp\left(-\frac{|x-n|^2}{2n}\right)\,\mathrm{d}x=\frac{\sqrt{2}}{n\sqrt{\pi}}\int_{\mathbf{R}_+}x\exp\left(-\frac{x^2}{2n}\right)\,\mathrm{d}x.$

Hence the answer is $\sqrt{\frac{2}{\pi}}$.

10 May 2015

Filtering sums

Filed under: Math problems — Paolo @ 02:16

Proposition. Let $(\lambda_n)_{n \in \mathbf{N}^+}$ be a divergent strictly increasing sequence of positive reals, $(a_n)_{n \in \mathbf{N}^+}$ a sequence of non-negative reals, and $f\colon \mathbf{R}^+ \to \mathbf{R}$ a differentiable function such that

$\displaystyle \sum_{n \in \mathbf{N}^+}a_nf(\lambda_n)=\infty \,\,\,\,\text{ and }\,\,\,\,\sum_{\lambda_n\le x}a_nf(x)=\mathcal{O}(1).$

Let also $(b_n)_{n \in \mathbf{N}^+}$ be a subsequence of $(a_n)_{n \in \mathbf{N}^+}$. Then

$\displaystyle \liminf_{x \to \infty} \frac{\sum_{\lambda_n \le x}b_nf(\lambda_n)}{\sum_{\lambda_n \le x}a_nf(\lambda_n)} \ge \liminf_{x\to \infty}\frac{\sum_{\lambda_n\le x}b_n}{\sum_{\lambda_n\le x}a_n}.$

Proof. For each $x\ge \lambda_1$ define $\alpha(x)=\sum_{\lambda_n\le x}a_n$ and $\beta(x)=\sum_{\lambda_n\le x}b_n$. Since $(b_n)_{n \in \mathbf{N}^+}$ be a subsequence of $(a_n)_{n \in \mathbf{N}^+}$ and the numbers $\lambda_n$s are strictly positive then $\beta(x)\le \alpha(x)$ whenever $x\ge \lambda_1$, with the consequence that also $f(x)\beta(x)=\mathcal{O}(1)$. According to partial Abel summation we have that

$\displaystyle \sum_{\lambda_n \le x}a_nf(\lambda_n)=\alpha(x)f(x)-\int_{\lambda_1}^x \alpha(t)f^\prime(t)\,\mathrm{d}t,$

and similarly for the sequence of $b_n$s. Define $c=\liminf_{x\to \infty}\beta(x)/\alpha(x)$ and, given a $\varepsilon>0$, let $x_0$ be a real such that $\beta(x)\ge (c-\varepsilon)\alpha(x)$ whenever $x\ge x_0$. Then, using our assumptions, it follows that

$\displaystyle \frac{\sum_{\lambda_n \le x}b_nf(\lambda_n)}{\sum_{\lambda_n \le x}a_nf(\lambda_n)} \ge \frac{\left|\int_{\lambda_1}^x \beta(t)f^\prime(t)\,\mathrm{d}t\right|-|\beta(x)f(x)|}{\left|\int_{\lambda_1}^x \alpha(t)f^\prime(t)\,\mathrm{d}t\right|+|\alpha(x)f(x)|} = \frac{\left|\int_{x_0}^x \beta(t)f^\prime(t)\,\mathrm{d}t\right|+\mathcal{O}(1)}{\left|\int_{x_0}^x \alpha(t)f^\prime(t)\,\mathrm{d}t\right|+\mathcal{O}(1)}.$

We conclude that

$\displaystyle \liminf_{x \to \infty} \frac{\sum_{\lambda_n \le x}b_nf(\lambda_n)}{\sum_{\lambda_n \le x}a_nf(\lambda_n)} \ge c-\varepsilon$

whenever $\varepsilon>0$, which is equivalent to the claim.

Remark. Simmetrically, the same argument shows that

$\displaystyle \limsup_{x \to \infty} \frac{\sum_{\lambda_n \le x}b_nf(\lambda_n)}{\sum_{\lambda_n \le x}a_nf(\lambda_n)} \le \limsup_{x\to \infty}\frac{\sum_{\lambda_n\le x}b_n}{\sum_{\lambda_n\le x}a_n}.$

In particular, if the limit $\beta(x)/\alpha(x)$ exists, then it is equal to the limit of the left hand side.

14 February 2014

Filed under: Math problems — Paolo @ 17:05

Trying to solve a seemingly-unrelated cyclic inequality […]

For each non-empty finite multiset $X$ of (possibly not distinct) positive real numbers define $\mathcal{A}(X)$ and $\mathcal{G}(X)$ its arithmetic and geometric mean by

$\displaystyle \mathcal{A}(X):=\left(\sum_{x \in X}{x}\right)/|X| \hspace{3mm} \text{ and }\hspace{3mm}\mathcal{G}(X):=\left(\prod_{x \in X}{x}\right)^{1/|X|}.$

Suppose that $X$ has at least two distinct elements, and let $Y$ be a non-empty subset of $X$ such that $|Y|^{|Y|}\le |X|$. Then the following inequality holds strictly:

$\displaystyle \frac{\mathcal{A}(X)}{\mathcal{G}(X)}> \left(1+\frac{8}{|X|}\left(\frac{\mathcal{A}(Y)}{\mathcal{G}(Y)}-1\right)\right)^{\frac{1}{|X|}}.$

8 December 2013

A random sum with the Mobius values is always a square

Filed under: Combinatorics — Paolo @ 01:17

Problem (Own). Show that for all integers $k \ge 1$ the following sum is always a square:

$\displaystyle \sum_{i=1}^k{\sum_{j=1}^{\lfloor 2k/i\rfloor}{\sum_{h\mid j}{\mu(j/h)h/2}}}.$

Solution. Recall the well known identity $n=\sum_{d\mid n}{\varphi(d)}$ for all positive integers $n$, which can be inverted by Mobius formula into $\varphi(n)/n=\sum_{d\mid n}{\mu(d)/d}$. It means that it is enough to prove the original sum, claiming that

$\displaystyle \sum_{i=1}^k{\sum_{j=1}^{\lfloor 2k/i\rfloor}{\varphi(j)}}=2k^2.$

At this point we can prove more generally that

$\displaystyle \sum_{i=1}^{\lfloor n/2\rfloor}{\sum_{j=1}^{\lfloor n/i\rfloor}{\varphi(j)}}=\binom{n}{2}+\left\lfloor \frac{n}{2} \right\rfloor.$

The claim would follow setting $n=2k$. Such equation can be rewritten equivalently as:

$\displaystyle \sum_{i=1}^{\lfloor n/2\rfloor}{f_n(i)}=\binom{n}{2},\text{ }\text{ } \text{ where } f_n(i):=\sum_{j=2}^{\lfloor n/i\rfloor}{\varphi(j)}.$

6 August 2012

A bound on n and q

Filed under: Math problems — Paolo @ 23:08

Problem.  For some integer $q\ge 2$, define $n \in \mathbb{N}_0$ such that $b^q \equiv 1 \pmod n$ for all $b\in (\mathbb{Z}/n\mathbb{Z})^*$. Then $n\le 4q(2^q-1)$

(Proposed by Salvatore Tringali,  from Romanian TST 2004)

In the solution something stronger will be shown, i.e. $n\mid 4q(2^q-1)$click here

28 July 2012

Factorization of a factorial

Filed under: Math problems — Paolo @ 19:03

Problem. Find all  positive integers a,b,c such that $(2^a-1)(3^b-1)=c!$.  (Gabriel Dospinescu)

(Edit: Sorry for the bad looking of the file!)

5 March 2011

First fundamental theorem of asset pricing (continuous time version)

Filed under: Economics — Paolo @ 18:48
Abstract
In $1973$ Fisher Black and Myron Scholes published their pathbreaking paper [Ref: The pricing of options and corporate liabilities, Journaly of Political Economy] on option pricing, where the main idea (attribuited to Rober Merton) is the use of trading in continous time and the notion of arbitrage. The simple and economically very convincing “principle of no-arbitrage” allows one to derive, in certain mathematical model of financial markets (such as Samuelson model, the so-called “Black-Scholes model” based on geometric Brownian motion), unique prices for options and other contingent claims. The main role of no-arbitrage has been started to be studied later, in the late seventies (see Harrison, Kreps and Pliska), and it can be summarized in the “Fundamental theorem of asset pricing”(the name was given by Ph.Dybvig and S.Ross), which is not just a theorem but rather a general principle deeply related with martingale theory. We’ll begin this article with the basic proof of the theorem, as in its first formultion by Harrison and Pliska, under contraints of discrete time and finite $|\Omega|$ (this implies that all the function spaces $L^p(\Omega,\text{F},P)$ are all finite dimensional and isomorphic to $\mathbb{R}^{|\Omega|}$). Clearly, these assumption are very restrictive and do not even apply to the very first example of the theory, such as Black-Scholes model ot the much older model considered by L.Bachelier. So we’ll establish some more general version of this theorem, first in a continous time model, and then assuming infinite dimensional spaces: these version are result of a long line of increasingly general research achieved in the past two decades up to nowadays. Loosely speaking, it states that a mathematic model of financial market is free of arbitrage if and only if it is a martingale under an equivalent probability measure (i.e. it has same sets of null measure); it plays a truly fundamental role in the theory of pricing and hedging of derivatives securities (or, synonymously, contingent claim, i.e., element of $L^0(\Omega,\text{F},P)$) by no-arbitrage arguments; in this way the relation to martingale theory and stochastic integration opens the gates to the application of a powerful mathematical theory.

The whole essay can now be downloaded here: LF1302108

25 July 2010

List of funny problems (2nd)

Filed under: Math problems — Paolo @ 16:59

Problem 16- A bound regarding binomial coefficients

For each $x\in\mathbb{R}\cap (0,1)$ define the binary entropy $H(\cdot): (0,1)\to\mathbb{R} : x\to -x \text{log} _2(x) - (1-x) \text{log} _2(1-x)$, and let $n>2$ a fixed integer. Show that the following inequality $\displaystyle 2^{nH(\frac{k}{n})}\le (n+1)\binom{n}{k}$ holds for all $k\in \mathbb{Z}\cap [1,n-1]$.

Solution. Substitute the explicit value of $H(kn^{-1})$ in the inequality, and just regroup to obtain the inequality $\displaystyle \frac{n^n}{k^k(n-k)^{n-k}} \le (n+1)\binom{n}{k}$. It means that we can reformulate the problem in the equivalent form: “Let $a,b$ be positive integers with sum $c>2$, then $\displaystyle \frac{a^a}{a!}\cdot \frac{b^b}{b!} \ge \frac{c^c}{(c+1)!}$”.  So, for every $c$ fixed we obtain that left hand side if this inequality is a function $f(\cdot): \mathbb{Z}\cap [1,c-1]\to \mathbb{Q}$ of the unique variable $a$, since $\displaystyle f(a):=\frac{a^a(c-a)^{c-a}}{a!(c-a)!}$. We can show that $f(\cdot)$ attains its minimum at $\displaystyle a=\lfloor \frac{c}{2} \rfloor$,so that it will be enough to show that $\displaystyle (c+1)!f(\lfloor \frac{c}{2} \rfloor)\ge c^c$. Observe also that the function $f(\cdot)$ is symmetric with respect to $\frac{c}{2}$.

Case1: $c=2C$ for some $C\in\mathbb{N}_0$. Fix $a \in \mathbb{Z}\cap [1,C-1]$, then $f(a)\ge f(a+1)$, that is true if and only if $a^a(2C-a)^{2C-a}\binom{2C}{a}=c!f(a)$ $\ge c!f(a+1)= (a+1)^{a+1}(2C-a-1)^{2C-a-1}\binom{2C}{a+1}$: it can be rewritten as $\displaystyle \left(1+\frac{1}{2C-a-1}\right)^{2C-a-1}\ge\left(1+\frac{1}{a}\right)^a$. Now it is well-known that the function $g(x):=(1+x^{-1})^x$ is strictly increasing in $\mathbb{R}\cap [1,+\infty)$, so that this inequality remains true if and only if $2C-a-1\ge a$, and in fact by construction $a\le C-1$. So, for the case $c$ even, we have to show that $\displaystyle \left(\frac{C^C}{C!}\right)^2=f(C)\ge \frac{c^c}{(c+1)!}$ $\displaystyle =\frac{4^C}{2C+1}\cdot \frac{C^{2C}}{(2C)!}$, that is $\displaystyle \binom{2C}{C}\ge \frac{4^C}{2C+1}$ for all positive integer $C$.

Case2: $c=2C+1$ for some $C\in\mathbb{N}_0$. Just repeat the same ideas of previous lines: fix $a \in \mathbb{Z}\cap [1,C-1]$, then $f(a)\ge f(a+1)$, that is true if and only if $a^a(2C+1-a)^{2C+1-a}\binom{2C+1}{a}=$ $c!f(a)\ge c!f(a+1)=$ $(a+1)^{a+1}(2C-a)^{2C-a}\binom{2C+1}{a+1}$: it can be rewritten as $\displaystyle \left(1+\frac{1}{2C-a}\right)^{2C-a}\ge\left(1+\frac{1}{a}\right)^a$. And, as before, it is enough that $2C-a\ge a$, and in fact by construction $a\le C-1$. So, for the case $c$ odd, we have to show that $\displaystyle \frac{C^C(C+1)^{C+1}}{C!(C+1)!}=f(C)$ $\ge\frac{c^c}{(c+1)!}=$ $\displaystyle \frac{(2C+1)^{2C+1}}{(2C+2)!}$. Now multiply both members to $\displaystyle \frac{(2C)!}{C^C(C+1)^C}$, and we obtain: $\displaystyle \binom{2C}{C}\ge \frac{(2C+1)^{2C}}{2C^C(C+1)^{C+1}}$. Set $d:=2C$ and observe the following chain of inequalities: $\displaystyle \frac{(2C+1)^{2C}}{2C^C(C+1)^{C+1}}=$ $\displaystyle \frac{1}{2C+2}\cdot \frac{(2C+1)^{2C}}{C^C(C+1)^{C+1}}$ $\displaystyle <\frac{1}{2C+2}\cdot \frac{(2C+1)^{2C}}{C^C\cdot C^C}$ $\displaystyle =\frac{1}{2C+2}\cdot \left(2+\frac{2}{d}\right)^d$ $\displaystyle <\frac{e\cdot 2^d}{2C+2}=4^C\cdot \frac{e}{2C+2}$. We have shown that for the case $c$ odd, it is enough to prove that $\displaystyle \binom{2C}{C}\ge 4^C\cdot \frac{e}{2C+2}$ for all positive integer $C$.

First, let’s verify manually that $k(C):=\binom{2C}{C}$ is greater than $h(C)$, defined as the maximum between $\frac{2^{2C}}{2C+ 1}$ and $\displaystyle \frac{(2C+1)^{2C}}{2C^C(C+1)^{C+1}}$ for all $C\in \mathbb{Z}\cap [1,11]$(C, k(C),  h(C)): { (1, 2,  1.3), (2, 6,  3.2), (3, 20, 9.1), (4,70 , 28.4), (5,  252, 93), (6,  924, 315), (7, 3432, 1092), (8, 12870, 3855), (9, 48620, 13797),(10,  184756, 49932),(11, 705432, 182361)}.

Note now that for all real $x>0$ the inequality $\displaystyle \frac{4^x}{2x+1}< \frac{e4^x}{2x+2} <\frac{2^{2x+1}}{x+1}$ holds, so that the whole problem can be summarized in $\displaystyle \binom{2C}{C}\ge \frac{2^{2C+1}}{C+1}$ for all positive integer $C\in \mathbb{Z}\cap [12,+\infty)$.

Define now the sequence of $\{x_n\}_{n\in\mathbb{N}}$ of positive reals by $\displaystyle x_n:=\int_0^{\pi}{\sin^n(x) dx}$. It is clear that such sequence is (strictly) decreasing, with $x_0=\pi, x_1=2$. Integrating two times by part, also $\displaystyle x_{n+2}=\frac{n+1}{n+2}x_n$: we can conclude that:

$\displaystyle 1\le \frac{x_{2C}}{x_{2C+1}}=$ $\displaystyle \frac{\pi}{2}(2C+1)\left(\frac{(2C-1)!!}{(2C)!!}\right)^2$ $\displaystyle =\binom{2C}{C}^2 \frac{\pi (2C+1)}{2^{4C+1}}$, that implies $\displaystyle \binom{2C}{C}\ge \left(\frac{2^{4C+1}}{\pi (2C+1)}\right)^{\frac{1}{2}}$.  So, for the proof of our problem, it is enough that $\displaystyle \left(\frac{2^{4C+1}}{\pi (2C+1)}\right)^{\frac{1}{2}} \ge \frac{2^{2C+1}}{C+1}$, that is $\displaystyle (C+1)^2\ge 2\pi (2C+1)$; using the weak inequalities $2C+1<2C+2$ and $\pi<3,15$, it is enough that $(C+1)^2\ge 4\cdot 3,15\cdot (C+1)$, that is $C\ge 4\cdot 3,15-1=11,6$. The proof is complete since we assumed $C\in \mathbb{Z}\cap [12,+\infty)$. []

Problem 17- A sum of prime powers is not a power of 2

Find all $(x,y,z)\in \mathbb{N}$ such that $5^x+7^y=2^z$,where $\mathbb{N}:=\{0,1,2,\cdots\}$.

Solution. We will prove that if $(x,y,z)$ is a solution that $(x,y,z)\in S:=\{(0,0,1), (0,1,3), (2,1,5)\}$.

1. If $x=y=0$ then $z=1$, so that $(0,0,1) \in S$.

2.If $x=0$ and $y\ge 1$ then $7^y+1=2^z$. If $2\mid y$ then in $\mathbb{Z}/4\mathbb{Z}$ we have $2^z=(-1)^y+1=2$, so that $y=1$, but $2=7^y+1\ge 7^1+1$ is absurd. Otherwise, $2\nmid y$, and in $\mathbb{Z}/16\mathbb{Z}$ we have $2^z=7^y+1=7\cdot 49^{\frac{y-1}{2}}+1=7+1$: this is enough to find the other trivial solution $(0,1,3)\in S$.

3. If $x\ge 1$ and $y=0$ then $5^x+1=2^z$. Since $5^x+1\ge 6$ we have that $z\ge 2$, and taking $\mathbb{Z}/4\mathbb{Z}$ we obtain $0=2^z=5^x+1=2$, absurd.

4. From now, we can suppose $\min\{x,y\}\ge 1$, so that $2^z=5^x+7^y\ge 5+7=12$ implies that $z\ge 4$.

5. In $\mathbb{Z}/3\mathbb{Z}$ we have that $(-1)^z=2^z=5^x+7^y=(-1)^x+1$, so $2\mid x$ and $2\nmid z$.

6. In $\mathbb{Z}/4\mathbb{Z}$ we have that $0=2^z=5^x+7^y=1+(-1)^y$, so $2\nmid y$.

7. In $\mathbb{Z}/16\mathbb{Z}$ we have that $0=2^z=5^x+7^y=25^{\frac{x}{2}}+7\cdot 49^{\frac{y-1}{2}}=$ $9^{\frac{x}{2}}+7=3^x+7$ but residues of $3^i$ are exactly $[3,9,11,1]$, so that we can conclude that $4\mid x-2$.

8. To sum up all observations in points 5,6,7 , we can reformulate the problem as “find all $(a,b,c)\in \mathbb{N}^3$ such that $5^{4a+2}+7^{2b+1}=2^{2c+1}$ for some $c\ge 2$.

9. In $\mathbb{Z}/25\mathbb{Z}$ we have that $0=5^{4a+2}=2^{2c+1}-7^{2b+1}=2^{2c+1}-7\cdot (-1)^b$; and since $\text{gcd}(13,25)=1$ then also $0=13(2^{2c+1}-7\cdot (-1)^b)=4^c-16\cdot (-1)^b$. Now residues of $4^i$ are exacty $[4,16,14,6,24;21,9,11,19,1]$, and we are searching $16\cdot (-1)^b \in \{9,16\}$, that is equivalent to $5\mid c-2$.

10. To sum up all observations in points 8,9 , we can reformulate the problem as “find all $(a,b,d)\in \mathbb{N}^3$ such that $5^{4a+2}+7^{2b+1}=2^{5(2d+1)}$. We divide the rest of the solution in two cases:

PART 1.

11. Let’s find all solutions in the case $b=0$, that is $5^{4a+2}+7=2^{10d+5}$ in non-negative integers.

12. The equation in point 11 is equivalent to $5^2\cdot (5^{4a}-1)=2^5\cdot (2^{10d}-1)$, and we can see the trivial solution with $a=d=0$ that is $(x,y,z)=(2,1,5) \in S$. Let’s show that no other integer solutions exist.

13. Consider the 2-adic valuations: it is true that $5=\upsilon_2(2^5(2^{10d}-1))=\upsilon_2(5^2(5^{4a}-1))=$ $\upsilon_2(5^{4a}-1)$. And by the lifting lemma it is equal to $\upsilon_2(\frac{5^2-1}{2})+\upsilon_2(4a)$, that implies $5=3+\upsilon_2(4a)$, so $2||a$.

14. Consider the equation in $\mathbb{Z}/13\mathbb{Z}$ (after observing that $13\mid 5^4-1$), and we obtain: $6\cdot 10^d=2^5\cdot 2^{10d}=5^2\cdot 5^{4a}+7=5^2+7=6$ that is equivalent to $6=\text{ord}_{13}(10)\mid d$

15. To sum up points 13,14, the equation becomes equivalent to $5^2\cdot (5^{2^3\cdot (2h-1)}-1)=2^5(2^{2^2\cdot 3\cdot 5k}-1)$ for some $h,k$ positive integers.

16. After observing that $17\mid \text{gcd}(5^8+1,2^4+1)$ (that is equivalent to $\text{ord}_{17}(5)=2\text{ord}_{17}(2)=16$ ), consider the equation of point 15 in $\mathbb{Z}/17\mathbb{Z}$: we have that $5^2(5^{2^3\cdot (2h-1)}-1)=5^2((-1)^{2h-1}-1)=-2\cdot 5^2=1$ and $2^5(2^{2^2\cdot 3\cdot 5k}-1)=15((-1)^k-1) \in \{0,4\}$. This is a contradiction.

PART 2.

17. Now let’s show that in the case $b\ge 1$, the equation $5^{4a+2}+7^{2b+1}=2^{10d+5}$ has no solutions.

18. In $\mathbb{Z}/49\mathbb{Z}$ (the information in this point makes the difference from the previous part) we have $37^a=50\cdot 37^a=2\cdot(5^2\cdot 5^{4a})=2(5^{4a+2}+7^{2b+1})$ $=2(2^{10d+5})=64\cdot 2^{10d}=15\cdot 44^d=37^{18+16d}$. Now, since $\text{ord}_{49}(37)=21$, we conclude that $21\mid (18+16d)-a$, that is equivalent to $3\mid a-d$ and $7\mid (2d+4)-a$.

19. Observe that $7^6-1=2^4\cdot 3^2\cdot 19\cdot 43$ and take the equation in $\mathbb{Z}/9\mathbb{Z}$, we have: $4^a+4^b=4\cdot (7\cdot 4^a+7\cdot 4^b)=4\cdot (25\cdot 5^{4a}+7\cdot 49^b)$ $=4\cdot (2^5\cdot 2^{10d})=2^7\cdot 2^{10d}=2\cdot 4^{2d}$. We can see directly by hand that residues of $4^i$ are exactly $[4,7,1]$ and residues of $2\cdot 4^{2i}$ are $[5,8,2]$. And we can see that $(a,b,d)$ is a solution if and only if $3\mid a+b-d$.

20. Since we know that $3\mid a-d$ for point 18, then it is also true that $3\mid (a+b-d)-(a-d)=b$. In particular if $d$ is a divisor of $7^6-1$ then $7^{2b+1}$ is constant in $\mathbb{Z}/d\mathbb{Z}$.

21. In $\mathbb{Z}/43\mathbb{Z}$ we have $25\cdot 23^a+7=5^{4a+2}+7^{2b+1}=2^{10d+5}=32\cdot 35^d$. Now $\text{ord}_{43}(23)=21$ and $\text{ord}_{43}(35)=7$: complete residues of LHS are $[23,31,0,18,2,21,28; 17,22,8,30,20,5,4; 24,11,13,16,42,38,32]$, and complete residues of RHS are $[2,27,42,8,22,39,32]$.

22. Looking previous residues we can see that if $(a,d)$ is a solution modulo $7$ ( we can say that because $7=\text{ord}_{43}(35)\mid \text{ord}_{43}(23)\mid \varphi(43)$ ) then $(a,d)\in\{(5,1),(5,3),(3,4),(2,5),(7,7)\}$.

23. In noone of previous couples $(a,d)$ modulo $7$ we verify that $7\mid (2d+4)-a$, as requested in point 18. This is a contradiction. []

Problem 18. A equation on 4 non negative integers.

Solve the equation $p^nq^m=(p+q)^2+1$ in nonnegative integers.

Solution. Since the equation is simmetric in $p,q$, we can assume without loss of generality that $0\le p\le q$.

Moreover, we must have $\min\{n.m\}\ge 1$: in fact, if $nm=0$ then there exists a integer $x\in \mathbb{Z}$ such that $x^2+1$ is a perfect non-trivial power. And it’s well known (working in $\mathbb{Z}[i]$) that the unique solution is $x=0$, that is $p=q=0$, but $(p,q,n,m)=(0,0,0,m)$ or $(0,0,n,0)$ do not work.

If $p=0$ then $0=q^2+1\ge 1$, that is a contradiction. And, if $d:=\text{gcd}(p,q)$ then $d\mid p^nq^m=(p+q)^2+1 = d^2 \left(\frac{p+q}{d}\right)^2+1$ that implies $d\mid 1$, so if $(p,q,n,m)$ is a solution then $p$ and $q$ are coprime positive integers.

Also, looking the equation in $\mathbb{Z}/p\mathbb{Z}$ and $\mathbb{Z}/q\mathbb{Z}$ we deduce also that $p\mid q^2+1$ and $q\mid p^2+1$.

If $p=1$ then $q^m=(q+1)^2+1$ and, as before, $x^2+1$ is never a non trivial perfect power.

If $p=2$ then, since $q\mid p^2+1=5$, we have to verify if $(2+5)^2+1=2^n5^m$, and we have the solutions $(p,q,n,m)=(2,5,1,2)$ (and the simmetrical $(p,q,n,m)=(5,2,2,1)$).

If $p=3$ then, since $q\mid 3^2+1$, we have to verify only two cases: $3^n5^m=8^2+1$ and $3^n10^m=13^2+1$, and both have no solutions. From now, we can assume $p\ge 4$.

Since $q\mid p^2+1$ then we can examine first cases (when $q$ is “big”): if $q=(p^2+1)\frac{1}{i}$ for some $i\in \{1,2,3\}$ then $p\mid q^2+1= \frac{p^4+2p^2+1}{i}^2+1 \equiv \frac{i^2+1}{i^2}\pmod{p}$ (this congruence is $i\mid p^2+1$ implies $\text{gcd}(p,i)=1$, so there exist $j$ such that $\text{gcd}(p,j)=1$ and $p\mid ij-1$). It means that $p\mid i^2+1$:

– if $i=1$ then $p\mid 1^2+1=2$, but we already examined this case;

– if $i=2$ then $p\mid 2^2+1=5$, and $q=\frac{1}{2}(p^2+1)=13$. But $5^n13^m=18^2+1=5^2\cdot 13$ and we have the solution $(p,q,n,m)=(5,13,2,1)$ and its simmetrical one.

– if $i=3$ then $p\mid 3^2+1=10$, and since $p\ge 4$ we have to check only cases $p\in \{5,10\}$. But in both cases $q=\frac{1}{3}(p^2+1)$ is not a integer, since $-1$ is not a quadratic residue in $\mathbb{Z}/3\mathbb{Z}$. From now, we can assume that if $q=\frac{p^2+1}{i}$ then $i\ge 4$: it means that $p^2\ge 4q-1$.

To sum, other than two previous solutions, if $(p,q,n,m)$ verify the original equation, then $\max\{\sqrt{4q-1},4\}\le p\le q-1$ and $\text{gcd}(p,q)=1$, and $\min\{n,m\}\ge 1$.

If $n+m=2$ then $n=m=1$ and $pq=(p+q)^2+1$ if and only if $0=(2p+q)^2+3q^2+4\ge 4$, that is a contradiction.

If $n+m=3$ then $n=1, m=2$ (that is $pq^2=(p+q)^2+1\le (2q-1)^2+1<4q^2$ implies $p<4$), or $n=2, m=1$ (that is $(2q-1)^2+1\ge (p+q)^2+1=p^2q\ge q(4q-1)$, contradiction).

If $n+m:=t\ge 4$ then $(2q-1)^2+1\ge (p+q)^2+1=p^nq^m\ge p^{t-1}q\ge$ $p^3q> p^2q\ge q(4q-1)$, that is a contradiction.

We proved that if $(p,q,n,m)$ is a solution (with $p\le q$) then it belongs in $\{(2,5,1,2),(5,13,2,1)\}$. []

Problem 19. Simmetric divisibilty

Find all $(a,b)\in \mathbb{N}_0^2$ such that $a^2b^2+ab^2+1\mid a^4+a^3+1$.

Solution.  It’s clear that $a=b$ is a infinite class of solutions and that otherwise we must have $1\le b\le a-1$. It holds also $a^2b^2+ab^2+1\mid a^4+a^3-1-(a^2b^2+ab^2+1)=a(a+1)(a^2-b^2)$. Since $\text{gcd}(a^2b^2+ab^2+1,a(a+1))=1$ then it holds also : $\displaystyle a^2b^2+ab^2+1$ divides $a^2-b^2$.  But $a^2-b^2, that’s a contradiction. []

Problem 20. Even implies divisible by 8

If $a,b\in \mathbb{N}_0^2$ are fixed such that $\displaystyle \frac{(2a)^{b+1}-1}{2a-1}$ is a perfect square, then $a$ is idivisible by $4$.

Solution. Define the integer $A:=2a$, then $1+A+A^2+\ldots+A^b$ is a perfect square. Since $A$ is even, then $8\mid A^i$ for all $i\ge 3$. If $A\equiv 2,4,6$ in $\mathbb{Z}/8\mathbb{Z}$ then $1+A+A^2+\ldots+A^b\equiv 1+A+A^2 \not \equiv 1$. Otherwise $8\mid A$, that’s our aim. []

Problem 21. Sum of powers of 2 is a fixed integer

Find all non negative integers $x,y,z$ such that $2^x+2^y+2^z=2336$.

Solution. It’s well-known that every positive integer has a unique binary representation. If $m$ is a fixed positive integer, then define $f(m)$ the number of 1 that are in his binary representation.  Since $2336=2^{11}+2^8+2^5$ then $f(2336)=3$. Now, if $x=y=z$ then $2^x+2^y+2^z=3\cdot 2^x=2^{x+1}+2^x$ and it means that $f(3\cdot 2^x)=2$.  Instead, if $x=y$ and $z\neq x$ then $2^x+2^y+2^z=2^{x+1}+2^z$: it means that $f(2^{x+1}+2^z)=2$ if $z\neq x+1$ or $1$ if $z=x+1$. In all previous cases $3=f(2336)=f(2^x+2^y+2^z)\le 2$. It means that if a triple solution $(x,y,z)\in \mathbb{N}^3$ exists then wlog $0\le x. But since the binary representation is unique, then we must have $(x,y,z)=(5,8,11)$ and all his $3!$ permutations. []

Problem 22.  Divisibility again

Define $m:=2007^{2008}$. How many positive integers $n satisfy $m\mid n(2n+1)(5n+2)$?

Solution. Since $\text{gcd}(n,2n+1)=\text{gcd}(2n+1, 5n+2)=1$ and $\text{gcd}(n,5n+2)$ is $1$ or $2$ (but in all cases coprime with $2007=3^2\cdot 223$), then by chinese remainder theorem we’ll have exactly a solution in the interval $[1,2007^{2008}]$ to the system of congruences: $3^{4016}\mid p_i(n), 223^{2008}\mid p_j(n)$, where $1\le i and $p_1(n):=n, p_2(n):=2n+1, p_3(n):=5n+2$. The number of way to choose $p_i(n)$ and $p_j(n)$ is evidently $2\binom{3}{2}=6$, and noone solution of them is exactly $2007^{2008}$. Otherwise we have the cases in which $m\mid p_i(n)$ for some $1\le i\le 3$, but we have to exclude the case $i=1$ that leads to the solution $n=m$.  So, we can conclude that there are exactly $8$ distinct positive integers $n such that $m\mid p_1(n)p_2(n)p_3(n)$. []

Problem 23.  A Easy equation in positive integers

Find all $(x,y)\in \mathbb{N}_0^2$ such that $x^3-y^3=2xy+8$.

Solution. Since $2xy+8>0$ then it implies that $x>y>0$, and since $2\mid 2xy+8$ then also $2\mid x^3-y^3$, that’s $2\mid x-y$. Now the following inequality holds: $xy+4=\frac{2xy+8}{2}=\frac{x-y}{2}(x^2+y^2+xy)\ge x^2+y^2+xy$, that’s equivalent to $x^2+y^2\le 4$: it means that $x=3, y=1$, but also this couple does not satisfy the original equation, so there are no solutions. []

Probem 24. Exponential equation with integers

Find all $(a,b)\in \mathbb{Z}^2$ such that $a^{2^b}-b^{2^a}=2$.

Solution. We’ll show that if $(a,b)$ is a solution then $(a,b)\in\{(0,-2),(2,0),(9,-1)\}$.

– If $a=0$ then $-b^1=2$.

– If $b=0$ then $a^1=2$.

– If $a>0, b<0$ then $a^{2^b}$ is a integer, since it’s difference of two integers. It means that a positive integer $A$ exists such that  $a=A^{2^{|b|}}$. The equation becomes $A-(-|b|)^{2^{A^{2^{|b|}}}}=2$, that’s $|b|^{2^{A^{2^{|b|}}}}=A-2$. If $|b|=1$ then $b=-1$, and $A=3$, implying that $a=A^{2^{|b|}}=9$. Otherwise $|b|\ge 2$: then $\displaystyle |b|^{2^{A^{2^{|b|}}}}$ $>2^{2^A}\ge 2^A+1>A-2$.

– If $a<0, b>0$, then $b^{2^a}$ is a integer, since it’s difference of two integers. It means that a positive integers $B$ exists such that $b=B^{2^{|a|}}$. The equation becomes $|a|^{2^{B^{2^{|a|}}}}=B+2$. Since $B>0$ then $|a|^{2^{B^{2^{|a|}}}}=B+2>2$ implies that $|a|\ge 2$.  The following chain of inequalities holds: $|a|^{2^b}\ge 2^{2^b}\ge 2^{b+1}=$ $2\cdot 2^b\ge 2(b+1)=$ $2(B^{2^{|a|}}+1)\ge 2B^4+2>B+2$, that’s a contradiction.

– If $a<0, b<0$ we have no solution since the equation becomes $(-|a|)^{2^{-|b|}}-(-|b|)^{2^{-|a|}}=2$ and $(-1)^{2^{-x}}$ is not defined in $\mathbb{R}$ for all integer $x>0$.

– If $a>0, b>0$, then define the positive integers $x:=a^{2^{b-1}}, y:=b^{2^{a-1}}$; the equation becomes $(x+y)(x-y)=2$ and it implies $x+y=2$ and $x-y=1$. This system has no solution in positive integers $x,y$. []

31 October 2009

A list of funny problems

Filed under: Math problems — Paolo @ 08:39

Problem 1- Every number m,2m,…,nm has all digits

From Cono Sur Olympiad: “Show that for all $n \in \mathbb{N}_0$ there exist $m \in \mathbb{N}_0$ such that the number $im$ has all digits in the set $\{0,1,2,\ldots,9\}$ for all $i \in \mathbb{Z} \cap [1,n]$“.

Solution. It is enough to set $\displaystyle m:=\sum_{1\le i \le 100}{i10^{in^2}}$.

Let’s verify our claim. If $n=1$ then $10^{10} \mid m-9876543210$, that clearly works. Otherwise, suppose that $n \in \mathbb{N} \setminus \{0,1\}$. We have by construction that $10 \mid m$ for all choice of $n \in \mathbb{N}_0$, so it is enough to concentrate our attention on the digits of the set $\{1,2,\ldots,9\}$. Since in decimal representation, for all $x \in \mathbb{N}_0$ there are exactly $\lfloor \text{Log}(x) \rfloor +1$ digits (such that the first one is strictly positive) then it is easy to see that the number of digits of $i10^{in^2}$ is less than the number of digits of $10^{(i+1)n^2}$ for all $i \in \mathbb{Z} \cap [1,100)$. In fact the inequality $\lfloor \text{Log}i10^{in^2} \rfloor +1< in^2+2 \le (i+1)n^2+1$ holds always. It means that it is enough to verify that the set of numbers $S:=\{j,2j,\ldots,100j\}$ has in total  all digits in the set $\{1,2,\ldots,9\}$ for all $j \in \mathbb{Z} \cap [1,n]$ fixed. And this is true, let see why; if $j$ is a power of $10$ then our claim is trivial, since it is true for $j=1$. Otherwise, define $\ell:=\{h \in \mathbb{N}:10^{h}. Since $100j>10^{\ell+2}$ and $j<10^{\ell+1}$, then in every set $\mathbb{Z} \cap [k10^{\ell+1},(k+1)10^{\ell+1})$ there is at least one element of $S$ for all $k \in \mathbb{Z} \cap [1,9]$ fixed. But it means that the leftmost digit of such element of $S$ is exactly $k$, for all $k \in \mathbb{Z} \cap [1,9]$ fixed. And it is enough to deduce that our claim is true. []

Problem 2- Extended sum of digits.

Let $(a,b,c,d,e) \in \mathbb{P}^4 \times \mathbb{N}$ such that $(a-2)(a-b)^2>0$ and define $s_b(\cdot)$ the sum of digit function in base $b \in \mathbb{N} \setminus\{0,1\}$. Show that if $s_b(an+b)=s_b(cn+d)$ for all integer $n>e$ and $b \in \mathbb{Z} \cap (1,a)$, then $a-c=b-d=0$. (Gabriel Dospinescu)

Solution. For $t$ sufficiently large choose $n = \frac {i^{(k + 1)t} - 1}{i^t - 1} - 1$, so $s_i(an + b) = ks_i(a)+s_i(b)=ks_i(c)+s_i(d)=s_i(cn + d)$. But $k \mid s_i(b)-s_i(d)$ for all $k$, so $s_i(b)=s_i(d)$ and $s_i(a)=s_i(c)$ for all $1. Choosing $i=a-1$ we obtain $2=s_{a - 1}(a)=s_{a - 1}(c)$, so $c=(a - 1)^{\ell_1}+(a - 1)^{\ell_2}$ that is divisible by $a-1$ if $\ell_1\ell_2>0$, otherwise divisible by $a$ (the case $\ell_1=\ell_2=0$ is trivial since $c = 2$ and $a$ would be a power of 2), that implies $a=c$. Now if $b then $1=s_b(b)=s_b(d)$ so $b=d$ otherwise we can assume $d\ge b>a$, so choosing enough large $i$ and enough large $j$ such that $2^i\mid aj + b$ we obtain $s_2(aj+b)=s_2(aj+d)=s_2(aj+b)+s_2(d-b)$ then $d=b$.[]

Problem 3- Number of coprime subset of {1,2,..,n}

Show that $f(n):=|\{A \subset \{1,2\ldots,n\} \text{ s.t. } \text{gcd}(x \in A) = 1\}|$ is not a perfect square for all integer $n>1$.

Solution. Define $g(n):=|\{A\subset \{1,2\ldots,n\}\text{ s.t. }n\in A\text{ and }\text{gcd}(x \in A)=1\}|$ for all $n \in \mathbb{N}_0$; here $*$ denotes the convolution product between two arithmetical function; define also $a(n):=2^{n-1}$ for all $n\in \mathbb{N}_0$; $b(n):=(-1)^n$ for all $n\in \mathbb{N}_0$; $u(n):=1$ for all $n\in \mathbb{N}_0$, and $I(n):=\lfloor n^{-1}\rfloor$ for all $n\in \mathbb{N}_0$. Clearly $\displaystyle f(n)=\sum_{i = 1}^n{g(i)}$, and $g(1)=g(2)=1$, and $a(n)=(g*u)(n)$. By Moebius inversion and operating in $\mathbb{F}_3$ we have $g(n)=(a*\mu)(n)=-(b*\mu)(n)$: if $n>2$ is odd then $g(n)=-(u*\mu)(n)=-I(n)=0$; if $n=2q$ for some odd $q>1$ then $g(n)=-(u*\mu)(q)-(u*\mu)(q)=- 2I(q)=0$, otherwise $n=2^tq$ for some $t>1$ and $q>1$ odd, then $g(n)=-(u*\mu)(q)-\mu(2)(u*\mu)(q)=(u*\mu)(q)-(u*\mu)(q)=0$. We have concluded that $f(n)=f(2)=2$ for all $n>1$, but $\left(\frac {2}{3}\right)=-1$, so $f(n)$ cannot be a perfect square.[]

Problem 4. A special case of Dirichlet theorem

Dirichlet theorem states that if $(a,b) \in \mathbb{N}^2$ is fixed such that $a>0$ and $b>1$ and defined $\mathbb{P}_{a,b}:=\{p \in \mathbb{P}:b \mid p-a\}$, then $\displaystyle \sum_{p \in \mathbb{P}_{a,b}}{p^{-1}}$ diverges. The problem is: show the statement for $(a,b)=(1,4)$.

Solution. Suppose that the statement is false, so we can define the number $\displaystyle x:=\min\{y \in \mathbb{N} \cap [100,+\infty): \sum_{p \in \mathbb{P}_{1,4}}{p^{-1}}<4^{-1}\text{ s.t. }y. Let $k \in \mathbb{N} \cap [x+1,+\infty)$ fixed and define also sets:

$A(k):=\{y \in \mathbb{N}:\exists z \in \mathbb{N} \cap [1,k]\text{ s.t. } y=4z^2+1\}$;

$B(k):=\{y \in \mathbb{N}:y \in A\text{ and }\text{gpf}(y)\ge x+1\}$;

$C(k):=A\setminus B=\{y \in \mathbb{N}:y \in A\text{ and }\text{gpf}(y) \le x\}$;

$D(k):=\{y \in \mathbb{N} \cap [1,k^4]:\upsilon_p(y)=0 \text{ for all } p \in \mathbb{P}_{3,4} \cup \{2\}\text{ and }\text{gpf}(y)\le x\}$.

Obviusly $\upsilon_p(t)=0$ for all t in A(k)  and $p \in \mathbb{P}_{3,4} \cup \{2\}$ and $C(k) \subseteq D(k)$. Furthermore, if $t \in \mathbb{N}$ and $p \in \mathbb{P}_{1,4} \cap (x,k]$ are fixed, then in the set $\{t+1,t+2,\ldots,t+p\}$ there are at most $2$ solution of $p \mid 4x^2+1$. And, again, we have that $|\{t+1,t+2,\ldots,t+12\} \cap \mathbb{P}_{1,4}\}| \le 2$. It is enough to deduce that $\displaystyle |B(k)| \le \sum_{p \in \mathbb{P}_{1,4} \cap (x,k]}{\left(2\lceil kp^{-1} \rceil\right)} < 2k\left(\sum_{p \in \mathbb{P}_{1,4} \cap (x,k]}{p^{-1}}\right)+2\sum_{p \in \mathbb{P}_{1,4} \cap (x,k]}{1}<$ $\displaystyle 2k\left(\sum_{p \in \mathbb{P}_{1,4} \cap (x,+\infty)}{p^{-1}}\right)+2\sum_{p \in \mathbb{P}_{1,4} \cap [1,k]}{1} \le$ $\displaystyle 2k(4^{-1})+2(2k \cdot 12^{-1})=\frac{5k}{6}$.

Now, we can show by PMI that if $k=2^{2^m}$ for some enough large $m \in \mathbb{N}$ then $|D(k)| \le 2^{x(m+2)}$. If $m=0$ it is clear, then suppose that it is true for $m \in \mathbb{N}$. For $k=2^{2^{m+1}}$ we’ll have that if $t \in D(2^{2^{m+1}})$ then $f(t)$ can be choosen in $2^r$ ways, where $r:=|\mathbb{P}_{1,4} \cap [1,x]|$ and $\displaystyle f(t):=\prod_{2\nmid \upsilon_p(t),p \in \mathbb{P}}{p}$; and $tf(t)^{-1}$ is clearly a square and $\displaystyle (tf(t)^{-1})^{\frac{1}{2}} \le 2^{2^m}$ can be choosen in $|D(2^{2^m})|\le 2^{x(m+2)}$ ways by assumption. It means that $|D(2^{2^{m+1}})| \le 2^r \cdot 2^{x(m+2)} \le 2^x \cdot 2^{x(m+2)}=2^{x(m+3)}$, that is our aim.

It means that if $k=2^{2^{x-2}}$ then |D(k)| is not greater than the value $2^{x^2}$ $<\frac{k}{6}$, but $\displaystyle k=|A(k)|=|B(k) \cup C(k)|=|B(k)|+|C(k)| \le |B(k)|+|D(k)| < \frac{5k}{6}+\frac{k}{6}=k$, that is a contradiction. []

Problem 5- A inequality with Euler function and gcd(.)

Show that for all $(m,n) \in \mathbb{N}_0^2$ the inequality $\displaystyle \frac{\text{gcd}\left(\varphi(2^n+1),\varphi(2^m+1)\right)}{\varphi\left(\text{gcd}(2^n+1,2^m+1)\right)} \ge \frac{2\text{gcd}(m,n)}{2^{\text{gcd}(m,n)}}$ holds. (Nanang Susyanto)

Solution. Let $p \in \mathbb{P}\setminus \{2\}$ such that $p \mid \text{gcd}(2^n+1,2^m+1)$. Define $(x,y) \in \mathbb{N}_0^2$ such that $x:=m\text{gcd}(m,n)^{-1}$ and $y:=n\text{gcd}(m,n)^{-1}$.So there exist $(c,d) \in \mathbb{N}^2$ such that $\displaystyle x=\left(\frac{\text{ord}_p(2^{\text{gcd}(m,n)})}{2}\right)(2c+1)$ and $\displaystyle y=\left(\frac{\text{ord}_p(2^{\text{gcd}(m,n)})}{2}\right)(2d+1)$. So we must have $2 \mid \text{ord}_p(2^{\text{gcd}(m,n)})$ and since by construction $\text{gcd}(x,y)=1$ then $\text{ord}_p(2^{\text{gcd}(m,n)})=2$, and it is equivalent to say that $p \mid 2^{2\text{gcd}(m,n)}+1$, and $p \nmid 2^{\text{gcd}(m,n)}-1$, that is $p \mid 2^{\text{gcd}(m,n)}+1$. Let $\displaystyle 2^{\text{gcd}(m,n)}+1=\prod_{1\le i\le k}{q_i^{a_i}}$ be its canonical factorization, then by Lifting lemma we know that $\upsilon_{q_i}\left(2^m+1\right)=a_i+\upsilon_{q_i}(x)$ and $\upsilon_{q_i}\left(2^n+1\right)=a_i+\upsilon_{q_i}(y)$ for all $i \in \mathbb{Z} \cap [1,k]$. But by construction $\min\{\upsilon_{q_i}(x),\upsilon_{q_i}(y)\}=0$, so $\upsilon_{q_i}\left(\text{gcd}(2^m+1,2^n+1)\right)=a_i$. It is sufficient to deduce that $\varphi\left(\text{gcd}(2^n+1,2^m+1)\right) \le \text{gcd}(2^n+1,2^m+1)-1 \le 2^{\text{gcd}(m,n)}$. So, it is enough to show that $\displaystyle \text{gcd}\left(\varphi(2^n+1),\varphi(2^m+1)\right) \ge 2\text{gcd}(m,n)$ to conclude the problem.

We claim that $2\text{gcd}(m,n) \mid \text{gcd}\left(\varphi(2^n+1),\varphi(2^m+1)\right)$, and it is enough to show that for all $(a,b,c) \in \mathbb{N}_0^3$ s.t. $b>c$ the relation $2a \mid \varphi(b^a+c^a)$  holds. In fact if $\alpha \mid \beta$ for some $(\alpha.\beta) \in \mathbb{N}_0^2$ then $\varphi(\alpha) \mid \varphi(\beta)$ so we can assume wlog $\text{gcd}(b,c)=1$. Define $d:=b^a+c^a$ and $e:=bc^{-1}$ in $\mathbb{Z}/d\mathbb{Z}$, so $\text{gcd}(b,d)=\text{gcd}(c,d)=\text{gcd}(e,d)=1$. We have by construction that $d \mid e^a+1$, so the smallest $k \in \mathbb{N}$ such that $d \mid x^k+1$ is $a$. Now we have $b^a+c^a=d \mid e^{\text{ord}_d(e)}-1=b^{\text{ord}_d(e)}-c^{\text{ord}_d(e)} < b^{\text{ord}_d(e)}+c^{\text{ord}_d(e)}$, so ${\text{ord}_d(e)}>a$. If $a<\text{ord}_d(e)<2a$ then in $\mathbb{Z}/d\mathbb{Z}$ we have $1=e^a \cdot e^{\text{ord}_d(e)-a}$ so $-1=e^{\text{ord}_d(e)-a}, that is impossible. So we have $\text{ord}_d(e) \ge 2a$. Obviusly $a \neq \text{ord}_d(e) \mid 2a$, so $\text{ord}_d(e)=2a$. And because $e^{\varphi(d)} \equiv 1 \pmod d$ we conclude that $2a \mid \varphi(d)=\varphi(b^a+c^a)$, that is our aim. []

Problem 6- A functonal with cubes

Find all function $f(\cdot) \mathbb{Z} \to \mathbb{Z}$ such that $f(x^3+y^3+z^3)=f(x)^3+f(y)^3+f(z)^3$ for all $(x,y,z) \in \mathbb{Z}^3$.

Solution. Define $g(\cdot):\mathbb{Z}^3 \to \mathbb{Z}:(x,y,z) \to f(x^3+y^3+z^3)-f(x)^3+f(y)^3+f(z)^3$ then $g(\cdot)$ is identically null. Now $g(0,0,0)=0$ implies that $f(0)=0$ and $0=g(0,0,z)=g(x,-x,z)$ for all $(x,z) \in \mathbb{Z}^2$ implies that $f(\cdot)$ is a odd function. Define $k:=f(1)$, then $g(1,0,0)=0$ implies that $k \in \{-1,0,1\}$. Now $g(1,1,0)=0$ and $g(1,1,1)=0$ respectively imply that $f(2)=2k$ and $f(3)=3k$. We claim now that all and only functions $f(\cdot)$ that we are searching are $f(x)=kx$ for all $x \in \mathbb{Z}$ for some $k \in \{-1,0,1\}$ fixed. Since $f(\cdot)$ is odd, it is enough to check that $f(x)=kx$ for all $x \in \mathbb{N}$. We have that $g(4,-3,-3)=g(2,1,1)=0$ so $f(4)=4k$, $g(5,-4,-4)=g(1,1,1)=0$ so $f(5)=5k$, $g(6,-5,-4)=g(3,0,0)=0$ so $f(6)=6k$ and $g(7,-6,-5)=g(1,1,0)=0$ so also $f(7)=7k$. Suppose now the we have proved the statement for all $y \in \mathbb{Z} \cap [-2t+1,2t-1]$ for some t in $\mathbb{Z} \cap [4,+\infty)$.Let’s prove the statement for $t+1$ by PMI: in fact since $\exists (z_1,z_2,z_3,z_4,z_5) \in \mathbb{Z}^5$ such that $\max\{|z_1|,|z_2|,|z_3|,|z_4|,|z_5|\} and $z_1^3+z_2^3+z_3^3+z_4^3+z_5^3=t$, so $g(2t,-2z_1,-2z_2)=g(2z_3,2z_4,2z_5)=0$ that means $f(2t)=2tk$ and finally $g(2t+1,1-2t,-4-t)=g(4-t,-1,-5)=0$ so also $f(2t+1)=k(2t+1)$, and the induction is complete. []

Problem 7- A strange divisibility

Let $p\in \mathbb{P}$ fixed such that $12\mid p-5$; show that $\displaystyle p\mid \left(\prod_{i \in \mathbb{Z} \cap [1,\frac{p-3}{2}]}{(i^2+i+1)}\right)+2$.

Solution.  Working in $\mathbb{Z}/p\mathbb{Z}$ we have that $\displaystyle \prod_{i \in \mathbb{Z} \cap [1,\frac{p-3}{2}]}{(i^2+i+1)}=2^{p-1}\prod_{i \in \mathbb{Z} \cap [1,\frac{p-3}{2}]}{(i^2+i+1)}$ $\displaystyle =(1^2+3)\prod_{i \in \mathbb{Z} \cap [1,\frac{p-3}{2}]}{(4i^2+4i+4)}$ $\displaystyle =\prod_{i \in \mathbb{Z} \cap [1,\frac{p-1}{2}]}{\left((2i-1)^2+3\right)}$ $\displaystyle =\prod_{i \in \mathbb{Z} \cap [1,\frac{p-1}{2}]}{(i^2+3)}:=S$ and by Euler criterion we have that the constant term of the polynomial $\displaystyle p(x):=(x-3)^{\frac{p-1}{2}}-1$ is $S$, so we can conclude $\displaystyle S=p(0)=\left(\frac{3}{p}\right)-1=-2$. []

Problem 8- Minimal sum and difference with primes

Let $p_i$ the $i$-th prime of $\mathbb{P}$ and  $n\in \mathbb{N} \setminus\{0,1\}$ a fixed integer. Find, if it exists, the smallest absolute constant $K$ such that $\displaystyle \left|\sum_{i \in \mathbb{N} \cap [1,n]}{e_ip_i}\right| \le K$ for at least one choose of $e_1,e_2,\ldots,e_n \in \{-1,1\}$.

Solution. We claim that $K$ exists and it is $1$. Define $\displaystyle K_n:=\min\{x \in \mathbb{N}:\exists e_1,e_2,\ldots,e_n \in \{-1,1\}\text{ s.t. }\left|\sum_{i \in \mathbb{N} \cap [1,n]}{e_ip_i}\right|=x\}$, and obviusly $K$ will be $\max\{K_1,K_2,\ldots\}$ for all $n\in \mathbb{N}\setminus\{0,1\}$. It is enough to prove that $K_n$ is $1$ if $n$ is even, otherwise is $0$ (note that if $2 \mid n$ then $K_n \ge 1$ since the required sum is invariant modulo $2$). Let’s begin with some cases and complete the proof by PMI showing that if $n$ is fixed, then we can obtain (by a suitable choice of $e_1,e_2,\ldots,e_n \in \{-1,1\}^n$) all integer $y \in \mathbb{Z} \cap [0,2p_n]$ such that $2 \mid n+1-y$. If $n=2$ then trivially $k_2=1$ since we can choose $(e_1,e_2)=(-1,+1)$. If $n=3$ then $k_3=0$ since we can choose $(e_1,e_2,e_3)=(-1,-1,+1)$. If $n=4$ then $k_4=1$ since we can choose $(e_1,e_2,e_3,e_4)=(+1,-1,-1,+1)$. If $n=2$ then $k_5=0$ since we can choose $(e_1,e_2,e_3,e_4,e_5)=(+1,-1,+1,+1,-1)$. With $n=6$ we can obtain all odd integers in the interval $[0,+2 \cdot 13]$ (in truth, if $n<6$ we can find always counterxamples), in fact it is enough to see that: $k_6=1=-2+3+5-7-11+13$, $3=+2-3-5+7-11+13$, $5=+2+3+5-7-11+13$, $7=-2-3-5-7+11+13$, $9=-2-3+5+7-11+13$, $11=-2-3+5+7-11+13$, $13=+2-3+5+7-11+13$, $15=-2+3+5+7-11+13$, $17=+2+3-5-7+11+13$, $19=+2+3+5+7-11+13$, $21=-2-3-5+7+11+13$, $23=-2+3+5-7+11+13$, $25=+2-3-5+7+11+13$. Now, remembering that $p_{n+1}<2p_n$ (Bertand postulate), we can obtain all integers with the parity of $n$ of the intervals $[-2p_n+p_{n+1},2p_n+p_{n+1}]$ (choosing $e_{n+1}=+1$) and of $[-2p_n-p_{n-1},2p_n+p_{n+1}]$ (choosing $e_{n+1}=-1$). But the interval $[-2p_{n+1},2p_{n+1}]$ is a subset of their union, so the induction is complete. []

Problem 9- When n^2 +1 divides n!

Show that $\displaystyle \frac{n!}{n^2+1} \in \mathbb{Z}$ for some $n \in \mathbb{N}_0$ if and only if the proposition i) and ii) are both false:

i) $\text{gpf}(n^2+1)>n$;

ii) $\displaystyle \left(\frac{n^2+1}{2}\right)^{\frac{1}{2}}:=p \in \mathbb{P}$.

Solution. Part 1: “only if”. If $\displaystyle \frac{n!}{n^2+1} \in \mathbb{Z}$ for some $n \in \mathbb{N}_0$ then clearly $\text{rad}(n^2+1) \mid \text{rad}(n!)$ and in particular $\text{gpf}(n^2+1)\le\text{gpf}(n)\le n$, that contradicts the proposition i). On the other hand, if $\displaystyle \left(\frac{n^2+1}{2}\right)^{\frac{1}{2}}:=p \in \mathbb{P}$ then it should be $p^2 \mid 2p^2=n^2+1\mid n!=\left(\sqrt{2p^2-1}\right)!$ and in particular $\left(\sqrt{2p^2-1}\right)\ge 2p$, that is false for all $p \in \mathbb{P}$. Part 2: “if”. If  $\text{gpf}(n^2+1)\le n$ and $\displaystyle \left(\frac{n^2+1}{2}\right)^{\frac{1}{2}}\not\in \mathbb{P}$ then we want to show that $n!\vdots n^2+1$. Remember that $x^2+1$ is never a non-trivial power of some positive integers. In fact, if $x^2+1=y^n$ for some positive integer $x,y,n$, then $x$ is even (otherwise modulo $4$ we should have $n\mid 1=\upsilon_2(x^2+1)$). But working in the extension $\mathbb{Z}[i]$ we have $\text{gcd}(x+i,x-i)=1$, so they are both $n$-power. So it must exist $(a,b) \in \mathbb{Z}^2$ such that $(a+bi)^n=x+i$, but seeing the $i$-coefficient we must have $(a,b)=(0,-1)$, from which the unique trivial solution $(x,y)=(0,1)$ follows. In particular since $n^2+1 \not\in \mathbb{P}$ then $\omega(n^2+1) \ge 2$. Part2/case1: $2 \nmid n$. We have $\upsilon_2(n^2+1)=1 \le \upsilon_2(n!)$. Let $p \in \mathbb{P} \cap [3,n]$ fixed: if $\upsilon_p(n^2+1)=1$ then $\upsilon_p(n^2+1) \le \upsilon_p(n!)$; if $\upsilon_p(n^2+1)=2$ then there exist $q \in \mathbb{P} \cap [3,n]$ such that $(p-q)^2>0$ and $2p^2q \mid n^2+1$: in particular we have $n \ge \sqrt{2p^2q-1} \ge 2p$ since $2p^2q-1 \ge 4p^2$ iff $2p^2(q-2) \ge 1$, and it shows that $\upsilon_p(n^2+1)=2 \le \upsilon_p(n!)$; otherwise $\upsilon_p(n^2+1):=z\ge 3$ then we have $2p^z \mid n^2+1$ and so $n \ge \sqrt{2p^z-1}$. It is enough to show that $\displaystyle \sqrt{2p^z-1} \ge pz$. But if a prime $r$ divides $n^2+1$ then $4 \mid r-1$ and then $r \ge 5$. And so the inequality $2p^{z-2}\ge 2\cdot 5^{z-2}>z^2$ holds for all integer $z \ge 3$ since $2\cdot 5>3^2$ and if it is true for $z\in \mathbb{N}\cap [3,+\infty)$ then $2\cdot 5^{z-1}>5z^2>(z+1)^2$, that is true. Part2/case2: $2 \mid n$. We have now $\upsilon_2(n^2+1)=0$, so the condition on proposition ii) is never satisfied. Let $p \in \mathbb{P} \cap [3,n]$ fixed:  if $\upsilon_p(n^2+1)=1$ then $\upsilon_p(n^2+1) \le \upsilon_p(n!)$; if $\upsilon_p(n^2+1)=2$ then there exist $q \in \mathbb{P} \cap [3,n]$ such that $(p-q)^2>0$ and $p^2q \mid n^2+1$: in particular we have $n^2+1\ge 5p^2$ and the conclusion is the same as in part2/case1; otherwise $\upsilon_p(n^2+1):=z\ge 3$ then we have $n^2+1 \ge 5p^z > 2p^z$and the conclusion is the same as in part2/case1 again. []

Problem 10- A condition for being a covering system

If $1 and $a_1,a_2,\ldots,a_n$ are fixed integers such that for all $x \in \mathbb{Z}$ there exist $i \in \mathbb{N} \cap [1,n]$ that satisfy $k_i \mid x+a_i$, then find the smallest possible value of the positive integer $n$. (Turkey National Math Olympiad 2009)

Solution. We claim that the required number is $n=5$.
Assume by contradiction that for $n=4$ we can find integers $1 and $(a_1,a_2,a_3,a_4) \in \mathbb{Z}^4$ s.t. $\{x \equiv a_i \pmod{k_i}\}_{1 \le i \le 4}$ is a covering system. Obviusly we must have that the system $\{x \equiv a_i \pmod{k_i}\}_{1 \le i \le 4}$ covers all residue classes in $\mathbb{Z}/\text{lcm}(k_1,k_2,k_3,k_4)\mathbb{Z}$, and if $\text{gpf}\left(\text{lcm}(k_1,k_2,k_3,k_4)\right):=p \in \mathbb{P}\setminus \{2,3\}$ then we cannot have a covering system since each congruence can cover at most one of the $p$ class residues. At the same way if $\text{gpf}(k_1k_2k_3k_4)=2$ then there exists a residue class $x$ in $\mathbb{Z}/k_4\mathbb{Z}$ that is not covered. Now $\text{lpf}\left(\text{lcm}(k_1,k_2,k_3,k_4)\right)=2$ since if $k_1>2$ then $\displaystyle \sum_{i \in \mathbb{N} \cap [1,4]}{k_i^{-1}} \le$ $\displaystyle \sum_{i \in \mathbb{N} \cap [3,6]}{i^{-1}}<1$, that is absurd. It means that $\text{rad}(k_1k_2k_3k_4)$ is exactly $6$. Now we must have that the system $\{x \equiv a_i \pmod{k_i}\}_{2 \le i \le 4}$ convers all $\mathbb{Z}/3\mathbb{Z}$ and clearly we need have $9 \nmid \text{lcm}(k_2,k_3,k_4)$ and $3 \mid \text{gcd}(k_2,k_3,k_4)$. Now we must have $k_2=3$ and $k_3=6$ since otherwise $\displaystyle \sum_{i \in \mathbb{N} \cap [1,4]}{k_i^{-1}} \le$ $\displaystyle 2^{-1}+3^{-1}+12^{-1}+24^{-1}<1$, that is absurd. So there exist $\alpha \in \mathbb{N} \setminus \{0,1\}$ such that $(k_1,k_2,k_3,k_4)=(2,3,6,3\cdot 2^{\alpha})$, but we have always $12 \mid k_4$, so if $(k_1,k_2,k_3,k_4)$ exists then it is $(2,3,6,12)$: but in $\mathbb{Z}/12\mathbb{Z}$ we have that the system $\{x \equiv a_i \pmod{k_i}\}_{1 \le i \le 3}$ covers at most $\left(\frac{12}{2}+\frac{12}{3}-\frac{12}{6}\right)+\frac{12}{6}-1=9$ residue class, and the last one $x \equiv a_4 \pmod{12}$ is not enough to close such bug. On the other hand $(k_1k_2,k_3,k_4,k_5)=(2,3,4,6,12)$ and $(a_1,a_2,a_3,a_4,a_5)=(0,2,1,1,3)$ is a covering system. []

Problem 11- Only a few element in harmonic sum determine its divergence

Let $k\in \mathbb N_0$ fixed and $N$ be the set of numbers such that $k$ doesn’t occur in their decimal representation, then $\displaystyle S:=\sum_{n\in N}n^{-1}<+\infty$.

Solution. Define $y:=\frac{1}{\lfloor Log_{10}(k) \rfloor +1}$ the reciprocal of number of digits of $k$ and $N(h):=N\cap [10^h,10^{h+1})$ for all $h\in \mathbb{N}$ then $\displaystyle S=\sum_{h \in \mathbb{N}}{\left(\sum_{n\in N(h)}{n^{-1}}\right)}\le$ $\displaystyle \sum_{h \in \mathbb{N}}{\left(\frac{|N(h)|}{10^h}\right)}$ $\displaystyle \le \sum_{h \in \mathbb{N}}{\left(\frac{10^{h-\lfloor hy \rfloor}9^{\lfloor hy \rfloor}}{10^h}\right)}$   $\displaystyle \le \sum_{h \in \mathbb{N}}{\left(\frac{10^{h- hy +1}9^{hy-1}}{10^h}\right)}$ $=\displaystyle \sum_{h \in \mathbb{N}}{\left(\frac{9}{10}\right)^{hy-1}}<+\infty$. Corollary: since $\sum_{p \in \mathbb{P}}{p^{-1}}$ is not convergent,then there exist infinitely many primes that contains $k$ in its decimal representation. []

Problem 12- A equation involving Euler Phi-part 1

Find all $n \in \mathbb{N}_0$ such that $n-\varphi(n)=402$.

Solution. Since $2 \mid \varphi(n)$ for all $n \in \mathbb{N}\setminus\{0,1,2\}$ we have that $2\mid n$, so the chain of inequalities $\frac{n}{2} \le n-\varphi(n)=402 \le n$ holds, so if $m:=\frac{n}{2} \in \mathbb{N}$ then $m \in \mathbb{Z}\cap [201,402]$. Since $402$ is not a power of $2$ then $n$ cannot be a power of $2$, so $\omega(n) \ge 2$. Now if $2 \mid m$ then $4 \mid \text{gcd}(n,\varphi(n)) \mid 402$ that is a contradiction, so $\upsilon_2(n)=1$, i.e. $m$ is odd. Suppose that $\upsilon_p(n) \ge 2$ for some $p \in \mathbb{P}$ then $p \mid \text{gcd}(n,\varphi(n))\mid 402$ that is $p \in \{3,67\}$; and it is easy to see that $\upsilon_{67}(n) \le 1$ since otherwise $67^2 \le m \le 402$ that is false. If $m \in \mathbb{P}$ then $2m-(m-1)=402$ i.e. $m=401 \in \mathbb{P}$, so $n=802$ is a solution. From now suppose that $m$ is not prime. If $\upsilon_3(n)=0$ then $\omega(m) \le 2$ since otherwise also $\upsilon_3(\varphi(m))=0$ i.e. if $p \in \mathbb{P}$ divides $m$ then $3 \mid p+1$ and so $5 \cdot 11 \cdot 17 \le m \le 402$ that is again a contradiction. So $2m-\varphi(m)=402$ and $|\mu(m)|=1\text{ and }\upsilon_2(m)=\upsilon_3(m)=0$. So there exist primes $p>q>3$ such that $m=pq$ and $2m-\varphi(m)=402$, i.e. $(p+1)(q+1)=4 \cdot 101$ that is absurd. It proves if $n$ is a solution then $3 \mid n$. Define  $\displaystyle t:=\frac{n}{6}=\frac{m}{3}$: if it prime then $6t-2\varphi(t)=402$, i.e. $t=100$, contradiction. If $\upsilon_3(n) \ge 3$ then $3^2 \mid \text{gcd}(n,\varphi(n)) \mid 402$, contradiction; case 1: if $3 \mid t$ and $r:=\frac{t}{3}$ then $\upsilon_3(r)=0$ and $r \not \in \mathbb{P}$ (as above), so we are lead to $3r-\varphi(r)=67$ with $r \in \{25,35\}$, and they are not solution. Case 2: $3t-\varphi(t)=201$ with $\upsilon_2(t)=\upsilon_3(t)=0$, $|\mu(t)|=1$ and $t \in \left(\mathbb{Z} \cap [67,134]\right) \setminus \mathbb{P}$. If $\omega(t) \ge 3$ then $5 \cdot 7 \cdot 11 \le t \le 134$ that is false, so there exist primes $p>q>3$ such that $t=pq$. It leads to $(2p+1)(2q+1)=405$ and the unique solution is clearly $(p,q)=(13,7)$. We have shown that $n-\varphi(n)=402$ for some positive integer $n$ if and only if $n \in \{546,802\}$. []

Problem 13- A equation involving Euler Phi-part 2

Find all $n \in \mathbb{N}_0$ such that $n-\varphi(n)=420$.

Solution. Since $2 \mid \varphi(n)$ for all $n \in \mathbb{N}\setminus\{0,1,2\}$ we have that $2\mid n$, so the chain of inequalities $\frac{n}{2} \le n-\varphi(n)=420 holds, so if $m:=\frac{n}{2} \in \mathbb{N}$ then $m \in \mathbb{Z}\cap [211,420]$. Since $420$ is not a power of $2$ then $n$ cannot be a power of $2$, so $\omega(n) \ge 2$. Note also that $\upsilon_p(420)=\upsilon_p(n-\varphi(n)) \ge \upsilon_p(n)-1$ that is $\max\{\upsilon_3(n),\upsilon_5(n),\upsilon_7(n)\}\le 2$ and $\upsilon_p(n)\le 1$ for all $p\in \mathbb{P}\setminus\{2,3,5,7\}$. If $2^4 \mid n$ then $2^3 \mid \text{gcd}(n,\varphi(n))\mid 420$,contradiction and if $\upsilon_2(n)=3$ then $2^3 \mid \text{gcd}(n,\varphi(n))\mid 420$ again, since $n>8$ implies $\displaystyle \sum_{p\in \mathbb{P}\setminus\{2\}}{\upsilon_p(n)}>0$,contradiction. Case 1. If $\upsilon_2(n)=1$ then $2m-\varphi(m)=420$ and $m \in 2\mathbb{Z}+1 \cap [211,419]$. Now $1=\upsilon_2(2m-420)=\upsilon_2(\varphi(m))$ implies that $\omega(m)=1$: if $m \in \mathbb{P}$ then $2m-(m-1)=420$, i.e. $m=419 \in \mathbb{P}$, that is a solution, otherwise it can only be a square of a prime and $211\le m\le 7^2$, contradiction. Case 2. If $\upsilon_2(n)=2$ and $h:=\frac{n}{4} \in 2\mathbb{Z}+1\cap[107,209]$ then $2h-\varphi(h)=210$. Now $\displaystyle \sum_{p\in \mathbb{P}\setminus\{2\}}{\upsilon_p(h)}\le 3$ since otherwise $209 \ge h \ge 3^2\cdot 5^2$, that is false. In particular it implies that $\omega(h) \le 3$. If $\omega(h)=1$ and $h\in \mathbb{P}$ then $2h-(h-1)=210$, i.e. $h=209\not\in \mathbb{P}$, otherwise, as before, it can only be a square of a prime and $107 \le h \le 7^2$, contradiction. If $\omega(h)=2$ and $h=pq$ for some primes $p>q>2$ then $2pq-(p-1)(q-1)=210$, i.e. $(p+1)(q+1)=2^2 \cdot 53$ and it has no solution; otherwise $h=pq^2$ for some distinct odd primes $p,q$ such that $q \in \mathbb{P}\cap[3,7]$, so we have $2pq^2-pq(q-1)=210$, i.e. $\displaystyle p=\frac{210-q(q-1)}{q(q+1)}$. Now in $\mathbb{Z}/(q+1)\mathbb{Z}$ we have $0=210-q(q-1)=208$, so $q=5$ cannot lead to some solution. We can also easily see that $q \in \{3,7\}$ lead both to solutions $n\in\{2^2\cdot 3\cdot 7^2,2^2\cdot 3^2 \cdot 17\}$. It remains only the last case $\omega(h)=3$, so $h=pqr$ for some primes $p>q>r>2$. So the equation becomes $2pqr-(p-1)(q-1)(r-1)=210$, but $210=(p+1)(q+1)(r+1)-2(p+q+r)$ $\ge (p+1)(5+1)(6+1)-2(3p-6)=18p+36$, that is false for all $p\in \mathbb{P}\setminus\{2,3,5,7\}$; otherwise we must have $(p,q,r)=(7,5,3)$ and so $p_4\#-2\cdot 4\cdot 6=210$, but $0=\upsilon_5(p_4\#-2\cdot 4\cdot 6)<\upsilon_5(210)=1$, contradiction. We have shown that $n-\varphi(n)=402$ for some positive integer $n$ if and only if $n \in \{588,612,838\}$. []

Problem 14- A strictly increasing sequence

Let $\{a_i\}_{i\in \mathbb{N}_0}$ a strictlyincreasing sequence of positive integers such that $a_k\neq a_i+a_j$ for all $1\le i\le j\le k-1$. Then $\sum_{1\le i\le n}{a_i}\le a_n^2-n^2+n$. (Carlo Sanna)

Solution. We assume to demonstrate it for all $n\ge 3$. Let $\{a_k\}_{k \in \mathbb{N}_0}$ a strictly increasing sequence of positive integers such that $\displaystyle \prod_{1\le i\le j\le k}{(a_k-a_i-a_j)^2}>0$ and define $A_n:=\mathbb{Z}\cap [(2n-1)a_1,(2n+1)a_1)$ for all $n\in \mathbb{N}_0$. Let $B$ the (numerable) set $\{n\in \mathbb{Z}:\exists i\in \mathbb{N}_0\text{ such that }a_i=n\}$, then by assumption $|A_n \cap B|\le a_1$. It means that in worst case we would have $\displaystyle a_n \ge \left(2\left\lfloor\frac{n}{a_1}\right\rfloor+1\right)a_1+\left(n-a_1\left\lfloor\frac{n}{a_1}\right\rfloor \right)$ $\displaystyle =\left(\left\lfloor\frac{n}{a_1}\right\rfloor+1\right)a_1+(n-1)$. It means that $\displaystyle a_n^2-\sum_{i \in \mathbb{Z}\cap [1,n]}{a_i}\ge$ $\displaystyle \sum_{i \in \mathbb{Z}\cap [1,n]}{(a_n-a_i)}+\left(\left\lfloor\frac{n}{a_1}\right\rfloor a_1+a_1-1\right)a_n$ $\displaystyle \ge \sum_{i \in \mathbb{Z}\cap [1,n]}{(n-i)}+\left(\left(\frac{n}{a_1}-1\right)a_1+a_1-1\right)a_n$ $\displaystyle =\binom{n}{2}+(n-1)a_n$. So it is enough to show that $\binom{n}{2}+(n-1)a_n \ge \binom{n}{2}$, that is $a_n \ge \frac{n}{2}$, but it is trivial since $\{a_i\}_{i \in\mathbb{N}_0}$ is a strictly increasing sequence.

Remark: The inequality $\displaystyle \sum_{i\in \mathbb{N}\cap [1,n]}{a_i}\le a_n^2-K(n^2-n)$ is true for $K\in \mathbb{R}\cap (-\infty,\frac{13}{6}]$. In fact, as before, $\displaystyle a_n \ge \left(\left\lfloor \frac{n}{a_1}\right\rfloor+1\right)a_1+(n-1)$ $\ge \displaystyle \left(\frac{n}{a_1}\right)a_1+(n-1)=2n-1$, so the last inequality $a_n\ge \frac{n}{2}$ can be replaced by $a_n \ge 2n-1$. It means that $\displaystyle a_n^2-\sum_{i\in \mathbb{N}\cap [1,n]}{a_i}\ge \binom{n}{2}+(n-1)(2n-1)=(n-1)\left(\frac{5}{2}n-1\right)\ge \frac{13}{6}(n^2-n)$ for all $n\ge 3$

Corollary:Define the sequence $b_1:=a_1$ and $b_{n+1}^2:=b_n^2+b_n+2n$ for all $n \in \mathbb{N}\setminus\{0,1\}$. Then $a_n\ge b_n$ for all positive integers $n$. For $n=1$ it is trivially true. Suppose it is true for all $n \in \mathbb{Z}\cap [1,m-1]$. Then, by PMI, we want to show that $a_m\ge b_m$. Summing all identities we have that $\displaystyle b_m^2=a_1^2+\sum_{i \in \mathbb{N}\cap[1,m-1]}{b_i}+(n^2-n)\le a_1^2+\sum_{i \in \mathbb{N}\cap[1,m-1]}{a_i}+(n^2-n)$. So it is enough to show that $\displaystyle a_n^2-a_1^2\ge \sum_{i \in \mathbb{N}\cap[1,m-1]}{a_i}+(n^2-n)$. Since $\displaystyle a_n \ge \left(\left\lfloor\frac{n}{a_1}\right\rfloor+1\right)a_1+(n-1)$, we have that it is enough that $\displaystyle a_1\left(\left\lfloor\frac{n}{a_1}\right\rfloor a_1+n-1\right)+a_1a_n\left\lfloor\frac{n}{a_1}\right\rfloor \ge \binom{n}{2}$. If $a_1\ge n$ then rhs is at least $a_1(n-1)\ge n(n-1)\ge \binom{n}{2}$. On the other hand, if $1\le a_1\le n-1$ then we have prove that $a_n(n-a_1)+a_1(n-a_1+n-1)\ge\binom{n}{2})$; the right hand side is a quadratic function in $a_1$ and with negative coefficients of degree 1 and 2 (taking in mind that $a_n\ge 2n-1$): it means that it is a decresing function in $a_1$, so it is enough to prove the inequality for the worst case, $a_1=n-1$. So we are lead to prove that $a_n+n(n-1)\ge \binom{n}{2}$, that is obvious. []

Problem 15- A generalization from IMO99

Find all $(n,p)\in\mathbb{N}_0\times \mathbb{P}$ such that $n^{p-1}\mid (p-1)^n+1$.

Solution. Trivially $(1,p)\in S:=\{(n,p)\in\mathbb{N}_0\times \mathbb{P}:n^{p-1}\mid (p-1)^n+1\}$. If $p=2$ then $n \mid 1^n+1$ implies that also $(2,2)\in S$. If $p=3$ then we should have that $n^2\mid 2^n+1$. Obviusly $n\in \mathbb{N}\setminus 2\mathbb{N}$ so that $q:=\text{lpf}(n)\in \mathbb{P}\setminus\{2\}$; and since $\text{gcd}(q,2)=1$ we have that $q\mid \text{gcd}(2^{2n}-1,2^{q-1}-1)=2^{\text{gcd}(2n,q-1)}-1=2^2-1$ we have that $q=3$. Now since $n^2\mid 2^n+1\mid 4^n-1$ we have that $2\upsilon_3(n)\le \upsilon_3(4^n-1^n)=\upsilon_3(n)+1$ so we have $\upsilon_3(n)=1$. Define $r:=\text{lpf}(n3^{-1}) \in \mathbb{P}\setminus \{2,3\}$, and if it is not defined then $(3,3)\in S$. As before $r\mid \text{gcd}(2^{2\cdot (3r \cdot \frac{n}{3r})}-1,2^{r-1}-1)=2^{\text{gcd}(6,r-1)}-1$. In particular $r\mid 2^{\text{gcd}(6,r-1)}-1\mid 2^6-1=3^2\cdot 7$ implies that $r=7$. So if another solution with $p=3$ exists then $7\mid n^2\mid 2^n+1$ for some $n\in \mathbb{N}_0$ but $\text{ord}_7(2)=3 \in \mathbb{N}\setminus 2\mathbb{N}$, that is a contradiction. Now we can suppose that $p\in \mathbb{P}\setminus\{2,3\}$. As before, define $q:=\text{lpf}(n) \in \mathbb{P}\setminus\{2\}$, then $q\mid q^{p-1}\mid n^{p-1}\mid (p-1)^n+1\mid (p-1)^{2n}-1$, and on the other side, since obviusly $\text{gcd}(q,p-1)=1$,then $q\mid (p-1)^{q-1}-1$. It means that $q\mid (p-1)^{\text{gcd}(q-1,2n)}-1=p(p-2)$. If $q=p$ then $(p-1)\upsilon_p(n)=\upsilon_p(n^{p-1})\le \upsilon_p((p-1)^n-(-1)^n)=\upsilon_p(n)+1$ that is absurd since $p\ge 5$. Otherwisev $q\mid p-2$ and we have at the same time $(p-1)\upsilon_q(n)\le \upsilon_q((p-1)^{2n}-1^{2n})=\upsilon_q(p-2)+\upsilon_q(2n)=\upsilon_q(p-2)+\upsilon_q(n)$, that is $p-2\le (p-2)\upsilon_q(n) \le \upsilon_q(p-2)$ that is clearly absurd. []

30 October 2009

Arbitrary large gap in the image of Euler function

Filed under: Math problems — Paolo @ 03:38

For all $k \in \mathbb{N}$ there exist $n \in \mathbb{N}_0$ such that $\varphi(\mathbb{N}_0) \cap [n,n+k]=\emptyset$. (Salvatore Tringali)

Solution. Define the aritmetical function $f(\cdot):\mathbb{N}_0 \to \mathbb{N}:x \to |\varphi(\mathbb{N}_0) \cap [1,x]|$ . Note that the statement is equivalent to $f(x)=o(x)$. Let’s begin with some estimates about $f(\cdot)$.

We have that $2^{\omega(n)-1} \mid \varphi(n)$ for all $n \in \mathbb{N} \setminus \{0,1\}$ since $\varphi(\cdot)$ is a multiplicative aritmetical function and $\omega(n)-1$ is a lower bound for the number of distinct odd prime factor of $n$. And define the set of functions $g_i(\cdot):\mathbb{N}_0 \to \mathbb{N}:x \to |\{y \in \mathbb{N}\cap [1,x]: \omega(y)=i\text{ and } |\mu(y)|=1\}|$ where $i \in \mathbb{N}_0$. Let $(m,n) \in \mathbb{N}\times \mathbb{N}_0$ fixed and define also the set $S_{m,n}:=\{ j2^i : (i,j) \in \mathbb{N}^2 \text{ and } i \le m, 2\nmid j \le n2^{-i}\}$.

Clearly $\displaystyle |S_{m,n}|=\sum_{0 \le i \le m}{\lfloor n2^{-i-1}\rfloor} = n\left(1-2^{-m-1}\right)+O(m)$. On the other hand, because of the observation above, we have that $\displaystyle |\varphi(\mathbb{N}_0) \cap S_{m,n}| \le \sum_{1 \le i \le m+1}{g_i(n)}$ . But it means that $\displaystyle |\left(\mathbb{N}_0 \setminus \varphi(\mathbb{N}_0)\right) \cap [1,n]| \ge |S_{m,n}| - \sum_{1 \le i \le m+1}{g_i(n)}$, or equivalently $\displaystyle f(n) \le O(n2^{-m-1})+O(m)-\sum_{1 \le i \le m+1}{g_i(n)}$.(*)

Let show now by PMI that $\displaystyle g_i(n) for some constants $k \text{ and }h$ fixed. For $i=1$ the statement is surely true (see for example well-known Chebychev’s result about $g_1(\cdot):=\pi(\cdot)$) and suppose that it is true for $i-1 \in \mathbb{N}_0$.

(Under construction)

9 October 2009

Numbers as sum of two odd primes

Filed under: Math problems — Paolo @ 01:01

This time we’ll prove that for every integer $k \in \mathbb{N}_0$ there exist infinitely many positive integer $x$ which can be written in more than $k$ ways as sum of two odd primes.

As almost proofs about prime numbers, we’ll show assuming the contrary, i.e. the sequence $\{y_i\}_{i \in \mathbb{N}_0}$ is bounded by some real constant $\ell>0$, where $y_i$ is defined as the number of ways that the number $2i$ is representable as sum of two odd primes.
Obviusly $y_i$ represents the coefficient of $x^{2i}$ in the infinite serie $p^2(x)$, where $\displaystyle p(x):=\sum_{p \in \mathbb{P} \setminus \{2\}}{x^p}$.

Assuming that $x$ is a random variable in $(0,1)$, we can say that the inequality $\displaystyle p^2(x) \le \ell \frac{x^4}{1-x^2}$ holds, where we have used the well-known identity $\displaystyle \sum_{i \in \mathbb{N}}{z^i}=(1-z)^{-1}$ for every $z \in (-1,1)$.

It follows that $\displaystyle \sum_{p \in \mathbb{P}\setminus\{2\}}{x^{p-1}} \le x\sqrt{\frac{\ell}{1-x^2}}$ holds. So it is also true that $\displaystyle \int_0^1{\sum_{p \in \mathbb{P}\setminus\{2\}}{x^{p-1}} } \le \ell^{\frac{1}{2}} \int_0^1{\frac{x}{\sqrt{1-x^2}}}$.

It means that $\displaystyle \left(\sum_{p \in \mathbb{P}\setminus\{2\}}{p^{-1}}\right)^2 \le \ell$, so it is enough to prove that the well-known serie $\displaystyle \sum_{p \in \mathbb{P}}{\frac{1}{p}}$ diverges to get a contradiction (note that we can substitute in the text of the problem the sequence of primes with a general sequence of positive integers $\{a_i\}_{i \in \mathbb{N}}$ such that $\displaystyle \sum_{i \in \mathbb{N}}{a_i^{-1}}$ diverges). (*)

We’ll use now the well-known Euler product: it states that if $f(\cdot):\mathbb{N}_0 \to \mathbb{C}$ is a multiplicative aritmetical function such that $\displaystyle \sum_{n \in \mathbb{N}}{f(n)}$ is absolutely convergent, then the identity $\displaystyle \sum_{n \in \mathbb{N}}{f(n)}=\prod_{p \in \mathbb{P}}{\sum_{i \in \mathbb{N}}{f(p^i)}}$ holds. We have $f(1)=1$ since $f(n)=f(1)f(n)$ for all $n \in \mathbb{N}_0$, and $f(\cdot)$ is not null everywhere by the definition of aritmetical function. Define $\displaystyle R:=\sum_{n \in \mathbb{N}}{f(n)}$ and $\displaystyle P(x):=\prod_{x\ge p \in \mathbb{P}}{\sum_{i \in \mathbb{N}}{f(p^i)}}$ and $\displaystyle Q(x):=\{n \in \mathbb{N}_0: \upsilon_p(n)>0 \implies x \le p \text{ for all }p \in \mathbb{P}\}$, for every real $x>0$ fixed.

It is clear that if a positive integer $y \not \in Q(x)$ then $y>x$, and it means that $\displaystyle |R-P(x)|=|\sum_{n \not \in Q(x)}{f(n)}| \le \sum_{n \not \in Q(x)}{|f(n)|} \le \sum_{n >x }{|f(n)|}$.

The statement follows taking the limit $x \to +\infty$, in fact the product $\displaystyle \prod_{p \in \mathbb{P}}{\sum_{i \in \mathbb{N}}{f(p^i)}}$ converges absolutely since $\displaystyle \left|\sum_{i \in \mathbb{N}_0}{f(p^i)}\right| \le \sum_{i \in \mathbb{N}_0}{|f(p^i)|} \le \sum_{n \in \mathbb{N}_0}{|f(n)|}$, that converges by assumption. So we have shown that $R-P(x)=o(1)$, taking in mind the additive stucture of $\mathbb{N}$. In particular if $f(\cdot)$ is a completely multiplicative function then $\displaystyle \sum_{n \in \mathbb{N}}{f(n)}= \prod_{p \in \mathbb{P}}{ \left( 1-f(p)\right)^{-1}}$.

Assuming the above notation, it is clear that $\displaystyle \prod_{x \le p \in \mathbb{P}}{ \left( 1-p^{-1} \right) ^{-1}} = \sum_{i \in Q(x)}{i^{-1}} \ge \sum_{1 \le i \le n}{i^{-1}}$. (**)

It can be useful also to know the Abel partial summation. Let $\displaystyle \{a_i\}_{i \in \mathbb{N}}$ a divergent and strictly increasing sequence of positive real numbers and let $\displaystyle \{\gamma_i\}_{i \in \mathbb{N}}$ a sequence of complex numbers. Define $\displaystyle \varphi(\cdot):\mathbb{R}^+ \to \mathbb{C}$ a arbitrary function and $\displaystyle A(x):= \sum_{\gamma_n \le x}{a_n}$, for every real $x>0$ fixed. Then $\displaystyle \sum_{1 \le n \le N}{a_n\varphi(\gamma_n)}= \sum_{1 \le n \le N}{[A(\gamma_n)-A(\gamma_{n-1}]\varphi(\gamma_n)} = A(\gamma_N)\varphi(\gamma_N)-\sum_{1 \le n \le N-1}{A(\gamma_n)\left(\varphi(\gamma_{n+1})-\varphi(\gamma_n)\right)}$.

In particular, if $\varphi(\cdot) \in C^1(\mathbb{R}^+)$ (so it is continous and derivable), and $x \ge \gamma_1$ and $\displaystyle N:=\max\{n \in \mathbb{N}_0:\gamma_n \le x\}$, then $A(\cdot)$ is constant in $[\gamma_n,\gamma_{n+1})$ and in $[\gamma_N,x)$, so we can say that:
$\displaystyle \displaystyle \sum_{1 \le n \le N}{a_n\varphi(\gamma_n)} =\left(A(x)\varphi(x)-\int_{\gamma_N}^x{A(t)\varphi'(t)dt}\right)-$ $\displaystyle \left( \sum_{1 \le n \le N-1}{\int_{\gamma_n}^{\gamma_{n+1}}{A(t)\varphi'(t)dt}}\right)$ $\displaystyle = A(x)\varphi(x)-\int_{\gamma_1}^x{A(t)\varphi'(t)dt}$.

Now, if $a_i:=1, \gamma_i:=i$ for all $i \in \mathbb{N}_0$ and $\varphi(x)=x^{-1}$ for all $x \in \mathbb{R}^+$, then $\displaystyle \sum_{i \le x}{i^{-1}}= \sum_{\gamma_n \le x}{a_n \varphi(\gamma_n)}= A(x)\varphi(x) - \int_1^{x}{\frac{\lfloor t \rfloor}{-t^2}dt}$ $\displaystyle =\frac{\lfloor x \rfloor}{x}+\ln(x)-\int_1^{x}{\frac{ \{t\}}{t^2}dt} = \frac{\lfloor x \rfloor}{x}+\ln(x)-\int_1^{+\infty}{\frac{ \{t\}}{t^2}dt}+O\left(\int_x^{+\infty}{\frac{ \{t\}}{t^2}dt}\right)$ $=\ln(x)+\gamma+O(x^{-1})$, where $\displaystyle \gamma:=1-\int_1^{+\infty}{\frac{ \{t\}}{t^2}dt}$ is the well-known Eulero Mascheroni constant.

Turning at (*) and noting that $\displaystyle -\ln(1-z)=z+O(z^2)$ for all $z \in [0,\frac{1}{2}]$, we can conclude with:
$\displaystyle \sum_{x \ge p \in \mathbb{P}}{p^{-1}}=-\sum_{x \ge p \in \mathbb{P}}{\ln\left(1-p^{-1}\right)}+O\left(\sum_{x \ge p \in \mathbb{P}}{p^{-2}}\right)$ $\displaystyle = \ln\left(\prod_{x \ge p \in \mathbb{P}}{(1-p^{-1})^{-1}} \right) + O(1) \ge \ln(\ln(x))+O(1)$, that is clearly unbounded.[]

We can note finally that we have shown a strong quantitative lower bound on $\displaystyle \sum_{x \ge p \in \mathbb{P}}{p^{-1}}$, in fact the famous Mertens formula for prime numbers states that exist a fixed $k \in \mathbb{R}$ such that for all $x$ sufficiently large we have $\displaystyle \sum_{x \ge p \in \mathbb{P}}{p^{-1}}=\ln(\ln(x))+k+O\left((\ln x)^{-1}\right)$.

We remember that first, second and third Mertens formula states respectively that: $\displaystyle \sum_{x \ge n \in \mathbb{N}_0}{\Delta(n)n^{-1}} =\sum_{x \ge p \in \mathbb{P}}{\ln(p)p^{-1}}=\int_1^x{\psi(t)t^{-2}dt}=\ln(x)+O(1)$ (with the usual notation) and the formula of primes, useful in the proof of Prime Number Theorem, can be obtained with the Abel partial summation directly on the second one, but it can be found in all number theory book.

8 October 2009

Arbitrary long sequences with distinct number of prime factors

Filed under: Math problems — Paolo @ 02:00

We’ll show that, once the integer $k >1$ is fixed, then there exist infinitely many $x \in \mathbb{N}$ such that $\displaystyle \prod_{1 \le i < j \le k}{(\omega(x+i)-\omega(x+j))^2}>0$.