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)

Advertisements

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

This is a conjecture made constructing an example linked to a seemingly unrelated question about densities on this MO thread.

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

Quadratic reciprocity with complex numbers

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

About the AM-GM inequality

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

Observe finally that \binom{n}{2} is the number of ordered pairs (x,y) such that 1\le x < y \le n, while f_{\lfloor n/i\rfloor}(1) represents the number of pairs (a,b) such that \text{gcd}(a,b)=1 and $latex 1\le a

29 October 2013

About finite sequences of integers none divisible by another

Filed under: Math problems — Paolo @ 14:42

Fix a positive constant k and a set \mathcal{N} \subset \mathbb{N}\cap [1,2n] such that |\mathcal{N}|\ge n and \min \mathcal{N} \le k\sqrt{n}. Then there exist distinct a,b \in \mathcal{N} such that a divides b whenever n is sufficiently large.

Proof. Define the arithmetical function f that maps every positive integer n into its greatest odd divisor n2^{-\upsilon_2(n)}. If |\mathcal{N}|\ge n+1 then there exist distinct a,b \in \mathbb{N}\cap [1,2n] such that f(a)=f(b), as far as \left|f\left(\mathbb{N}\cap [1,2n]\right)\right|=n. If the claim would be not verified then |\mathcal{N}|=n and f(\mathcal{N}) would be exactly 2\mathbb{N}+1 \cap [1,2n], and in particular f would be a bijective function. Consider now the sequence of divisibility

\displaystyle 1 \mapsto 3 \mapsto 3^2 \mapsto \cdots \mapsto 3^{\lfloor \ln_3(2n)\rfloor},

where each term is (strictly) smaller than 2n. Since f is invertible, if the claim would be not true then we should have by force

\displaystyle \upsilon_2\left(f^{-1}(1)\right)>\upsilon_2\left(f^{-1}(3)\right)>\upsilon_2\left(f^{-1}(3^2)\right)>\cdots>\upsilon_2\left(f^{-1}(3^{\lfloor \ln_3(2n)\rfloor})\right)\ge 0.

In particular it implies that

\displaystyle f^{-1}(3^i) \ge 3^i2^{\lfloor \ln_3(2n)\rfloor-i}\ge 2^{\lfloor \ln_3(2n)\rfloor}>(2n)^{\ln_3(2)},

which is definitively greater than k\sqrt{n}. So, there should exist a odd integer m such that 5\le m\le k\sqrt{n} and f^{-1}(m)\le k\sqrt{n}. Consider now the sequence of divisibility

\displaystyle 1 \mapsto m \mapsto m\cdot 3 \mapsto m\cdot 3^2 \mapsto \cdots \mapsto m\cdot 3^{\lfloor \ln_3(2n/m)\rfloor},

where each term is again smaller than 2n. Reasoning as before, it implies that

f^{-1}(m) \ge m\cdot 2^{\lfloor \ln_3(2n/m)\rfloor}\ge m\cdot \left(\frac{2n}{m}\right)^{\ln_3(2)}=m^{1-\ln_3(2)}(2n)^{\ln_3(2)},

which is an increasing function of m. It means that in the lowest lower bound can be obtained with m=5, so that

f^{-1}(m) \ge f^{-1}(5) \ge 2^{\ln_3(2)}\cdot 5^{1-\ln_3(2)}\cdot n^{\ln_3(2)},

which is always strictly greater than kn^{\frac{63}{100}} for all positive constants k, that is stronger than our claim. \blacksquare

21 October 2013

Covering sets with geometric progressions

Filed under: Math problems — Paolo @ 15:46

The following question comes from All Russian Olympiad 1995, Grade 11.

Problem. Can the number 1,2,\ldots,100 be covered with 12 geometric progressions?

Solution. A collection of sequences \{(a_{i,n})_{n\in \mathbb{N}}\}_{i \in \mathcal{I}} is said to cover a certain set \mathcal{S} whenever \mathcal{S} \subseteq \bigcup_{i \in \mathcal{I}} \bigcup_{n \in \mathbb{N}}{\{a_{i,n}\}}. Once we fix i \in \mathcal{I}, a sequence (a_{i,n})_{n \in \mathbb{N}} called geometric whenever there exists a real q_i such that a_{i,n}=a_{i,0}q_i^n for all n \in \mathbb{N}. Suppose by contradiction that there exist three distinct primes p_1,p_2,p_3 such that \{p_1,p_2,p_3\} \subseteq \bigcup_{n \in \mathbb{N}}{\{a_{i,n}\}} for some fixed i \in \mathcal{I}. If |q_i| \in \{0,1\} then \left|\bigcup_{n \in \mathbb{N}}{\{a_{i,n}\}}\right|\le 2. If 0<|q_i|1, and obviously also that p_1<p_2<p_3. It means that there exist three positive integers x_1<x_2<x_3 such that p_j=a_{i,x_j}=a_{i,0}q_i^{x_j} for all j \in \{1,2,3\}. In particular

\displaystyle q_i=\left(\frac{p_2}{p_1}\right)^{\frac{1}{x_2-x_1}}=\left(\frac{p_3}{p_2}\right)^{\frac{1}{x_3-x_2}},

that is clearly impossible. In few words every geometric sequence contains at most two distinct primes. In particular it implies that if \mathcal{S} \subseteq \bigcup_{i \in \mathcal{I}} \bigcup_{n \in \mathbb{N}}{\{a_{i,n}\}} for some certain set \mathcal{S} then the following inequality holds true:

\displaystyle \left|\mathcal{S}\cap \mathbb{P}\right| \le \left| \bigcup_{i \in \mathcal{I}} \bigcup_{n \in \mathbb{N}}{\{a_{i,n}\}} \cap \mathbb{P}\right| \le 2|\mathcal{I}|.

The negative conclusion follows from the false inequality \pi(100)\le 24, once we set \mathcal{S}=\{1,\ldots,100\} and \mathcal{I}=\{1,\ldots,12\}.

\text{ }

Generalization. Can the number 2,3,\ldots,100 be covered with 23 geometric progressions?

Solution. We show again that the answer is negative, i.e. a much stronger form of the original question. Such bound can be most probably still improved, following different techniques. Fix i \in \mathcal{I} and suppose (a_{i,n})_{n \in \mathbb{N}} is a geometric sequence such that \left|\bigcup_{n \in \mathbb{N}}{\{a_{i,n}\}}\cap \mathbb{P}\right|\ge 2. Then it’s claimed that

\displaystyle \left|\bigcup_{n \in \mathbb{N}}{\{a_{i,n}\}}\cap \mathbb{Z}\right|=2,

