Show that, for every positive integer $n$, there exist $n$ consecutive positive integers such that none is divisible by the sum of its digits. (Alternative Formulation: Call a number good if it's not divisible by the sum of its digits. Show that for every positive integer $n$ there are $n$ consecutive good numbers.)
Problem
Source:
Tags: logarithms, floor function, number theory proposed, number theory
Vo Duc Dien
04.10.2012 21:45
Let $n = 18$. Compare this problem with problem $2$ of Tournament of Towns $1984$: "Prove that among $18$ consecutive three digit numbers there must be at least one which is divisible by the sum of its digits."
hvaz
05.10.2012 03:45
We will prove the assertion by inducting on $n$. The basis is $n=1$, which is straightforward. Just consider the number $11$.
Our hypothesis is that, $\forall k < n+1$, there exist a sequence $a_1, a_2, \ldots, a_k$ of consecutive integers (yeah, $a_{k+1} = a_k + 1$) satisfying the conditions.
We will now work on the inductive step:
From the hypothesis, there exist consecutive integers $a_1, a_2, \ldots, a_n$ satisfying the conditions. Let $P = s(a_1) \times s(a_2) \times \ldots \times s(a_n) \times s(a_{n+1})$, where $a_{n+1} = a_n + 1$, and $s(x)$ is the sum of the digits of $x$. Also, let $Q = a_1 \times a_2 \times \ldots \times a_n$.
Now, consider the sequence $b_k = a_k + D$, where $D = 10^{e_1} + 10^{e_2} + \ldots + 10^{e_t}$. We choose the $e_i 's$ to be very very big, in such a way that this new sequence is also of consecutive integers. Also, consider $t = PQx$, where $x$ will be defined forward.
Choose the $e_i 's$ in such a way that $10^{e_i} \equiv r \mod{P}$, $\forall i$, and for some random $r$. (we will prove on the end that we can choose infinitely many $e_i's$ satisfying this condition).
Notice that $s(b_k) = t + s(a_k)$. So, if $s(b_k) \mid b_k$, we have that $t + s(a_k) \mid D + a_k$ $\Leftrightarrow$ $PQx + s(a_k) \mid D + a_k$ $\Rightarrow$ $s(a_k) \mid D + a_k$, once $s(a_k) \mid PQx$. But then:
$0 \equiv D + a_k \equiv PQxr + a_k \equiv a_k(\frac{PQxr}{a_k} + 1) \mod{s(a_k)}$.
However, $\frac{Q}{a_k}$ is an integer, and then $\frac{Qxr}{a_k}$ is an integer. We also have that $s(a_k) \mid P$, and therefore
$\frac{PQxr}{a_k} \equiv 0 \mod{s(a_k)}$ $\Leftrightarrow$ $0 \equiv a_k(\frac{PQxr}{a_k} + 1) \equiv a_k \mod{s(a_k)}$ $\Rightarrow$ $s(a_k) \mid a_k$, contradiction!
So, for all $1 \le k \le n$, we have that $s(b_k) \nmid b_k$
We now prove that it's possible to find an $x$ such that $s(b_{n+1}) \nmid b_{n+1}$.
Suppose wlog that $s(a_{n+1}) \mid a_{n+1}$, otherwise we have a new term in our sequence by the reasons we have just shown. Suppose as well that $s(b_{n+1}) \mid b_{n+1}$.
We have $s(b_{n+1}) = t + s(a_{n+1})$, and therefore $t + s(a_{n+1}) \mid b_{n+1} = D + a_{n+1}$ $(*)$
Notice that, as $s(a_{n+1}) \mid t$, we have $s(a_{n+1}) \mid D + a_{n+1}$ $\Rightarrow$ $\frac{D}{s(a_{n+1})}$ is an integer. Write $a_{n+1} = k \times s(a_{n+1})$ and pay attention to $(*)$ again:
$t + s(a_{n+1}) \mid D + a_{n+1}$ $\Leftrightarrow$ $PQx + s(a_{n+1}) \mid D + a_{n+1}$ $\Leftrightarrow$
$\frac{PQx}{s(a_{n+1})} + 1 \mid \frac{D}{s(a_{n+1})} + k$.
Now, by Dirichilet's Theorem, there are infinitely many $w's$ such that $hw + 1$ is prime, for fixed $h$. In particular, there are infinitely many $x$ such that $\frac{PQx}{s(a_{n+1})} + 1$ is prime. Choose a really big $x$, and let $g = \frac{PQx}{s(a_{n+1})} + 1$, $g$ prime.
Now, let $l = 10^{\beta} > k$, and choose the $e_i's$ s.t. $10^{e_i} \equiv l \mod{g}$, $\forall i$(it's clear that for big $x$, $l < x$, and therefore $10^{\beta} = l$ is always a remainder $\mod{g}$. Considering the set of numbers of the form $ord^{10}_{g} \times y + \beta$, we obtain infinitely many possible $e_i's$ satisfying this condition).
We have that:
$0 \equiv \frac{D}{s(a_{n+1})} + k \equiv \frac{PQxl}{s(a_{n+1})} + k \mod{g}$ $(**)$.
We also have $PQx \equiv -s(a_{n+1})$. Replacing in $(**)$, we obtain
$0 \equiv \frac{PQxl}{s(a_{n+1})} + k \equiv \frac{-l \times s(a_{n+1})}{s(a_{n+1})} + k \mod{g}$ $\Leftrightarrow$ $k \equiv l \mod{g}$
But for really big $g$, $l = 10^{\beta}$ is always a remainder, because $g > 10^{\beta} = l$, while $k$ keeps constant, and less than $x$, for big $x$. We also have $g > k$. Therefore, for big $l$ and big $g$, $k \equiv l \mod{g}$ implies $k = l$. But we chose $\beta$ in such a way that $l = 10^{\beta} > k$, a contradiction.
So, we can find $x$ such that we have a new term, as desired. This completes the inductive step.
Observation: We chose the $e_i's$ in such a way that $10^{e_i} \equiv r \mod P$, $\forall$ $i$ and $10^{e_i} \equiv l \mod g$, $\forall$ $i$, where $10^{\beta} = l$ was especially chosen. This is possible because, considering the infinit set $S = \{ ord^{10}_{g} \times y + \beta,$ $y \ge 1$ $\}$, there exist infinitely many $w \in S$ such that $10^{w} \equiv r \mod{P}$, for some residuo $r$, and that's what we need.
vsalazar
06.10.2012 15:12
We are going to find a number $k$ of the form $\frac{10^a-1}{9}$ such that if $b$ is the number of digits of $n$ then the numbers $10^bk+i$ with $i\in{1,2,\dots n}$ are not divisible by the sum of their digits. Let $p_1,p_2,\dots,p_n$ be primes greater than $n$ and greater than $3$ such that $(p_1p_2\dots p_n,\phi(p_1p_2\dots p_n)=1$ and they exist because we choose each $p_k$ greater than $\phi(p_1p_2\dots p_{k-1})$ and of the form $p_1p_2\dots p_{k-1}X-1$ (it exist because of Dirichlet's theorem) and in that way $(p_1p_2\dots p_{k-1}, \phi(p_k))=(\phi(p_1p_2\dots p_{k-1}),p_k)=1$ (*). Now we find with CRT, which we are allowed to do because of (*), an $a$ such that $a\equiv -s(i) \mod{p_i}$ and $\phi(p_1p_2\dots p_n)|a$ then $p_1p_2\dots p_n|k$ but since $p_i>n\geq i$ then $p_i\not| i$ then $p_i\not 10^bk+i$ but $p_i|a+s(i)=s(k)+s(i)=s(10^bk+i)$ then $s(10^bk+i)\not |10^bk+i$
SebP
08.10.2012 07:51
This problem turns out to be mine. Here are a few solutions/remarks.
The most natural solution to this problem is probably constructive, using some repunit manipulations or things of the same spirit, tweaked to avoid the particular obstacles of the problem. Luckily, constructive solutions turn out to be less obvious than one might expect; I suppose this is this reason why this problem is problem 6 and not less. However, with some experience and inspiration this problem solves fast, so I think it might be too easy for problem 6. Anyway, these are aspects which exceed the problem and are more related to the exam context, so lets leave them aside.
For the first solution, which in my opinion captures the escence of the problem and I particularly love, consider the following (non formal, heuristic) argument: Suppose I were to give you $k$ consecutive positive integers. How many distinct digital sums would you expect there to be among them? A simple heuristic reasoning should convince you that the answer is about $\log k$. This motivates the following approach to the problem: take $k$ consecutive positive integers with large enough digital sums (say, larger than $k$), so that at most one of these numbers is divisible by each posible digital sum. Since there are only $\log k$ digital sums, if we partition these $n$ numbers into more than $\log k$ blocks of consecutive integers, each containing about $\frac{k}{\log k}$ numbers, there will be some block in which no number is a multiple of the sum of its digits. Since $\frac{k}{\log k}$ diverges, it suffices to choose large enough $k$ so that $\frac{k}{\log k}$ is larger than $n$, and the result will follow. Now it is only a matter of writing out this idea into an actual solution. You might obtain:
First Solution. For a positive integer $m$, consider the following $10^m$ consecutive positive integers:
${A_0}=11\dots1100\dots00$,
${A_1}=11\dots1100\dots01$,
${A_2}=11\dots1100\dots02$,
$\dots$
$\dots$
${A_{10^m-1}}=11\dots1199\dots99$
where each of these numbers begin with $10^m$ digits $1$ and their remaining $m$ digits are a positive integer between $0$ and $10^{m}-1$ inclusive. More precisely,
$A_k=\dfrac{(10^{10^m}-1)}{9} {10^m}+k,0\leq k\leq 10^m-1.$
For each of these numbers $A_k$, the sum of its digits $S(A_k)$ satisfies $10^m\leq S(A_k)\leq10^{m}+9m$. Then, since $1\leq |A_i-A_j|\leq 10^{m}-1$ for each $i\neq j$, it follows that $S(A_k)$ divides at most one of the numbers $A_0,A_1,\dots,A_{10^{m-1}}$. Since the set $\{S(A_0 ),S(A_1 ),\dots,S(A_{10^{m-1}})\}$ contains at most $9m+1$ elements, then at most $9m+1$ of the numbers $A_0,A_1,\dots,A_{10^{m-1}}$ are divisible by the sum of their digits. The rest is clear: just group these numbers into $9m+2$ blocks of $\left\lfloor \frac{10^m}{9m+2}\right\rfloor$ consecutive integers, from smallest to the largest. Some numbers may be left out, but we will never be missing numbers, because $(9m+2)\left\lfloor \frac{10^m}{9m+2}\right\rfloor\leq 10^m$. Some of these sets is such that none of its elements is disible by the sum of its digits, thus we obtain $\left\lfloor \frac{10^m}{9m+2}\right\rfloor$ consecutive positive integers, none of them divisible by the sum of their digits. For each $n$ it suffices to take large enough $m$ so that $\left\lfloor \frac{10^m}{9m+2}\right\rfloor\ge n$, and the result follows.
For completness, here is a second, constructive solution (probably similar to what most people might have done):
Second Solution. We give a constructive solution. The idea will be as follows: given $n \in \mathbb N$, we choose large distinct primes $p_1,p_2,\dots,p_n$ and a number $K$ divisible by each of these primes and such that each of the numbers $K00\dots0+i, \ 1\le i \le n$ has the sum of its digits divisible by $p_i$ respectively. In such case, these numbers will not be divisible by the sums of their digits because if not we would have some $i$ for which $p_i|K00\dots0+i\Rightarrow p_i|i$ (since $p_i|K$), absurd.
So lets find such $K$. Let $P=p_1p_2\dots p_n$ and consider $A=100\dots0100\dots0100\dots0$ the number which has $P-10$ digits one in the positions $10^{j\phi (P)}, \ 1\le j\le P-10$. More precisely,
$A=10^{\phi (P)}\dfrac{10^{(P-10)\phi (P)}-1}{10^{\phi (P)}-1}$.
Denote by $S(m)$ the sum of the digits of $m$. We have that $S(A)=P-10$ and $A\equiv -10 $ (mod $P$). Then, if we consider the number $B=A+10$, this number satisfies $S(B)=P-9$ and $B=A+10\equiv 0 $ (mod $P$). Let $C=BB\dots B$ be the result of concatenating copies of $B$ a total of $t$ times for some $t\in \mathbb N$. Lets look at the numbers $10^x C+i, \ 1\le i \le n$ for large $x$. The sum of their digits is $S(10^x C+i)=S(C)+S(i)=t(P-9)+S(i)$. By the Chinese Remainder Theorem, the system of congruences
$t(P-9)+S(i)\equiv 0$ (mod $p_i$), $1\le i \le n$
has solution $t$ (note that $1\le S(i)\le i<p_i$ for each $i$ and that $P-9$ and $p_i$ are coprime). For this value of $t$, we claim that the numbers $10^x C+i, \ 1\le i \le n$ satisfy what we wanted (in which case our sought $K$ would be $C$). This is so, beacause for each $i$, the sum of the digits of $10^x C+i$ is divisible by $p_i$ as a consequence of the above system of conguences. Also, $C$ is divisible by $p_i$ because $B$ was divisible by $p_i$. Thus, if some of these numbers were divisible by the sum of their digits we would have $p_i|i$, absurd. Then, these $n$ numbers have the desired property.
Whatever the solution, I think part of what makes this problem interesting is that what is being asked to prove is unusual or unexpected. One is used to being asked for numbers which are divisible by the sum of their digits. But how good are we at doing the oposite, finding those which we doom as the trivially un-interesating case? (in fact, note that the first solution is not constructive at all, so we actually never find them in that case )
Emerson_Soriano
06.04.2015 02:10
La demostración lo haré por inducción. En efecto, para cada entero positivo $n$, sea $S(n)$ la suma de sus respectivos dígitos. Notemos que para $n=1$, el ejemplo es $14$, y por si fuera poco, daremos el ejemplo para $n=2$, que es: $14, 15$. Supongamos que existen $n$ enteros positivos consecutivos, con $n \geq 2$: $x+1, x+2, ... , x+n$ tales que ninguno es divisible por la suma de sus dígitos. Para cada $1 \leq i \leq n$, sea $t_i$ el producto de todos los factores primos diferentes de $2$ y $5$ del número $S(x+i)$, en caso que no tuviera consideremos como $t_i=1$ y $\phi(1)=1$. Sea $k=r \times \prod_{i=1}^{n}S(x+i) \times \prod_{i=1}^{n} \phi(t_i)$, donde $r$ es suficientemente grande. Note que para un entero positivo $m$ suficientemente grande, y para cada $1 \leq i \leq n$, se cumple que $9k+S(x+i)$ no puede dividir al número $(10^k-1) \times 10^m+(x+i)$ y lo demostraremos por el absurdo. En efecto, supongamos que es cierto, note que $S(x+i)$ divide a $(10^k-1) \times 10^m$, pues $V_2(S(x+i)) \leq V_2(10^m)$, $V_5(S(x+i)) \leq V_5(10^m)$ y $t_i \mid 10^k-1$, luego como $S(x+i) \mid 9k+S(x+i)$ y $S(x+i) \mid (10^k-1) \times 10^m$, se deduce que $S(x+i) \mid x+i$, lo cual es una contradicción. Observe que este resultado realmente no depende de $m$, solo importa que $m$ sea suficientemente grande. Por otro lado, tomemos el mismo $m$ de arriba. Note que ambos números: $A=(10^k-1) \times 10^m + x+n+1$ y B=$(10^k-1) \times 10^{m+1}+x+n+1$ no pueden ser simultáneamente divisibles por $9k+S(x+n+1)$, pues si eso ocurre, entonces $9k+x+n+1\mid 10A-B$, es decir, $9k+x+n+1\mid 9(x+n+1)$, pero esto es imposible, pues $k$ es suficientemente grande. Luego, podemos asegurar que existe un entero $b$ tal que $b=m$ o $b=m+1$ tal que para cada $1 \leq i \leq n+1$ se cumple que $9k+S(x+i)$ no divide a $(10^k-1) \times 10^b+x+i$, quedando completa la inducción
mathocean97
19.04.2015 18:20
If we want to avoid any Dirichlet-ish arguments, you can do the below: Choose $p_1, p_2, \dots, p_n$ to be very large primes, and choose a $k$ such that $p_i | k+i.$ (Do this using CRT). Next, find an $x$ such that $p_i | x +s(k+i)$ for all $i$. (Once again, CRT) In fact, we can find arbitrarily large $x$. I think $x > 2P$ should be enough for what follows. Let $P = p_1p_2\dots p_n$ and let $S$ be the set of powers of $10$ $\pmod{P}$. I claim that $|S+S+ \dots + S| = P.$ $S$ is added $x$ times. In other words, $S+S+\dots +S$ can take any value $\pmod{P}$. The proof is very easy once you notice that $1, 10 \in S$. Say that in the sum, $1$ is used $a$ times, and $10$ is used $b$ times. Then we need to solve the equation \[ a+b = x \] \[ a+10b \equiv y \pmod{P} \] for any $y$, $a, b$ positive integers. It is easy to check that this always gives a solution for $a, b$. Given the above lemma, find a set $T$ of very large powers of 10 such that $|T| = x$ and for any $p_i$, $p_i \not| k+i+\sum_{t \in T}{10^t}.$ This is possible because as explained above, $S+S+\dots + S$ covers everything. This construction finishes the problem.
blackbluecar
21.08.2022 01:28
We call a positive integer soba if it is not divisible by its sum of digits. Let $p_1,p_2, \ldots ,p_n$ be arbitrarily large distinct primes, $s$ be the sum of digits function, and $10^k>n$. By crt, there exists a positive integer $X$ for which $X+s(i)+1$ is divisible by $p_i$ for all positive integers $i \leq n$. Thus, if we set set $s(Y)=X$ then $s(10^k \cdot Y+i)+1$ is divisible by $p_i$. Thus, let $a_i=10^k \cdot Y+i$. We claim that there exists a positive integer $N>n$ for which $10^N+a_i$ is soba for all $i$. Indeed, notice that $s(10^j+a_i)=s(a_i)+1$. Thus, if $s(10^\alpha+a_i)=s(a_i)+1$ divides $10^\alpha+a_i$ and $s(10^\beta+a_i)=s(a_i)+1$ divides $10^\beta+a_i$, then $s(a_i)+1$ divides $(10^\alpha+a_i)-(10^\beta+a_i)=10^\alpha-10^\beta$. Which implies that $\alpha-\beta \geq \text{ord}_{p_i}(10) \geq \log(p_i)$ which is arbitrarily large. Thus, by $p_i$'s being sufficiently large, they cannot cover every possible of $N$. So there exists a choice of $N$ where all of the numbers are soba. $\blacksquare$
Bigtaitus
03.09.2023 03:32
Take $p_1,p_2,...p_n$ be very big primes such that $(p_i,p_j-1)=1$ for any $i,j,$ which is obviously possible. Now, we choose some $s(A)$ to satify that $p_i\mid s(A)+i$ for every $i\in\{1,2,\dots, n\}.$ Our objective is to find some $A$ multiple of $p_1\cdots p_n$ with suck $s(A).$ If we can obtain this, we'll be done, as we can the choose a very big $a$ and consider $10^aA.$ In that case, we get that for $j=s(i),$ then $$p_j\mid s(10^aA+i)\mid 10^aA+i\implies p_j\mid i,$$but this will be a contradiction if we choose all $p's$ to be as big as we want. Now the desired $s(A)$ satisfies a certain congruence modulo $p_1\cdots p_n.$ In order to end the problem we will show that we can choose some $B$ multiple of $p_1\cdots p_n$ such that $s(B)$ obtains any value we want modulo $p_1\cdot p_k.$ Assume the contrary, that is, we $s(np_1\cdot p_n)$ obtains finitely many values modulo $p_1\cdots p_n.$ Now, this values are trivially closed under addition, and thus, applying Bezout, we get that all these values must be divisible by some $p_i.$ We will show this is a contradiction, which will end the problem. That is because we can choose number $10^{\prod (p_i-1)}-1.$ By Fermat this number is divisible by all $p_i's,$ but at the same time is a number with $\prod (p_i-1)$ $9's.$ Thus $s(10^{\prod (p_i-1)}-1)=9\cdot \prod (p_i-1),$ but as we chose that $(p_i,p_j-1)=1$ for any $i,j,$ this value is not divisible by any of the $p_i's,$ ending the problem.
IAmTheHazard
25.09.2023 17:09
Let $s(n)$ denote the sum of the decimal digits of $n$. We begin with the following. Claim: Let $e$ be a positive integer. Then for any $1 \leq n \leq 10^e$, $s(n(10^e-1))=9e$. Proof: See here. Let $P(x)=(x+1)\ldots(x+n)$. Pick $k \gg n$ massive so that $P(10^k-1) \ll 10^{\frac{10^k-1}{9}}-1$ and define $N=(10^{\frac{10^k-1}{9}}-1)P(10^k-1)$. Apply the claim to get that $s(N)=10^k-1$. Then pick some large enough $\ell$ so that the decimal digits of $10^\ell N+i$ don't overlap for $1 \leq i \leq n$ and consider the integers $10^\ell N+1,\ldots,10^\ell N+n$. The digit sum of any of these integers is between $(10^k-1)+1$ and $(10^k-1)+n$, and thus divides $P(10^k-1)$ and therefore $10^\ell N$, so if some $1 \leq i \leq n$ has $s(10^\ell N+i) \mid 10^\ell N+i$, then $s(10^\ell N+i) \mid i$. But since we picked $k \gg n$, the LHS is much larger than $10^n-1$ and we get a size contradiction. Therefore we are done. $\blacksquare$
thdnder
04.12.2023 21:00
Let $s(n)$ be the sum of its digits. Let $a$ be an arbitrary positive integer. Let $p_1$ be a prime such that $p_1 > a + n$ and define $(p_n)_{n >= 1}$ such a way: (a): Every $p_i$ is prime. (b): $p_i - 1$ is relatively prime to $p_1p_2 \cdots p_{i-1}$. By Dirichlet's theorem, there exist sequence $(p_n)_{n >= 1}$ that satisfies $(a)$ and $(b)$. Now by CRT, there exists $t \equiv -s(a + i) (p_i)$, for $1 \le i \le n$ and $(p_1 - 1)(p_2 - 1) \cdots (p_n - 1) \mid t$. Then $s((a + i) \cdot 10^t + \frac{10^t - 1}{10 - 1}) = s(a + i) + t$ and since $p_i \mid s(a + i) + t$, $(a + i) \cdot 10^t + \frac{10^t - 1}{10 - 1} \equiv (a + i) (p_i)$, therefore $(a + i) \cdot 10^t + \frac{10^t - 1}{10 - 1}$ isn't divisible by $s(a + i) + t$, for $1 \le i \le n$. Thus we're done. $\blacksquare$
YaoAOPS
12.01.2025 19:46
Fix $n$. Call a number smooth if it is divisible by a prime less $9n + 1$. Claim: There exists a $c$ such that at most $c \sqrt{N}$ of the numbers less than $N$ are smooth. Proof. Let $t$ be the number of primes less than $9n + 1$. Each smooth number can be represented as $a \cdot b^2$ for one of $2^t$ choices of $a$. This means that we can take $c = (1 + \varepsilon)2^t$ to get the result. $\blacksquare$ As such, this implies there exist an interval $I = [N, N+n]$ of non smooth numbers with $N-1 \ge n+1$. Since the sum of digits of a number are less than a number and greater than $0$, if we fix some $10^N \mid k$ such that the digit sum of $k$ is $N-1$, then the sum of the digits of $k + i$ for $1 \le i \le n$ are non smooth. We now choose $k$ to get the desired result. For each $i$, let $p_i > 9n + 1$ be a prime dividing the digit sum of $k + i$. We initially start off $k$ as $\sum_{i=1}^{N-1} 10^{(i+N)O}$ where $O$ is the lowest common multiple of the orders of $10 \pmod{p_i}$. We can then consider replacing $10^{(i+N)O}$ with $10^{(i+N)O + 1}$, which increase the value of each $k + i \pmod{p_i}$ by $9$. If we consider the result of doings this $n$ times, we get $n+1$ candidates $k_0, k_1, \dots, k_n$ which each have distinct residues $k_j + i \pmod p_i$. Then since at most one candidate is $0 \pmod{p_i}$, one of the candidates has all $k + i \pmod{p_i}$ be nonzero, which wins.