Interview Question: 2^n – 1 divide by 7

ACMer

13 years ago

Q: n is a none-negative numbers, in order to let divides perfectly 7, characterise n.

A: in binary representation is n ones. And 7 in binary is 111. The n has to be multiples of 3 in order for to be zero.

The following python script proves this by output the first then n (excluding zero because it is so obvious)

#!/usr/bin/python

cnt = 0
n = 1

while 1:
	if (2**n - 1) % 7 == 0:
		cnt += 1
		print n
		if cnt > 10: break
	n += 1

It will output 3, 6, 9, 12 … 33. can be replaced by bit logics operation , which is a lot faster.