Tuesday, 19 August 2014

summation - Digit-sum division check in base-n




Several years ago now I realised that for any natural numbers x and y you could write xy=(x1)(y1i=0xi)+1


This shows that xy1 will always be divisible by x1, which after a bit of deliberation I realised meant that in any base a quick check for divisibility could be employed for divisors that are factors of the base number 1 (hence 3 and 9 in base 10) by adding the digits until only one digit was left and checking if that digit was divisible by the divisor.



I wrote the above formula and use in back of my maths book when I started high school (probably when I should have been listening to the teacher!) and completely forgot about it, until I was looking through my old book the other day and saw it. Now I'm wondering what the general version of this formula is (say for all integers), and what other uses it has beside division checks. If anyone could point me in the right direction I would be very grateful.


Answer



To be honest, I think there is a way to expand this for x,yR.



Start by dividing,



xy1x1=?




Basically, we have some polynomial of the form xy1 set equal to 0, and x=1 is one obvious root. The other roots can be found be dividing the said factors, and we result with



xy1x1=Πyn=2(xrn)



Where rn is the nth root. Interestingly, with Euler's formula, we can find a nice closed form solution for rn,



rn=enπi=cos(nπ)+isin(nπ)



And looking a little bit further, I see you found the summation formula for a geometric series,




xn=0an=an+11a1



We may derive this solution in numerous ways, one way being Perturbation methods, which I will not explain here, but an example is here. Just replace all of the 10's with x, and you derive your solution.



Lastly, I note that my formula for xy1x1 stops looking pretty when yR, so I would stick to the summation formula.


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}...