Project Euler - Let's do Math/Programming Challenges

Monoxide · November 2007

Project Euler
click it, it's an url dummy

What is Project Euler?

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

I've started looking through these after reading the thread about it on Something Awful and they seem pretty neat. It's a great way to get some programming practice in or get some practice in while learning a new language. Since I've decided to toy with Python, I'll be trying to do these with that, but you can use any language you like.

Veegeezee · November 2007

Holy crap, these look fun.

0blique · November 2007

Hmmm, looks pretty interesting. I'll have a look at solving some of these when I get some time.

Smasher · November 2007

I did the first 63 or so a while back, but I think I was at the point where my math skills were having trouble keeping up with the later problems. Good mix of math and programming though; I may have to pick this up again.

Jasconius · November 2007

How are we comparing our answers, by execution time? Fewest lines?

Oh, maybe it's not a contest. D'oh.

These are pretty cool, but shit, I have a too much real programming to do already.

I'm dreaming about calling methods and objects every now and then.

Sheesh.

Cold Koala · November 2007

The way me and my roommate handle it is this: Execution time is paramount. Elegance and shortness of code do count for style points sometimes. If you do it with pencil and paper, you are a hardass, but if it takes you longer to do than the other guy takes to write, compile, and run his code, then you lose.

Jragghen · November 2007

Hmm. This looks interesting. Will have to investigate further tomorrow.

Edit: This finally prompted me to download an environment at home, because while it'd be easier (and I'd be more in the mindset) to do it at work, I really shouldn't.

Cranked out the first few. I'm being nowhere near the most efficient manner possible, but it's more an effort to make sure I remember how to do some of this stuff (both math and programming-wise).

Lewisham · November 2007

Can we do these in Haskell? Haskell seems like the perfect thing for these.
The first one needs modulus stuff! Yay!

Smasher · November 2007

You can use whatever language(s) you want. I used c++ for most of them, but ended up going with python for a few where I had to deal with really large numbers and didn't want to write my own integer class.

Lewisham · November 2007

OK, so I went ahead and did some of these in Haskell.

Problem 3 was a cheat, because I didn't know how to specify whether a number was prime. Now I do! I'm using these to learn maths and Haskell at the same time. I did problem 1 all by myself, found out it was horribly slow, then used the clever Haskell way on the Internet. Again, learning is fun! Problem 1 and 7 I did all by myself. I like Problem 7 a LOT, as it really illustrates how much power Haskell's infinite lists can buy you. It's basically a one-liner, albeit with an expensive boolean test.

module Euler
    where

-- Support functions
sqrtFloor :: Integer -> Integer
sqrtFloor n = floor $ sqrt $ fromIntegral n

fib n = fibs !! n
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

_isPrime n x y | x > y = True
               | n `mod` x == 0 = False
               | otherwise  = _isPrime n (x + 1) y
               
isPrime n | n < 2 = False
          | otherwise  = _isPrime n 2 (sqrtFloor n)

primeFactors n = [x | x <- [1..(sqrtFloor n)], n `mod` x == 0, isPrime x]
primeNumbers = [x | x <- [1..], isPrime x]

-- Answers
p1 [] = 0
p1 (x:xs) | (x `mod` 3 == 0) || (x `mod` 5 == 0) = x + p1 xs
          | otherwise = x + p2 xs

p2 [] = 0
p2 (x:xs) | x > 1000000 = 0
          | (x `mod` 2 /= 0) = p2 xs
          | otherwise = x + p2 xs
          
p3 n = last (primeFactors n)

-- Take one off the value to get the index
p7 n = primeNumbers !! (n - 1)

Haskell gurus: I require your help!

primeNumbers = [x | x <- [1..], isPrime x]
primesUpto n = [x | x <- [1..n], isPrime x]

Is there a way I can merge these into one function so that it runs infinitely if not passed n, or up to the sequence if passed a limit?

EDIT: Answer - primesUpto n = takeWhile (< n) primeNumbers

Yayyyy.

Lewisham · November 2007

I've become addicted to this shit.

Problem 6 was so easy in Haskell.

square n = n * n
p6 x = abs (sum (map square x) - square (sum x))

Mr_Anonymous · November 2007

I hope I can java these with only two months of java under my belt, because this crap looks fun...

Lewisham · November 2007

Expressing the solutions in Java isn't hard, but you'd need the math skills to understand what you're doing.

I have to sit and think about pretty much every line of Haskell I write, but it means that the code is cleaner, and better for it. You can't half ass a Haskell implementation of anything.

Randall_Flagg · November 2007

I like doing these in scheme, mainly because scheme requires basically no knowledge of programming at all

I guess I'll probably switch to C for some of the later ones, especially the ones that require you to read ridiculous long .txt files

Nibble · November 2007

Lewisham wrote: »
OK, so I went ahead and did some of these in Haskell.

Problem 3 was a cheat, because I didn't know how to specify whether a number was prime. Now I do! I'm using these to learn maths and Haskell at the same time. I did problem 1 all by myself, found out it was horribly slow, then used the clever Haskell way on the Internet. Again, learning is fun! Problem 1 and 7 I did all by myself. I like Problem 7 a LOT, as it really illustrates how much power Haskell's infinite lists can buy you. It's basically a one-liner, albeit with an expensive boolean test.
module Euler
    where

-- Support functions
sqrtFloor :: Integer -> Integer
sqrtFloor n = floor $ sqrt $ fromIntegral n

fib n = fibs !! n
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

_isPrime n x y | x > y = True
               | n `mod` x == 0 = False
               | otherwise  = _isPrime n (x + 1) y
               
isPrime n | n < 2 = False
          | otherwise  = _isPrime n 2 (sqrtFloor n)

primeFactors n = [x | x <- [1..(sqrtFloor n)], n `mod` x == 0, isPrime x]
primeNumbers = [x | x <- [1..], isPrime x]

