Problem

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Solution #1

//-----------------------------------------------------------------------------
// From: www.slashgeek.org
// Proj: Problem5
// File: Program.fs
// Desc: This is my take on Project Euler's problem #5
//-----------------------------------------------------------------------------

// Problem:
// 2520 is the smallest number that can be divided by each of the numbers
// from 1 to 10 without any remainder.
//
// What is the smallest number that is evenly divisible by all of the numbers
// from 1 to 20?

#light

// Starts the stopwatch.
let stopwatch = System.Diagnostics.Stopwatch.StartNew()

// Tests if an integer is divisible by [1;20].
let isDivisibleBy1To20 c =
    let mutable divisible = true
    let mutable i = 1
    while i <= 20 do
        if c % i <> 0 then
            divisible <- false
            i <- 21
        i <- i + 1
    divisible = true

// Tests all integers, starting from 20.
let mutable n = 20
let mutable found = false

while not found do
    if isDivisibleBy1To20 n then
        found <- true
    else
        n <- n + 20

// Stop the stopwatch.
stopwatch.Stop()

// Print the result.
printfn "The result is %d" n
printfn "Time elapsed is %d milliseconds" stopwatch.ElapsedMilliseconds

Solution #2 (by hand)

// Compute the prime factorization of each number from 1 to 20, and multiply the
// greatest power of each prime together:
//
// 20 = 2^2 * 5
// 19 = 19
// 18 = 2 * 3^2
// 17 = 17
// 16 = 2^4
// 15 = 3 * 5
// 14 = 2 * 7
// 13 = 13
// 11 = 11
//
// All others are included in the previous numbers.
//
// ANSWER: 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19 = 232 792 560

Download the article

Problem

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91  99.

Find the largest palindrome made from the product of two 3-digit numbers.

Solution #1

//-----------------------------------------------------------------------------
// From: www.slashgeek.org
// Proj: Problem4
// File: Program.fs
// Desc: This is my take on Project Euler's problem #4
//-----------------------------------------------------------------------------

// Problem:
// A palindromic number reads the same both ways. The largest palindrome made
// from the product of two 2-digit numbers is 9009 = 91  99.
//
// Find the largest palindrome made from the product of two 3-digit numbers.

#light

// Starts the stopwatch.
let stopwatch = System.Diagnostics.Stopwatch.StartNew()

// Reverses a string: "abc" -> "cba"
let reverseString (s : string) =
    new string(s |> Array.ofSeq |> Array.rev)

// Reverses an integer: 12345 -> 54321
let reverseInt32 (n : System.Int32) =
    n |> string |> reverseString|> System.Int32.Parse

// Returns "true" if n is palindromic, "false" otherwise.
let isPalindromic n =
    n = reverseInt32 n

// Product of the 3 digit integers
let mutable product = 0

// Candidate for the largest palindrome
let mutable candidate = 0

// First 3 digit integer.
let mutable i = 999

// Second 3 digit integer.
let mutable j = 0

// Finds the largest palindrome.
while i >= 100 do
    j <- 999
    while j >= i do               // Avoid to compute twice the same values.
        if i * j <= candidate then
            j <- 0
        else
            product <- i * j
            if isPalindromic product then
                candidate <- i * j
            j <- j - 1
    i <- i - 1

// Stop the stopwatch.
stopwatch.Stop()

// Print the result.
printfn "The result is %d" candidate
printfn "Time elapsed is %d milliseconds" stopwatch.ElapsedMilliseconds

Download the article

Problem

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution #1(using sequences)

//-----------------------------------------------------------------------------
// From: www.slashgeek.org
// Proj: Problem3
// File: Program.fs
// Desc: This is my take on Project Euler's problem #3
//-----------------------------------------------------------------------------

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

#light

open System

// Starts the stopwatch.
let stopwatch = System.Diagnostics.Stopwatch.StartNew()

// Determines if a number is prime.
let IsPrime (x : int) =
    let squareRoot = Convert.ToInt32(Math.Sqrt(Convert.ToDouble(x)))
    x > 1 && not (Seq.exists (fun n -> x % n = 0) {2 .. squareRoot})

// Generates an infinite sequence of prime numbers.
let primeSequence = Seq.initInfinite (fun x -> x) |> Seq.filter IsPrime

// The number to factor.
let targetNumber = 600851475143L

// Gets the next prime from a given prime.
let next_primes prime =
    Seq.skipWhile (fun i -> i <= prime) (seq {
                                                for prime in primeSequence do
                                                    yield int64(prime)
                                             })

// Generates the prime factors sequence for a given number,
// starting from a given prime.
let generate (n, p) =
    if n = 1L then
        None
    else
        if n % p = 0L then
            let q = n / p
            Some(p, (q, p))
        else
            let f = Seq.find (fun i -> n % i = 0L) (next_primes p)
            let q = n / f
            Some(f, (q, f))

