Let $S$ be the [set](https://artofproblemsolving.com/wiki/index.php/Set) of [integers](https://artofproblemsolving.com/wiki/index.php/Integer) between $1$ and $2^{40}$ whose binary expansions have exactly two $1$'s. If a number is chosen at random from $S,$ the [probability](https://artofproblemsolving.com/wiki/index.php/Probability) that it is divisible by $9$ is $p/q,$ where $p$ and $q$ are relatively prime positive integers. Find $p+q.$
Any number from 1 to $2^{40}$ can be represented in binary with 40 digits (because $2^{40}$ has 41) with leading zeroes if necessary. Therefore the number of sets where there are exactly two 1’s in this binary representation is just $\binom {40}{2}$ because we’re choosing 2 1s to go in 40 digit slots. This is equal to 780; we have found $q$, our denominator.
With these particular numbers, when converting back to decimal note that the 38 zeroes all cancel out. Let the first 1 when reading the number in binary from left to right be in position $y$, I.e. when converting to decimal, it will have value $2^{y}$. Similarly, let the second 1 have position $x$ (note $x<y$); then the decimal value of that 1 will be $2^{x}$. For example, with the binary string 0001001000 $y$ is 6 and $x$ is 3 (note that it is zero indexed).
It should also be noted that our constraints on $x$ and $y$ are $0 \leq x < y < 40$ and $x, y \in \mathbb{Z}$.
The numbers that satisfy the constraints are therefore equal to $2^{x}+2^{y} = 2^{x} \cdot (1+2^{y-x})$. The conditions say that this is divisible by 9. $2^{x}$ is clearly never divisible by 9, so we can just focus on $1+2^{y-x}$. 
\[1+2^{y-x} \equiv 0 \pmod 9 \implies 2^{y-x} \equiv -1 \pmod 9 \implies 2^{y-x} \equiv 8 \pmod 9\]
$y-x = 3$ clearly satisfies the congruence, but are there any more? Well, we see that any time we raise -1 (in the second congruence above) to an odd power we get -1 again, so if we raise $2^{3}$, which we know already works, to an odd power, we will also satisfy the congruence. Thus, $2^{3}, 2^{9}, 2^{15},$ etc. work; or, \[y-x \equiv 3 \pmod 6\]
To count the numbers that satisfy the condition, we need to find the amount of numbers that satisfy $2^{x} \cdot (1+2^{y-x}) \leq 2^{40}$, and $y-x \equiv 3 \pmod 6 = 6n +3$ for some whole number $n$. 
Since we know $1+2^{y-x} = 1+2^{6n+3}$ is positive, we can divide both sides of the inequality by it;
\[2^{x} \cdot (1+2^{y-x}) \leq 2^{40} \implies 2^{x} \leq \frac{2^{40}}{1+2^{y-x}} \implies 2^{x} \leq \frac{2^{40}}{1+2^{6n+3}}\]
\[\implies 2^{x} < \frac{2^{40}}{2^{6n+3}} \implies 2^{x} < 2^{40-(6n+3)}\implies 2^{x} < 2^{37-6n} \implies x < 37 - 6n\]
Finally, the number of possible values of $x$ is $37-6n$ because $x$ can also be 0 and must be an integer.Therefore, as we increase $n$ from zero upwards, we get the total number of possibilities for $x$ is $37+31+25+\ldots+1 = 7 + 36 + 30 + 24 + \ldots + 6 + 0 = 7 + 6 \cdot (6 + 5 + 4\ldots + 1)$
$= 7 + 6 \cdot 3 \cdot 7 = 7 + 18 \cdot 7 = 19 \cdot 7 = 133$.
Since 133 and 780 are relatively prime, the answer is $\frac{133}{780}$ and our final answer is $133+780 = \boxed{913}$
~KingRavi