wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> multiples of 13
        
(Message started by: Christine on Aug 3^rd, 2013, 12:57pm)

Title: multiples of 13
Post by Christine on Aug 3^rd, 2013, 12:57pm

How can you find multiples of 13 such that the sum of digits is divisible by 13?

for example,
247 = 13*19 and 2+4+7 = 13

and generally, how do you find multiples of N such that the sum of digits is divisible by N

Title: Re: multiples of 13
Post by towr on Aug 4^th, 2013, 7:16am

The simplest way to find some multiple of N such that the digits sum to another multiple of N, is imo to find when powers of 10 that are 1 modulo N
So, e.g. 10⁶ % 13 = 1; then find at which interval that reoccurs ( http://en.wikipedia.org/wiki/Euler%27s_totient_function ), so for 13, every (6+12k)th power of 10 is 1 modulo 13
Now we can just pick any number that is a multiple of N and distribute that total over digits; so e.g. for every d_a and d_b such that d_a+d_b=13, d_a*10¹⁸+d_b*10⁶ is also a multiple of 13. For example 5000000000008000000; but also (if we use 3 nonzero digits) 8000000000009000000000009000000 and 7000000000004000000000009000000000006000000 (if we use 4), etc

Since 13 and 10 are coprime, you can actually just remove the trailing 0s in this case. Which won't stop this from giving ridiculously large numbers, but it's an easy way to make as many as you want.