1
$\begingroup$

I know that every third number is divisible by $3$ and hence, sum of its digits is divisible by $3$. Same holds for $9$ also. But how do we generalise it? We know that the divisibility condition for higher powers of $3$ is not about the sum of digits. How can we find $n$ such that in a group of $n$ consecutive positive integers, there is a number such that the sum of its digits is divisible by $27$ (or $81,$ say)? Does it exist? Please prove or disprove.

$\endgroup$
  • 1
    $\begingroup$ Do you understand what makes things work for 3 and 9. Do you have any thoughts about connecting that idea with 27 or 81? Also, since this problem is a bit open ended, it reads like a contest or challenge problem - could you provide the source so we know it's not an active contest/application problem? $\endgroup$ – Mark S. Jul 27 at 11:37
  • $\begingroup$ math.stackexchange.com/questions/328562/… $\endgroup$ – lab bhattacharjee Jul 27 at 11:57
  • $\begingroup$ No, I was just thinking about it, related to no contest. I know the idea for $3$ and $9$, we write number as $n_0+10n_1+100n_2+...$ and then take out the sum of the digits, remaining sum turns out to be divisible by $9$, making things easy. $\endgroup$ – Martund Jul 27 at 11:59
  • $\begingroup$ This is another question by me math.stackexchange.com/questions/3305361/… $\endgroup$ – Martund Jul 27 at 12:02
  • $\begingroup$ polynomial remainder theorem. $\endgroup$ – Roddy MacPhee Jul 27 at 12:53
2
$\begingroup$

New answer instead of editing the - already accepted - answer because the argument is significantly different (and much simpler).


Let $Q(x)$ denote the digit sum of $x$.

Let $r\ge 1$. Then $n=10^r-1=\underbrace{99\ldots 9}_r$ is the smallest $n$ such that among any $n$ consecutive positive integers, at least one has digit sum a multiple of $9r$.

That no smaller $n$ works, is immediately clear because in $1,2,3,\ldots, 10^r-2$, all digit sums are $>0$ and $<9r$.

Remains to show that in any sequence of $n$ consecutive integers, a digit sum divisible by $9r$ occurs. This is well-known for $r=1$. For $r>1$, consider $n$ consecutive positive integers $$a,a+1,\ldots, a+n. $$ Among the first $9\cdot 10^{r-1}=n-(10^{r-1}-1)$ terms, one is a multiple of $9\cdot 10^{r-1}$. Say, $9\cdot 10^{r-1}\mid a+k=:b$ with $0\le k<9\cdot 10^{r-1}$. Then $Q(b)$ is a multiple of $9$, and as the lower $r-1$ digits of $b$ are zero, we have $Q(b+i)=Q(b)+Q(i)$ for $0\le i<10^{r-1}$ and hence $$Q( b+10^j-1)=Q(b)+9j,\qquad 0\le j\le r-1.$$ (Note that $k+10^{r-1}-1<10^r-1$, so these terms are really all in our given sequence). It follows that $9r$ divides one of these $Q(b+10^j-1)$.

$\endgroup$
1
$\begingroup$

Note that the natural numbers $\{1,2,\cdots, 999\}$ contain integers for which the sum of the digits is any specified value $\pmod {27}$

Considering the multiples of $1000$ we see that each block of $1000$ integers contains one which ends in three $0's$.

Starting from any integer $k$, we go to the next multiple of $1000$ (a gap of at most $999$). We then add whatever three (or fewer) digit integer we need to "correct" the sum of the digits $\pmod {27}$, which takes, at most, another $999$.

Thus, every block of $2\times 999$ consecutive integers contains at least one for which the sum of the digits is a multiple of $27$. A similar argument works for any desired divisor.

I expect the bound could be tightened considerably, but at least this shows that a bound exists.

$\endgroup$
  • $\begingroup$ Simple insight, great help, thank you:) $\endgroup$ – Martund Jul 27 at 13:57
1
$\begingroup$

Let $Q(x)$ denote the digit sum of $x$.

