What is the least number of square roots needed to express $\sqrt{1}+\sqrt{2}+\cdots+\sqrt{100}$?

What is the least number of square roots needed to express $\sqrt{1}+\sqrt{2}+\cdots+\sqrt{100}$ if it must be expressed in the form $a+b\sqrt{c}+d\sqrt{e}+\cdots$ where $a,b,c,d,e,\ldots$ are all integers?

Solution

In order to find the least number of square roots, we must express this number in simplest form. Thus, the numbers in the radicand that are in simplest form that will get counted are numbers with at most one of each prime factor. Then the question simplifies to "How many numbers are there between $1-100$ with at most one of each prime factor?

There are a few ways to proceed from here. I think the best way would be to complementary count. Then we are looking for numbers with at least $2$ factors of each prime, thus multiples of perfect squares. Our perfect squares are $1,4,9,16,25,36,49,64,81$. Thus we have $1+25+11-2+3+2 = 40$ such numbers by the principle of inclusion-exclusion. Thus, the answer is $100-40 = 60$.

Question

How is it that the number being expressed in simplest form will give the least number of radicals? The solution seems to imply that but why is it true?

• You mean expressing it as $a + b \sqrt{c} + d\sqrt{e} + \cdots$ where $a,b,c,\dots \in \mathbb N$ right? Because otherwise the question would be very problematic. – ThePortakal Jan 8 '16 at 3:45
• Yes, of course. Otherwise I wouldn't technically have to use any square roots. – user19405892 Jan 8 '16 at 3:45
• I added the extra condition in the question so that doesn't work as $3+\sqrt{3}+\sqrt{5}$ is not an integer. By least number of square roots, I mean the number of square root symbols. So $\sqrt{3}+\sqrt{3}$ would be two square roots while $2\sqrt{3}$ would be one. – user19405892 Jan 8 '16 at 4:07
• Why are you copying the exact solution here? – GohP.iHan Jan 9 '16 at 11:04
• @GohP.iHan It is actually my solution. – user19405892 Jan 9 '16 at 13:44

The square root of each square-free number less than $100$ contributes a term to the sum with a surd (a square root that cannot be simplified out), but all the square multiples of the number under the square root ($4$ times, $9$ times, $16$ times, etc.) can be combined with the term for the original square-free number, so they do not contribute any additional terms. For example,

$$\sqrt{11} + \sqrt{44} + \sqrt{99} = 6\sqrt{11}.$$

One way to count the integers whose square roots do not contribute new surds to the sum is as follows:

• $10$ perfect squares in the range $1$ to $100$, inclusive;
• $6$ cases of twice a perfect square in the range $8$ to $98$, inclusive;
• $4$ cases of $3$ times a perfect square in the range $12$ to $75$, inclusive;
• $3$ cases of $5$ times a perfect square in the range $20$ to $80$, inclusive;
• $3$ cases of $6$ times a perfect square in the range $24$ to $96$, inclusive;
• $6$ cases including $2$ cases each of $7$ times a perfect square, $10$ times a perfect square, and $11$ times a perfect square in the range $28$ to $99$, inclusive;
• $8$ cases including $13 \times 4$, $14 \times 4$, $15 \times 4$, $17 \times 4$, $19 \times 4$, $21 \times 4$, $22 \times 4$, and $23 \times 4$.

These add up to $40$ terms of the original sum that either are integers or can be combined with other terms, leaving $60$ unique surds. This is the same as your result, of course.

Here is the sum completely worked out, confirming that $60$ square roots are needed:

\begin{align} \sqrt1 + & \sqrt2 + \cdots + \sqrt{100} \\ =& \quad 1 + \sqrt2+\sqrt3 + 2 + \sqrt5+\sqrt6+\sqrt7 + 2\sqrt2 + 3 + \sqrt{10} \\ & + \sqrt{11} + 2\sqrt3 + \sqrt{13} + \sqrt{14} + \sqrt{15} + 4 + \sqrt{17} + 3\sqrt2 + \sqrt{19} + 2\sqrt{5} \\ & + \sqrt{21} + \sqrt{22} + \sqrt{23} + 2\sqrt6 + 5 + \sqrt{26} + 3\sqrt3 + 2\sqrt7 + \sqrt{29} + \sqrt{30} \\ & + \sqrt{31} + 4\sqrt2 + \sqrt{33} + \sqrt{34} + \sqrt{35} + 6 + \sqrt{37} + \sqrt{38} + \sqrt{39} + 2\sqrt{10} \\ & + \sqrt{41} + \sqrt{42} + \sqrt{43} + 2\sqrt{11} + 3\sqrt5 + \sqrt{46} + \sqrt{47} + 4\sqrt3 + 7 + 5\sqrt2 \\ & + \sqrt{51} + 2\sqrt{13} + \sqrt{53} + 3\sqrt6 + \sqrt{55} + 2\sqrt{14} + \sqrt{57} + \sqrt{58} + \sqrt{59} + 2\sqrt{15} \\ & + \sqrt{61} + \sqrt{62} + 3\sqrt7 + 8 + \sqrt{65} + \sqrt{66} + \sqrt{67} + 2\sqrt{17} + \sqrt{69} + \sqrt{70} \\ & + \sqrt{71} + 6\sqrt2 + \sqrt{73} + \sqrt{74} + 5\sqrt3 + 2\sqrt{19} + \sqrt{77} + \sqrt{78} + \sqrt{79} + 4\sqrt5 \\ & + 9 + \sqrt{82} + \sqrt{83} + 2\sqrt{21} + \sqrt{85} + \sqrt{86} + \sqrt{87} + 2\sqrt{22} + \sqrt{89} + 3\sqrt{10} \\ & + \sqrt{91} + 2\sqrt{23} + \sqrt{93} + \sqrt{94} + \sqrt{95} + 4\sqrt6 + \sqrt{97} + 7\sqrt2 + 3\sqrt{11} + 10 \\ =& \quad 55 + 28\sqrt2 + 15\sqrt3 + 10\sqrt5 + 10\sqrt6 + 6\sqrt7 + 6\sqrt{10} \\ & + 6\sqrt{11} + 3\sqrt{13} + 3\sqrt{14} + 3\sqrt{15} + 3\sqrt{17} + 3\sqrt{19} \\ & + 3\sqrt{21} + 3\sqrt{22} + 3\sqrt{23} + \sqrt{26} + \sqrt{29} + \sqrt{30} \\ & + \sqrt{31} + \sqrt{33} + \sqrt{34} + \sqrt{35} + \sqrt{37} + \sqrt{38} \\ & + \sqrt{39} + \sqrt{41} + \sqrt{42} + \sqrt{43} + \sqrt{46} + \sqrt{47} \\ & + \sqrt{51} + \sqrt{53} + \sqrt{55} + \sqrt{57} + \sqrt{58} + \sqrt{59} \\ & + \sqrt{61} + \sqrt{62} + \sqrt{65} + \sqrt{66} + \sqrt{67} + \sqrt{69} \\ & + \sqrt{70} + \sqrt{71} + \sqrt{73} + \sqrt{74} + \sqrt{77} + \sqrt{78} \\ & + \sqrt{79} + \sqrt{82} + \sqrt{83} + \sqrt{85} + \sqrt{86} + \sqrt{87} \\ & + \sqrt{89} + \sqrt{91} + \sqrt{93} + \sqrt{94} + \sqrt{95} + \sqrt{97} \\ \end{align}

• How do you know that we can't use nested radicals to reduce the number of radicals used? – GohP.iHan Jan 9 '16 at 11:03
• @GohP.iHan The problem statement stipulates that the answer must be in the form $a+b\sqrt{c}+d\sqrt{e}+\cdots$ where $a,b,c,d,e,\ldots$ are all integers. – David K Jan 9 '16 at 13:37
• Ohhh my bad... the author had a different question when I first viewed it. Thank you!! – GohP.iHan Jan 9 '16 at 13:51