// Computes the prime factors of 600851475143.
let factors = Seq.unfold generate (targetNumber, 2L)

// Stop the stopwatch.
stopwatch.Stop()

// Print the result.
printfn "The result is %A" (Seq.max factors)
printfn "Time elapsed is %d milliseconds" stopwatch.ElapsedMilliseconds

Download the article

Problem

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

 

Solution #1(using sequences)

//-----------------------------------------------------------------------------
// From: www.slashgeek.org
// Proj: Problem2
// File: Program.fs
// Desc: This is my take on Project Euler's problem #2
//-----------------------------------------------------------------------------

// Problem:
// Each new term in the Fibonacci sequence is generated by adding the previous
// two terms. By starting with 1 and 2, the first 10 terms will be:
// 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
// Find the sum of all the even-valued terms in the sequence which do not exceed
// four million.

module Program

#light

// Starts the stopwatch.
let stopwatch = System.Diagnostics.Stopwatch.StartNew()

// Compute a Fibonacci sequence.
let fib = Seq.unfold(fun (i, j) -> Some(i, (j, i + j)))(1,1)

// Filter the sequence to take only the even values and do the sum.
let result = Seq.filter(fun x -> (x % 2 = 0)) (fib |> Seq.takeWhile(fun n -> n <= 4000000)) |> Seq.sum

// Stop the stopwatch.
stopwatch.Stop()

// Print the result.
printfn "The result is %d" result
printfn "Time elapsed is %d milliseconds" stopwatch.ElapsedMilliseconds

Solution #2 (better)

//-----------------------------------------------------------------------------
// From: www.slashgeek.org
// Proj: Problem2
// File: Program2.fs
// Desc: This is my take on Project Euler's problem #2
//-----------------------------------------------------------------------------

// Problem:
// Each new term in the Fibonacci sequence is generated by adding the previous
// two terms. By starting with 1 and 2, the first 10 terms will be:
// 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
// Find the sum of all the even-valued terms in the sequence which do not exceed
// four million.

module Program2

#light

// Starts the stopwatch.
let stopwatch = System.Diagnostics.Stopwatch.StartNew()

// Fib sequence:
//
// 1 1 2 3 5 8 13 21 34 55 89 144
// a b c a b c a  b  c  a  b  c
//
// We can see that every third Fibonacci numbers are even.
//
// Compute the sum of every third Fibonacci number up to 4000000.
let result =    let mutable sum = 0
                let mutable a = 1
                let mutable b = 1
                let mutable c = 2
                while c < 4000000 do
                    sum <- sum + c
                    a <- b + c
                    b <- c + a
                    c <- a + b
                sum

// Stop the stopwatch.
stopwatch.Stop()

// Print the result.
printfn "The result is %d" result
printfn "Time elapsed is %d milliseconds" stopwatch.ElapsedMilliseconds

Download the article

Problem

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Solution #1 (easy)

//-----------------------------------------------------------------------------
// From: www.slashgeek.org
// Proj: Problem1
// File: Program.fs
// Desc: This is my take on Project Euler's problem #1
//-----------------------------------------------------------------------------

// Problem:
// If we list all the natural numbers below 10 that are multiples of 3 or 5, we
// get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the
// multiples of 3 or 5 below 1000.

module Program

#light

// Starts the stopwatch.
let stopwatch = System.Diagnostics.Stopwatch.StartNew()

// Returns true if n is a multiple of 3.
let isMultipleOf3 = fun n -> n % 3 = 0

// Returns true if n is a multiple of 5.
let isMultipleOf5 = fun n -> n % 5 = 0

// Returns true if n is a multiple of 3 or 5.
let isMultipleOf3Or5 = fun n -> isMultipleOf3 n || isMultipleOf5 n

// Returns the multiples of 3 or 5 in [1,999]
let multiplesOf3Or5 = seq { for i in 1 .. 999 do if isMultipleOf3Or5 i then yield i }

// Initializes the sum.
let mutable sum = 0

// Computes the sum.
for multiple in multiplesOf3Or5 do
    sum <- sum + multiple

// Stop the stopwatch.
stopwatch.Stop()

// Print the result.
printfn "The result is %d" sum
printfn "Time elapsed is %d milliseconds" stopwatch.ElapsedMilliseconds

Solution #2 (harder)

//-----------------------------------------------------------------------------
// From: www.slashgeek.org
// Proj: Problem1
// File: Program2.fs
// Desc: This is my take on Project Euler's problem #1
//-----------------------------------------------------------------------------

// Problem:
// If we list all the natural numbers below 10 that are multiples of 3 or 5, we
// get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the
// multiples of 3 or 5 below 1000.

module Program2

#light

// Starts the stopwatch.
let stopwatch = System.Diagnostics.Stopwatch.StartNew()