$999$ is the smallest $n$ such that among any $n$ consecutive positive integers, at least one has digit sum a multiple of $27$.

First note that none of the $998$ consecutive integers $1,2,\ldots ,998$ has digit sum a multiple of $27$.

Any sequence of $999$ consecutive integers is either of the form $$\tag11000N+1,\ldots, 1000N+999$$ or $$\tag21000N+k+2,\ldots, 1000N+999,1000(N+1),\ldots, 1000(N+1)+k$$ with $0\le k\le 997$.

In $(1)$, the digit sums are $Q(N)+Q(i)$ with $i$ running from $1$ to $999$ and hence $Q(i)$ covering all values from $1$ to $27$. We conclude that $(1)$ contains a term with digit sum a multiple of $27$.

So let's look at $(2)$: We know $Q(N+1)\equiv Q(N)+1\pmod 9$, hence $Q(N+1)\equiv Q(N)+(1\text{ or }10\text{ or }19)\pmod{27}$.

  • If $Q(N+1)\equiv 0\pmod{27}$, then already $1000(N+1)$ has the desired property.

  • If $Q(N+1)\equiv 1\pmod {27}$, then among $1000(N+1),\ldots, 1000(N+1)+899$, all remainders $\bmod27$ occur, which solves the problem for all $k\ge 899$. For $k\le 898$, the sequence contains $1000N+900$, $1000N+909$, and $1000N+999$ with digit sums $Q(N)+9$, $Q(N)+18$, $Q(N)+27$. As $Q(N)\bmod 27$ is one of $0$, $9$, $18$, we are done.

  • More generally, if $Q(N+1)\equiv r\pmod {27}$ with $1\le r\le 9$, then $Q(1000(N+1)+999-100r)=Q(N+1)+27-r\equiv 0\pmod{27}$, which solves the problem for all $k\ge 999-100r$. For $k\le 998-100r$, the sequence contains $1000N+(1000-100r)$, $1000N+(1009-100r)$, and $1000N+(1099-100r)$ with digit sums $Q(N)+10-r$, $Q(N)+19-r$, $Q(N)+28-r$. As $Q(N)\bmod 27$ is one of $r-1$, $r+8$, $r+17$, we are done.

  • If $Q(N+1)\equiv 10+r\pmod{27}$ with $0\le r\le 8$, then $Q(1000(N+1)+89-10r)=Q(N+1)+17-r\equiv 0\pmod{27}$, which solves the problem for all $k\ge 89-10r$. For $k\le 89-10r$, the sequence contains $1000N+999-r$, $1000N+909-r$, and $1000N+900-100r$ with digit sums $Q(N)+27-r$, $Q(N)+18-r$, $Q(N)+9-r$. As $Q(N)\bmod 27$ is one of $r$, $r+9$, $r+18$, we are done.

  • If $Q(N+1)\equiv 19+r\pmod{27}$ with $0\le r\le 7$, then $Q(1000(N+1)+8-r)=Q(N+1)+8-r\equiv 0\pmod{27}$, which solves the problem for all $k\ge 8-r$. For $k\le 8-r$, the sequence contains $1000N+999-r$, $1000N+909-r$, and $1000N+900-100r$ with digit sums $Q(N)+27-r$, $Q(N)+18-r$, $Q(N)+9-r$. As $Q(N)\bmod 27$ is one of $r$, $r+9$, $r+18$, we are done.

$\endgroup$
  • $\begingroup$ Great answer, thanks a lot. $\endgroup$ – Martund Jul 27 at 13:56
  • $\begingroup$ or use polynomial remainder theorem for a rule. $\endgroup$ – Roddy MacPhee Jul 27 at 14:06
1
$\begingroup$

Obviously there are number whose digits add to $27$. ($999$ or $524385$ etc.) and obviously the sum of the digits $27$ is a multiple of $9$ so they are a multiple of $9$ but are they a multiples of $27$; and must multiples of $27$ have digits adding to a multiple of $27$.

Well, $27$ itself is an obvious counter example of the latter.

