Found problems: 16
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]
Prove that there exist infinitely many integers $n$ such that $n^2+1$ is squarefree.
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]
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.
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}.\]
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.\]
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]
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)\,\,?
\]
Prove that there exist infinitely many integers $n$ such that $n^2+1$ is squarefree.
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$.
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.
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]
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. \]
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) $$
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$.
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$.