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.
5 thoughts on “Euler Problem 80”
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
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
If AA(k) .GT=. BA(k) Then BigVal = 1 Else BigVal = 2
If i .GT. j Then BigVal = 1 Else BigVal = 2
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
Do While AA(i) = 0
i = i – 1
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
If k .GT. j Then j = k
‘ b .GT. a
For k = i + 2 To 3 Step -1
AA(k) = AA(k – 2)
AA(2) = 0
AA(1) = 0
i = i + 2
For k = j + 1 To 3 Step -1
BA(k) = BA(k – 1)
BA(2) = 0
j = j + 1
‘ Find sum of digits
For j = Dig + 2 To Dig – 97 Step -1
SumDig(1, 1) = SumDig(1, 1) + BA(j)
SumDig(1, 2) = Timer – SumDig(1, 2)
SqRtI = SumDig
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.
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 :)
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!
Posting code? Use <pre> tags for VBA and <code> tags for inline.