Project Euler, problem 26

Problem is stated as following:

---

A unit fraction contains 1 in the numerator. The decimal representation of the unit 
fractions with denominators 2 to 10 are given:

    1/2  =  0.5
    1/3  =  0.(3)
    1/4  =  0.25
    1/5  =  0.2
    1/6  =  0.1(6)
    1/7  =  0.(142857)
    1/8  =  0.125
    1/9  =  0.(1)
    1/10 =  0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen
that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in 
its decimal fraction part.

---

Solution is based on idea that longest recurring cycle should have 1/p form, where p - prime number. After quick look at wikipedia about repeating decimals I thought that I should just search biggest prime, but at closer examination of wiki, I understood that not necessary biggest prime would result in biggest recurring cycle of 1/prime. So for the sake of mathematical integrity, I decided to implement 'correct' search of biggest recurring cycle, which is based on calculating multiplicative order of 10 modulo prime. Solution also is pretty fast - executes in about 130 ms. Below is solution code in language F#:

---

open System.Diagnostics

// http://en.wikipedia.org/wiki/Modular_exponentiation
let modular_exponent b e m =
    let rec modular_exponent0 b e e0 m c0 = 
        match () with
        | _ when e0 >= e -> c0
        | _  -> let e1 = e0 + 1 in
                let c1 = (c0 * b) % m in
                modular_exponent0 b e e1 m c1
    modular_exponent0 b e 0 m 1

// http://en.wikipedia.org/wiki/Multiplicative_order
let multiplicative_order a n =
    let rec multiplicative_order0 a n k0 = 
        let me = modular_exponent a k0 n in
            match me with
            | 1 -> k0
            | _ -> let k1 = k0 + 1 in
                   multiplicative_order0 a n k1
    multiplicative_order0 a n 1

// http://en.wikipedia.org/wiki/Repeating_decimal#Fractions_with_prime_denominators
let period_of_1divp p = multiplicative_order 10 p

// http://en.wikipedia.org/wiki/Prime_number#Verifying_primality
let is_prime x = 
    let rec is_prime0 x d0 = 
        match () with
        | _ when d0 > int (sqrt (float x)) -> true
        | _ when x % d0 = 0 -> false
        | _ -> let d1 = d0 + 1 in
               is_prime0 x d1
    is_prime0 x 2

let main = let stopwatch = new Stopwatch()
           stopwatch.Start()
           let prime,max_period = 
               [ for x in 6..999 do if is_prime x then yield x,period_of_1divp x ] |> 
               Seq.fold (fun (a,b) (x,y) -> if y > b then (x,y) else (a,b)) (0,0)
           stopwatch.Stop()
           printfn "Fraction with greatest period of %d is 1/%d, calculated in %d ms" 
                    max_period
                    prime
                    stopwatch.ElapsedMilliseconds

---

Have fun with Project Euler and F# !

Evaluating math expressions in F#

This time we will try to write math expressions evaluator in F#. At first - why we need that ? Well, math expressions evaluator is useful in computer algebra systems - for evaluating some equations. Also such evaluator may be useful for financial institutions where also some kind of formula computation/evaluation is needed and etc. It`s a pitty that such eval function is not implemented in F# language. Possible reasons is that F# is compiled language... Anyway we will try to write such universal eval function which accepts arbitrary math expression and returns result to the user. So what are possible ways of implementing such function in F# ?

- by writing so called domain-specific language - math expressions compiler. This is achieved by using some tools such as fsyacc and fslex. Defining custom tokens and etc.

- by using .NET System.CodeDom.Compiler libraries. This is achieved by generating class definition "on the fly" and with the help of CodeDom - compiling this class in memory.

- another different approach - is try to write F# script which recursively analyzes math expression and evaluates it piece by piece until it finds the answer. This solution does not use tools mentioned above.

So the last approach will be discussed here. Main algorithm of evaluating math expressions is displayed below:


F# code which implements this idea is placed here.
There are also some eval() function tests implemented in this code. So that after executing this script you will get output something like:


Conclusions:

It is possible to generalize eval() function algorithm in about 90~ lines of F# code without using CodeDom model or fsyacc/fslex tools. This makes solution pretty much "homogeneous" which can be useful in some situations. Also this eval() implementation takes as input arbitrary math expression. As for the bad side - solution is very slow (can be hundreds of times slower than plain F# function call), because of joining/spliting lists constantly. So if you need fast implementation of eval - you should optimize/rewrite this code if possible or take a look in other above mentioned solutions. But in systems where speed issues are not critical - this solution may be OK.

Have fun with F# and eval !!

Projecteuler.net problem 14 - Csharp vs Fsharp

Problem 14 stated as following:

The following iterative sequence is defined for the set of positive integers: n → n/2 (n is even) n → 3n + 1 (n is odd) Using the rule above and starting with 13, we generate the following sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain?

Ok, so here it is. Lets have fun with F#:

---

let seq_length n = n > Seq.unfold(fun x -> match x with
x when x = 0L -> None
x when x = 1L -> Some((1L,0L))
x when x%2L=0L -> Some((x,x/2L))
_ -> Some((x,3L*x + 1L))
) > Seq.length
[for i in 1L..1000000L -> (i, seq_length i)]
> List.fold1_left(fun (ai,al) (i,l) -> if l > al then (i,l) else (ai,al) )
> (fun (x,y) -> x ) > print_any

---

Elegant, slow version of solution-> ~20 lines; ~10 seconds.

Now lets try C#:

---

static long CountTerms(long x, ref long[] terms)
{
 long tc = 1;
 long k = x;

 while (k!=1)
 {
  tc++;
  k = (k % 2 == 0) ? k / 2 : 3 * k + 1;
  if (k <= x) 
  {
   if (terms[k] > 0)
   {
    terms[x] = terms[k] + tc;
    return terms[x];
   }
  }
 }
 terms[x] = tc;
 return terms[x] ;
}

static long LongestSeq()
{
 long max = 1000000;
 long[] termcount = new long[max+1];
 long tcmax = 0;
 long c = 0;
 long ix = 0;

 for (int i = 1; i <= max; i++) 
 {
  c = CountTerms(i, ref termcount);
  if ( c > tcmax)
  {
   tcmax = c;
   ix = i;
  }
 }
 return ix;
}

static void Main(string[] args)
{
 Console.WriteLine(LongestSeq());
 Console.ReadLine();
}

---

Ugly, fast version of solution -> ~0.18 second; ~60 lines.

Conclusion:

F# solutions can be done in more elegant/less code way, but in contrary it is slower that C#
counterpart. Also C# solutions can be written in fast way, but needs more code and attention.
F# solution was by factor 55 slower than C# solution, but also code was by factor of 3 shorter than C# counterpart. So if you want elegancy/generics power - take F#; and if you want only perfomance- take C#.
P.S. There is a way in F# to code (using mutable keyword) very very ugly like in C#, but i`ve not
suggest using it on F#,- why to code ugly in F# if you can grab C# instead ?? :-)