Euler Problem 80 asks:
It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.
The square root of two is 1.41421356237309504880…, and the digital sum of the first one hundred decimal digits is 475.
For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.
The first thing I wanted to know to solve this problem was what the square root of 2 was to 100 places. I wasn’t getting the right sum. I found it here.
When I summed the decimal digits, I got 481, not 475. But if I drop the right-hand 7 and add the left-of-the-decimal 1, that’s a down-spot of 6. Euler wants the sum of the first 100 digits, not the first 100 after the decimal.
To make the calulation I wanted an algorithm that computed square roots as strings. I found that here. The author says of his Japanese method
It is an amusing exercise to program a computer to do this algorithm, at least if n is an integer, and because only integer additions and subtractions are used, there are no errors due to floating-point arithmetic. On the other hand, it is necessary to use more complicated storage techniques (strings or arrays) to store the values of a and b as they get larger and larger, and the algorithm will get slower and slower at producing successive digits.
Amusing? I’m not so sure. To implement the Japanese method in strings, it took me a while to find the equivalent of “a greater than or equal to b” where a and b are string representations of numbers. I ended up with:
- If the length of a is greater than the length of b, then a is greater than b
- If the length of a is less than the length of b, then a is less than b
- If the length of a equals the length of b then do a string-comparison
Don’t know why that took as long as it did.
I also needed an algorithm for subtracting strings. Rather than write a “borrowing” routine, I used the “method of nines’-complement” found here on Wikipedia.
When it was all done, the code runs in 11 seconds.
Dim i As Long, j As Long
Dim TEMP As String
Dim Answer As Long, T As Single
T = Timer
For i = 2 To 99 ‘ Square Roots of 1, 100 not needed
If Sqr(i) != Int(Sqr(i)) Then
TEMP = JSqrRoot(i, 110, False) ‘a little padding for convergence
For j = 1 To 100
Answer = Answer + CLng(Mid(TEMP, j, 1))
Debug.Print Answer; ” Time:”; Timer – T
Function JSqrRoot(n As Long, NumDigits As Long, Optional Dec) As String
‘Long Integer implementation only
‘Dec = True returns with decimal point
Dim strA As String, strB As String
Dim SAT As Boolean, i As Long, Num As Double
strA = CStr(5 * n)
strB = “5”
If IsMissing(Dec) Then Dec = True
Num = Sqr(n)
If Int(Num) = Num Then
JSqrRoot = CStr(Num)
Do While Len(strB) LT NumDigits
If Len(strA) GT Len(strB) then ‘a GT b
SAT = True
ElseIf Len(strA) LT Len(strB) Then ‘ b GT a
SAT = False
ElseIf strA GTE strB Then ‘do string comparison for equal lengths
SAT = True
SAT = False
If SAT Then
strA = SubAsStrings(strA, strB)
strB = AddAsStrings(strB, “10”)
strA = strA & “00”
strB = Left(strB, Len(strB) – 1) & “05”
JSqrRoot = strB
If Dec Then
i = InStr(1, CStr(Num), “.”)
JSqrRoot = Left(JSqrRoot, i – 1) & “.” & Right(JSqrRoot, Len(JSqrRoot) – i + 1)
Function SubAsStrings(ByVal Term1 As String, ByVal Term2 As String) As String
‘Uses “method of nines’-complement”
‘Term1 GT Term2 GT 0…ie. postive integers only
Dim Difference As String
Dim Complement As String
Dim Sum As String
Dim c As Long
If Len(Term1) GT Len(Term2) Then
Term2 = String(Len(Term1) – Len(Term2), “0”) & Term2
For c = 1 To Len(Term2)
Complement = Complement & (9 – CLng(Mid(Term2, c, 1)))
Sum = AddAsStrings(Term1, Complement)
Sum = AddAsStrings(Sum, “1”)
Difference = Right(Sum, Len(Sum) – 1)
While Left(Difference, 1) = “0”
Difference = Right(Difference, Len(Difference) – 1)
SubAsStrings = Difference
The usual angle bracket adjustments have been made above. The AddAsStrings function has been put up before. Dr Jervis’ Japanese method requires you to independently place the decimal point in the square root. I made that optional, and set it to false to accomodate Euler’s way of counting.