MathDB

Binary is FUN!

Source:

November 17, 2005

probabilitymodular arithmeticnumber theorygreatest common divisorrelatively prime

Problem Statement

Let

S

be the set of integers between

1

and

2^{40}

whose binary expansions have exactly two

1

's. If a number is chosen at random from

S

, the probability that it is divisible by

9

p/q

, where

p

and

q

are relatively prime positive integers. Find

p+q