Euler Problem 80

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.

Sub Problem_080()
   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

Posted in Uncategorized

5 thoughts on “Euler Problem 80

  1. 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.

  2. 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

  3. 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

  4. 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

  5. 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


Posting code? Use <pre> tags for VBA and <code> tags for inline.

Leave a Reply

Your email address will not be published.