which seems to be a very strong implication. According to the proof the original question, we have that \left|\bigcup_{n \in \mathbb{N}}{\{a_{i,n}\}}\cap \mathbb{P}\right|=2. We have to show then there does not exists other integers covered by such sequence. Define as before non-negative integers x_1<x_2 such that p_1=a_{i,x_1}=a_{i,0}q_i^{x_1} and p_2=a_{i,x_2}=a_{i,0}q_i^{x_2} for some primes p_1<p_2 and a real q_i greater than 1. Then q_i=(p_2/p_1)^{\frac{1}{x_2-x_1}}: it implies that every element of such geometric sequence has a certain form, so that

\displaystyle \bigcup_{n \in \mathbb{N}}{\{a_{i,n}\}}= \bigcup_{z \in \mathbb{Z} \cap [-x_1,\infty)}{\left\{p_1\left(\frac{p_2}{p_1}\right)^{\frac{z}{x_2-x_1}}\right\}}.

Suppose for the sake of contradiction that there exist integers \alpha \not \in \{p_1,p_2\} and y \ge -x_1 such that a_{i,y}=\alpha. Then

\displaystyle \alpha=\frac{p_2^{\frac{h}{x_2-x_1}}}{p_1^{\frac{h}{x_2-x_1}-1}}

Clearly the condition y \not\in\{p_1,p_2\} is equivalent to h\not\in \{0,x_2-x_1\}. If h is greater than x_2-x-1 then such fration is clearly irreducible, hence not an integer. If 0<h<x_2-x_1 then \alpha will be in the form p_1^lp_2^m for some rational 0<l,m<1, that is still not an integer. Finally, if h is negative then \alpha will be in the form p_1^{\frac{|h|}{x_2-x_1}+1} / p_2^{\frac{|h|}{x_2-x_1}}, which cannot be an integer.

Consider now a index i \in \mathcal{I} such that \bigcup_{n \in \mathbb{N}}{\{a_{i,n}\}}\cap \mathbb{P}=\{p\}, for some prime p. And suppose that

\displaystyle \left|\bigcup_{n \in \mathbb{N}}{\{a_{i,n}\}}\cap \mathbb{Z}\right|\ge 2.

Then there exists an integer \beta \neq p greater than 1 such that a_{i,x_1}=\beta and a_{i,x_2}=p for some distinct non-negative integers x_1,x_2. It implies that q_i=(\beta/p)^{\frac{1}{x_2-x_1}}, and so that every member of the sequence will have the form p(\beta/p)^{\frac{z}{x_2-x_1}} for some integer z\ge -x_2.

On the one hand, suppose that \beta=pk for some integer k\ge 1; then they will have the form pk^{\frac{z}{x_2-x_1}}, which is integer if and only if x_2-x_1 \mid z. That means that the intersection with \mathbb{Z} is made by only elements of the form pk^n for some non-negative integer n.

On the other hand, suppose that p\nmid \beta. Then \upsilon_p\left(p(\beta/p)^{\frac{z}{x_2-x_1}}\right) has to belong to \mathbb{N}, which happens if and only if z \in \{0,x_2-x_1\}. It’s enough to conclude that in such case no other integer will be covered.

To sum up, in the best case, the geometric sequence (2^n)_{n\ge 1} and (3\cdot 2^n)_{n\ge 1} will cover six integers in \{2,3,\ldots,100\}. Also, only (5\cdot 2^n)_{n\ge 1} and (4\cdot 2^n)_{n\ge 1} will cover at most five integers, but the last one cannot be used together with (2^n)_{n\ge 1}. All other ones will cover at most 4 distinct integers. (*)

Define A the number of sequences such that each one of them covers at most one prime, and define B the number of sequences which covers at least two primes (in particular, exactly two integers, these two primes!). Then A+2B\ge 25 and 6A+2B\ge 99. Drawing on a graph A-B it’s clear that A+B is at least 20. Such bound can be improved to 24 with consideration (*).

7 October 2013

Divisibility between sum of powers of residuals.

Filed under: Math problems — Paolo @ 11:18

Let p be a prime number, k\ge 2 an integer and 0<a_1<\ldots<a_k<p be integers such that a_1^k \equiv \ldots \equiv a_k^k \pmod p and \text{lpf}(a_1\cdots a_k) \ge \sqrt{k} or \sum_{1\le i\le k}{a_i} is square-free. Then there exists a positive constant C such that the number of integers 1\le n\le x such that a_1+\ldots+a_k divides a_1^n+\ldots +a_k^n is at least Cx.

Proof. Since integers a_1,\ldots,a_k exist by assumption, then in particular the prime p has to be greater than k, which cannot be divisible by p. Define also \alpha_n:=a_1^n+\ldots+a_k^n for all positive integers n. The relation p\mid a_i^k-a_j^k for 1\le i< j\le k and integers a_i,a_j coprime with p can be rewritten as \left(a_i/a_j\right)^k \equiv 1 \pmod{p}. It means that in \mathbb{Z}/p\mathbb{Z} the non-zero integers b_i:=a_i/a_1 are all distinct and such that b_1^k\equiv \ldots \equiv b_k^k \equiv 1 \pmod{p}, i.e.

x^k-1=\prod_{1\le i\le k}{(x-b_i)}.

In particular p divides a_1+\ldots+a_k. For every positive integer m the number of non-zero m-th residues is well-known to be \frac{p-1}{\text{gcd}(m,p-1)}. In particular if y is a m-th residue in \mathbb{Z}/p\mathbb{Z} then the equation x^m=y has exactly \text{gcd}(m,p-1) solution. Since in our case 1 is a k-th residue and b_1,\ldots,b_k are distinct then \text{gcd}(k,p-1)=k, i.e. k \mid p-1 (that is a necessary and sufficient condition such that integers a_1,\ldots,a_k really exist; moreover it can be shown with elementary tools that there exists infinitely many primes p such that k\mid p-1). Let g be a primitive root, then \{b_1,\ldots,b_k\} has to be exactly \{g^{\frac{p-1}{k}},g^{2\cdot \frac{p-1}{k}},\ldots,g^{k\cdot \frac{p-1}{k}}\}. It implies that

\alpha_n=a_1^n\sum_{1\le i\le k}{b_i^n}=a_1^n\sum_{1\le i\le k}{g^{\frac{p-1}{k}in}}.

It’s clear that if k\mid n then \alpha_n=ka_1^n \neq 0. Otherwise p divides \alpha_n.

To sum up, we know that p\mid \alpha_n if and only if k\nmid n, and that 0<\alpha_1<kp, so that a_1+\ldots+a_k=hp for some integer h \in \{1,\ldots,k-1\}. As far as (\alpha_n)_{n \in \mathbb{N}_0} is a strictly increasing sequence, then we are trying to obtain a lower bound on the number of elements of the set

