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.
1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727
which is
979291172255376750081652821559640563801792871084643
divided by
692463428657900307544320387485120303323686251920582
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))
Next j
End If
Next i
Debug.Print Answer; ” Time:”; Timer – T
End Sub
Function JSqrRoot(n As Long, NumDigits As Long, Optional Dec) As String
‘http://www.shef.ac.uk/~pm1afj/maths/jarvisspec02.pdf
‘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)
Exit Function
End If
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
Else
SAT = False
End If
If SAT Then
strA = SubAsStrings(strA, strB)
strB = AddAsStrings(strB, “10”)
Else
strA = strA & “00”
strB = Left(strB, Len(strB) – 1) & “05”
End If
Loop
JSqrRoot = strB
If Dec Then
i = InStr(1, CStr(Num), “.”)
JSqrRoot = Left(JSqrRoot, i – 1) & “.” & Right(JSqrRoot, Len(JSqrRoot) – i + 1)
End If
End Function
Function SubAsStrings(ByVal Term1 As String, ByVal Term2 As String) As String
‘Uses “method of nines’-complement”
‘http://en.wikipedia.org/wiki/Method_of_complements
‘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
End If
For c = 1 To Len(Term2)
Complement = Complement & (9 – CLng(Mid(Term2, c, 1)))
Next c
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)
Wend
SubAsStrings = Difference
End Function
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.
…mrt
Interesting problem. Partly prompted by Project Euler, I’m starting to learn Python, and I suspect that this problem would be dead simple in Python, but then it wouldn’t be interesting any more. I’ll have a go at it with arrays of longs instead of strings and see how that goes.
I might have a go at a spreadsheet based solution as well.
OK, did it with arrays. I was tempted to use an array of 10 digit integers, to save memory, but it makes it much simpler to have one digit for each array location.
Fairly straightforward with the help of Prof. Jarvis. Run time = about 0.3 sec :)
Function SqRtI(val As Long, Dig As Double) As Variant
Dim AA() As Long, BA() As Long, Digp As Long
Dim SumDig(1 To 1, 1 To 2) As Double
Dim i As Long, j As Long, k As Long, NumDig As Long
Dim BigVal As Long, dStep As Long, n As Long
SumDig(1, 2) = Timer
Digp = Dig + 10
For n = 2 To val
If n ^ 0.5 .NE. Int(n ^ 0.5) Then
ReDim AA(1 To Digp)
ReDim BA(1 To Digp)
AA(1) = n * 5
i = 1
‘ Split AA(1) into digits
Do While AA(i) .GT. 9
AA(i + 1) = AA(i)
AA(i) = AA(i) Mod 10
AA(i + 1) = Int(AA(i + 1) / 10)
i = i + 1
Loop
BA(1) = 5
j = 1
Do While j .LT=. Dig + 1
‘ Check if a .GT=. b
If i = j Then
k = i
Do While AA(k) = BA(k)
k = k – 1
Loop
If AA(k) .GT=. BA(k) Then BigVal = 1 Else BigVal = 2
Else
If i .GT. j Then BigVal = 1 Else BigVal = 2
End If
If BigVal = 1 Then
‘ a .GT=. b
For k = 1 To i
AA(k) = AA(k) – BA(k)
If AA(k) .LT. 0 Then
AA(k) = AA(k) + 10
AA(k + 1) = AA(k + 1) – 1
End If
Next k
Do While AA(i) = 0
i = i – 1
Loop
BA(2) = BA(2) + 1
If j = 1 Then j = 2
If BA(2) .GT. 9 Then
k = 2
Do While BA(k) .GT. 9
BA(k + 1) = BA(k)
BA(k) = BA(k) Mod 10
BA(k + 1) = Int(BA(k + 1) / 10)
k = k + 1
Loop
If k .GT. j Then j = k
End If
Else
‘ b .GT. a
For k = i + 2 To 3 Step -1
AA(k) = AA(k – 2)
Next k
AA(2) = 0
AA(1) = 0
i = i + 2
For k = j + 1 To 3 Step -1
BA(k) = BA(k – 1)
Next k
BA(2) = 0
j = j + 1
End If
Loop
‘ Find sum of digits
For j = Dig + 2 To Dig – 97 Step -1
SumDig(1, 1) = SumDig(1, 1) + BA(j)
Next j
End If
Next n
SumDig(1, 2) = Timer – SumDig(1, 2)
SqRtI = SumDig
End Function
Hi Doug –
If Prof Jarvis ever reads this thread, I apologize for misspelling his name above.
I’m not going to learn Python, I going to get a better handle on arrays. That’s quite (!) a speed jump.
Have you done #72 yet? My GCD method looks like it’d still be running into next week if I let it, and my recursive solution exhausts the stack somewhere north on 100,000. Using data points of D=10, 100, 1000, 10000, and 100,000, the answer is approximately 0.30*(D^1.99), or around 3 billion for D=10^6. Not quite good enough. I can’t noodle out the trick.
…mrt
Michael – arrays are definitely worth getting a good handle on.
I haven’t looked at #72, and I don’t have a lot of time spare at the moment, but if I do find time for it, and if I can solve it, I’ll definitely report back here.
By the way, 0.2*((10^6)^1.99) is much closer to 300 billion than 3 billion :)
Doug
Hi Doug –
So it is! But what’s two orders of magnitude ;-)
I just wish Euler would accept 298,714,475,488.1710 as an answer. That’s what I get from the trendline coefficients. Ought to be good enough!
…mrt