-- Answers
p1 [] = 0
p1 (x:xs) | (x `mod` 3 == 0) || (x `mod` 5 == 0) = x + p1 xs
          | otherwise = x + p2 xs

p2 [] = 0
p2 (x:xs) | x > 1000000 = 0
          | (x `mod` 2 /= 0) = p2 xs
          | otherwise = x + p2 xs
          
p3 n = last (primeFactors n)

-- Take one off the value to get the index
p7 n = primeNumbers !! (n - 1)

Maybe I just don't get Haskell, but I count 22 lines.

Lewisham · November 2007

Nibble wrote: »

Maybe I just don't get Haskell, but I count 22 lines.

That code has the answers to 4-5 questions. Admittedly, problem 7 builds on things from the other problems, but my point was that you can take things and adapt them very quickly. I did actually solve a problem in one line (the one about finding the difference between the sum of squares of all numbers in a sequence and the square of the sum of the numbers in the sequence), but I left it at work

Linden · November 2007

God, I spent far too long on problem 5 (I've done these in Haskell also – 1 through 7 at present, and I have some more time soonish)

I ended up doing it by hand, then realised that there's an lcm function in the Prelude. At that point, of course, it was just a fold away.

Your solution to 7 is much briefer than mine, although that's probably because I just grabbed a prime list I already had that was designed for efficiency as much as readability (there are two lists building on each other, and two helper functions that might well exist elsewhere)

If you just want clarity (execution speed is abysmal) then this isn't bad.

primes :: [Integer]
primes = sieve [2..]
	where
		sieve (p:xs) = p : sieve [ x | x <- xs, x `mod` p > 0 ]

Technicality · November 2007

I cheated on number 3. Didn't particularly want to muck about with primes so just calculated the big factors and looked a few of them up. Looking at number 7 though, it might have helped to have done a bit of groundwork

These are good stuff though, great find!

Lewisham · November 2007

Linden wrote: »
If you just want clarity (execution speed is abysmal) then this isn't bad.
primes :: [Integer]
primes = sieve [2..]
	where
		sieve (p:xs) = p : sieve [ x | x <- xs, x `mod` p > 0 ]

I did that for the question about the sum of the primes less than a million (question 10?).

It took 2 hours on an Intel Mac

But my Math is not good enough to do it more efficently.

jackal · November 2007

I should probably be using C# 3.0 for this, but problem 10 in VB.Net 2005:

I could have written this faster if I just used a list instead of an IEnumerable. Execution time is around 3 seconds. This is obviously not optimal at all.

I know it seems like a lot of code, but most of it will be reused a lot.

Private Sub uxProblem10_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem10.Click
    Dim test As New NaturalNumbersCollection
    Dim primes As New PredicatedCollection(Of Integer)(test, AddressOf Factor.IsPrime)
    Dim sum As Long

    For Each tempInteger As Integer In primes
        If tempInteger >= 1000000 Then
            Exit For
        End If
        sum = sum + tempInteger
    Next
    uxOutput.Text = sum.ToString
End Sub

Public Class Factor
    'Snip

    Public Shared Function IsPrime(ByVal value As Integer) As Boolean
        Dim factorList As New Collections.Generic.List(Of Long)
        Dim square As Long

        If value < 2 Then
            Return False
        End If
        If value = 2 Then
            Return True
        End If

        square = CInt(Math.Ceiling(Math.Sqrt(value)))
        For tempNumber As Long = 2 To square
            If value Mod tempNumber = 0 Then
                Return False
            End If
        Next

        Return True
    End Function
End Class

'I could avoid this trouble by using lists for everything instead of
'Enumerables, or I could just use Orcas.
Public Class PredicatedCollection(Of T)
    Implements IEnumerable
    Implements IEnumerator

    Private _predicate As Predicate(Of T)
    Private _internalCollection As IEnumerator

    Public Sub New(ByVal internalCollection As IEnumerator, ByVal predicate As Predicate(Of T))
        _internalCollection = internalCollection
        _predicate = predicate
    End Sub

    Public Function GetEnumerator() As System.Collections.IEnumerator Implements System.Collections.IEnumerable.GetEnumerator
        Return Me
    End Function

    Public ReadOnly Property Current() As Object Implements System.Collections.IEnumerator.Current
        Get
            Return _internalCollection.Current
        End Get
    End Property

    Public Function MoveNext() As Boolean Implements System.Collections.IEnumerator.MoveNext
        _internalCollection.MoveNext()
        Do While _predicate(DirectCast(_internalCollection.Current, T)) = False
            If Not _internalCollection.MoveNext Then Return False
        Loop
        Return True
    End Function

    Public Sub Reset() Implements System.Collections.IEnumerator.Reset
        Throw New NotSupportedException
    End Sub
End Class

Public Class NaturalNumbersCollection
    Implements IEnumerable
    Implements IEnumerator

    Private _current As Integer = 0

    Public Function GetEnumerator() As System.Collections.IEnumerator Implements System.Collections.IEnumerable.GetEnumerator
        Return Me
    End Function

    Public ReadOnly Property Current() As Object Implements System.Collections.IEnumerator.Current
        Get
            Return _current
        End Get
    End Property

    Public Function MoveNext() As Boolean Implements System.Collections.IEnumerator.MoveNext
        _current += 1
        Return True
    End Function

    Public Sub Reset() Implements System.Collections.IEnumerator.Reset
        Throw New NotSupportedException
    End Sub
End Class

Problem 1:

    Private Sub uxProblem1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem1.Click
        Dim naturals As New NaturalNumbersCollection
        Dim modThreeFive As New PredicatedCollection(Of Integer)(naturals, AddressOf modulusThreeFive)
        Dim sum As Integer

        For Each tempNumber As Integer In modThreeFive
            If tempNumber >= 1000 Then
                Exit For
            End If
            sum = sum + tempNumber
        Next
        uxOutput.Text = sum.ToString
    End Sub

    Public Function modulusThreeFive(ByVal value As Integer) As Boolean
        Return (value Mod 3 = 0) Or (value Mod 5 = 0)
    End Function

Problem 2:

Private Sub uxProblem2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem2.Click
        Dim fibs As New FibonacciNumbersCollection
        Dim evenFibs As New PredicatedCollection(Of Integer)(fibs, AddressOf isEven)
        Dim sum As Integer

        For Each tempInteger As Integer In evenFibs
            If tempInteger > 1000000 Then
                Exit For
            End If
            sum = sum + tempInteger
        Next
        uxOutput.Text = sum.ToString
    End Sub

'This is all types of inelegant.
Public Class FibonacciNumbersCollection
    Implements IEnumerable
    Implements IEnumerator

    Dim _beforeLast As Integer
    Dim _last As Integer
    Dim _currentIndex As Integer = 0

    Public ReadOnly Property Current() As Object Implements System.Collections.IEnumerator.Current
        Get
            Return _last + _beforeLast
        End Get
    End Property

    Public Function MoveNext() As Boolean Implements System.Collections.IEnumerator.MoveNext
        Dim tempNumber As Integer
        If _currentIndex = 0 Then
            _beforeLast = 0
            _last = 1
            _currentIndex += 1
        ElseIf _currentIndex = 1 Then
            _beforeLast = 1
            _last = 1
            _currentIndex += 1
        Else
            tempNumber = _beforeLast
            _beforeLast = _last
            _last = tempNumber + _last
        End If
        Return True
    End Function

    Public Sub Reset() Implements System.Collections.IEnumerator.Reset
        Throw New NotSupportedException
    End Sub

    Public Function GetEnumerator() As System.Collections.IEnumerator Implements System.Collections.IEnumerable.GetEnumerator
        Return Me
    End Function
End Class

Problem 3:

    Private Sub uxProblem3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem3.Click
        Dim factors As List(Of Long) = Factor.FactorNumber(317584931803)
        'The sort isn't actually necessary, but if FactorNumber was implemented differently
        'it would be.
        factors.Sort()
        uxOutput.Text = factors(factors.Count - 1).ToString
    End Sub

Public Class Factor
    Public Shared Function FactorNumber(ByVal value As Long) As Collections.Generic.List(Of Long)
        Dim factorList As New Collections.Generic.List(Of Long)
        Dim toFactor As Long
        Dim square As Long
        toFactor = value

        Do While True
            square = CInt(Math.Ceiling(Math.Sqrt(toFactor)))
            For tempNumber As Long = 2 To square
                If toFactor Mod tempNumber = 0 Then
                    factorList.Add(tempNumber)
                    toFactor = toFactor \ tempNumber
                    Continue Do
                End If
            Next
            factorList.Add(toFactor)
            Exit Do
        Loop

        Return factorList
    End Function

'snip
End Class

Problem 4:

'cheesy, but fast to write.
    Private Sub uxProblem4_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem4.Click
        Dim products As New ProductOfThreeDigitNumbersCollection
        Dim palindromes As New PredicatedCollection(Of Integer)(products, AddressOf isPalindrome)
        Dim palindromeList As New Collections.Generic.List(Of Integer)
        Dim largest As Long = 0

        For Each tempInteger As Integer In palindromes
            palindromeList.Add(tempInteger)
        Next
        palindromeList.Sort()
        uxOutput.Text = palindromeList.Item(palindromeList.Count - 1).ToString
    End Sub

    Public Function isPalindrome(ByVal value As Integer) As Boolean
        Dim valueText As String = value.ToString
        For counter As Integer = 0 To valueText.Length - 1
            If valueText.Substring(counter, 1) <> valueText.Substring(valueText.Length - counter - 1, 1) Then
                Return False
            End If
        Next
        Return True
    End Function

Public Class ProductOfThreeDigitNumbersCollection
    Implements IEnumerable
    Implements IEnumerator

    Dim _x As Integer = 99
    Dim _y As Integer = 100

    Public ReadOnly Property Current() As Object Implements System.Collections.IEnumerator.Current
        Get
            Return _x * _y
        End Get
    End Property

    Public Function MoveNext() As Boolean Implements System.Collections.IEnumerator.MoveNext
        _x = _x + 1
        If _x = 1000 Then
            _x = 100
            _y = _y + 1
            If _y = 1000 Then
                Return False
            End If
        End If
        Return True
    End Function

    Public Sub Reset() Implements System.Collections.IEnumerator.Reset
        Throw New NotSupportedException
    End Sub

    Public Function GetEnumerator() As System.Collections.IEnumerator Implements System.Collections.IEnumerable.GetEnumerator
        Return Me
    End Function
End Class

Problem 7: (uses stuff from problem 10)

    Private Sub uxProblem7_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem7.Click
        Dim naturals As New NaturalNumbersCollection
        Dim primes As New PredicatedCollection(Of Integer)(naturals, AddressOf Factor.IsPrime)
        Dim primeCount As Integer = 0

        For Each tempInteger As Integer In primes
            primeCount += 1
            If primeCount = 10001 Then
                uxOutput.Text = tempInteger.ToString
                Return
            End If
        Next
    End Sub

I just got 11, but the code is too ugly to post. I need to clean it up.

Linden · November 2007

Lewisham wrote: »
Linden wrote: »
If you just want clarity (execution speed is abysmal) then this isn't bad.
primes :: [Integer]
primes = sieve [2..]
	where
		sieve (p:xs) = p : sieve [ x | x <- xs, x `mod` p > 0 ]
I did that for the question about the sum of the primes less than a million (question 10?).

It took 2 hours on an Intel Mac But my Math is not good enough to do it more efficently.

I did say that performance was bad!

My current code for that particular problem (using a generalised version of your primesUpto function) gives pretty reasonable timing.

primes, nonprimes :: [Integer] -- These are circularly defined.
primes    = [2, 3, 5] ++ (diff [7, 9 ..] nonprimes) 
nonprimes = foldr1 f $ map g $ tail primes
	where 
		f (x:xt) ys = x : (merge xt ys)
		g p         = [ n * p | n <- [p, p + 2 ..]]

merge :: (Ord a) => [a] -> [a] -> [a]
merge [] y                = y
merge x []                = x
merge xs@(x:xt) ys@(y:yt) = 
	case compare x y of
		LT -> x : (merge xt ys)
		EQ -> x : (merge xt yt)
		GT -> y : (merge xs yt)

diff :: (Ord a) => [a] -> [a] -> [a]
diff xs@(x:xt) ys@(y:yt) = 
	case compare x y of
		LT -> x : (diff xt ys)
		EQ -> diff xt yt
		GT -> diff xs yt

upTo n list = takeWhile (< n) list

p10 = sum $ upTo 1000000 primes

The lists and first two helper functions are from literateprograms.org (was looking at these during my earlier explorations), and both functions work only with infinite sorted lists.

jackal · November 2007

Eh, this isn't a beauty contest. Forgive the ugliness of this code. Integers are initialized to 0, so everything that is not assigned to is a sentinel value. It makes everything that goes outside of the 20 x 20 grid show up as 0.

Problem 11:

Private Sub uxProject11_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProject11.Click

        Dim grid(22, 25) As Integer
        Dim inputText As String
        Dim currentRow As Integer
        Dim currentColumn As Integer
        Dim max As Integer
        Dim temp As Integer
        inputText = uxInput.Text
        For Each tempLine As String In inputText.Split(New String() {ControlChars.NewLine}, StringSplitOptions.RemoveEmptyEntries)
            currentColumn = 3
            For Each tempNumberText As String In tempLine.Split(" "c)
                grid(currentRow, currentColumn) = Integer.Parse(tempNumberText)
                currentColumn += 1
            Next
            currentRow += 1
        Next
        For rowIndex As Integer = 0 To 19
            For columnIndex As Integer = 3 To 22
                'across
                temp = grid(rowIndex, columnIndex) * grid(rowIndex, columnIndex + 1) * grid(rowIndex, columnIndex + 2) * grid(rowIndex, columnIndex + 3)
                If max < temp Then
                    max = temp
                End If
                'down
                temp = grid(rowIndex, columnIndex) * grid(rowIndex + 1, columnIndex) * grid(rowIndex + 2, columnIndex) * grid(rowIndex + 3, columnIndex)
                If max < temp Then
                    max = temp
                End If
                'down left
                temp = grid(rowIndex, columnIndex) * grid(rowIndex + 1, columnIndex + 1) * grid(rowIndex + 2, columnIndex + 2) * grid(rowIndex + 3, columnIndex + 3)
                If max < temp Then
                    max = temp
                End If
                'down right
                temp = grid(rowIndex, columnIndex) * grid(rowIndex + 1, columnIndex - 1) * grid(rowIndex + 2, columnIndex - 2) * grid(rowIndex + 3, columnIndex - 3)
                If max < temp Then
                    max = temp
                End If
            Next
        Next
        uxOutput.Text = max.ToString
    End Sub

I feel dirty because I looked up an algorithm for problem 12.

Lewisham · November 2007

Linden wrote: »

p10 = sum $ upTo 1000000 primes

A little OT: but how do you feel about $ notation? I just read what it meant, which is to say it essentially wraps up the next thing in parathenses, so your code goes to:

p10 = sum (upTo 1000000 primes)

Maybe I'm just stuck in my ways, but I find parens more obvious as to what is binding to what.

Linden · November 2007

Lewisham wrote: »

A little OT: but how do you feel about $ notation? I just read what it meant, which is to say it essentially wraps up the next thing in parathenses, so your code goes to:
<-->

Maybe I'm just stuck in my ways, but I find parens more obvious as to what is binding to what.

I find it helpful, but mostly for obvious examples with several nested functions. That example is probably the result of me changing the code – I'm pretty sure there was more there initially. As an example, I had a main function in Problem 4 which contained

print $ show $ last $ palindromes [100..999] [100..999]
(or)
print (show (last (palindromes [100..999] [100..999] )))

In this situation, I find the $ clearer than the parentheses, but there are certainly circumstances where the reverse would be true.

Incidentally, those functions are equivalent to

print . show . last $ palindromes [100..999] [100..999]

but replacing the $ with parens causes a typing error. If we also surround the three functions with parens, it works as expected.

Clearly someone really wanted a variety of options. There's $!, as well, which causes strict evaluation.

Edit: This is also posted here, for any interested parties and to avoid cluttering this thread.

jackal · November 2007

Problem 15:

    'This one could really use some comments.
    Private Sub uxProblem15_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem15.Click
        uxOutput.Text = (2L * 2L * 7L * 5L * 23L * 29L * 31L * 33L * 37L * 39L).ToString
    End Sub

    'Here is the brute force. It only takes a small fraction of a millisecond.
    Private Sub uxProblem15_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem15.Click
        Dim grid(20, 20) As Long
        For rowIndex As Integer = 0 To 20
            grid(rowIndex, 0) = 1
        Next
        For columnIndex As Integer = 0 To 20
            grid(0, columnIndex) = 1
        Next
        For rowIndex As Integer = 1 To 20
            For columnIndex As Integer = 1 To 20
                grid(rowIndex, columnIndex) = grid(rowIndex - 1, columnIndex) + grid(rowIndex, columnIndex - 1)
            Next
        Next
        uxOutput.Text = grid(20, 20).ToString
    End Sub

Woo! Finished the first 15.

jackal · November 2007

Problem 18 and 67:

    'It mentions you can brute force 18, but it seems like that would be harder.
    Private Sub uxProblem18_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem18.Click
        Dim rows()() As Integer
        Dim rowText() As String
        Dim currentRowLength As Integer
        Dim lastRow() As Integer
        rowText = uxInput.Text.Split(New String() {ControlChars.NewLine}, StringSplitOptions.RemoveEmptyEntries)
        ReDim rows(rowText.Length - 1)
        For counterX As Integer = 0 To rowText.Length - 1
            rows(counterX) = Array.ConvertAll(rowText(counterX).Split(" "c), New Converter(Of String, Integer)(AddressOf Integer.Parse))
        Next
        For counterX As Integer = 1 To rows.Length - 1
            currentRowLength = rows(counterX).Length
            rows(counterX)(0) += rows(counterX - 1)(0)
            For counterY As Integer = 1 To currentRowLength - 2
                rows(counterX)(counterY) += Math.Max(rows(counterX - 1)(counterY), rows(counterX - 1)(counterY - 1))
            Next
            rows(counterX)(currentRowLength - 1) += rows(counterX - 1)(currentRowLength - 2)
        Next
        lastRow = rows(rows.Length - 1)
        Array.Sort(lastRow)
        uxOutput.Text = lastRow(lastRow.Length - 1).ToString
    End Sub

jackal · November 2007

Problem 16 and 20

Private Sub uxProblem16_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem16.Click
    Dim bigNumber As java.math.BigInteger = java.math.BigInteger.valueOf(2)
    bigNumber = bigNumber.pow(1000)
    uxOutput.Text = SumDigitsInBigInteger(bigNumber).ToString
End Sub

Private Sub uxProblem20_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem20.Click
    Dim bigNumber As java.math.BigInteger = java.math.BigInteger.valueOf(2)
    bigNumber = Factorial(100)
    uxOutput.Text = SumDigitsInBigInteger(bigNumber).ToString
End Sub

Private Function SumDigitsInBigInteger(ByVal value As java.math.BigInteger) As Integer
    Dim total As Integer
    Dim temp As java.math.BigInteger
    Dim zero As java.math.BigInteger = java.math.BigInteger.valueOf(0)
    Dim ten As java.math.BigInteger = java.math.BigInteger.valueOf(10)
    temp = value
    Do
        total += temp.mod(ten).ToInt32(Nothing)
        temp = temp.divide(ten)
    Loop Until temp.Equals(zero)
    Return total
End Function

Private Function Factorial(ByVal value As Integer) As java.math.BigInteger
    Dim fact As java.math.BigInteger = java.math.BigInteger.valueOf(1)
    For counter As Integer = 1 To value
        fact = fact.multiply(java.math.BigInteger.valueOf(counter))
    Next
    Return fact
End Function

I needed to speed up the function I used to sum the digits of BigIntegers:

The original:

    Private Function SumDigitsInBigInteger(ByVal value As java.math.BigInteger) As Integer
        Dim total As Integer
        Dim temp As java.math.BigInteger
        Dim zero As java.math.BigInteger = java.math.BigInteger.valueOf(0)
        Dim ten As java.math.BigInteger = java.math.BigInteger.valueOf(10)
        temp = value
        Do
            total += temp.mod(ten).ToInt32(Nothing)
            temp = temp.divide(ten)
        Loop Until temp.Equals(zero)
        Return total
    End Function

Used DivideAndRemainder function instead of seperate function (twice the speed of original):

    Private Function SumDigitsInBigInteger2(ByVal value As java.math.BigInteger) As Integer
        Dim total As Integer
        Dim temp As java.math.BigInteger
        Dim zero As java.math.BigInteger = java.math.BigInteger.valueOf(0)
        Dim ten As java.math.BigInteger = java.math.BigInteger.valueOf(10)
        Dim quotientAndRemainder As java.math.BigInteger()
        temp = value
        Do
            quotientAndRemainder = temp.divideAndRemainder(ten)
            total += quotientAndRemainder(1).ToInt32(Nothing) ' temp.mod(ten).ToInt32(Nothing)
            temp = quotientAndRemainder(0)
        Loop Until temp.Equals(zero)
        Return total
    End Function

Broke number up into Integer sized chunks and then summed their digits (ten times the speed of the original):

    Private Function SumDigitsInBigInteger3(ByVal value As java.math.BigInteger) As Integer
        Dim total As Integer
        Dim currentInInteger As Integer
        Dim temp As java.math.BigInteger
        Dim zero As java.math.BigInteger = java.math.BigInteger.valueOf(0)
        Dim billion As java.math.BigInteger = java.math.BigInteger.valueOf(1000000000)
        Dim quotientAndRemainder As java.math.BigInteger()
        temp = value
        Do
            quotientAndRemainder = temp.divideAndRemainder(billion)

            currentInInteger = quotientAndRemainder(1).ToInt32(Nothing)
            Do
                total += currentInInteger Mod 10
                currentInInteger = currentInInteger \ 10
            Loop Until currentInInteger = 0

            temp = quotientAndRemainder(0)
        Loop Until temp.Equals(zero)
        Return total
    End Function

I tried one that breaks the number up into long sized chunks, but it didn't run any faster. I tried a function that would split up the number into half on a power of 10 border and then subdivide that until it is down to integer size, but it ran slow. I think I did something wrong.

Janin · December 2007

Bumping this, because it's great fun. Just solved #5, which was much more trouble than it first seemed.

to_check = (20, 19, 18, 17, 16, 15, 14, 13, 12, 11)
factors = (1, 2, 3, 5, 7)

divisible = lambda num: all ((num &#37; ii == 0) for ii in to_check)
increment = reduce (lambda a, b: a * b, factors)
num = increment
while not divisible (num):
	num += increment
	
print num

Cold Koala · December 2007

@Jackal: How is it that you used java.math.BigInteger but I don't recognize your code as Java at all?

Also, how many has everyone solved so far? I'm on 25. (I took a long hiatus.)

Monoxide · December 2007

Cold Koala wrote: »

@Jackal: How is it that you used java.math.BigInteger but I don't recognize your code as Java at all?

Also, how many has everyone solved so far? I'm on 25. (I took a long hiatus.)

It looks like Visual Basic. I think you can call Java classes in VB .NET to some extent, though I don't know the details.

jackal · December 2007

Monoxide wrote: »

Cold Koala wrote: »

@Jackal: How is it that you used java.math.BigInteger but I don't recognize your code as Java at all?

Also, how many has everyone solved so far? I'm on 25. (I took a long hiatus.)

It looks like Visual Basic. I think you can call Java classes in VB .NET to some extent, though I don't know the details.

Several Java classes can be used if you reference vjslib. I think most versions of Visual Studios should come with it. If not just install Visual J# 2005 Express Edition. It seems like a lot of trouble, but it is easier than implementing your own bigint library.

I have solved 36 problems so far, but I haven't touched any in at least a month. I'm glad this got resurrected. After a while it was just me talking to myself. I need to get back to work on 76.

jackal · January 2008

I've decided to redo some of these in C# 3.0. I am loving me some C# 3.0.

Problem 1

        public static void Problem1()
        {
            var oneTo999 = Enumerable.Range(1, 999);
            Console.WriteLine(oneTo999.Where(x => x &#37; 5 ==0 || x % 3 == 0).Sum());
        }

Problem 2

       public static void Problem2()
        {
            var fibs = NumberSequences.Fibonacci();
            Console.WriteLine(fibs.TakeWhile( x => x <= 1000000 ).Where(x => x % 2 == 0).Sum());
        }

It seems like I should be able to do this more easily. I actually had to use a control structure!

If you let it run long enough it will throw an overflow exception. That actually seems more correct than if it stopping, because the Fibonacci numbers don't stop.

    static class NumberSequences
    {
        public static IEnumerable<int> Fibonacci()
        {
            int secondToLastTerm = 1;
            int lastTerm = 2;
            int current;
            yield return secondToLastTerm;
            yield return lastTerm;
            while (true)
            {
                current = secondToLastTerm + lastTerm;
                yield return current;
                secondToLastTerm = lastTerm;
                lastTerm = current;
            }
        }
    }

Problem 3

I didn't bother creating a functional style prime factor function. Making it an extension method is a little silly.

        public static void Problem3()
        {
            Console.WriteLine(317584931803.PrimeFactors().Max());
        }

Avert your eyes. There is imperative code ahead!

        public static IEnumerable<long> PrimeFactors(this long value)
        {   bool foundFlag;
            do
            {
                foundFlag = false;
                long square = (long)Math.Ceiling(Math.Sqrt(value));
                for (int counterX = 2; counterX <= square; counterX++)
                {
                    if (value % counterX == 0)
                    {
                        yield return counterX;
                        value = value / counterX;
                        foundFlag = true;
                        break;
                    }
                }
            } while (foundFlag == true);
            yield return value;
        }

Problem 4

This one is a little slow because I reversed the string instead of the integer.
I could also speed it up if I could manage to only join when the value from the second range is greater than or equal to the value from the first range.

        public static void Problem4()
        {
            
            var range = Enumerable.Range(100, 900);
            var products = range.Join(range, x => 1, x => 1, (x, y) => x * y);
            var palindromes = products.Where(x => x.ToString() == x.ToString().Reverse());
            Console.WriteLine(palindromes.Max());
        }

        public static string Reverse(this string value)
        {
            return value.ToCharArray().Reverse().Aggregate(new StringBuilder(), (x, y) => x.Append(y), x => x.ToString());
        }

Problem 6

        public static void Problem6()
        {
            var oneToTen = Enumerable.Range(1, 100).ToList();
            Console.WriteLine(oneToTen.Sum().Square() - oneToTen.ConvertAll(x => x.Square()).Sum());
        }

        public static int Square(this int value)
        {
            return value * value;
        }

Problem 7 and 10

        public static void Problem7and10()
        {
            var range = Enumerable.Range(1 , 999999 ).Cast<long>();
            var primes = range.Where(x => x.IsPrime()).ToList();
            if (primes.Count >= 10001)
            {
                Console.WriteLine(string.Format("Problem  7: {0}", primes[10000]));
            }
            Console.WriteLine(string.Format("Problem 10: {0}", primes.Sum()));
        }

        public static bool IsPrime(this long value)
        {
            if (value <= 1) return false;
            int square = Convert.ToInt32((Math.Sqrt(value)));
            return !Enumerable.Range(2, square - 1).Any(x => value % x == 0);
        }

jackal · January 2008

For 9 the functional style solution was not very good compared to the imperative solution. Either I am doing something wrong or this doesn't lend itself to this type of solution. The one positive point about the first example is that it more naturally emerges from the problem definition.

        public static void Problem9()
        {
            var range = Enumerable.Range( 1, 999);
            var duplets = range.Join( range,  x => 1 , x => 1, (x, y) => new { a = x, b = y });
            var filteredDuplets = duplets.Where(x => x.a < x.b && x.a + x.b <= 999);
            var triplets = filteredDuplets.ToList().ConvertAll(x => new { a = x.a, b = x.b, c = 1000 - x.a - x.b });
            var filteredTriplets = triplets.Where(x => x.b < x.c);
            var pythagoreanTriplet = filteredTriplets.First(x => x.a * x.a + x.b * x.b == x.c * x.c);
            Console.WriteLine(pythagoreanTriplet.a * pythagoreanTriplet.b * pythagoreanTriplet.c);
        }

    Private Sub uxProblem9_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem9.Click
        For a As Integer = 1 To 998
            For b As Integer = 1 To 999 - a
                Dim c As Integer = 1000 - b - a
                If (a * a + b * b) = (c * c) Then
                    uxOutput.Text = (a * b * c).ToString
                    Return
                End If
            Next
        Next
    End Sub

EDIT:
Yeah, I was doing something wrong. This is much better.

        public static void Problem9b()
        {
            var range = Enumerable.Range(1, 999);
            var triplets = range.Join(range, x => 1, x => 1, (x, y) => new { a = x, b = y, c = 1000 - x - y });
            var filteredTriplets = triplets.Where(x => x.a < x.b && x.b < x.c);
            var pythagoreanTriplet = filteredTriplets.First(x => x.a * x.a + x.b * x.b == x.c * x.c);
            Console.WriteLine(pythagoreanTriplet.a * pythagoreanTriplet.b * pythagoreanTriplet.c);
        }

Janin · January 2008

This is my solution to #9. Also, please use spoilers.

is_trip = lambda a, b, c: (a < b) and (b < c) and ((a**2) + (b**2) == (c**2))
for a, b in ((a, b) for a in xrange (1001) for b in xrange (1001)):
	c = 1000 - (a + b)
	if is_trip (a, b, c):
		print a*b*c
		break

jackal · January 2008

What language is that?

Anyway 9 using LINQ:

        public static void Problem9c()
        {
            var range = Enumerable.Range(1, 999);
            var triplets =
               from x in range
               join y in range on 1 equals 1
               where x < y && y < (1000 - x - y)
               select new { a = x, b = y, c = 1000 - x - y };

            var pythagoreanTriplet = (from x in triplets
                     where x.a * x.a + x.b * x.b == x.c * x.c
                     select x).FirstOrDefault();

            Console.WriteLine(pythagoreanTriplet.a * pythagoreanTriplet.b * pythagoreanTriplet.c);
        }

EDIT:
Using nested froms seems to be appropriate than the explicit join. It looks like it could be more optimizable this way.

        public static void Problem9c2()
        {
            var range = Enumerable.Range(1, 999);
            var triplets =
               from x in range
                   from y in range
               where x < y && y < (1000 - x - y)
               select new { a = x, b = y, c = 1000 - x - y };

            var pythagoreanTriplet = (from x in triplets
                                      where x.a * x.a + x.b * x.b == x.c * x.c
                                      select x).FirstOrDefault();

            Console.WriteLine(pythagoreanTriplet.a * pythagoreanTriplet.b * pythagoreanTriplet.c);
        }

Here it is in a single LINQ query. It is getting ugly or beautiful. I'm not sure which.

        public static void Problem9d()
        {
            var range = Enumerable.Range(1, 999);
            var pythagoreanTriplet =
                (from z in
                   from x in range
                        from y in range
                   where x < y && y < (1000 - x - y)
                   select new { a = x, b = y, c = 1000 - x - y }
                        where z.a * z.a + z.b * z.b == z.c * z.c
                        select z).FirstOrDefault();

            Console.WriteLine(pythagoreanTriplet.a * pythagoreanTriplet.b * pythagoreanTriplet.c);
        }

I am digging the anonymous data types.

Janin · January 2008

jackal wrote: »

What language is that?

Python

jackal · January 2008

Oh man, I really need to figure out how to make this stuff readable.

Problem 5 (this is a lot of code for something that takes about a minute to solve on paper):

I'm casting the ints to longs because the PrimeFactors extension method I wrote works with longs.

        public static void Problem5()
        {
            var range = Enumerable.Range(2, 19).Cast<long>();
            var factors = range.SelectMany(x => x.PrimeFactors().GroupBy(y => y).Select(z => new {factor = z.Key, count = z.Count()}));
            var groupedFactors = factors.GroupBy(y => y.factor);
            var factorsAndExponents = groupedFactors.Select(x => new { Factor = x.Key, Exponent = x.Max(z => z.count) });
            Console.WriteLine(factorsAndExponents.Aggregate(1d, (x, y) => x * Math.Pow(y.Factor, y.Exponent), x => x.ToString("0")));
        }

The disturbing thing is that it can all be smashed into one line of code.

        public static void Problem5ForTheLoveOfGodDontDoThis()
        {
            Console.WriteLine(Enumerable.Range(2, 19).Cast<long>().SelectMany(x => x.PrimeFactors().GroupBy(y => y).Select(z => new { factor = z.Key, count = z.Count() })).GroupBy(y => y.factor).Select(x => new { Factor = x.Key, Exponent = x.Max(z => z.count) }).Aggregate(1d, (x, y) => x * Math.Pow(y.Factor, y.Exponent), x => x.ToString("0")));
        }

Problem 12:

        public static void Problem12()
        {
            var primeFactorsOfTriangleNumbers = NumberSequences.TriangleNumbers().Cast<long>().Select(x => new { number = x, primeFactors = x.PrimeFactors().GroupBy(y => y)});
            var numberOfDivisorsOfTriangleNumbers = primeFactorsOfTriangleNumbers.Select(x => new {number = x.number, divisorCount = x.primeFactors.Aggregate(1, (y, z) => y * (z.Count() + 1))});
            Console.WriteLine(numberOfDivisorsOfTriangleNumbers.First(x => x.divisorCount > 500).number);
        }

Problem 29:
This one turned out really well.

        public static void Problem29()
        {
            var range = Enumerable.Range(2, 99);
            var answer = (from x in range
                            from y in range
                                select java.math.BigInteger.valueOf(x).pow(y))
                                    .Distinct().Count();
            Console.WriteLine(answer);
        }

Problem 30:
This is the first one I tried from scratch with C# 3.0

        public static void Problem30()
        {
            var numbersAndDigits = Enumerable.Range(10, 360000).Select(x => new {number = x, digits = NumberSequences.Digits(x)});
            var numbersAndTransforms = numbersAndDigits.Select(x => new {x.number, transform = x.digits.Aggregate(0d, (y, z) => y + Math.Pow(z, 5), y => (int)y)});
            var targetNumbers = numbersAndTransforms.Where(x => x.number == x.transform);
            Console.WriteLine(targetNumbers.Sum(x => x.transform));
        }

        public static IEnumerable<int> Digits(int value)
        {
            do
            {
                yield return value &#37; 10;
                value /= 10;
            } 
            while (value != 0);
        }

Janin · January 2008

jackal wrote: »

Oh man, I really need to figure out how to make this stuff readable.

Problem 5 (this is a lot of code for something that takes about a minute to solve on paper):

I'm casting the ints to longs because the PrimeFactors extension method I wrote works with longs.

        public static void Problem5()
        {
            var range = Enumerable.Range(2, 19).Cast<long>();
            var factors = range.SelectMany(x => x.PrimeFactors().GroupBy(y => y).Select(z => new {factor = z.Key, count = z.Count()}));
            var groupedFactors = factors.GroupBy(y => y.factor);
            var factorsAndExponents = groupedFactors.Select(x => new { Factor = x.Key, Exponent = x.Max(z => z.count) });
            Console.WriteLine(factorsAndExponents.Aggregate(1d, (x, y) => x * Math.Pow(y.Factor, y.Exponent), x => x.ToString("0")));
        }

The disturbing thing is that it can all be smashed into one line of code.

        public static void Problem5ForTheLoveOfGodDontDoThis()
        {
            Console.WriteLine(Enumerable.Range(2, 19).Cast<long>().SelectMany(x => x.PrimeFactors().GroupBy(y => y).Select(z => new { factor = z.Key, count = z.Count() })).GroupBy(y => y.factor).Select(x => new { Factor = x.Key, Exponent = x.Max(z => z.count) }).Aggregate(1d, (x, y) => x * Math.Pow(y.Factor, y.Exponent), x => x.ToString("0")));
        }

Good lord. Mine might have a few more lines, but I think it's much more readable:

to_check = range (20, 10, -1)
factors = (1, 2, 3, 5, 7)

divisible = lambda num: all ((num &#37; ii == 0) for ii in to_check)
increment = reduce (lambda a, b: a * b, factors)

num = increment
while not divisible (num):
	num += increment
	
print num

jackal · January 2008

Janin wrote: »

jackal wrote: »

Oh man, I really need to figure out how to make this stuff readable.

Problem 5 (this is a lot of code for something that takes about a minute to solve on paper):

I'm casting the ints to longs because the PrimeFactors extension method I wrote works with longs.

        public static void Problem5()
        {
            var range = Enumerable.Range(2, 19).Cast<long>();
            var factors = range.SelectMany(x => x.PrimeFactors().GroupBy(y => y).Select(z => new {factor = z.Key, count = z.Count()}));
            var groupedFactors = factors.GroupBy(y => y.factor);
            var factorsAndExponents = groupedFactors.Select(x => new { Factor = x.Key, Exponent = x.Max(z => z.count) });
            Console.WriteLine(factorsAndExponents.Aggregate(1d, (x, y) => x * Math.Pow(y.Factor, y.Exponent), x => x.ToString("0")));
        }

The disturbing thing is that it can all be smashed into one line of code.

        public static void Problem5ForTheLoveOfGodDontDoThis()
        {
            Console.WriteLine(Enumerable.Range(2, 19).Cast<long>().SelectMany(x => x.PrimeFactors().GroupBy(y => y).Select(z => new { factor = z.Key, count = z.Count() })).GroupBy(y => y.factor).Select(x => new { Factor = x.Key, Exponent = x.Max(z => z.count) }).Aggregate(1d, (x, y) => x * Math.Pow(y.Factor, y.Exponent), x => x.ToString("0")));
        }

Good lord. Mine might have a few more lines, but I think it's much more readable:

to_check = range (20, 10, -1)
factors = (1, 2, 3, 5, 7)

divisible = lambda num: all ((num % ii == 0) for ii in to_check)
increment = reduce (lambda a, b: a * b, factors)

num = increment
while not divisible (num):
	num += increment
	
print num

Well, the techniques are very different. I basically translated how the problem would be solved on paper. Yours looks like a good middle ground between simplicity and speed. If I am understanding your code correctly couldn't you include 11, 13, 17 and 19 in factors and get a pretty significant speed improvement?

Janin · January 2008

I have no idea how any of these problems would be solved on paper, so all my solutions are wild guesses. Didn't notice any difference in speed including 11, 13, 17, and 19, but it still came up with the correct solution vOv.

jackal · January 2008

Janin wrote: »

I have no idea how any of these problems would be solved on paper, so all my solutions are wild guesses. Didn't notice any difference in speed including 11, 13, 17, and 19, but it still came up with the correct solution vOv.

I think this is how your code could be implemented in C#. How long does your code take to run? This takes a little over a minute and a half on an Athlon XP 1900+.

        public static void Problem5Janin()
        {
            var toCheck = Enumerable.Range(10, 10);
            int[] factors = { 2, 3, 5, 7, 11, 13, 17, 19 };
            Func<int, bool> divisible = x => toCheck.All(y => x % y == 0);
            var increment = factors.Aggregate(1, (x,y) => x * y);
            var incrementMultiples = Enumerable.Range(1, int.MaxValue);
            Console.WriteLine(incrementMultiples.First(x => divisible(x)));     
        }

Penny Arcade

Quick Links

Project Euler - Let's do Math/Programming Challenges

Posts