\left\{\frac{\alpha_1}{\alpha_1},\frac{\alpha_2}{\alpha_1},\ldots,\frac{\alpha_{\lfloor x\rfloor}}{\alpha_1}\right\} \cap \mathbb{Z}.

That is equivalent to estimate the number of integers 1\le n\le x such that h divides \alpha_n. Notice that if q is a prime number (not necessarily odd) and r a positive integer then q^r divides x^{\varphi(q^r)+1}-x whenever x is an integer coprime with q. If h=1 the claim follows trivially. Otherwise suppose that h=\frac{\alpha_1}{p}=\prod_{1\le j\le \omega}{q_j^{\beta_j}} is its canonical factorization, for some primes 2\le q_1<\ldots<q_{\omega}<p, since 0<h<k<p.

If \alpha_1 is square-free then \beta_1=\ldots=\beta_{\omega}=1 and h is square-free too and the claim follows considering that h \mid x^{\ell\varphi(h)+1}-x whenever \ell is a positive integer, i.e. \alpha_1 \mid \alpha_{\ell\varphi(h)+1}. Otherwise, if \text{lpf}(a_1\cdots a_k) \ge \sqrt{k} and \alpha_1 is not square-free; in such case choose q_j a prime such that \beta_j \ge 2. Obviously we must have q \le \sqrt{h} \le \sqrt{k-1} < \sqrt{k}, implying that q does not divide a_1\cdots a_k. The claim follows as before, since \alpha_1 \mid \alpha_{\ell\varphi(h)+1}.

As far as \varphi(h)\le h<k, it shows also that it's enough to fix the constant C=k^{-1}. \blacksquare

4 October 2013

A recursive sequence containing squares

Filed under: Math problems — Paolo @ 14:04

Problem. (China 1992 /6) Let (a_n)_{n \in \mathbb{N}} a sequence of integers such that a_{n+1}-a_{n-2}=3(a_n-a_{n-1}) for all integers n\ge 2, a_1+1=\frac{1}{2}(a_0+a_2) and for all positive integers m there exist m consecutive terms that are all perfect squares. Then all terms of the sequence are perfect squares.

Solution. Consider the characteristic equation (\lambda-1)^3=0, so that there exist constants x,y,z such that for all integers n\ge 0:

a_n=xn^2+yn+z.

In particular we obtain a_0=z, a_1=x+y+z and a_2=4x+2y+z. As far as the rank of the matrix coefficients

\begin{bmatrix}         0 & 0 & 1           \\[0.3em]         1 & 1           & 1 \\[0.3em]         4           & 2 & 1       \end{bmatrix}

is full, the solution (x,y,z) exists and it’s unique, as function of a_0,a_1,a_2. More precisely we obtain:

a_n=\left(-a_1+\frac{1}{2}(a_2+a_0)\right)n^2+\left(2a_1-a_0-\frac{1}{2}(a_2+a_0)\right)n+a_0.

Considering the assumption a_1+1=\frac{1}{2}(a_2+a_0) we obtain finally a simple closed formula:

a_n=n^2+(a_1-a_0-1)n+a_0.

Notice that if there exist at least m consecutive perfect squares for all positive integers m, then in particular a_n is a square for infinitely many values of n.

Suppose that \alpha,\beta are two integers such that n^2+\alpha n+\beta is a square for some sufficiently large integer n. Then the same holds for 4(n^2+\alpha n+\beta)=(2n+\alpha)^2+(4\beta-\alpha^2). But the difference between two consecutive squares is definitively unbounded, that’s why we are forced to conclude that 4\beta=\alpha^2 (and in particular \alpha has to be even).

Turning back to our problem, it implies that 4a_0=(a_1-a_0-1)^2, and in particular \chi:=\frac{1}{2}(a_1-a_0-1) is an integer. But it means also that our sequence can be rewritten as

a_n=n^2+2\chi n+\chi^2,

and the claim follows. \blacksquare

17 September 2013

Symmetric sums mod p: generalizing Wilson.

Filed under: Math problems — Paolo @ 13:14

Proposition. Let p\ge 3 be a prime, and q\ge 1 be an integer. Define \mathcal{A}_q be the subset of \{2,3,\ldots,p-1\} such that a \in \mathcal{A}_q if and only if p divides x^q-a for some integer x. Let also b,c,d be integers such that \text{gcd}(b,p-1)=1 and 1\le d\le |\mathcal{A}_q|. Then p divides

\displaystyle \sum_{a_1<a_2<\cdots<a_d \text{ s.t. } a_1,\ldots,a_d \in \mathcal{A}_q}{\left(\prod_{1\le i\le d}{(a_i^b+c)}\right)} \text{ }- \text{ }\sum_{0\le j\le d}{\binom{\frac{p-1}{\text{gcd}(q,p-1)}-1-j}{d-j}(-1)^jc^{d-j}}  .

Proof. As far as there exists a primitive root g in \mathbb{Z}/p\mathbb{Z}, then

\displaystyle \mathcal{A}_q=\{g^{q^\star},g^{2q^{\star}},\ldots,g^{q^\star\left(\frac{p-1}{q^\star}-1\right)}\}  ,

where q^\star:=\text{gcd}(q,p-1), and in particular |\mathcal{A}_q|=\frac{p-1}{q^\star}-1. Moreover, since b is coprime with p-1 by assumption then the set of all a^b with a \in \mathcal{A}_q is equivalent to the set \mathcal{A}_q itself. Given a polynomial f(x) \in \mathbb{C}[x] define [x^n]f(x) the coefficient of the monomial x^n, whenever n\ge 0. It means that in \mathbb{Z}/p\mathbb{Z} the required sum

\displaystyle \sum_{a_1<a_2<\cdots<a_d \text{ s.t. } a_1,\ldots,a_d \in \mathcal{A}_q}{\left(\prod_{1\le i\le d}{(a_i+c)}\right)}

is (-1)^d times the coefficient of the monomial x^{\frac{p-1}{q^\star}-1-d} of \frac{(x-c)^{\frac{p-1}{q^\star}}-1}{(x-c)-1}, i.e.

\displaystyle \sum_{a_1<a_2<\cdots<a_d \text{ s.t. } a_1,\ldots,a_d \in \mathcal{A}_q}{\left(\prod_{1\le i\le d}{(a_i+c)}\right)}=(-1)^d[x^{\frac{p-1}{q^\star}-1-d}]\left((x-c)^{\frac{p-1}{q^\star}-1}+(x-c)^{\frac{p-1}{q^\star}-2}+\ldots+(x-c)+1\right),

that is equivalent to our claim:

\displaystyle \sum_{a_1<a_2<\cdots<a_d \text{ s.t. } a_1,\ldots,a_d \in \mathcal{A}_q}{\left(\prod_{1\le i\le d}{(a_i+c)}\right)}=(-1)^d\sum_{0\le j\le d}{\binom{\frac{p-1}{q^\star}-1-j}{\frac{p-1}{q^\star}-1-d}(-c)^{d-j}}.

