Olympiad problems

Fractal Edition 1, P4

Let $ P(x) $ be a polynomial with natural coefficients. We denote by $ d(n) $ the number of positive divisors of the natural number $ n $, and by $ \sigma(n) $, the sum of these divisors. The sequence $ a_n $ is defined as follows: \[ a_{n+1} \in \left\{ \begin{array}{ll} \sigma(P(d(a_n))) \\ d(P(\sigma(a_n))) \end{array} \right. \] That is, $ a_{n+1} $ is one of the two terms above. Show that there exists a constant $ C $, depending on $ a_1 $ and $ P(x) $, such that for all $ i $, $ a_i < C $; in other words, show that the sequence $ a_n $ is bounded.

2020 Brazil National Olympiad, 2

Tags: fibonacci , analytic number theory , number theory

For a positive integer $a$, define $F_1 ^{(a)}=1$, $F_2 ^{(a)}=a$ and for $n>2$, $F_n ^{(a)}=F_{n-1} ^{(a)}+F_{n-2} ^{(a)}$. A positive integer is [i]fibonatic[/i] when it is equal to $F_n ^{(a)}$ for a positive integer $a$ and $n>3$. Prove that there are infintely many not [i]fibonatic[/i] integers.

2003 Kurschak Competition, 3

Tags: phi function , analytic number theory , expected value , probabilistic method , summation , number theory , inequalities

Prove that the following inequality holds with the exception of finitely many positive integers $n$: \[\sum_{i=1}^n\sum_{j=1}^n gcd(i,j)>4n^2.\]

KoMaL A Problems 2022/2023, A.838

Tags: number theory , analytic number theory

Sets $X\subset \mathbb{Z}^{+}$ and $Y\subset \mathbb{Z}^{+}$ are called [i]comradely[/i], if every positive integer $n$ can be written as $n=xy$ for some $x\in X$ and $y\in Y$. Let $X(n)$ and $Y(n)$ denote the number of elements of $X$ and $Y$, respectively, among the first $n$ positive integers. Let $f\colon \mathbb{Z}^{+}\to \mathbb{R}^{+}$ be an arbitrary function that goes to infinity. Prove that one can find comradely sets $X$ and $Y$ such that $\dfrac{X(n)}{n}$ and $\dfrac{Y(n)}{n}$ goes to $0$, and for all $\varepsilon>0$ exists $n \in \mathbb{Z}^+$ such that \[\frac{\min\big\{X(n), Y(n)\big\}}{f(n)}<\varepsilon. \]

KoMaL A Problems 2023/2024, A. 863

Tags: number theory , analytic number theory

Let $n\ge 2$ be a given integer. Find the greatest value of $N$, for which the following is true: there are infinitely many ways to find $N$ consecutive integers such that none of them has a divisor greater than $1$ that is a perfect $n^{\mathrm{th}}$ power. [i]Proposed by Péter Pál Pach, Budapest[/i]

2015 USA TSTST, 5

Tags: relatively prime , number theory , analytic number theory , function

Let $\varphi(n)$ denote the number of positive integers less than $n$ that are relatively prime to $n$. Prove that there exists a positive integer $m$ for which the equation $\varphi(n)=m$ has at least $2015$ solutions in $n$. [i]Proposed by Iurie Boreico[/i]

2015 China Team Selection Test, 6

Tags: analytic number theory , squarefree , number theory

Prove that there exist infinitely many integers $n$ such that $n^2+1$ is squarefree.

2014 Olympic Revenge, 4

Tags: number theory , real analysis , analytic number theory , limit

Let $a>1$ be a positive integer and $f\in \mathbb{Z}[x]$ with positive leading coefficient. Let $S$ be the set of integers $n$ such that \[n \mid a^{f(n)}-1.\] Prove that $S$ has density $0$; that is, prove that $\lim_{n\rightarrow \infty} \frac{|S\cap \{1,...,n\}|}{n}=0$.

2014 Contests, 4

Tags: limit , real analysis , analytic number theory , number theory

Let $a>1$ be a positive integer and $f\in \mathbb{Z}[x]$ with positive leading coefficient. Let $S$ be the set of integers $n$ such that \[n \mid a^{f(n)}-1.\] Prove that $S$ has density $0$; that is, prove that $\lim_{n\rightarrow \infty} \frac{|S\cap \{1,...,n\}|}{n}=0$.

2016 Miklós Schweitzer, 1

Tags: number theory , analytic number theory , complex number

For which complex numbers $\alpha$ does there exist a completely multiplicative, complex-valued arithmetic function $f$ such that \[ \sum_{n<x}f(n)=\alpha x+O(1)\,\,? \]

2015 China Team Selection Test, 6

Tags: analytic number theory , squarefree , number theory

Prove that there exist infinitely many integers $n$ such that $n^2+1$ is squarefree.

2024 VJIMC, 4

Tags: number theory , analytic number theory , divisibility

Let $p>2$ be a prime and let \[\mathcal{A}=\{n \in \mathbb{N}: 2p \mid n \text{ and } p^2\nmid n \text{ and } n \mid 3^n-1\}.\] Prove that \[\limsup_{k \to \infty} \frac{\vert \mathcal{A} \cap [1,k]\vert}{k} \le \frac{2\log 3}{p\log p}.\]

2024 Romanian Master of Mathematics, 6

Tags: algebra , polynomial , number theory , analytic number theory , complex roots

A polynomial $P$ with integer coefficients is [i]square-free[/i] if it is not expressible in the form $P = Q^2R$, where $Q$ and $R$ are polynomials with integer coefficients and $Q$ is not constant. For a positive integer $n$, let $P_n$ be the set of polynomials of the form $$1 + a_1x + a_2x^2 + \cdots + a_nx^n$$ with $a_1,a_2,\ldots, a_n \in \{0,1\}$. Prove that there exists an integer $N$ such that for all integers $n \geq N$, more than $99\%$ of the polynomials in $P_n$ are square-free. [i]Navid Safaei, Iran[/i]

STEMS 2021 Math Cat C, Q3

Tags: analytic number theory

Let $p \in \mathbb{N} \setminus \{0, 1\}$ be a fixed positive integer. Prove that for every $K > 0$, there exist infinitely many $n$ and $N$ such that there are atleast $\dfrac{KN}{\log(N)}$ primes among the following $N$ numbers given by \[n + 1, n + 2^p, n + 3^p, \cdots, n + N^p.\] [i]Proposed by Bimit Mandal[/i]

2020 Spain Mathematical Olympiad, 6

Tags: number theory , difference of squares , analytic number theory

Let $S$ be a finite set of integers. We define $d_2(S)$ and $d_3(S)$ as: $\bullet$ $d_2(S)$ is the number of elements $a \in S$ such that there exist $x, y \in \mathbb{Z}$ such that $x^2-y^2 = a$ $\bullet$ $d_3(S)$ is the number of elements $a \in S$ such that there exist $x, y \in \mathbb{Z}$ such that $x^3-y^3 = a$ (a) Let $m$ be an integer and $S = \{m, m+1, \ldots, m+2019\}$. Prove: $$d_2(S) > \frac{13}{7} d_3(S)$$ (b) Let $S_n = \{1, 2, \ldots, n\}$ with $n$ a positive integer. Prove that there exists a $N$ so that for all $n > N$: $$ d_2(S_n) > 4 \cdot d_3(S_n) $$

2011 Tuymaada Olympiad, 4

Tags: polynomial , algebra , quadratic , analytic number theory , integer sequence , integer polynomial

Let $P(n)$ be a quadratic trinomial with integer coefficients. For each positive integer $n$, the number $P(n)$ has a proper divisor $d_n$, i.e., $1<d_n<P(n)$, such that the sequence $d_1,d_2,d_3,\ldots$ is increasing. Prove that either $P(n)$ is the product of two linear polynomials with integer coefficients or all the values of $P(n)$, for positive integers $n$, are divisible by the same integer $m>1$.