Tuesday, 18 August 2015

elementary number theory - Sum of digits divisible by 27




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.


Answer



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 r1. Then n=10r1=999r 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,,10r2, 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,,a+n.


Among the first 910r1=n(10r11) terms, one is a multiple of 910r1. Say, 910r1a+k=:b with 0k<910r1. Then Q(b) is a multiple of 9, and as the lower r1 digits of b are zero, we have Q(b+i)=Q(b)+Q(i) for 0i<10r1 and hence
Q(b+10j1)=Q(b)+9j,0jr1.
(Note that k+10r11<10r1, so these terms are really all in our given sequence). It follows that 9r divides one of these Q(b+10j1).


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...