Binary 2^n - 1 divisibility

  • #1
kurtulmehtap
3
0
Dear All,
I have to test if a binary number is divisible to
2^n - 1 where n is even.
Is there a test available for binary numbers like to test a divisibility by 3.
Thanks in advance...
 

Answers and Replies

  • #2
robert Ihnot
1,056
0
You are talking about what, in general, is studied as Mersenne primes. Even powers are generally not prime. That's not hard to show.
 
Last edited:
  • #3
CRGreathouse
Science Advisor
Homework Helper
2,824
0
The sum of the base 2^n digits is divisible by 2^n-1 iff the number is, so you could use that. But I'm not sure how much of a speedup that gives.
 
  • #4
CRGreathouse
Science Advisor
Homework Helper
2,824
0
You are talking about what, in general, is studied as Mersenne primes. Even powers are generally not prime. That's not hard to show.

I interpreted the question as "how can I tell if N is divisible by 2^n-1" rather than "how can I tell if N divides 2^n-1".
 
  • #5
kurtulmehtap
3
0
You are talking about what, in general, is studied as Mersenne primes. Even powers are generally not prime. That's not hard to show.

in my case n is even, not odd or prime
 
  • #6
robert2734
77
0
Testing if a binary number is divisible by three is like testing if a number base 10 is divisible by 11. Alternately subtract than add the bits together and if your answer is divisable by three than the whole string was divisable by three.

1100101 1-1+0-0+1-0+1=2 not divisible by 3
1100110 1-1+0-0+1-1+0=0 divisible by three.
 
  • #7
CRGreathouse
Science Advisor
Homework Helper
2,824
0
Testing if a binary number is divisible by three is like testing if a number base 10 is divisible by 11. Alternately subtract than add the bits together and if your answer is divisable by three than the whole string was divisable by three.

1100101 1-1+0-0+1-0+1=2 not divisible by 3
1100110 1-1+0-0+1-1+0=0 divisible by three.

3 is a funny number, since it's 2^1 + 1 and 2^2 - 1. You can use either type of test: add digits in blocks of two, or alternately add and subtract digits.

10101011 = 10+10+10+11 = 1001 = 10 + 01 = 11 = 0 (mod 3)
10101011 -> 1-0+1-0+1-0+1-1 = 11 = 0 (mod 3)

The first preserves residues (not just divisibility) mod 3; the second works with smaller numbers (though twice as many).
 
  • #8
robert2734
77
0
You can test if a number base 4 is a multiple of three the way you test if a number base ten is a multiple of nine. I saw your earlier post and decided to add some additional information. I don't know which approach , if either, gives you any calculating speed up.
 

Suggested for: Binary 2^n - 1 divisibility

Replies
7
Views
3K
  • Last Post
Replies
12
Views
8K
  • Last Post
Replies
7
Views
8K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
2
Views
3K
  • Last Post
Replies
18
Views
4K
  • Last Post
Replies
5
Views
3K
Replies
4
Views
2K
  • Last Post
Replies
10
Views
7K
Top