// Compute the sum of the multiple of n, from n up to max.
//
// If we take n = 3, and max = 999:
// 3 + 6 + 9 + ... + 999 = 3 * ( 1 + 2 + 3 + ... + 333 )
// If we take n = 5, and max = 999:
// 5 + 10 + 15 + ... + 995 = 5 * ( 1 + 2 + 3 + ... + 199 )
//
// We get:
// 1 + 2 + 3 + ... + i = i * ( i + 1 ) / 2 with i being the nearest integer of
// max / multiple.
let sumDivisibleBy multiple max = let i = max / multiple
                                  multiple * i * ( i + 1 ) / 2

// Compute the sum of the multiple of 3, of 5, and substract the multiples of
// 3 by 5 (15).
let sum =   (sumDivisibleBy 3 999)
          + (sumDivisibleBy 5 999)
          - (sumDivisibleBy 15 999)

// Stop the stopwatch.
stopwatch.Stop()

// Print the result.
printfn "The result is %d" sum
printfn "Time elapsed is %d milliseconds" stopwatch.ElapsedMilliseconds

Download the article

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.

The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

 

Here’s the website: http://projecteuler.net/

If I’m writing about Project Euler, that’s because it’s the way that I chose to learn F# programming. I think that’s a great way to sharpen my mathematical skills as well as my understanding of functional programming. Since I’m still learning F#, you may find better ways to solve theses problems, in a programming and/or in a mathematical way.

Anyway, I hope that you will enjoy theses articles.

.. and guess what ? My NX8800 GTX is dead. If you have installed NVidia’s ForceWare 196.75, I suggest that you roll back to version 196.21 ;)

Here comes a new HD 5850 to replace the 8800 GTX. At least, the stock ATI/AMD drivers allows you to override the fan settings. If you want to do the same with an NVidia card, you can google for “Riva Tuner”.

The following namespaces are supported in the .NET Compact Framework for Xbox 360:

System
System.CodeDom.Compiler
System.Collections
System.Collections.Generic
System.Collections.ObjectModel
System.Collections.Specialized
System.ComponentModel
System.Configuration.Assemblies
System.Diagnostics
System.Diagnostics.CodeAnalysis
System.Globalization
System.IO
System.Net
System.Reflection
System.Resources
System.Runtime.CompilerServices
System.Runtime.InteropServices
System.Runtime.Serialization
System.Security
System.Security.Permissions
System.Security.Policy
System.Text
System.Text.RegularExpressions
System.Threading
System.Xml
System.Xml.Schema
System.Xml.Serialization
System.Xml.XPath
System.Xml.Xsl

There is only one method added to the .NET Compact Framework, and not an useless one:

public void SetProcessorAffinity ( params int[] cpus )

in the System.Threading.Thread class.

This method sets the processor or hardware thread on which a software thread will execute. Each of the three CPU cores on the Xbox 360 has two hardware threads; the hardware thread number selects a specific hardware thread on a specific core.

Xbox 360 software threads are associated with, and run on, only a single hardware thread at a time. The hardware thread on which a thread runs (the thread’s processor affinity) must be set to a single hardware thread, but can be subsequently changed by calling SetProcessorAffinity with a different hardware thread number. When a thread is created, it is initially assigned to the current hardware thread (that is, the hardware thread on which the current thread is running). Also, the two hardware threads executing on a single core do share some resources, such as the vector unit and L1 cache.

For Xbox 360 threads, you cannot clear the thread’s processor affinity by passing an empty array as the cpus parameter. An Xbox 360 thread will always be associated with one hardware thread.

XNA Game Studio games should not use hardware threads 0 or 2, which are reserved for the XNA Framework. The following table identifies Xbox 360 hardware thread usage.

This method should not be used with threads created by the ThreadPool or Timer classes. It should only be called from the thread whose affinity is being changed. Regarding ThreadPool, the default maximum number of threads in an Xbox 360 thread pool is 256. When a new task is queued with ThreadPool.QueueUserWorkItem, the thread pool first tries to assign the task to an available thread in the pool. If all threads in the thread pool are busy performing tasks, the thread pool will create a new thread to handle the task, up to the maximum number of threads set for the pool. If no threads are available and the maximum number of threads have already been created, the task is queued until a thread in the pool becomes available.

To specify the maximum number of threads for the pool, use ThreadPool.SetMaxThreads. If the threads in a thread pool do not require much processing time and are cycling their tasks quickly, it may be more efficient to lower the maximum number of threads for the pool (from its default of 256). Doing so reduces the amount of context switching that occurs when a large number of ready threads are being scheduled alternately for execution on the available processors.

Here’s a few pictures of the beast:

View Full Album

I’ve bought a new SSD hard drive for my workstation, and I’m more than happy with the speed boost that I’ve got now, compared to using one of my many Seagate Barracuda 7200RPM for the operating system.

Here’s a picture of the SSD:

Here’s the specifications of the P64 series: