# 2021 AIME I Problems/Problem 3

## Problem

Find the number of positive integers less than $1000$ that can be expressed as the difference of two integral powers of $2.$

## Solution

$\binom{11}{2} = 55$ We need to subtract 5 since $2^{10} - 2^0, 2^1, 2^2, 2^3, 2^4$ don't work. $55-5=\boxed{050}$ ~hansenhe

## Solution 2 (More Detailed Explaination)

All of the powers of $2$ subtracted by another power of $2$ that can result within 1000 are $0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024$ since $2048-1024>1000$. None of the numbers when chosen two numbers will be the same because the difference of powers of $2$ can be written as a power of two times a non-power of two.

Case 1: The subtrahend (the second number in a subtraction expression) must be greater than $24$ if the minuend is $1024$. In this case, the subtrahend can be ranging from $32$ to $512$ giving $5$ total choices.

Case 2: If both numbers are powers of two less than $1024$, then we can choose two numbers from that list and order them to form a positive number. The amount of ways to do this is $10\choose2$ $=\frac{10\cdot9}{2}=45$. In total, there are $45+5=\boxed{050}$ numbers.

~Interstigation