Detailed mathematical approach

Problem Summary

Among the integers \(1,2,\dots,100\), only the non-squares matter, because perfect squares have rational square roots and are excluded by the statement. For each irrational \(\sqrt{n}\), we read the first 100 digits of its decimal expansion, counting the digit before the decimal point, sum those 100 digits, and then add the 90 resulting digit sums.

The challenge is precision rather than size. Ordinary floating-point arithmetic cannot reliably preserve 100 decimal digits, so the problem has to be reformulated in exact integer terms or handled with guarded arbitrary-precision decimal arithmetic.

Mathematical Approach

The key object is the 100-digit prefix of \(\sqrt{n}\) after removing the decimal point. Since every relevant \(n\) satisfies \(1<n<100\), each irrational square root lies between 1 and 10, so the required block is always one integer digit followed by 99 fractional digits.

Turn the decimal prefix into an integer

For a fixed non-square \(n\), define

$P_k=\left\lfloor 10^{k-1}\sqrt{n}\right\rfloor \qquad (k\ge 1).$

Then \(P_1\) is the integer part of \(\sqrt{n}\), \(P_2\) is the first two digits with the decimal point removed, and in general \(P_{100}\) is exactly the 100-digit string required by the problem. If \(s(n)\) denotes the digit sum of \(P_{100}\), then the final quantity is

$\sum_{\substack{1\le n\le 100\\ n\notin\{1,4,9,16,25,36,49,64,81,100\}}} s(n).$

The longhand square-root invariant

Set

$R_k=10^{2k-2}n-P_k^2.$

Because \(P_k=\lfloor 10^{k-1}\sqrt{n}\rfloor\), we always have

$P_k^2\le 10^{2k-2}n < (P_k+1)^2,$

so \(R_k\) is a nonnegative remainder. To append the next decimal digit, write

$P_{k+1}=10P_k+x,\qquad x\in\{0,1,\dots,9\},$

and require \(P_{k+1}^2\le 10^{2k}n\). Expanding the square gives

$100P_k^2+(20P_k+x)x\le 100(P_k^2+R_k),$

which is equivalent to

$ (20P_k+x)x\le 100R_k. $

Therefore the next correct digit is the largest \(x\in\{0,\dots,9\}\) satisfying this inequality.

The recurrence used by the exact method

Once that maximal digit \(x\) is chosen, the state updates to

$P_{k+1}=10P_k+x,$

$R_{k+1}=10^{2k}n-P_{k+1}^2=100R_k-(20P_k+x)x.$

This is the classical digit-by-digit square-root algorithm. In the usual handwritten interpretation, each step brings down the next pair \(00\), tests the candidate digits from 9 down to 0, subtracts the best probe, and appends the chosen digit to the growing root prefix.

Worked example: the first digits of \(\sqrt{2}\)

Start with \(n=2\). The first digit is \(1\) because \(1^2\le 2<2^2\). Hence \(P_1=1\) and \(R_1=2-1^2=1\).

For the next digit, choose the largest \(x\) such that

$ (20\cdot 1+x)x\le 100. $

Here \(x=4\) works because \(24\cdot 4=96\), while \(x=5\) fails because \(25\cdot 5=125\). So \(P_2=14\) and \(R_2=100\cdot 1-96=4\).

Repeat once more: choose the largest \(x\) with

$ (20\cdot 14+x)x\le 400. $

Now \(x=1\) works and \(x=2\) fails, so \(P_3=141\). Therefore the expansion begins \(1.41\dots\), exactly as expected. Continuing this process to 100 digits gives a digit sum of 475 for \(\sqrt{2}\), which is the checkpoint used by the exact implementation.

Why the decimal implementations also work

The Python and Java implementations compute \(\sqrt{n}\) directly with arbitrary-precision decimal arithmetic instead of reproducing the longhand recurrence. They request 110 significant digits, remove the decimal point, and keep the first 100 characters. Those extra guard digits keep the wanted 100-digit prefix away from the rounding boundary, so the extracted block matches the same mathematical object \(P_{100}\).

How the Code Works

All three implementations loop over \(n=1,2,\dots,100\), detect perfect squares with an ordinary integer square root, and skip them because the problem only counts irrational roots.

The C++ implementation follows the exact recurrence above. Its state consists of a current prefix \(P\) and a current remainder \(R\). It performs exactly 100 rounds, multiplies the remainder by 100 after the first digit, searches the next digit from 9 downward using the probe \((20P+d)d\), updates the remainder, appends the chosen digit, and finally sums the digits of the resulting 100-digit integer.

The Python and Java implementations instead rely on arbitrary-precision decimal square roots. They set the working precision to 110 digits, compute \(\sqrt{n}\), convert the result to a plain decimal string, delete the decimal point, take the first 100 digits, and add them. The mechanics differ, but the target is identical: the first 100 digits of \(\sqrt{n}\) written without the decimal point.

Complexity Analysis

Let \(D\) be the number of requested digits and \(L\) the upper limit for \(n\). The exact digit-by-digit method performs \(D\) rounds for each irrational \(n\), and each round tests at most 10 candidate digits. Since the intermediate integers have \(O(D)\) decimal digits, a natural bound is \(O(LD^2)\) elementary digit work with \(O(D)\) memory.

For this problem, \(L=100\) and \(D=100\), so the computation is tiny. The decimal-square-root versions delegate the work to optimized arbitrary-precision libraries at roughly 110-digit precision and are also easily fast enough. The important point is that every implementation avoids binary floating-point shortcuts and keeps enough precision to recover the exact 100-digit prefixes.

Footnotes and References

1. Problem page: Project Euler 80
2. Square root: Wikipedia - Square root
3. Digit-by-digit extraction: Wikipedia - Methods of computing square roots
4. Arbitrary-precision arithmetic: Wikipedia - Arbitrary-precision arithmetic
5. Digit sum: Wikipedia - Digit sum