Author |
Topic: Divisible by 3 or 7 (Read 927 times) |
|
johny_cage
Full Member
Gender: 
Posts: 155
|
 |
Divisible by 3 or 7
« on: Nov 24th, 2007, 4:57am » |
 Quote  Modify
|
Q(1) Check for the divisibility of a number by 3 in most optimized way.
Q(2) Check for the divisibility of a number by 7 in most optimized way.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Divisible by 3 or 7
« Reply #1 on: Nov 24th, 2007, 6:19am » |
Quote Modify
|
In reality, using n%==3 and n%7==0 is probably fastest.
For other suggestions you could read the previous threads on the subject.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
swami
Newbie
Gender:
Posts: 17
|
|
Re: Divisible by 3 or 7
« Reply #2 on: Nov 28th, 2007, 12:58am » |
Quote Modify
|
Quote:| For other suggestions you could read the previous threads on the subject. |
|
I am not able to understand the logic for divisibility by 11 testing in the following code
div11(x)
{
if(x < 16)
return x == 0 || x == 11;
l4 = x&15;
f16 = x>>4;
return div11(l4 + f16 + f16<<2 );
}
Can u pls. clarify???
Also, what about testing divisibility by 7?? Is there any general technique for testing divisibility in binary that I am missing?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Divisible by 3 or 7
« Reply #3 on: Nov 28th, 2007, 1:59am » |
Quote Modify
|
on Nov 28th, 2007, 12:58am, swami wrote:| I am not able to understand the logic for divisibility by 11 testing in the following code |
|
First note that 16 % 11 = 5 = 1+4
So if we have N=16*x+y (take 0 <= 0 < 16), N is divisible by 11, if 5x + y is divisible by 11, i.e. if y + x + x << 2 is divisible by 11.
By repeating this we can repeatedly reduce N (if x > 0, the new N' is at most slightly more than 1/3rd the size)
And if N < 16, obviously it's only divisible by 11 if it's 0 or 11.
Quote:| Also, what about testing divisibility by 7?? |
|
8%7 = 1,
so if N = 8*x + y (take 0 <= 0 < 8), then you can equivalently test N' = x+y
Quote:| Is there any general technique for testing divisibility in binary that I am missing? |
|
It's a general method for all bases, not just binary, also decimal, hexadecimal or anything else.
d divides bk*x + y (with 0 <= y < bk) if and only if d divides (bk % d)x + (y % d)
The choice you make for k can make a big difference to how simple your calculation becomes, and of course you can generalize it.
If you take decimal for example, and divisibility by 9, you have that 10i % 9 = 1, so for a decimal number you can just add all the digits and test whether that's divisible by 9 (rather then removing the last digit and adding it to the rest repeatedly; i.e.
12345 ->1+2+3+4+5 (=15) -> 1+5 (=6), rather than 12345 -> 1234+5 (=1239) -> 123+9 (=132) -> 13+2 (=15) -> 1+5 (=6) ).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print