Keeping it Small and Simple

2007.05.12

Is it divisible by three?

Filed under: Mathematics, Ruby Programming — Lorenzo E. Danielsson @ 18:16

If you want to know whether or not a really big number is divisible by three, you don’t need a calculator to find it out. Simply add the digits together. If the sum of the digits is divisible by three, then the number itself is divisible by three as well.

Not following? Let’s look at an example. Is the number 12,345 divisible by three? Let’s try it.


1 + 2 + 3 + 4 + 5 = 15

Now 15/3 is exactly 5, so 12,345 is divisible by three. The really neat thing about this is that it is recursive so:


1 + 2 + 3 + 4 + 5 = 15
1 + 5 = 6

..and of course 6/3 is exactly 2. Let’s try another one. Is 987,654,321 divisible by three? Hm, let’s see..

9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45
4 + 5 = 9

So 987,654,321 is divisible by three (you can use your calculator to confirm it). Last example, is 287,765,982,173,888,234 divisible by three?


2 + 8 + 7 + 7 + 6 + 5 + 9 + 8 + 2 + 1 + 7 + 3 + 8 + 8 + 8 + 2 + 3 + 4 = 98
9 + 8 = 17
1 + 7 = 8

The number 8 is not divisible by three, so the number 287,765,982,173,888,234 is not divisible by three.

I wanted to write a little program to test this theorem, and came up with the following in Ruby:

#! /usr/bin/ruby -w

def sum_digits(str)
  sum = 0
  for i in 0..str.length-1
    sum += str[i, 1].to_i
  end

  if sum.to_s.length > 1
    sum_digits(sum.to_s)
  else
    return sum
  end
end

# Test with a few numbers. Add any numbers you like.
for num in [ 6, 15, 21, 99, 100, 2005, 4141, 12345, 20000, 32000 ] do
  puts "#{num.to_s.rjust(5)} : #{sum_digits(num.to_s)} : #{(num % 3)}"
end

Note that the sum_digits method (yes, in Ruby functions are actually methods) recurses down until there is only a single digit left. Also you can see that I created an array with a few random and a few not-so-random numbers. You could easily modify the program to allow the user to enter a number to be tested or one the takes the number(s) to be tested as command-line arguments.

There is obviously More Than One Way of Doing This in Ruby. Feel free to add your own implementations in the comments section. The same goes for if you’ve written an implementation in another language.

Advertisements

3 Comments »

  1. well, the first step is add up the individual components like this;
    2 + 8 + 7 + 7 + 6 + 5 + 9 + 8 + 2 + 1 + 7 + 3 + 8 + 8 + 8 + 2 + 3 + 4 = 98

    Then you do this.
    9 + 8 = 17
    1 + 7 = 8

    Excuse me, i thought after the first step the real number would then be divided to test it.
    Any explanations here.

    Comment by bbaka — 2007.12.13 @ 15:34

  2. That’s the really cool thing about this divisibility rule. It works recursively.

    From the post, the sum of the digits of 987,654,321 is 45. If you do 45 / 3 you get 15. So we have already proved that 987,654,321 is divisible by three.

    But, you could continue. The sum of the digits of 45 is 9, and 9 / 3 is 3.

    So you are right that we could divide after the first step. But why miss out on such an excellent opportunity to recurse?

    If you think a bit about it, there is another interesting thing about it as well. Since we only need to count the sum of the individual digits, it should follow that 123,456,789 is also divisible by three, as is 649,728,135. However you re-arrange those nine digits, the number will always be divisible by three.

    Comment by Lorenzo E. Danielsson — 2007.12.13 @ 16:00

  3. OK. got it . Thanks.

    Comment by bbaka — 2007.12.13 @ 16:41


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: