The Midlife Geek

Ramblings of a middle aged engineer, runner and open source enthusiast

Tag: Mathematics

Number letter counts

Project Euler problem 17:

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

Continue reading

Names scores

Project Euler again, this time Python. The problem is to sort a list of 5000 names alphabetically then give them a value. For example “COLIN” is 3 + 15 + 12 + 9 + 14 = 53 and is the 938th item – so its value is 49714 (53*938).

Continue reading

Find the sum of amicable numbers under 10000

Project Euler problem 21 is to find the sum of all amicable numbers under 10000. An amicable number is:

Let \(d(n)\) be the sum of proper divisors of \(n\) then \(d(a)=b\) and \(d(b)=a\) if \(a!=b\) then \(a\) and \(b\) are amicable numbers.

Continue reading

First triangular number with 500 divisors

OK so today I’m trying problem 12 – find the first triangular number with over 500 divisors. This is the first Project Euler problem I’ve really struggled to find a solution in a reasonable amount of time. Continue reading

Pythagorean triplet

Project Euler again, this time its problem 9.

A Pythagorean triplet is a set of three natural numbers, a<b<c, for which:

$latex a^{2}+b^{2}=c^{2}$

For example:

$latex 3^{2}+4^{2}=9+16=25=5^{2}$.

There exists exactly one Pythagorean triplet for which abc = 1000.
Find the product abc.

My first draft is simply brute force checking:

Module Module1

  Sub Main()
    Dim beganAt As Date = Now

    Dim answer As Integer = pythagorean(1000)

    Dim endAt As Global.System.TimeSpan = Now.Subtract(beganAt)
    Dim took As Integer = endAt.Milliseconds

    Console.WriteLine(answer.ToString + " in " + took.ToString + "ms.")
    Console.ReadKey()
  End Sub

  Private Function pythagorean(ByVal thisNumber As Integer) As Integer
    For a As Integer = 1 To thisNumber
      For b As Integer = 1 To thisNumber
        For c As Integer = 1 To thisNumber
          If a + b + c = 1000 Then
            If (a * a) + (b * b) = (c * c) Then
              Return (a * b * c)
            End If
          End If
        Next
      Next
    Next
    Return -1
  End Function

End Module

It takes 375 milliseconds but gives the correct answer.

 

The 10001st prime number

Project Euler time again, I’ve come out of sequence – here’s problem 7:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

I’m going to start at the beginning and check if each is a prime, until I find the 10001th.

Module Module1
  Sub Main()
    Dim beganAt As Date = Now
    Dim n = 10001
    Dim prime As Integer = 0
    Dim counter As Integer = 0

    ' Check each number until you've got 10001 prime numbers.
    Do Until prime = n + 1
      counter = counter + 1
      If isPrime(counter) Then
        prime = prime + 1
      End If
    Loop

    Dim endAt As Global.System.TimeSpan = Now.Subtract(beganAt)
    Dim took As Integer = endAt.Milliseconds

    Console.WriteLine(counter.ToString + " in " + took.ToString + "ms.")
    Console.ReadKey()
  End Sub

  Private Function isPrime(ByVal thisNumber As Integer) As Boolean
    ' Prime numbers other than two are odd...
    If thisNumber = 2 Then
      Return True
    ElseIf thisNumber Mod 2 = 0 Then
      Return False
    End If

    'Check it isn't divisible by up to its square root
    '(consider n=(root n)(root n) as factors)
    For counter As Integer = 3 To (Math.Sqrt(thisNumber)) Step 2
      If thisNumber Mod counter = 0 Then
        Return False
      End If
    Next
    Return True
  End Function

End Module

I used a function for finding primes, it keeps coming up. It takes an integer and returns true or false by discounting even numbers except 2 and checking for divisibility up to the integer’s square root. If you consider $latex n=sqrt{n} times sqrt{n} $ then if you have not found a number that divides into $latex n$ evenly once reaching $latex sqrt{n}$, its factors can only be one and itself. This significantly reduces processing time and appears to be how my HP40gs works out its ISPRIME() function.

It gives the answer 104743 in 125 milliseconds.

Largest prime factor of a composite number

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

Prime factors are prime numbers that can be multiplied together to make a given number. One way to find them is to start by dividing the number by the first prime (2) and continuing to do so until it cannot be divided, then moving on to the next.

Module Module1
  Sub Main()
    Dim beganAt As Date = Now
    Dim n As Long = 600851475143
    Dim factor As Integer = 2
    Dim highestFactor As Integer = 1
    While n > 1
      If n Mod factor = 0 Then
        highestFactor = factor
        n = n / factor
        While n Mod factor = 0
          n = n / factor
        End While
      End If
      factor = factor + 1
    End While
    Dim endAt As Global.System.TimeSpan = Now.Subtract(beganAt)
    Dim took As Integer = endAt.Milliseconds
    Console.WriteLine(highestFactor.ToString + " in " + took.ToString + "ms.")
    Console.ReadKey()
  End Sub
End Module

© 2018 The Midlife Geek

Theme by Anders NorenUp ↑