Check if Divisible by 3

[rar]

One of the assignments I've received has asked me to check if a number is divisible by 3. However, I'm not allowed to use the built in remainder functions to check....so how would you normally check for a number's divisibility by another number? (in this case, 3)

If it matters, I'm using Miranda.

[jbking]

Ever notice that if a number's digits sum is 3,6, or 9 that the number will be divisible by 3? That's my hint for what you may want to use.

[rar]

But how would I apply that? How would I divide a number up by its digits?

[Joel92]

You could try the modulus operator (%), if that is allowed.

If that's not allowed, think about jbkings hint. Off the top of my head you might also beable to use a regex pattern somehow to get it done.

[jbking]

rar @ Mon Sep 28, 2009 9:44 am wrote:

But how would I apply that? How would I divide a number up by its digits?

I'm not familiar with Miranda at all so I can't help that specifically, but I can give a couple of ideas:

Using strings:

Convert the number into a string which can then be traversed, taking a substring of 1 character that is converted back to an int, with a running sum of the digits and then repeated should the sum be greater than 9, e.g. if the sum of the digits is 42 you could rerun this on the 42 and get 6. This should be easy if you know strings and how to manipulate them.

Using Math operators:

If there exists a div operator, then you could do the following:

Take the original number and div it by 10 and then take 10 times that and subtract it to get a single value, e.g. if the original number is 23524 then the result of the div is 2352 and 23524-(2352*10) = 4.
Keep a running total of the digits just as above
Do this again and again until you get down to a zero from the div to indicate there aren't any more digits. Repeat this on the sum if it is more than 9.

Div is not the same as divide. Div is returning the quotient of a divide and in the case of two integers, the return should also be an integer,e.g. 5 div 3 = 1 or 15 div 20 = 0.

[Vermette]

Quote:

1.4. Write Miranda programs to do the following:

A recursive program called p7 which takes a positive number n as input
and returns True if the number is divisible by 3 and False otherwise. (Do
NOT use the mod or rem functions). Examples of executing p7 are:
p7 30 => True
p7 25 => False

Miranda means you go to Windsor

Dr. Frost has a GA on office hours from 2-5 today. You can ask them for help.

Or you can look at the slides for lecture 3, p11 is similar to what you have to do.

[jbking]

Just as a general aside, here are a few other divisibility tricks:

By 2: Number ends in an even number 0,2,4,6, or 8. With some languages you could just check the last bit on this.
By 4: Numbers last 2 digits are a multiple of 4. With some languages you could just check the last 2 bits for this.
By 5: Number ends in 0 or 5.
By 6: Divisible by 2 and 3.
By 8: Numbers last 3 digits are divisible by 8, though this isn't necessarily the easiest way to do it.
By 9: Digits sum to 9.

For 2,4,5 and 8 the key is that either 10 or a power of 10 is a multiple of that number and thus all higher multiples can be skipped.

[Vermette]

jbking @ September 28th 2009, 11:29 wrote:

Ever notice that if a number's digits sum is 3,6, or 9 that the number will be divisible by 3? That's my hint for what you may want to use.

Determining if the sum is divisible is the same problem.

[DemonWasp]

Recurse. Eventually the sum will be one of 3, 6 and 9 (divisible by 3) or something else (not).

[jbking]

There is a simple brute force approach one could take for this of simply subtracting 3 over and over,e.g. recursively or in a loop, to see if they eventually hit 0 or not. Why didn't I think of this before?

[Alexmula]

jbking @ Mon Sep 28, 2009 2:00 pm wrote:

There is a simple brute force approach one could take for this of simply subtracting 3 over and over,e.g. recursively or in a loop, to see if they eventually hit 0 or not. Why didn't I think of this before?

thats what i did for the assignment you ppl here think way too complicated except when it hit 3 then it is divisible by 3

jbking wrote:

Ever notice that if a number's digits sum is 3,6, or 9 that the number will be divisible by 3? That's my hint for what you may want to use.

a number is divisible by 3 if the sum of its digits is divisible by 3 for example: 2031 = 2 + 0 + 3 + 1 = 6 -> 6 is divisible by 3, therefore 2031 is divisible by 3

[DemonWasp]

What if the number is -12?

There are two main cases: either the number becomes too large and "overflows", or else it just goes on forever. Either way, it's going to take a bloody long time (bad!). If it overflows, I'm pretty sure it won't preserve the "divisible by 3" property, since that would add 2^(number of bits) to the number's effective value as calculated:

code:

3 * N + 2 ^ X mod 3 = 2 ^ X mod 3 = -1 ^ X mod 3 = -1 or +1 (not divisible by 3).

Sure, you could add 3 each time if the number is negative...or you could do it right.

Look around in the documentation to see if there's a "split" method that will let you split the string-version of the number into a list of strings of one digit each, which you can convert to integers and sum. This could look like:

code:

define sum_digits ( number_string ) :     return int ( number_string ( 1 ) ) + sum_digits ( substring ( number_string, 2 );

If you take a number and do sum_digits on it, the result should be the sum of its digits. If that's a single digit, compare against 3, 6 and 9. If not, feed it back into sum_digits and try again.

[Vermette]

DemonWasp @ September 28th 2009, 16:37 wrote:

What if the number is -12?

To repeat:

Quote:

1.4. Write Miranda programs to do the following:

A recursive program called p7 which takes a positive number n as input
and returns True if the number is divisible by 3 and False otherwise. (Do
NOT use the mod or rem functions). Examples of executing p7 are:
p7 30 => True
p7 25 => False

DemonWasp @ September 28th 2009, 16:37 wrote:

There are two main cases: either the number becomes too large and "overflows", or else it just goes on forever. Either way, it's going to take a bloody long time (bad!). If it overflows, I'm pretty sure it won't preserve the "divisible by 3" property, since that would add 2^(number of bits) to the number's effective value as calculated:

code:

3 * N + 2 ^ X mod 3 = 2 ^ X mod 3 = -1 ^ X mod 3 = -1 or +1 (not divisible by 3).

Sure, you could add 3 each time if the number is negative...or you could do it right.

Look around in the documentation to see if there's a "split" method that will let you split the string-version of the number into a list of strings of one digit each, which you can convert to integers and sum. This could look like:

code:

define sum_digits ( number_string ) :     return int ( number_string ( 1 ) ) + sum_digits ( substring ( number_string, 2 );

If you take a number and do sum_digits on it, the result should be the sum of its digits. If that's a single digit, compare against 3, 6 and 9. If not, feed it back into sum_digits and try again.

After the assignment is due (tomorrow) and it's discussed in lecture or lab I expect someone will bring up the (recursive) digit approach, which could serve as an example for their lecture(s) on algorithmic complexity

[DemonWasp]

Valid point. I hadn't actually looked closely enough at the problem description. Point on algorithmic complexity stands.