Let $Q$ be a set of prime numbers, not necessarily finite. For a positive integer $n$ consider its prime factorization: define $p(n)$ to be the sum of all the exponents and $q(n)$ to be the sum of the exponents corresponding only to primes in $Q$. A positive integer $n$ is called special if $p(n)+p(n+1)$ and $q(n)+q(n+1)$ are both even integers. Prove that there is a constant $c>0$ independent of the set $Q$ such that for any positive integer $N>100$, the number of special integers in $[1,N]$ is at least $cN$. (For example, if $Q=\{3,7\}$, then $p(42)=3$, $q(42)=2$, $p(63)=3$, $q(63)=3$, $p(2022)=3$, $q(2022)=1$.)
Problem
Source: ISL 2022 N6
Tags: number theory, prime factorization, function, prime numbers, primes
blackmetalmusic
09.07.2023 16:42
any ideas?
TheUltimate123
09.07.2023 17:48
For each positive integer \(N\), consider \[S=\{5040N,\;5040N+70,\;5040N+72,\;5040N+75,\;5040N+80\}.\]There are 4 possible values of \(\{p(n)\bmod2,q(n)\bmod2\}\), so by Pigeonhole, there are distinct \(a\) and \(b\) in \(S\) with \(p(a)\equiv p(b)\pmod2\) and \(q(a)\equiv q(b)\pmod2\). But \(S\) is constructed with the property that for any \(a<b\) in \(S\), \(b-a\) divides both \(a\) and \(b\). Hence \[ p\left( \frac a{b-a} \right)+p\left( \frac b{b-a} \right) =p(a)+p(b)-2p(b-a) \equiv0\pmod2, \]and similarly \[q\left( \frac a{b-a} \right)+q\left( \frac b{b-a} \right)\equiv0\pmod2.\]Since \(\frac a{b-a}\) and \(\frac b{b-a}\) are one apart, each \(N\) generates a valid \(n\). Hence for each \(M\), the first \(M\) choices of \(N\) generate \(M\) different \(n\) up to \(5040N+80\). Each value of \(n\) is counted at most \(\binom52\) times, so any \(c<\frac1{50400}\) works.
Th3Numb3rThr33
10.07.2023 09:58
The choice of two specific sets (all primes and $Q$) is a bit silly. USA TST 2015/2 is (more than) enough to imply that the statement works for any number of any sets of prime numbers.
IAmTheHazard
10.07.2023 22:22
Th3Numb3rThr33 wrote: The choice of two specific sets (all primes and $Q$) is a bit silly. USA TST 2015/2 is (more than) enough to imply that the statement works for any number of any sets of prime numbers. Fun fact: apparently, while developing the mock tests, one MOP staff member suggested making $Q$ be the set of 1 mod 4 primes to troll contestants. Thankfully, this was not done.
62861
10.07.2023 22:42
Pretty disappointing problem to see on the SL if you're familiar with contest literature: CIIM 2017/3 is the same problem, but generalized and only asking to show there are infinitely many special $n$, rather than a positive lower density. Though, if you can show infinitely many special $n$ exist, it's not too difficult to show the positive lower density... well, I say that, but I couldn't figure out how to do it for ages. Maybe it actually isn't that easy. The generality of the CIIM problem arguably makes it easier: the special (ha) case in the SL problem might invite some approaches that actually don't work. TheUltimate123 wrote:
For each positive integer \(N\), consider \[S=\{5040N,\;5040N+70,\;5040N+72,\;5040N+75,\;5040N+80\}.\]There are 4 possible values of \(\{p(n)\bmod2,q(n)\bmod2\}\), so by Pigeonhole, there are distinct \(a\) and \(b\) in \(S\) with \(p(a)\equiv p(b)\pmod2\) and \(q(a)\equiv q(b)\pmod2\).
But \(S\) is constructed with the property that for any \(a<b\) in \(S\), \(b-a\) divides both \(a\) and \(b\). Hence \[ p\left( \frac a{b-a} \right)+p\left( \frac b{b-a} \right) =p(a)+p(b)-2p(b-a) \equiv0\pmod2, \]and similarly \[q\left( \frac a{b-a} \right)+q\left( \frac b{b-a} \right)\equiv0\pmod2.\]Since \(\frac a{b-a}\) and \(\frac b{b-a}\) are one apart, each \(N\) generates a valid \(n\).
Hence for each \(M\), the first \(M\) choices of \(N\) generate \(M\) different \(n\) up to \(5040N+80\). Each value of \(n\) is counted at most \(\binom52\) times, so any \(c<\frac1{50400}\) works.
This is incomplete: you need to show there is one special integer in $[1, 101]$. It's not too hard to do, but it is a trap that exists in this version of the problem and should be acknowledged in a solution. As someone who is extremely lazy, I didn't want to engage with the trap. This also felt like a purely asymptotics problem, so checking this small case felt pointless, and so we decided to modify the problem for the USA training camp in order to remove the trap: Quote: Prove that there exist a positive real $c$ and a positive integer $N_0$ such that the following holds: Let $Q$ be any set of prime numbers. For each positive integer $n$, let $p(n)$ denote the number of primes dividing $n$, counted with multiplicity, and let $q(n)$ denote the number of primes in $Q$ dividing $n$, counted with multiplicity. Then, for any positive integer $N>N_0$, there exist at least $cN$ positive integers $n$ in $\{1, \dots, N\}$ such that $p(n) + p(n+1)$ and $q(n) + q(n+1)$ are both even.
math90
10.07.2023 23:03
CantonMathGuy wrote: you need to show there is one special integer in $[1, 101]$. Here is a solution, essentially the same as the one of TheUltimate123, which also handles this issue.
We will prove that $\boxed{c=8000}$ works.
First observe that the functions $p,q$ satisfy the properties
$$p(ab)=p(a)+p(b),\quad q(ab)=q(a)+q(b)\quad(*)$$for all $a,b\in\mathbb N$. We can now forget about prime sets and use $(*)$ only.
For every positive integer $N$, consider the set
$$X_N\doteqdot\{360N,360N+8,360N+9,360N+10,360N+12\}$$Observe that for every distinct $a,b\in X_N$ one has $a-b\mid a$. Moreover, for every positive integer $n$, there are four possibilities for $(p(n)\mod 2,q(n)\mod 2)$. Hence by pigeonhole principle, there exist $a,b\in X_N$ such that $a<b$, $p(a)\equiv q(a)\pmod 2$ and $p(b)\equiv q(b)\pmod 2$.
Now,
$$p\left(\frac{a}{b-a}\right)+p\left(\frac{b}{b-a}\right)=p(a)+p(b)-2p(b-a)\equiv 0\pmod 2.$$Similarly,
$$q\left(\frac{a}{b-a}\right)+q\left(\frac{b}{b-a}\right)=q(a)+q(b)-2q(b-a)\equiv 0\pmod 2.$$This proves that $\frac{a}{b-a}$ is special. Call this number $f(N)$, and choose $f(N)$ for every positive integer $N$.
Now assume $N>800$. Let $k=\lfloor\frac{N}{400}\rfloor$. Then the numbers $f(1),\ldots,f(k)$ are at most $360k+12<400k\le N$. Each number can be chosen at most $\binom{5}{2}$ times. Moreover, note that
$$k=\lfloor\frac{N}{400}\rfloor\ge\frac{N-400}{400}\ge\frac{\left(\frac{N}{2}\right)}{400}=\frac{N}{800}.$$Hence, the number of special positive integers up to $N$ is at least
$$\frac{k}{\binom{5}{2}}\ge\frac{\left(\frac{N}{800}\right)}{10}=\frac{N}{8000}.$$It remains to show that $c=8000$ works for $100<N\le 800$. To do so, it suffices to prove that there is one special integer in $[1, 101]$. We split into cases:
Case 1. $2\notin Q$. In this Case
$$p(1)+p(2)=q(1)+q(2)=0.$$
Case 2. $3\notin Q$. In this Case $p(3)=q(3)=0$ and $p(4),q(4)$ are even since $4$ is a square. Hence $3$ is special.
Case 3. $2\in Q$ and $3\in Q$. In this Case $p(24)=q(24)=4$ and $p(25),q(25)$ are both even since $25$ is a square. Hence $24$ is special.
This exhausts all cases.
This is how I came up with the solution. It seemed very likely that you don't really need tedious calculations to solve the problem, but using more abstract observations. A useful tool to achieve non-constructive results is by using pigeonhole. Then I recalled part a) of 2009 N2, which used a very similar idea. This way you easily guarantee positive integers $a,b$ such that $a<b$, $p(a)\equiv q(a)\pmod 2$ and $p(b)\equiv q(b)\pmod 2$. But the problem is that $b-a$ is not necessarily $1$. Then I realized that if $a,b$ have a common divisor $d$, then you can divide both $a,b$ by $d$ without changing the result. This way we can achieve $b-a=1$ if and only if $b-a\mid b$. Then I recalled the well-known problem (what is the source BTW?) that for every positive integer $n\ge 2$, there exists a set consisting of $n$ positive integers, such that for every distinct $a,b\in S$ one has $a-b\mid a$. From the solution of the problem and the freedom of construction, the problem is pretty straightforward.
math90
11.07.2023 00:51
TheUltimate123 wrote: For each positive integer \(N\), consider \[S=\{5040N,\;5040N+70,\;5040N+72,\;5040N+75,\;5040N+80\}.\] A small note: $75$ does not divide $5040$. But, it is easy to fix: you can replace $5040N+75$ by $5040N+60$. This way you can also scale $S$ by $2$.
Inconsistent
27.11.2023 23:59
$40, 42, 44, 45, 48$. The rest is left as an exercise.
Kayak
22.12.2023 09:19
In fact any $c < \frac{1}{8}$ would work for sufficiently large $100$ Let's ignore $Q$ for now, and try to compute the constant just for $P$, the set of all prime numbers. Color a number black if $p(n)$ is odd and white otherwise. We can squeeze some structure from the lack of special ness: if there's no $p$-special number in a consecutive $4$ block $[4N, 4N+1, 4N+2, 4N+3]$, then $4N$ and $4N+2$ must have the same color, but then $2N$ is special cuz $p(2N) + p(2N+1) = p(4N) + p(4N+2) - 2 \equiv 0 \mod 2$. This gives us a way to get $c$: given $M$, split $[\frac{M}{2}, M]$ into $\frac{1}{4} \cdot \frac{M}{2}$ consecutive blocks of $4$. Each block either has a $p$-special number, or corresponds uniquely to a $p$-special number in $[1, \frac{M}{2}]$. Either way, we get atleast $\frac{M}{8}$ $p$-special numbers. Good. Now let's re introduce $Q$: life would be simple if $p(n) \equiv q(n) \mod 2$ for all $n$. But life is complicated, so let's call a $n$ bad if $p(n) \equiv q(n)+1 \mod 2$. Now, if almost all numbers (ie, density 1) are bad then we would be good again, cuz then almost all pairs of consecutive numbers would be bad, so for almost all $n$, $p(n) + p(n+1) \equiv q(n) + q(n+1) \mod 2$. Now almost all $p$-special numbers would be special anyway, and the same constant would work. So...what's the density of bad numbers? A basic PIE flavored arguement gives that it's $$ b_Q := \sum_{n = 1}^{\infty} (-1) \prod_{q_i \in Q, i = 1}^{n} \frac{(-1)}{q_i} = 1 - \prod_{q_i \in Q} \sum_{n = 1}^{\infty} \frac{ (-1)^{n+1}}{q_i^{n}} = 1 - \prod_{q_i \in Q} \left( \frac{1}{ q_i \cdot (1 + \frac{1}{q_i})} \right) = 1 - \prod_{q_i \in Q} \left (1 - \frac{1}{q_i+1} \right ) =: 1 - S_Q $$ Observe that if you replace $Q$ with $Q^c$ then the special numbers don't change. Now, $(1-b_Q)(1-b_{Q^c}) = S_Q S_{Q^c} = \prod_{p \in P} (1 - \frac{1}{p+1}) = 0$ (the last equality being well known), so atleast one of $b_Q$ or $b_{Q^c}$ is $1$, as we wanted.
math_comb01
22.03.2024 21:48
Cute! Choose the set $\mathcal{S}$ such that for any $a,b \in \mathcal{S}$ we have $b-a \mid a,b$, obviously by PHP we may choose $a,b$ such that $p(a) \equiv p(b), q(a) \equiv q(b) (\mod 2)$ now the idea is that $p(\frac{a}{b-a})+p(\frac{b}{b-a}) \equiv p(a)+p(b) \equiv 0 (\mod 2)$ and similarly for $q$ and we're done. Remark:(on $\mathcal{S}$ and $c$) There are many possible values of $\mathcal{S}$ one can take (all of them have a central composite number, say $C$), then $c = o(c)$ works. (for instance one may take $\mathcal{S}= \{72k,72k+6,72k+8,72k+9,72k+12\}$ and get $c < 1/2000 $)