And $999= 27*37$ but $524385= 27*19421\frac 23$ so the first is not true either.

So the question I guess is why not?

Well the rule works for $9$ because $9 = 10-1$. And it works for $3$ because $3|9$.

Details: If $k|b-1$ and $n= \sum_{i=0}^m a_ib^i= \sum_{i=0}^m (a_i)(b^i-1) + \sum_{i=0}^m a_i$. Now $b^i-1 =(b-1)(b^{i-1} + b^{i-2}+ ..... + 1)$ so $(b-1)$ divides all of the $b^i-1$ so $b-1$ divides $n$ if and only if $(b-1)$ divides $\sum_{i=0}^m a_i$. If we let $b= 10$ and $b-1=9$ and $a_i$ be the digits of $n$ that's our result.

And it follows that if $k|b-1$ then $k|(b^i-1)$ so $k|n$ if and only if $k$ divides $\sum_{i=0}^m a_i$ as well.

And this will be true for any decimal system base $b$ (not just $b=10$ and and $k|b-1$ (not just $3|9$).

The fact that $3^2 = 9$ is mostly a coincidence and powers of $3$ is a bit of a red herring. It's not powers of $3$ going up that matter, but factors $10-1$ going down that matter.

We can note that in base $7$ a number is a multiple of $6$ if and only if the sum of the digits is a multiple of $6$ and a multiple of $2$ or of $3$ if and only if the sum of the digits is a multiple of $2$ or of $3$ respectively but nothing can be said of $4$ or $3$. ($11_7 = 8$ is a multiple of $4$ but $1+1=2$ is not. And $12_7 =9$ is a multiple of $9$ but $1+2=3$ which is not.)

Why doesn't it work? Well. $27 = 3*(10-1)= (3-1)*10 + (10-3)$. The sum of the digits of $27$ are $(3-1) + (10-3) = 10-1$. Our rule of $9$s apply and we can't jump magically to $27$. And if we increas by $27$ if we ignore carrying and borrowing we get $ab + 27 = (a+2)(b+7)$ and the sums of the digits are $a+b + 9$. That's an increase of $9$; not of $27$. Ind if we carry (i.e. $b \ge 3$ or $a \ge 8$ or $b\ge 3$ and $a\ge 7$) we get the sums are $(a+2+1)(b+7-10)$ or $1(a+2-10)(b+7)$ or $1(a+2+1-10)(b+7 - 10)$ and the sum of the digits stay the same or decreases by $9$; not $27$.

But if $b-1 = k^m$ then in base $b$ we will have that multiples of $k^i; i\le m$ will have the sum of the digits add to a multiple of $k^i$.

Example in base $28$ then sum of the digits of a multiple of $27$ will add to a multiple of $27$.

FWIW $999_{10} = 28^2 + 7*28 + 19 = 17T_{28}$ where $T$ is the digit for $19$.

And $27*92 = 2484_{10} = 3*28^2+4*28 + 20= 34U_{28}$ where $U$ is the digit for $20$ is another example.

Less trivial example. The number $8ATR_{28}$ were $A=10$ and $T=19$ and $R=17$ will have digits that add to $8+10+19+17=54$, so my claim is that it ought to be a multiple of $27$. And

$8ATR_{28} = 8*28^3 + 10*28^2+ 19*28 + 17 =$

$8(27+ 1)^3 + 10(27+1)^2 + 19(27+1) + 17 =$

$8(27^3 + 3*27^2+3*27 + 1) + 10(27^2 + 2*27 + 1) + 19(27+1)+17=$

$[8*27^3 + 3*27^2 + 3*27 + 20*27^2 + 2*27 + 19*27] + 8 + 10 + 19+17=$

$27(8*27^2 + 3*27 + 3 + 20*27 + 2 + 19) + 54 = $

$27(8*27^2 + 3*27 + 3 + 20*27 + 2 + 19 + 2)$ is a multiple of $27$.

And indeed $8*28^3 + 10*28^2+ 19*28 + 17=184005 = 27*6815$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.