Project Eulers problem 16 in visual basic. Sum of digits in the number 2^1000

Question

Project Euler's problem 16: 2^(15) = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^(1000)?

I have been trying to do this problem for a few days now and i just can't figure out how to get vb.net 2008 to recognize anywhere near that large a number. I have seen in other posts that some software like java has the integer type BigNumber or BigInteger but i cant find anything like that in visual basic. I'm running into this problem a lot using Visual Basic. I also can't seem to find any of the standard upper level math features in visual basic such as factorials and a few others that i can't remember but couldn't find under the math feature. any suggestions? (Sorry let me rephrase, any suggestions on how to do this stuff without switching to a different programming language.)

Answer 1

There are several BigInteger libraries that are freely available which you can use.

• http://msdn.microsoft.com/en-us/magazine/cc163696.aspx
• http://www.codeproject.com/KB/cs/biginteger.aspx?df=100&forumid=4524&exp=0&fr=26

In this case the limitations are not necessarily the language. Visual Basic, outside of basic math operations, largely depends on the BCL for functionality. This is true of most languages which run on the CLR (including C#). In most cases though, there are libraries available which you can use to augment the functionality of the framework.

Answer 2

I haven't tried it but there seems to be a Big Integer construct for Visual Basic.

Answer 3

here's the function I wrote, it's not so difficult to do your own implementation of a BigInteger purely for this purpose (very difficult to make it efficient and versatile however, but that's what libraries are for)

Public Shared Function Problem16(ByVal power As Integer) As String

    Dim digits As Integer = CInt(Int(power * Log10(2)))

    Dim number(digits) As Byte
    number(digits) = 1

    For i As Integer = 1 To power
        Dim carry As Byte = 0
        For j As Integer = digits To 0 Step -1
            number(j) <<= 1
            number(j) += carry
            If number(j) > 9 Then
                carry = number(j) \ CByte(10)
                number(j) -= CByte(10)
            Else
                carry = 0
            End If
        Next
    Next

    Dim result As Integer
    For i As Integer = 0 To digits
        result += number(i)
    Next
    Return result.ToString

End Function