$n$ - some natural. We write on the board all such numbers $d$, that $d\leq 1000$ and $d|n+k$ for some $ 1\leq k \leq 1000$. Let $S(n)$ -sum of all written numbers. Prove , that $S(n)<10^6$ and $S(n)>10^6$ has infinitely many solutions.
Problem
Source: St Petersburg Olympiad 2011, Grade 10, P2
Tags: number theory
11.02.2019 22:34
A cleaner statement of the problem would be : Let $n$ be a natural , all positive divisors not bigger than $1000$ of $n+1, n+2 ,\dots n+1000$ are written on a table ( a number can be written more than once). Let $S(n)$ be the sum of all written numbers.Prove , that $S(n)<10^6$ and $S(n)>10^6$ have infinitely many solutions. Here's my solution. For $S(n)>10^6$ , take $n=t\cdot 1000!-1$ where $t$ is some natural. $n+1=t\cdot 1000!$ is divisible by all numbers not larger than $1000$ and sum of its written divisors is $1+2+\dots+1000=\frac{1001\cdot 1000}{2}$ , and all numbers $t\cdot 1000!+k$ for $1\leq k\leq 999$ are divisible by at least $k$. So we have $S(n)>\frac{1000 \cdot 1001}{2}+1+2+\dots 999=\frac{1001\cdot 1000 + 999\cdot 1000}{2}=10^6$ For $S(n)<10^6$ , let $P$ be the product of all primes less than $1000$ and take $n=q\cdot P$ where $q$ is a prime bigger than $1000$ . The times a number $p$ is written is at most $\frac{1000}{p}$ , so sum of all these numbers is at most $1000$ , and since that equality can't hold because prime squares aren't written,we get that $S(n)<1000\cdot 1000=10^6$. $\blacksquare$
24.01.2022 10:09
For second case, enough to pick n = t * 1000!. Any divisor d (1<=d<=1000) is written indeed at most [1000/d] times. [1000/d] < 1000/d when d doesnt divide 1000.