MathDB
Prime factorization functions have even sum

Source: ISL 2022 N6

July 9, 2023
number theoryprime factorizationfunctionprime numbersprimes

Problem Statement

Let QQ be a set of prime numbers, not necessarily finite. For a positive integer nn consider its prime factorization: define p(n)p(n) to be the sum of all the exponents and q(n)q(n) to be the sum of the exponents corresponding only to primes in QQ. A positive integer nn is called special if p(n)+p(n+1)p(n)+p(n+1) and q(n)+q(n+1)q(n)+q(n+1) are both even integers. Prove that there is a constant c>0c>0 independent of the set QQ such that for any positive integer N>100N>100, the number of special integers in [1,N][1,N] is at least cNcN.
(For example, if Q={3,7}Q=\{3,7\}, then p(42)=3p(42)=3, q(42)=2q(42)=2, p(63)=3p(63)=3, q(63)=3q(63)=3, p(2022)=3p(2022)=3, q(2022)=1q(2022)=1.)
Back to ProblemsView on AoPS