Corollary. Choosing b=1, c=0, d=p-2 and q=1 we obtain the Wilson theorem, i.e. p\mid (p-1)!+1.

15 August 2013

Euler’s product

Filed under: Math problems — Paolo @ 11:13

Theorem 1. Let f be a arithmetical multiplicative function, i.e. such that

f\colon \mathbb{N}_0 \to \mathbb{C} \text{ and }f(n_1,n_2)=f(n_1)f(n_2)\text{ whenever }\text{gcd}(n_1,n_2)=1.

If the serie \sum_{n \in \mathbb{N}_0}f(n) converges absolutely, i.e. there exists C \in \mathbb{R}_{\ge 0} such that

\lim_{n\to \infty}{\sum_{n \in \mathbb{N}_0}|f(n)|}=C

then the following identity holds true:

\displaystyle \sum_{n \in \mathbb{N}_0}f(n)=\prod_{p \in \mathbb{P}}\sum_{i \in \mathbb{N}}f(p^i)

We are going to give two different proof of this result: one centered on the additive structure of natural numbers, the other on the multiplicative one.
First Proof. For every real x\ge 2 define:

\mathcal{P} \stackrel{\text{\tiny def}}{=}\sum_{n \in \mathbb{N}_0}f(n)\text{ and } \mathcal{P}(x)\stackrel{\text{\tiny def}}{=}\prod_{p \in \mathbb{P}\cap [1,x]}\sum_{i \in \mathbb{N}}f(p^i).

Define then also the sets

\mathcal{A}(x)\stackrel{\text{\tiny def}}{=}\{n \in \mathbb{N}_0\colon \text{gpf}(n) \le x\} \text{ and } \mathcal{B}(x)\stackrel{\text{\tiny def}}{=}\{n \in \mathbb{N}_0 \colon n\ge x+1\}.

It’s claimed that \mathcal{P}-\mathcal{P}(x)=o(1).

Clearly \mathbb{N}_0 \setminus \mathcal{A}(x) \subseteq \mathcal{B}(x) for all choices of x \ge 2, so that

\displaystyle \left|\mathcal{P}-\mathcal{P}(x)\right|=\left|\sum_{n \in \mathbb{N}_0\setminus \mathcal{A}(x)}f(n)\right| \le \sum_{n \in \mathbb{N}_0\setminus \mathcal{A}(x)}|f(n)| \le \sum_{n \in \mathcal{B}(x)}|f(n)|.

Under the assumption of absolute convergence, the claim follows taking the limit x \to \infty.

Second Proof. Here, instead, it’s claimed that \mathcal{P}=\mathcal{P}(x)\left(1+o(1)\right). Here we have:

\displaystyle \mathcal{P}=\mathcal{P}(x)\left(1+\sum_{n \in \mathbb{N}_0\setminus \mathcal{A}(x)}{f(n)}\right).

Then, we conclude with the same triangular inequality of before, implies by the assumption of absolute convergence, i.e.

\displaystyle \left|1+\sum_{n \in \mathbb{N}_0\setminus \mathcal{A}(x)}{f(n)}\right| \le 1+\sum_{n \in \mathbb{N}_0\setminus \mathcal{A}(x)}{|f(n)|} \le 1+\sum_{n \in \mathcal{B}(x)}{|f(n)|} \le 1+\varepsilon ,

for all choice of \varepsilon \in \mathbb{R}_{>0}.

Theorem 2. Let f be a arithmetical completely multiplicative function, i.e. such that

f\colon \mathbb{N}_0 \to \mathbb{C} \text{ and }f(n_1,n_2)=f(n_1)f(n_2) \text{ for all }n_1,n_2 \in \mathbb{N}_0.

If the serie \sum_{n \in \mathbb{N}_0}f(n) converges absolutely, i.e. there exists C \in \mathbb{R}_{\ge 0} such that

\lim_{n\to \infty}{\sum_{n \in \mathbb{N}_0}|f(n)|}=C

then the following identity holds true:

\displaystyle \sum_{n \in \mathbb{N}_0}f(n)=\prod_{p \in \mathbb{P}}\frac{1}{1-f(p)}.

Proof. As far as the function is completely multiplicative, and in particular moltiplicative, we have f(n)=f(n)f(1) for all integers n\ge 1. Supposing that there exists a integer n\ge 2 such that f(n) \neq 0 then f(1)=1 by force. The product of Theorem 1 converges absolutely because

\displaystyle \left|\prod_{p \in \mathbb{P}}\sum_{i \in \mathbb{N}}f(p^i)\right| \le \prod_{p \in \mathbb{P}}\sum_{i \in \mathbb{N}}|f(p^i)| \le \sum_{n \in \mathbb{N}_0}|f(n)| \le C.

It implies that |f(p)|<1 otherwise, together with the relation f(p^k)=f^k(p), such convergence cannot hold. The claim follows.

13 July 2013

The hardest PEN problem

Filed under: Math problems — Paolo @ 18:35

Prove that if x,y,z are positive integers such that (xy+1)(yz+1)(zx+1) is a perfect square, than each factor is a perfect square too. (Kiran Kedlaya)

Solution. A non-empty set of positive integers is defined good whenever the product of any two distinct elements is smaller of some squares by 1. In these terms \{x,y,z\} is a good set. Let’s start proving that if \{x,y,z\} is a good set, then \{x,y,z,w\} is a good set too, whenever w=x+y+z+2xyz\pm 2\sqrt{(xy+1)(yz+1)(zx+1)} is a positive integer. The two values of w are roots of the following equivalent quadratic equations:

(*) \text{ }(x+y-z-w)^2=4(xy+1)(zw+1)

(**) \text{ }(x-y+z-w)^2=4(xz+1)(yw+1)

(***) \text{ }(x-y-z+w)^2=4(yz+1)(xw+1)

And that’s clear that \alpha w+1 is a integer that can be expressed as ratio of two squares, i.e. it’s a square too, for all \alpha \in \{x,y,z\}. Since the problem is symmetric in x,y,z we can assume without loss of generality that x\le y\le z. Let’s suppose for the sake of contradiction that not all \{x,y,z\} is not a good set, i.e. there exists at least one between xy+1,yz+1,zx+1 such that it is not a perfect square. Choose now such a set \{x,y,z\} such that x+y+z is minimal, and define w using the negative square root part. It’s claimed that 0<w<z and xy+1,yw+1,wx+1 are not all perfect squares, but their product it is. This will contradict the minimaly of x+y+z, showing that \{x,y,z\} has to be a good set by force. Then, multiplying (*), (**) and (***) we get that (xy+1)(yw+1)(wx+1) is a perfect square. Moreover, e.g. yz+1 is a perfect square if and only if xw+1 is a square too, so not all xy+1,yw+1,wx+1 can be perfect squares. We are missed to show only that 0<w<z. Let's rewrite (*) as

