Note: In this solution, we will take for granted that if \(n\) is a positive integer that is not a perfect square, then \(\sqrt{n}\) is an irrational number.
Since \(\sqrt{2}\approx1.4142\) and \(\sqrt{3}\approx1.7320\), we have that \(f(2)=4\) and \(f(3)=7\).
In the table below, the first column contains the integers \(n\) from \(37\) through \(48\), the second column contains \(\sqrt{n}\) truncated to four digits past the decimal point, and the third column contains \(f(n)\).
| \(n\) | \(\sqrt{n}\) | \(f(n)\) |
|---|---|---|
| \(37\) | \(6.0827\) | \(0\) |
| \(38\) | \(6.1644\) | \(1\) |
| \(39\) | \(6.2449\) | \(2\) |
| \(40\) | \(6.3245\) | \(3\) |
| \(41\) | \(6.4031\) | \(4\) |
| \(42\) | \(6.4807\) | \(4\) |
| \(43\) | \(6.5574\) | \(5\) |
| \(44\) | \(6.6332\) | \(6\) |
| \(45\) | \(6.7082\) | \(7\) |
| \(46\) | \(6.7823\) | \(7\) |
| \(47\) | \(6.8556\) | \(8\) |
| \(48\) | \(6.9282\) | \(9\) |
Among the values of \(f(n)\) for \(n\) from \(37\) through \(48\), each integer from \(0\) through \(9\) appears exactly once except for \(4\) and \(7\), which appear exactly twice each. Notice that \(4\) and \(7\) are the values of \(f(2)\) and \(f(3)\), respectively.
Since \(\sqrt{5} \approx 2.2360\), \(\sqrt{6} \approx 2.4494\), \(\sqrt{7} \approx 2.6457\), and \(\sqrt{8} \approx 2.8284\), we have that \(f(5)=2\), \(f(6)=4\), \(f(7)=6\), and \(f(8)=8\).
In the table below, the first column contains the integers \(n\) from \(50\) through \(63\), the second column contains \(\sqrt{n}\) truncated to four digits past the decimal point, and the third column contains \(f(n)\).
| \(n\) | \(\sqrt{n}\) | \(f(n)\) |
|---|---|---|
| \(50\) | \(7.0710\) | \(0\) |
| \(51\) | \(7.1414\) | \(1\) |
| \(52\) | \(7.2111\) | \(2\) |
| \(53\) | \(7.2801\) | \(2\) |
| \(54\) | \(7.3484\) | \(3\) |
| \(55\) | \(7.4161\) | \(4\) |
| \(56\) | \(7.4833\) | \(4\) |
| \(57\) | \(7.5498\) | \(5\) |
| \(58\) | \(7.6157\) | \(6\) |
| \(59\) | \(7.6811\) | \(6\) |
| \(60\) | \(7.7459\) | \(7\) |
| \(61\) | \(7.8102\) | \(8\) |
| \(62\) | \(7.8740\) | \(8\) |
| \(63\) | \(7.9372\) | \(9\) |
Similar to part (a), observe that among the values of \(f(n)\) for \(n\) between \(50\) and \(63\) inclusive, every integer from \(0\) through \(9\) appears either once or twice, and the integers that appear twice are exactly \(f(5)=2\), \(f(6)=4\), \(f(7)=6\), and \(f(8)=8\).
Suppose \(m\) is a positive integer in the list \(n^2+1,n^2+2,\dots,n^2+2n\). This is equivalent to \(n^2 < m < (n+1)^2\), which is equivalent to \(n < \sqrt{m} < n+1\) since \(m\), \(n\), and \(n+1\) are non-negative.
Fix an integer \(d\) satisfying \(0\leq d\leq 9\) and assume that \(m\) is an integer satisfying both \(n^2<m<(n+1)^2\) and \(f(m)=d\). That \(f(m)=d\) means \(d\) is the first digit past the decimal point in the decimal expansion of \(\sqrt{m}\). That \(\sqrt{m}\) is between \(n\) and \(n+1\) means the integer part of \(\sqrt{m}\) is \(n\). Therefore, \(\sqrt{m}\) is at least \(\dfrac{d}{10}\) more than \(n\) and at most \(\dfrac{d+1}{10}\) more than \(n\). Since \(\sqrt{m}\) is between two consecutive perfect squares, it is not a perfect square, which means \(\sqrt{m}\) is irrational. Putting this together, we get that \[n +\frac{d}{10} < \sqrt{m} < n+\frac{d+1}{10}\] where the strict inequalities are justified by the irrationality of \(\sqrt{m}\). We are also assuming that \(n\) is a positive multiple of \(5\), which means there is some positive integer \(k\) such that \(n=5k\).
The quantities in the chain of inequalities above are all positive, which means \[\left(n +\frac{d}{10}\right)^2 < \sqrt{m}^2 < \left(n+\frac{d+1}{10}\right)^2\] Expanding and substituting \(n=5k\), we get \[25k^2+dk+\frac{d^2}{100} < m < 25k^2+(d+1)k+\frac{(d+1)^2}{100}\]
We will now count the number of integers that satisfy the inequalities above.
Since the integer \(d\) satisfies \(0 \leq d \leq 9\), we must have that \(0\leq\dfrac{d^2}{100} < 1\). Therefore, \(25k^2+dk+\dfrac{d^2}{100}\) is between the consecutive integers \(25k^2+dk\) and \(25k^2+dk+1\), possibly equal to the smaller of the two but not equal to the larger of the two. Since \(m\) is an integer that is greater than \(25k^2+dk+\dfrac{d^2}{100}\), we conclude that \[25k^2+dk+1\leq m\]
Similarly, \(0\leq d\leq 9\) implies that \(0 < \dfrac{(d+1)^2}{100} \leq 1\). This means \(25k^2+(d+1)k+\dfrac{(d+1)^2}{100}\) is between the consecutive integers \(25k^2+(d+1)k\) and \(25k^2+(d+1)k+1\), possibly equal to the larger of the two but not equal to the smaller of the two. Since \(m\) is an integer that is smaller than \(25k^2+(d+1)k+\dfrac{(d+1)^2}{100}\), we can conclude that \(m\leq 25k^2+(d+1)k\). Combining this inequality with the inequality from earlier, we now have that \[25k^2+dk+1 \leq m \leq 25k^2 +(d+1)k\] The number of integers \(m\) that satisfy this inequality is \[(25k^2+(d+1)k)-(25k^2+dk) = k\]
We have now shown the following: For each integer \(d\) satisfying \(0\leq d\leq 9\), there are at most \(k\) integers \(m\) in the list \(n^2+1,n^2+2,\dots,n^2+2n\) with the property that \(f(m)=d\). There are \(2n\) integers in the list above and only ten different values that the function \(f\) can output. Since \(10k=2n\), there is no possibility other than that \(f\) takes every possible value exactly \(k=\dfrac{n}{5}\) times.
To get an idea of how to proceed, we first discuss the results of parts (a), (b), and (c).
In part (a), we saw that for values of \(m\) between \(1^2\) and \(2^2\), the function \(f\) takes on every possible value the same number of times (zero) with the exception of \(4\) and \(7\), which occur one extra time each. For values of \(m\) between \(6^2\) and \(7^2\), the function \(f\) takes on every possible value the same number of times (one) with the exception of \(4\) and \(7\), which occur one extra time each.
Similarly, in part (b) we observed that \(f\) takes on every value the same number of times, with the exceptions of \(2\), \(4\), \(6\), and \(8\) when \(m\) ranges between \(2^2\) and \(3^2\) as well as between \(7^2\) and \(8^2\).
The result of part (c) was that if \(n\) is a multiple of \(5\), then \(f(m)\) takes on every possible value the same number of times (with no exceptions) as \(m\) ranges over the integers strictly between \(n^2\) and \((n+1)^2\).
The patterns in part (a) and (b) continue, and there are similar patterns for other ranges between perfect squares. A bit more precisely, if \(n\) is a positive integer, then as \(m\) ranges over the integers between \(n^2\) and \((n+1)^2\), \(f(m)\) takes on every possible value the same number of times, possibly with some exceptions that occur one extra time each. These exceptional values depend only on the remainder when \(n\) is divided by \(5\).
Even more precisely, the following five claims are true. The claims are numbered to correspond to remainders after division by \(5\).
Claim 0: Suppose \(n=5k\) for some integer \(k\geq 0\). As \(m\) ranges over the integers strictly between \(n^2\) and \((n+1)^2\), \(f(m)\) takes every value from \(0\) through \(9\) exactly \(k\) times.
Claim 1: Suppose \(n=5k+1\) for some integer \(k\geq 0\). As \(m\) ranges over the integers strictly between \(n^2\) and \((n+1)^2\), \(f(m)\) takes the values \(4\) and \(7\) a total of \(k+1\) times each and takes every other value \(k\) times.
Claim 2: Suppose \(n=5k+2\) for some integer \(k\geq 0\). As \(m\) ranges over the integers strictly between \(n^2\) and \((n+1)^2\), \(f(m)\) takes the values \(2\), \(4\), \(6\), and \(8\) a total of \(k+1\) times each and takes every other value \(k\) times.
Claim 3: Suppose \(n=5k+3\) for some integer \(k\geq 0\). As \(m\) ranges over the integers strictly between \(n^2\) and \((n+1)^2\), \(f(m)\) takes the values \(1\), \(3\), \(4\), \(6\), \(7\), and \(8\) a total of \(k+1\) times each and takes every other value \(k\) times.
Claim 4: Suppose \(n=5k+4\) for some integer \(k\geq 0\). As \(m\) ranges over the integers strictly between \(n^2\) and \((n+1)^2\), \(f(m)\) takes the values \(1\), \(2\), \(3\), \(4\), \(5\), \(6\), \(7\), and \(8\) a total of \(k+1\) times each and takes the values \(0\) and \(9\) a total of \(k\) times each.
In part (c), we showed that Claim 0 is true. Before proving Claims 1, 2, 3, and 4, we will answer the actual question which was to determine how many times each digit occurs in the list \[f(1),f(2),f(3),\dots,f(10^4)\] Because \(10^4\) is a perfect square, \(f(0)=f(10^4)=0\), so we can instead count the number of times each digit occurs in the slightly different list \[f(0),f(1),f(2),\dots,f(10^4-1)\]
There are \(100\) perfect squares among the integers from \(0\) through \(10^4-1\), so there are \(100\) occurrences of \(0\) in the list that come from perfect squares.
For every other integer \(m\) in the list \(0,1,2,3,4,\dots,10^4-1\), there are unique integers \(k\) and \(r\) with \(0\leq k\leq19\) and \(0\leq r\leq 4\) with the property that \((5k+r)^2 < m < (5k+r+1)^2\).
Suppose \(d\) is a non-zero digit. For fixed \(k\) and \(r\), as we let \(m\) take the values strictly between \((5k+r)^2\) and \((5k+r+1)^2\), Claim \(r\) tells us whether the digit \(d\) occurs either \(k\) times or \(k+1\) times in that range. We are considering values of \(m\) satisfying \((5k+r)^2 < m < (5k+r+1)^2\) for every pair \((k,r)\) with \(0\leq k\leq 19\) and \(0\leq r\leq 4\). For every pair of the form \((k,0)\), we get \(k\) occurrences of \(d\) (see Claim 0). For every pair of the form \((k,1)\), we always get \(k\) occurrences or we always get \(k+1\) occurrences of \(d\), depending on what Claim 1 says about the digit \(d\). Continuing with this reasoning, the number of occurrences of \(d\) in the list \(f(0),f(1),f(2),\dots,f(10^4-1)\) can be expressed in the form \[a(0+1+2+\cdots+18+19)+b(1+2+3+\cdots+19+20) = 190a+210b\] where \(a\) is the number of values of \(r\) for which Claims 0 through 4 say there are \(k\) occurrences of \(d\), and \(b\) is the number of values of \(r\) for which Claims 0 through 4 say there are \(k+1\) occurrences of \(d\).
For example, for \(d=1\), there are \(k\) occurrences when \(r=0\), \(r=1\), and \(r=2\), and there are \(k+1\) occurrences when \(r=3\) and \(r=4\). Therefore, with \(d=1\), we have \(a=3\) and \(b=2\), so the number of times that \(d=1\) occurs in the list is \(3\times190+2\times210=990\).
Using Claims 0 through 4, the table below summarizes the count for the remaining non-zero digits. In the first column, the digit \(d\) appears, in the second column the value of \(a\) appears, in the third column, the value of \(b\) occurs, and in the fourth column, \(190a+210b\) appears, which is the number of times \(d\) appears in the list.
| \(d\) | \(a\) | \(b\) | \(190a+210b\) |
|---|---|---|---|
| \(1\) | \(3\) | \(2\) | \(990\) |
| \(2\) | \(3\) | \(2\) | \(990\) |
| \(3\) | \(3\) | \(2\) | \(990\) |
| \(4\) | \(1\) | \(4\) | \(1030\) |
| \(5\) | \(4\) | \(1\) | \(970\) |
| \(6\) | \(2\) | \(3\) | \(1010\) |
| \(7\) | \(2\) | \(3\) | \(1010\) |
| \(8\) | \(2\) | \(3\) | \(1010\) |
| \(9\) | \(5\) | \(0\) | \(950\) |
Finally, for \(d=0\), we already have \(100\) occurrences of \(0\) in the list coming from the perfect squares. Otherwise, we can use the exact same technique as above to count the number of \(0\)s in the list coming from integers that are not perfect squares. For \(d=0\), \(a=5\) and \(b=0\), so there are \(5(190)+0(210)+100=1050\) occurrences of the digit \(0\) in the list \(f(0),f(1),f(2),\dots,f(10^4-1)\).
We will now prove Claims 1 through 4.
Suppose \(k\) is a non-negative integer, \(r\) is \(0\), \(1\), \(2\), \(3\), or \(4\), and that \(d\) is a digit between \(0\) and \(9\) inclusive. We wish to count the number of integers \(m\) such that \(f(m)=d\) and \((5k+r)^2 < m < (5k+r+1)^2\). Specifically, we want to show that this number is either \(k\) or \(k+1\) depending on \(r\) and \(d\) in the way delineated in Claims 0 through 4.
The condition \((5k+r)^2 < m < (5k+r+1)^2\) is equivalent to \(5k+r < \sqrt{m} < 5k+r+1\), and this combined with \(f(m)=d\) (note that \(m\) is not a perfect square and that \(5k+r\) and \(5k+r+1\) are consecutive integers) is equivalent to \[5k+r+\frac{d}{10}<\sqrt{m}<5k+r+\frac{(d+1)}{10}.\] Since everything is non-negative, everything can be squared to get the equivalent chain of inequalities \[(5k+r)^2+\frac{2(5k+r)d}{10}+\frac{d^2}{100} < m < (5k+r)^2+\frac{2(5k+r)(d+1)}{10}+\frac{(d+1)^2}{100}.\] After some expansion, we have \[(5k+r)^2+kd+\frac{2rd}{10}+\frac{d^2}{100} < m < (5k+r)^2+kd+k+\frac{2r(d+1)}{10}+\frac{(d+1)^2}{100}.\] We are interested in how many integers \(m\) satisfy the chain of inequalities above. Since \((5k+r)^2+kd\) is an integer, the number of integers \(m\) satisfying the inequalities above is the same as the number of integers \(m'\) that satisfy \[\frac{2rd}{10}+\frac{d^2}{100}< m' <k+\frac{2r(d+1)}{10}+\frac{(d+1)^2}{100}\] and after combining fractions on the left and right, we get \[\frac{20rd+d^2}{100}<m'<k+\frac{20r(d+1)+(d+1)^2}{100} \tag{$*$}\]
Suppose \(\dfrac{20rd+d^2}{100}\) and \(\dfrac{20r(d+1)+(d+1)^2}{100}\) are both strictly between \(0\) and \(1\). Then the integers \(m'\) satisfying \((*)\) are precisely the integers \(1\) through \(k\). More generally, we will show that whether there are \(k\) or \(k+1\) integers depends on whether or not the quantities \(\dfrac{20rd+d^2}{100}\) and \(\dfrac{20r(d+1)+(d+1)^2}{100}\) are between the same pair of consecutive integers.
To give an idea of how the argument will proceed, consider the situation when \(r=1\) and \(d=4\). Then \(\dfrac{20rd+d^2}{100}=\dfrac{96}{100}\), but \(\dfrac{20r(d+1)+(d+1)^2}{100}=\dfrac{125}{100}\). Thus, \((*)\) becomes \[\frac{96}{100} < m' < k+ \frac{125}{100}\] The integers \(m'=1\) through \(m'=k+1\) satisfy these inequalities, for a total of \(k+1\) integers.
Observe that \[\begin{align*} \frac{20r(d+1)+(d+1)^2}{100}-\frac{20rd+d^2}{100} &= \frac{(20rd+20r+d^2+2d+1)-(20rd+d^2)}{100} \\ &= \frac{20r+2d+1}{100} \\ &\leq\frac{20(4)+2(9)+1}{100} \quad\quad \text{(since $r\leq 4$, $d\leq 19$)}\\ &=\frac{99}{100}\end{align*}\] This means the difference between \(\dfrac{20rd+d^2}{100}\) and \(\dfrac{20r(d+1)+(d+1)^2}{100}\) is less than \(1\), which leads to the following two possibilities.
Possibility 1: There is an integer \(a\) so that \[a\leq\dfrac{20rd+d^2}{100}<\dfrac{20r(d+1)+(d+1)^2}{100}\leq a+1\] In this case, the integers satisfying \((*)\) are \(a+1\), \(a+2\), \(a+3\), and so on through \(a+k\) for a total of \(k\) integers.
Possibility 2: There is some integer \(a\) with the property that \[a<\dfrac{20rd+d^2}{100}<a+1<\dfrac{20r(d+1)+(d+1)^2}{100}<a+2\] In this case, the integers satisfying \((*)\) are \(a+1\) through \(a+1+k\), for a total of \(k+1\) integers.
We have now shown that there will be \(k+1\) integers satisfying \((*)\) exactly when there is an integer strictly between \(\dfrac{20rd+d^2}{100}\) and \(\dfrac{20r(d+1)+(d+1)^2}{100}\). Multiplying through by \(100\), this is equivalent to there being a multiple of \(100\) strictly between \(20rd+d^2\) and \(20r(d+1)+(d+1)^2\)
The table below contains the values of \(20rd+d^2\) for every \(0\leq r\leq 4\) and \(0\leq d\leq 9\). The columns after the first are indexed by a value of \(d\) from \(0\) through \(9\) from left to right and the rows after the first are indexed by values of \(r\) from \(0\) through \(4\) from top to bottom. The cell in the row corresponding to \(r\) and the column corresponding to \(d\) contains \(20rd+d^2\). Cells are highlighted if there is a multiple of \(100\) between the value in the cell and the value in the cell immediately to its right.
| \(r\)/\(d\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 | 100 |
| 1 | 0 | 21 | 44 | 69 | 96 | 125 | 156 | 189 | 224 | 261 | 300 |
| 2 | 0 | 41 | 84 | 129 | 176 | 225 | 276 | 329 | 384 | 441 | 500 |
| 3 | 0 | 61 | 124 | 189 | 256 | 325 | 396 | 469 | 544 | 621 | 700 |
| 4 | 0 | 81 | 164 | 249 | 336 | 425 | 516 | 609 | 704 | 801 | 900 |
The highlighted cells correspond to pairs \((r,d)\) for which \(20rd+d^2\) is less than a multiple of \(100\) and \(20r(d+1)+(d+1)^2\) is greater than that multiple of \(100\). As noted above, these correspond to the pairs \((r,d)\) for which \(k+1\) integers satisfy \((*)\). For \(r=0\), we see no values of \(d\), which gives another proof of Claim 0. For \(r=1\), the values of \(d\) for which there are \(k+1\) integers are \(d=4\) and \(d=7\), which proves Claim 1. Continuing, the data in the table above verifies Claims 0 through 4.