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