zw+1=\frac{(x+y-z-w)^2}{4(xy+1)}\ge 0 \implies w \ge -z^{-1}

If z=1 then we are forced to x=y=z=1, but (xy+1)(yz+1)(zx+1) would not be a square. That means that w\ge 0, as far as it is a integer. But if w=0 then looking at (*), (**), (***), each terms in xy+1,yz+1,zx+1 would be a perfect square, against our assumptions. That means that w\ge 1. hence, proving that w<z will be enough to reach our contradiction. Define w^\prime the other (greater) root of (*), then

w w^\prime=x^2+y^2+z^2-2(xy+yz+zx)-4<z^2-x(2y-x)-y(2z-y)<z^2,

implying that w<z, as far as 0<w<w^\prime. The proof is complete.

4 July 2013

Differentiating generating functions

Filed under: Math problems — Paolo @ 11:32

The aim of this post is to express with an example to express the deep relation of continuous functions with discrete ones; a relatively simple answer is: generating function.

Let’s find for instance the number of ways to obtain the positive integer n as (non-ordered) sum of 1,2,3. A pretty standard way is: define a_n such result, compute manually a_1,a_2,a_3 and obtain recursively a_{n+4}, once we know a_{n+i} for some positive integer n and i \in \{1,2,3\}, hoping to obtain a simple closed formula for a_n.

A smarter way exists: it’s clear that the n-th Taylor coefficient of \left(\prod_{1\le i\le 3}{(1-z^i)}\right)^{-1} is exactly a_n, i.e.

\displaystyle \sum_{n \in \mathbb{N}_0}{a_nz^n} = \frac{1}{(1-z)(1-z^2)(1-z^3)}

where the convergence is absolute in the right hand side, whenever |z| \le 1.

Consider now the following identity:

\displaystyle \frac{1}{(1-z)(1-z^2)(1-z^3)}=\frac{1}{6(1-z)^3}+\frac{1}{4(1-z)^2}+\frac{1}{4(1-z^2)}+\frac{1}{6(1-z^3)}

and that algebraic fact that for all costants C and positive integers k we have:

\displaystyle \frac{C}{(1-z)^k}=\frac{\partial}{\partial z} \frac{C}{(k-1)(1-z)^{k-1}}

so that

\displaystyle \frac{c}{(1-z)^3}=\sum_{j \in \mathbb{N}}{c\binom{n+2}{2}z^n},\text{ and }\frac{c}{(1-z)^2}=\sum_{j \in \mathbb{N}}{c(n+1)z^n}.

Considering the above equality, we can easily conclude that

\displaystyle a_n=\left\lfloor \frac{1}{12}(n+3)^2 \right\rfloor.

Something similar can be done with distinct positive integers a_1,\ldots,a_k such that \text{gcd}(a_1,\ldots,a_k)=1 (instead of 1,2,3). It’s almost evident there is no hope to obtain a closed formula for the general case (related to the fact to obtain a general identity as before). Then we want to obtain a asymptotic formula for a_n, where

\sum_{n \in \mathbb{N}}{a_nz^n}=\left(\prod_{1\le j\le k}{(1-z^{a_j})}\right)^{-1}.

The fact is that the right hand side has a k-fold at 1, and all other roots are unit roots with multeplicity strictly smaller than k. Now we have also the identity

\frac{c}{(1-\omega z)^j}=\sum_{j \in \mathbb{N}}{c\omega^j \binom{n+j}{j-1}},

but as far as j is smaller than k then it’s negligible with respect to the main binomial coefficient \binom{n+k}{k-1}.

We have finally to evaluate the constant c: define R(z) the difference of the right hand side with respect to its main term (1-z)^{-k}, i.e.

R(z):=\left(\prod_{1\le j\le k}{(1-z^{a_j})}\right)^{-1}-c(1-z)^{-k}.

It follows by De L’Hopital rule that

c=\lim_{z\to 1}{\left(R(z)-\left(\prod_{1\le j\le k}{(1-z^{a_j})}\right)^{-1}\right)(1-z)^k}=\left(\prod_{1\le j\le k}{a_j}\right)^{-1}.

We can conclude then that

\displaystyle a_n \sim c\binom{n+k}{k-1}\sim \frac{n^{k-1}}{(k-1)!\prod_{1\le j\le k}{a_j}}.

21 May 2013

A (symmetric) equation with minimum.

Filed under: Math problems — Paolo @ 12:18

The following problem has been proposed by Titu Andreescu In Mathematical Reflection, issue 3, 2013.

Problem: Solve in positive integer the equation (x^2-y^2)^2-6\min\{x,y\}=2013.

Solution. If x=y then we have clearly no solutions. Notice that the equation is symmetric in x,y, so that we can assume wlog x>y>0. In particular 2013+6y=(x^2-y^2)^2 \ge ((y+1)^2-y^2)^2=(2y+1)^2, implying that 2y-1 < \sqrt{2013} < 50, so that y\le 25. At this point the problem already "lost his fascion" since it can be solved in a finite number of steps. But let's continue without the help of a calculator, and having in mind that we want to avoid heavy computations (well, I should define "heavy"…). We know that 2013+6y is a (odd) square, with 1\le y\le 25, so that 2000 < (x^2-y^2)^2 \le 2013+6\cdot 25.

– If 4\mid y then 2013+6y \equiv 5\pmod 8 and \left(\frac{5}{8}\right)=-1, that is absurd.

– If 3\mid y then 2013+6y \equiv 6\pmod 9, that is absurd again.

– If 3\mid y-1 then 2013+6y=2013+6\left(3\frac{y-1}{3}+1\right) \equiv 3\pmod 9, that is absurd.

It implies that if y is a solution then 3\mid y+1 and 4\nmid y, meaning equivalently that y \equiv -1 \pmod 6 or y \equiv 2\pmod{12}. Define \mathcal{S} the set of solution of y, then \mathcal{S}\subseteq \mathcal{T}:=\{2,5,11,14,17,23\}.

We already know that if y is a solution then 6y+2013 is a odd square divisible by 9. Well, let’s compute \frac{1}{9}(6t+2013)=224+\frac{1}{3}(2t-1) for all t \in \mathcal{T}. We get \{225,227,231,232,234,238\}. Well, 15^2=225 and the successive odd square is (15+2)^2>15^2+4\cdot 15=225+60>238.

We proved that unique solutions (x,y) are (2,7) and (7,2). []

7 May 2013

Shuffling a deck until..

Filed under: Combinatorics — Paolo @ 14:54

The following problem is taken from Mathlink.ro, Batilc Way 2005 / 6 (problem of the day 7 May 2013).

