Counting Almost Square Numbers
A non-negative integer is called "almost square" if it satisfies both conditions: 1. It is not a perfect square. 2. Every one of its digits is a perfect square (i.e., each digit is $0$,
For example,
Find the number of positive integers less than
Hints
- The digits of an almost-square number must each be a perfect square digit: $0, 1, 4,$ or $9$. How many numbers less than 1000 have only these digits?
- Use complementary counting: total numbers with square digits minus those that are actually perfect squares.
- Pad numbers to 3 digits. There are $4^3 = 64$ such numbers. Now check which perfect squares below 1000 have all digits in $\{0,1,4,9\}$ -- there are exactly 10 of them.
Worked Solution
How to Think About It: This is a complementary counting problem. Directly listing all almost-square numbers would be tedious, but counting all numbers whose digits are in $\{0, 1, 4, 9\}$ is easy (it's just $4^k$ for $k$-digit slots), and the number of perfect squares among them is small. So count the full set, then subtract the perfect squares.
Quick Estimate: Numbers less than 1000 have at most 3 digits. With 4 choices per digit, there are $4^3 = 64$ three-digit strings (including those with leading zeros, which represent 1- and 2-digit numbers). Out of these 64, how many are perfect squares? Perfect squares below 1000 are $0^2, 1^2, \ldots, 31^2$, so only 32 candidates to check. Most won't have all digits in $\{0,1,4,9\}$. Quick mental scan: probably around 10 of them. So the answer should be around $64 - 10 = 54$.
Approach: Enumerate all numbers with digits in $\{0,1,4,9\}$, then subtract perfect squares from this set.
Formal Solution:
Step 1: Count all non-negative integers less than 1000 with digits in $\{0,1,4,9\}$.
Pad every number to 3 digits with leading zeros (e.g., $9 \to 009$, $44 \to 044$). Each digit slot has 4 choices, giving $4^3 = 64$ total numbers (from $000$ to $999$ with only digits $0,1,4,9$).
Step 2: Identify which of these 64 are perfect squares.
We need perfect squares
| $k$ | $k^2$ | Digits OK? | |-----|-------|------------| | 0 | 0 | Yes | | 1 | 1 | Yes | | 2 | 4 | Yes | | 3 | 9 | Yes | | 7 | 49 | Yes | | 10 | 100 | Yes | | 12 | 144 | Yes | | 20 | 400 | Yes | | 21 | 441 | Yes | | 30 | 900 | Yes |
All other perfect squares $\leq 961$ contain at least one digit outside $\{0,1,4,9\}$. That gives us 10 perfect squares.
Step 3: Subtract and adjust.
The 64 numbers include $000 = 0$, which is a non-negative integer but not a positive integer. We need positive integers, so we exclude $0$. Since $0$ is a perfect square (already in our list of 10), it gets removed from both the total and the perfect-square count.
Almost-square positive integers $= (64 - 1) - (10 - 1) = 63 - 9 = 54$.
Alternatively: $64$ total $- 10$ perfect squares $= 54$ almost-square non-negative integers. Since we want positive integers and $0$ is not almost-square (it's a perfect square), the count is still $54$.
Answer: There are $\boxed{54}$ positive integers less than
Intuition
The key technique here is complementary counting -- instead of directly constructing objects that satisfy a "not X" condition, count all objects satisfying the other conditions and subtract those that are X. This is almost always cleaner than direct enumeration.
The padding trick (treating all numbers as 3-digit strings with leading zeros) is a small but important detail that makes the counting uniform: you avoid having to separately handle 1-digit, 2-digit, and 3-digit cases. This kind of trick -- making your counting space uniform -- shows up repeatedly in combinatorics problems. The exhaustive check of 10 perfect squares is manageable because perfect squares grow quadratically, so there are only about $\sqrt{1000} \approx 31$ to check.