aime26-03

Proposed solution

I need to find the number of integers less than or equal to 100 that can be expressed as $a + b + ab$ for distinct positive integers $a$ and $b$.

First, let me rewrite the expression in a more useful form:
$a + b + ab = a + b + ab + 1 - 1 = (a + 1)(b + 1) - 1$

So I'm looking for integers of the form $(a + 1)(b + 1) - 1$ where $a$ and $b$ are distinct positive integers.

Let me set $x = a + 1$ and $y = b + 1$, where $x$ and $y$ are integers greater than or equal to 2, and $x \neq y$.

Then I want numbers of the form $xy - 1$ where $x, y \geq 2$ and $x \neq y$.

This means I want all integers $n$ such that $n + 1 = xy$ for some distinct integers $x, y \geq 2$.

So I need to count integers $n \leq 100$ such that $n + 1$ can be factored as a product of two distinct integers both at least 2.

Let me think about this systematically. If $n + 1 = pq$ where $p, q \geq 2$ and $p \neq q$, then I want to count all such factorizations of numbers from 3 to 101.

Actually, let me reconsider the constraint. Since we want $n \leq 100$, we have $n + 1 \leq 101$.

So I need to count integers $k$ where $3 \leq k \leq 101$ and $k$ can be written as a product of two distinct integers both at least 2.

Let me approach this by considering all possible values of $k$ from 3 to 101 and checking if they have such factorizations.

But there's a better way. I'll count the numbers that CANNOT be expressed in this form, then subtract from the total.

A number $k \geq 3$ cannot be written as a product of two distinct integers both at least 2 if and only if:
1. $k$ is prime (since if $k = pq$ with $p, q \geq 2$, then $k$ has a proper factorization)
2. $k = p^2$ for some prime $p \geq 2$ (since the only way to write $p^2$ as a product of two integers $\geq 2$ is $p \cdot p$, but we need them distinct)

Wait, let me be more careful about what numbers can be written as $xy$ with $x, y \geq 2$ and $x \neq y$.

The numbers that CANNOT be written in this form are:
- Numbers less than 3 (but we're considering $k \geq 3$)
- Prime numbers (since they have no non-trivial factorizations)
- Perfect squares of primes (since the only factorization is $p \cdot p$)

So I want to count integers from 3 to 101 that are NOT prime and NOT of the form $p^2$ where $p$ is prime.

Let me count:
- Primes from 3 to 101
- Perfect squares of primes from 3 to 101

Primes from 3 to 101: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

That's 24 primes.

Perfect squares of primes from 3 to 101:
- $2^2 = 4$
- $3^2 = 9$ 
- $5^2 = 25$
- $7^2 = 49$
- $11^2 = 121 > 101$

So we have: 4, 9, 25, 49 (4 numbers)

But wait, I need to be more careful. The number 4 = 2² is not of the form $xy$ with $x, y \geq 2$ and $x \neq y$, because we must have $x = y = 2$.

Similarly for 9 = 3², 25 = 5², 49 = 7².

So there are 4 numbers that cannot be expressed as $xy$ with $x, y \geq 2$ and $x \neq y$.

The total number of integers from 3 to 101 is 99.

Therefore, the number of integers from 3 to 101 that CAN be expressed in this form is: $99 - 4 - 24 = 71$

Wait, I need to double-check this. The numbers from 3 to 101 are 99 numbers total.
The numbers that cannot be written as $xy$ with $x, y \geq 2$ and $x \neq y$:
- Primes: 24 numbers
- Perfect squares of primes: 4 numbers

But I need to check if any perfect square of a prime is also a prime. No, perfect squares of primes are not prime.

So the count is: $99 - 24 - 4 = 71$

But let me reconsider what we want. We want integers $n \leq 100$, so we want $n + 1 \leq 101$.

The numbers from 3 to 101 that can be written as $xy$ with $x, y \geq 2$ and $x \neq y$ are those that are NOT prime and NOT perfect squares of primes.

Numbers from 3 to 101: 99 numbers
Primes from 3 to 101: 24 numbers  
Perfect squares of primes from 3 to 101: 4 numbers (4, 9, 25, 49)

So the count is $99 - 24 - 4 = 71$.

But I should verify that these 4 perfect squares are indeed not expressible as products of distinct integers $\geq 2$:
- 4 = 2×2 (n