Problem. Fix two integers N,K such that 1\le K \le N. A deck of N different playing cards is shuffled by repeating the operation of reversing the order of K topmost cards and moving these to the bottom of the deck. Prove that the deck will be back in its initial order after a number of operation not greater than (2N/K)^2.

Solution. It’s clear that after a finite number of operation the deck will be back to its original position, since the order at n+1-operation depends strictly only on the order of n-th stage; it means that if we define \sigma(N,K,n) the permutation of \{1,\ldots,N\} after n \in \mathbb{N} operation, then such a sequence of permutations cannot be preperiodic. Define T(N,K) the period of such sequence of permutations. In particular the total number of permutation is N^N, so that T(N,K)\le N^N independently on the value of K. That’s clear we can do better.

Define t,r integers such that t:=\lfloor N/K\rfloor \ge 1 and r:=N-tK \in \mathbb{N} \cap [0, K-1], so that N=tK+r. If K \mid N (i.e. iff r=0) then T(N,K)=2t=2N/K (indeed \sigma(N,K,t) represents exactly the whole deck with all cards in the reverse order). Otherwise r\neq 0. Consider initial cards \sigma(N,K,1)=\{1,2,\ldots,N\}, and let’s see what happens in \mathbb{Z}/K\mathbb{Z}. In particular we have t blocks of K elements, and a last block of r elements. If a card i belongs to the set \{K+1,K+2,\ldots,N\} then its new position will be simply i-K. Otherwise we have two cases: if i \in \{1,2,\ldots,r\} and at some stage it will be reversed, taking the residue -i: it will need t+1 operations to be reversed again, implying that the period of such a single card is exactly 2(t+1). Otherwise i \in \{r+1,r+2,\ldots,K\}, once it’s reversed it takes the residue -i, but it needs only t operation to be reversed again. That means the period of such cards is exactly 2t. If each one card is periodic with period 2t or 2(t+1) (each one of them surely exists if r \neq 0 then T(N,K)=\text{lcm}(2t,2(t+1))=2t(t+1).

Now it’s straighforward to verify that T(N,K) \le (2N/K)^2 for all integers 1\le K\le N. []

4 May 2013

Four consecutive integers in a sequence.

Filed under: Math problems — Paolo @ 20:48

Suppose that x and y are complex numbers such that \frac{x^n -y^n}{x-y} are integers for some four consecutive positive integers n. Prove that it is an integer for all positive integers n.

Solution. Define s:=x+y, p:=xy, and for all positive integers n:

a_n:=\frac{x^n-y^n}{x-y}=\sum_{i=0}^{n-1}{x^iy^{n-1-i}}.

It’s evident that

(*) \text{   }a_{n+2}=sa_{n+1}-pa_n.

We claim that for all positive integers n:

(**) \text{   }a_{n+1}^2-a_na_{n+2}=p^n.

Let’s prove it by induction: we have a_1=1, a_2=s, a_3=s^2-p, so a_2^2=p+a_1a_3. Suppose the claim if true for n, then we have to prove that a_{n+2}^2-a_{n+1}a_{n+3}=p^{n+1}=p(a_{n+1}^2-a_na_{n+2}), that is equivalent to a_{n+2}(a_{n+2}+pa_n)=a_{n+1}(pa_{n+1}+a_{n+3}). Using (*), we can rewrite it as a_{n+2}(sa_{n+1})=a_{n+1}(sa_{n+2}), that is trivially true.

Suppose that a_{n_0}, a_{n_0+1}, a_{n_0+2}, a_{n_0+3} are integers, for some integer n_0\ge 1. Then

p=\frac{p^{n_0+1}}{p^{n_0}}=\frac{a_{n_0+2}^2-a_{n_0+1}a_{n_0+3}}{a_{n_0+1}^2-a_{n_0}a_{n_0+2}} \in \mathbb{Q}

So there exists \alpha,\beta coprime integers such that p=\frac{\alpha}{\beta}. But using (**) in n_0 we have that \beta^{n_0} \mid \alpha^{n_0}, implying that p \in \mathbb{Z}.

Using (*) and the fact that p is integer, we deduce that s \in \mathbb{Q}. But a_{n_0}=\sum_{i=0}^{n_0-1}{x^iy^{n_0-1-i}} is a symmetric polynomial in p and s, and in particular it’s a monic polynomial in s. It means that if s is a rational root of such polynomial, then it’s must be integer, thanks to Ruffini theorem.

To sum up, a_1,a_2, s, p are all integers; then, thanks to (*), a_n \in \mathbb{Z} for all positive integers n.

A kind of approximation

Filed under: Economics — Paolo @ 09:40

(Decision theory) Given a preference criterion over a set of available actions and under some general assumptions, we study the asymptotic behaviour of the ranking of actions with respect to change of a parameter, from a double point of view.

See here.

[Last proposition is going to be completed]

A system of equations with primes

Filed under: Math problems — Paolo @ 09:20

Actually available on ArXiV at http://arxiv.org/abs/1212.0802. (w/ Salvatore Tringali)

Abstract: Given an integer n \ge 3, let u_1,..., u_n be pairwise coprime integers for which 2 \le u_1 <...< u_n, and let \mathcal D be a family of nonempty proper subsets of \{1,..., n\} with "enough" elements and \varepsilon a map \mathcal D \to \{\pm 1\}. Does there exist at least one q \in \mathbb P such that q divides \prod_{i \in I} u_i - \varepsilon(I) for some I \in \mathcal D and q \nmid u_1...u_n? We answer this question in the positive in the case where the integers u_i are prime powers and some restrictions hold on \varepsilon and \mathcal D. We use the result to prove that, if \varepsilon_0 \in \{\pm 1\} and A is a set of three or more primes with the property that A contains all prime divisors of any product of the form \prod_{p \in B} p - \varepsilon_0 for which B is a finite nonempty proper subset of A, then A contains all the primes.

30 March 2013

Divisors of Fermat primes are arbitrarily large

Filed under: Math problems — Paolo @ 00:14

Problem25- Maybe Fermat primes are infinte?

Show that \displaystyle \lim_{n\to +\infty}{\sigma_{-1}(2^{2^n}+1)}=1.
Solution. For every positive integer \displaystyle m=\prod_{1\le i\le \omega(m)}{p_i^{\alpha_i}} we have by definition \sigma_{-1}(m)=\displaystyle \sum_{d\mid m}{d^{-1}}=\prod_{1\le i\le \omega(m)}{\left(\sum_{0\le j \le \alpha_i}{p^{-j}}\right)}= \prod_{1\le i\le \omega(m)}{\frac{p-p^{-\alpha_i}}{p-1}}.

It means that for m=2^{2^n}+1 we have \sigma_{-1}(2^{2^n}+1)=\displaystyle \prod_{p_i\mid 2^{2^n}+1}{\frac{p_i-p_i^{-\alpha_i}}{p_i-1}} < \prod_{p_i\mid 2^{2^n}+1}{\frac{p_i}{p_i-1}}= \prod_{p_i\mid 2^{2^n}+1}{\left(1+\frac{1}{p_i-1}\right)}.

Note now that if a prime p_i \mid 2^{2^n}+1 then \text{ord}_{p_i}=2^{n+1}; but since \text{ord}_{p_i}(2)\mid \varphi(p_i)=p_i-1 then there exists a positive integer k_i>0 such that p_i=k_i2^{n+1}+1.

Also this trivial inequality holds: 2^{(n+1)2^n}>2^{2^n}+1=\displaystyle \prod_{p_i\mid 2^{2^n}+1}{p_i^{\upsilon_{p_i}(2^{2^n}+1)}} \ge \prod_{1\le i\le \omega(2^{2n}+1)}{p_i}> 2^{(n+1)\omega(2^{2^n}+1)}: so \omega(2^{2^n}+1)<2^n.

Summing up, \sigma_{-1}(2^{2^n}+1)<\displaystyle \prod_{1\le i\le \omega(2^{2^n}+1)}{\left(1+\frac{1}{p_i-1}\right)} = \displaystyle \prod_{1\le i\le \omega(2^{2^n}+1)}{\left(1+\frac{1}{k_i2^{n+1}}\right)} \le \prod_{1\le i\le \omega(2^{2^n}+1)}{\left(1+\frac{1}{i2^{n+1}}\right)}.

Extendig this product, we have \sigma_{-1}(2^{2^n}+1)< \displaystyle \sum_{0\le i\le \omega(2^{2^n}+1)}\left(\frac{1}{2^{i(n+1)}}\left(\sum_{1\le x_1<x_2<\ldots<x_i\le \omega(2^{2^n}+1)}{\frac{1}{x_1x_2\ldots x_i}}\right) \right) \displaystyle < \sum_{0\le i\le 2^n}\left(\frac{1}{2^{i(n+1)}}\left(\sum_{1\le x_1<x_2<\ldots<x_i\le 2^n}{\frac{1}{x_1x_2\ldots x_i}}\right) \right) < \displaystyle \sum_{0\le i\le 2^n}\left(\frac{1}{2^{i(n+1)}}\left(\sum_{1\le x_1\le x_2\le \ldots\le x_i\le 2^n}{\frac{1}{x_1x_2\ldots x_i}} \right)\right)
\displaystyle = \displaystyle \sum_{0\le i\le 2^n}\left(\frac{1}{2^{i(n+1)}}\left(\sum_{1\le j\le 2^n}{j^{-1}} \right)^i\right).

For every integer y\ge 2 it’s also true that \displaystyle \sum_{1\le j\le y}{j^{-1}}<1+\int_1^y{x^{-1}dx}=1+\ln(y).

Then we can say that there exists a positive constant C>0 such that \displaystyle \sum_{1\le j\le 2^n}{j^{-1}}< Cn.

Turning back to our problem, we proved that \displaystyle \sigma_{-1}(2^{2^n}+1)<\displaystyle \sum_{0\le i\le 2^n}\left(\frac{1}{2^{i(n+1)}}\left(\sum_{1\le j\le 2^n}{j^{-1}} \right)^i\right) \displaystyle < \sum_{0\le i\le 2^n}{\left(\frac{Cn}{2^{n+1}}\right)^i} \displaystyle< \sum_{0\le i\le \infty}{\left(\frac{Cn}{2^{n+1}}\right)^i}= \displaystyle \frac{2^{n+1}}{2^{n+1}-Cn}.

Now since for every \epsilon>0 the following inequality \displaystyle 2^{n+1}\left(1-\frac{1}{1+\epsilon} \right)>Cn holds definitively, then we finished, indeed:

\displaystyle \lim_{n\to +\infty}\sigma_{-1}(2^{2^n}+1)< \displaystyle \frac{2^{n+1}}{2^{n+1}-C\ln(n)} < 1+\epsilon. []

A functional

Filed under: Math problems — Paolo @ 00:09

Find all functions f(\cdot):\mathbb{N}_0\to \mathbb{N}_0 such that

f^2(x)<xf(x+1)\le 2x^2f\left(\left\lfloor \frac{x+1}{2}\right\rfloor\right)\text{ for all }x\in \mathbb{N}_0

(Troileto Br00tal)

Proof. If x=1 then f^2(1)<2f(1) implies f(1)=1. At the same way, if x=2 then f^2(2)<2\cdot 2^2f(1)=8, together with 1=f^2(1)<f(2), implies f(2)=2.

Define y the smallest positive integer such that f(y) \ge y+1 (if it exists). Notice that if f(z)\ge z+k for some positive integers z,k, then f(z+1)>\frac{f^2(z)}{z}>z+2k and since we are working on integers, then f(z+1)\ge (z+1)+2k. Once we defined y then it’s true by induction that

f(y+m) \ge (y+m)+2^m for all m \in \mathbb{N} (i)

Since the inequality xf(x+1)\le 2x^2f\left(\left\lfloor \frac{x+1}{2}\right\rfloor\right) must hold too, then choosing x=2^t-1 we obtain:

f(2^t)<2(2^t-1)f(2^{t-1})<2^2(2^t-1)(2^{t-1}-1)f(2^{t-2})<\ldots<2^t\prod_{1\le i\le t}{(2^i-1)}f(1)

and it implies that

f(2^t)<2^{t+\sum_{1\le i\le t}i}<2^{t^2} for all integers t sufficiently large. (ii)

Choosing m=2^t-y in (i)  and using (ii) we have finally:

2^{t^2}>f(2^t) \ge 2^t+2^{2^t-y}>2^{2^{t-1}} for all integers t sufficiently large

but the chain of inequalities becomes definitively false, i.e. f(x)=x for all x \in \mathbb{N}_0. On the other hand, f(x)=x really satifies our costraints. []

27 March 2013

(Another) Dirichlet corollary

Filed under: Math problems — Paolo @ 17:18

Show that there exist infinitely many primes ending with the digit 9.

Proof. Call \mathcal{P} the subset of the set of primes \mathbb{P} ending with the digit 9. It’s obvious that \mathcal{P}\neq \emptyset since 19 \in \mathbb{P} \cap \mathcal{P}. Suppose by absurd that \mathcal{P} is finite, so that the product P:=\prod_{p \in \mathcal{P}}{p} is well defined. Define q a prime divisor of 4P^2-5. Then q is odd, and 1=\left(\frac{5}{q}\right)=\left(\frac{q}{5}\right) implying that q\equiv 1 \pmod 5 or q\equiv -1 \pmod 5. But 4P^2-5 \equiv -1 \pmod5 so that at least one of his prime divisors has residue -1 modulo 5: call q_0 this prime. But then q_0 \equiv -1 \pmod 9, and we have the same time q_0 \in \mathcal{P} (implying that q_0 \mid P) and q_0 \mid 4P^2-5, a contradiction. []

25 March 2013

A invariant

Filed under: Math problems — Paolo @ 14:59

Let’s fix some positive integers a_1,a_2,\ldots,a_n not necessarily distinct. An available move consists in removing two of them and substitute with their great common divisor and their least common multiple. Show that we can do only a finite number of available moves, and at the end noone number will be changed definitively.

Proof. Just for definition we start we integers a_1,a_2,\ldots,a_n and at m-th step (with m \in \mathbb{N}\setminus \{0\}) we have integers a_{m,1},a_{m,2},\ldots,a_{m,n}. Notice that if we have integers a_{m,1} \le a_{m,2} \le \ldots \le a_{m,n} at some step m such that a_{m,i} \mid a_{m,i+1} for all i=1,2,\ldots,n-1, then noone integer will be changed. We can also show that this is the unique way to end this algorithm. It’s clear that \text{gcd}(a_i,a_j)\text{lcm}(a_i,a_j)=a_ia_j for some 1\le i<j\le n, so that \prod_{1\le i\le n}{a_i}=\prod_{1\le i \le n}{a_{m,i}}\text{ for all }m \in \mathbb{N}\setminus \{0\}. In particular, since the product is constant then there exists a positive integer M such that \sum_{1\le i\le n}{a_{m,i}} \le M, indipendently from the value of m. Define M_0:=\sum_{1\le i\le n}{a_i}, and M_m:=\sum_{1\le i\le n}{a_{m,i}}. We claim finally that there exist 1\le iM_m, i.e. we have to show that M_{m+1}-M_m=\text{gcd}(a_{m,i},a_{m,j})+\text{lcm}(a_{m,i},a_{m,j})-a_{m,i}-a_{m,j}
is strictly positive. Define x:=a_{m,i}, y:=a_{m,j}, g:=\text{gcd}(a_{m,i},a_{m,j}) and P:=a_{m,i}a_{m,j}. Then we have to show that \left(g+\frac{P}{g}\right)-\left(x+\frac{P}{x}\right)>0 under the assumption that 0<g<x<\sqrt{P}<y<\frac{P}{g}<P. But the function f(x)=x+Px^{-1} is strictly decreasing in [0,\sqrt{P}), and that's enough to conclude. Assuming that the algorithm will never stop, we created a strictly increasing sequence of positive integers M_0<M_1<M_2<\ldots such that M_m \le M for all m \in \mathbb{N} \setminus \{0\}, and that's a contradiction.

20 January 2013

Kobayashi theorem

Filed under: Math problems — Paolo @ 10:17

If a infinite sequence of positive integers (a_i)_{i \in \mathbb{N}} is not bounded and \displaystyle \omega\left(\prod_{i \in \mathbb{N}}{a_i}\right) is finite, then \displaystyle \omega\left(\prod_{i \in \mathbb{N}}{(a_i+t)}\right) is finite too if and only if t=0.

Solution: The “if” part follows by definition; about the “only if”, the proof heavily relies on a elementary and non trivial result of Axel Thue, i.e. ¬†a theorem proved in 1909 that states the following: the equation f(x,y)=r\in \mathbb{Q}\setminus \{0\} has only finitely many solutions in \mathbb{Z}^2 whenever f is a irreducible bivariate form of degree at least 3 (in thruth a generalization holds too for the field extension with the root of f, see Alan Baker, Trascendental Number Theory, 1975 for a reference). A complete and detailed proof is uploaded¬†here¬†. In particular, we’ll use the fact that if A,B,C are non zero integers then the equation Ax^3+By^3=C has finitely many integer solutions. Let’s go back to the original problem; to ease the notation, define¬†\mathbb{P}(\mathcal{A}_k) the set of prime numbers p such that there exists some term |a_n+k|>1 for which p \mid a_n+k.

Define b_n=a_n+t and assume \mathbb{P}(\mathcal{A}_t) is finite. We have b_n-a_n=t for all n\ge 1.
Each a_n can be written as a product $latex \prod_{p\in P} p^{\alpha_p}$ for some $latex P \subseteq \mathbb{P}(\mathcal{A}_0)$, and each $latex b_n$ can be written as a product $latex \displaystyle \prod_{q\in Q} q^{\beta_q}$ for some $latex Q \subseteq \mathbb{P}(\mathcal{A}_t)$. For each of the representations, when $latex \alpha_p \equiv a_p \pmod{3}$, write $latex p^{\alpha_p} = p^{a_p}\cdot \left( p^{(\alpha_p Рa_p)/3\right )^3$, so $latex \displaystyle a_n = \left AX^3$, where $latex \displaystyle A = \prod_{p\in P} p^{\a_p}$ and $latex \displaystyle X = \prod_{p\in P} p^{(\alpha_p Рa_p)/3$ (and similarly $latex b_n = BY^3$). The number of possible values for the coefficients $latex A$ and $latex B$ is clearly finite, and so we have a finite number of cubic Diophantine equations $latex BY^3 РAX^3 = t$ (with $latex t\neq 0$ and $A,B$ not perfect cubes), so that for all $latex n\geq 1$ the pair $(b_n,a_n)$ should satisfy one of them. But as we said, such equation has only a finite number of integer solutions, which is in contradiction with the fact there exist infinitely many distinct values for $latex a_n$ (and $latex b_n$). Therefore $latex \mathbb{P}(\mathcal{A}_t)$ must be infinite. []

Notice it is enough to prove it for t>0, since otherwise we had a finite $latex \mathbb{P}(\mathcal{A}_t)$, then denoting $latex \mathcal{B}_0 = (a_n + t)_{n\geq 1}$ we would have a finite $latex \mathbb{P}(\mathcal{B}_0)$, and also a finite $latex \mathbb{P}(\mathcal{B}_{-t} = \mathcal{A})$. So, in all, we should not bother with negative terms.

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)

Solution. A pdf version of the solution can be found here

(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<a^2<a^2b^2+ab^2+1, 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<y<z. 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<m 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<j\le 3 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<m 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}<j<10^{h+1}\}. 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<i<a. 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<a 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<p\}. 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}<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|\}<t 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^zand the conclusion is the same as in part2/case1 again. []

Problem 10- A condition for being a covering system

If 1<k_1<k_2<\ldots<k_n 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<k_1<k_2<k_3<k_4 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<n 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)<h\frac{n(\ln{\ln{n}}+k)^{i-1}}{(i-1)!\ln{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.

[Proof: to be added]