I Write

This was another interesting problem at Project Euler (Problem 12). Interesting because the naïve solution to this was all too trivial but slow, which forced me to seek out a better approach and I finally ended up learning something new  

The nth triangle number is defined as the sum of all natural numbers till n. Well, that’s definitely trivial to calculate. It’s basically the sum of first n natural numbers and can be calculated using the well known formula:   

So, all that remains is to calculate the divisors and we all know how to do that right? Just count the numbers from 2 to half (or square root, if you prefer) the triangle number that divide the triangle number. So, here’s the code I started with: 

// Sum of first n natural numbers
let triangle_number (n:bigint) =
    (n * (n + 1I)) / 2I ;;
 
let divisors (n:bigint) =
    let rec divisor_loop (i:bigint) (a_list:bigint list) =
        if (i = 1I) then
            (i :: a_list)
        else if ((n % i) = 0I) then
            (divisor_loop (i - 1I) (i :: a_list))
        else
            (divisor_loop (i - 1I) a_list)
 
    (divisor_loop (n / 2I) [n;]) ;;

As it turned out, using this method, it takes a really looooong time to even find the divisors of a large number, let alone use it for searching the triangle number with over 500 divisors.

So, I started looking for alternate methods, and finally found one here: http://www.algebra-online.com/positive-integral-divisors-1.htm (you’ll have to scroll to the end of the page to get to the part where they explain finding the number of divisors for a number)

The idea is simple actually. Take 5050 for example (the 100th triangle number). It’s prime factors are: 2, 5, 5 and 101. Now reduce the list to a list of unique numbers with their repetition represented in their exponents. So, the list 2, 5, 5, 101 becomes: 2¹, 5²,101¹. Now, add 1 to every exponent and multiply the resulting numbers. So, that would give us: (1+1) * (2 + 1) * (1 + 1) = 12. That’s the number of divisors that 5050 has. And, of course, that can be verified using the divisors method:

(divisors 5050I);; -> [1I; 2I; 5I; 10I; 25I; 50I; 101I; 202I; 505I; 1010I; 2525I; 5050I]

Since I’d already written a function to find the prime factors to solve Problem 3, solving this one was just a matter of writing code to search through a list of triangle numbers to find the first one with more than 500 divisors. Here’s the final code I ended up with:

// Sum of first n natural numbers
let triangle_number (n:bigint) =
    (n * (n + 1I)) / 2I ;;
 
let divides (n:bigint) (i:bigint) =
    n % i = 0I ;;
 
let is_prime (n:bigint) =
    let rec prime_check_loop (i:bigint) =
        ( i > (n / 2I) ) || ((not (i |> divides n)) && prime_check_loop (i + 1I))
 
    prime_check_loop 2I ;;
 
let rec prime_factors (n:bigint) (factors:bigint list) =
    if (is_prime n) then
        n :: factors
    else
        let mutable i:bigint = 2I;
        while (n % i <> 0I) && (i <= n/2I) do
            i <- i + 1I
        done
 
        if( i <= n/2I) then
            factors @ (prime_factors i factors) @ (prime_factors (n / i) factors)
        else
            [] ;;
 
open System.Collections.Generic
 
let prime_factor_map (factors:bigint list) =
    let factor_map = Dictionary<bigint, bigint>()
 
    for factor in factors do
        if (factor_map.ContainsKey(factor)) then
            factor_map.[factor] <- (factor_map.[factor] + 1I)
        else
            factor_map.Add(factor, 1I)
    done
 
    factor_map ;;
 
let number_of_divisors (n:bigint) =
    let factor_map = (prime_factors n []) |> prime_factor_map
    let exponents = factor_map.Values
    let mutable divisor_count = 1I
 
    for exponent in exponents do
        divisor_count <- (divisor_count * (exponent + 1I))
    done
 
    divisor_count ;;
 
let triangle_number_search (minimum_divisor_count:bigint) =
    let mutable keep_searching = true
    let mutable next = 1I
    let mutable n = (triangle_number next)
 
    while keep_searching do
        let divisor_count = (number_of_divisors n)
        if (divisor_count < minimum_divisor_count) then
            next <- next + 1I
            n <- (triangle_number next)
        else
            keep_searching <- false
    done
    n ;;

This took less than a minute to run and running it gives:

(triangle_number_search 500I);; -> 76576500I

So, the first triangle number to have over 500 divisors is: 76576500
(btw, it has 576 divisors)

(and as you can see, I’m still not very proficient with F# )

My current project is a UML modeling tool, and I’m working on the C# 3.0 bits. One of the things it lets you do is to Reverse Engineer your code and obtain the model. And that includes reversing the assemblies too.

C# 3.0 introduced Auto Properties (or Automatically Implemented Properties if you like the wordy versions ), and the tool lets you model them. To maintain the symmetry, reverse engineering should detect and mark the Auto Properties appropriately. This’s easy in case of a source file since the rule for identifying an Auto Property is pretty simple. It’s a property contained in a concrete type (non-abstract class/struct) which has both it’s accessors without their implementing bodies. Simple, eh?

But it gets a wee bit more complicated to do that once you compile it. Because, the compiler generates a body for the Auto Property accessors. So, the last bit about the accessors not having an implementing body fails. Essentially, it seems like there’s no way to distingush an Auto Property from a regular one once it’s been compiled. And in fact, you shouldn’t have to because that’s the whole idea! Auto Properties help reduce some clutter in code and possibly save you a few keystrokes and let the compiler do the gruntwork. So, if you’re trying to distinguish an Auto Property, think again. You probably don’t have to.

Anyways, I still wanted to see if there’s a way to do it and the first thing I did was to Google for it. Since that didn’t turn up anything useful, I decided to figure it out myself and fired up Reflector. Long story (relative to a blog post, that is) short, I figured it out and decided to write this post to fill up a gaping hole in the public knowledge base

The C# compiler decorates all the stuff it generates with the CompilerGeneratedAttribute. Even vbc.exe & vjc.exe should do the same, but I haven’t checked. Since the accessors of an Auto Property are generated, they’re decorated too  Therefore, the rule for identifying an Auto Property after it’s been compiled is: It’s a property which has both the accessors, both of which have been decorated with the CompilerGeneratedAttribute. Simple isn’t it?

Here’s what my C# code looks like:

using System.Reflection;
using System.Runtime.CompilerServices;
 
public class PropertyWrapper
{
	private PropertyInfo _property;
 
	public PropertyWrapper(PropertyInfo property)
	{
		_property = property;
	}
 
	public bool IsAutoProperty
	{
            get
            {
            	return isGenerated(_property.GetGetMethod(true))
                    && isGenerated(_property.GetSetMethod(true));
            }
	}
 
    private bool isGenerated(MethodInfo method)
    {
        return method != null
            && method.GetCustomAttributes(typeof(CompilerGeneratedAttribute), false).Length == 1;
    }
}

Ironically, after doing all these, I realized there’s not much sense in distinguishing them anyway. I mean, they are your regular properties for most of the purposes. Moreover, in my case, the the information derived from the assembly is used only to let the user extend the existing types. i.e. create generalizations and such.. So, even the existing implementation doesn’t bother showing the assembly types in much detail. They’re mostly limited to the high level details like classes, interfaces and such..

Ultimately, it wasn’t really useful, but was interesting nonetheless

Subtext is a visual programming language where you express the application logic in a tabular fashion. I’m not gonna try to explain Subtext in this post. You can find out more from its homepage: http://subtextual.org/.

I learned about Subtext nearly 2 months back. It sounded interesting, but all I could find on the site were 2 screencasts and a bunch of papers. Apparently, it’s still a research project and the prototype used in the screencast isn’t publicly available yet. I was a little disappointed, and almost forgot about it until today.

Today, someone posted this link on programming reddit where someone had posted a link to the the page where Jonathan Edwards (Subtext creator) has posted a link to the prototype used in the demo! (hmm.. that was just 3 indirections   but still, here’s a direct link to the download if all that confused you: http://subtextual.org/subtext2.zip ) Yay! Finally, something for me to dabble with   And guess what, it’s even got the sources!

I’m not expecting much from the prototype (not yet). Good if it’s mature enough for me to go beyond the hello worldish programs. Even otherwise, I’m happy just to play around

I’ve written about Project Euler in my previous post (which I guess was the day before yesterday). I was going pretty well with solving the problems until I reached this one – to calculate the sum of all primes below 2 million. That’s the 10th problem in Project Euler and the one I’ve had to spend the most time on till now. It’s a fairly trivial problem, if you exclude the scale that is. If you’re planning to calculate 2 million primes with your regular algorithm which checks each number for primality, then you better run it on a supercomputer

I’m solving these problems in F#, and this’s what I started with:

 
let divides (n:bigint) (x:bigint) =
    n % x = 0I;;
 
let is_prime (n:bigint) =
    let rec prime_check_loop (i:bigint) =
        ( i > (n / 2I) ) || ((not (i |> divides n)) && prime_check_loop (i + 1I))
 
    prime_check_loop 2I;;
 
let rec next_prime (from:bigint) =
    if from < 2I then 2I
    else if is_prime (from + 1I) then (from + 1I)
    else next_prime (from + 1I) ;;

As a quick test, I tried calculating the next prime after 2 million and got the result fairly immediately. Happy with that, I started writing the summation code.

 
let sum_of_primes_below (limit:bigint) =
    let rec add_prime (n:bigint) (acc:bigint) =
        let next = next_prime n
        if next < limit then
            add_prime next (acc + next)
         else
            acc
 
    add_prime 0I 0I;;

Did a quick check for the sum of primes below 10, 20, 200, 2000 and 20000. The last one took a bit of time, but that didn’t really concern me much. After all, it’s my computer doing the job right?

So, ask it to calculate the sum of all primes below 2 million and left it for a minute. I switch back to the F# interactive window and see that it’s still happily calculating. I check the fsi.exe process, and it’s maxing out one of the cores completely and taking around 50M. So, I leave it for a little longer. Now, I start getting worried about the range of BigInt and whether the result would overflow. So, I quickly google around and see that BigInt is for arbitrarily large integers. Then found that the SQL Sever BigInt is actually a 64 bit int, so guess even the .net type is the same, and that maxes out at 2⁶⁴ – 1 = 9,223,372,036,854,775,807. hmm.. Is the sum larger than that? It’s already been around 4 minutes and I’m impatient. So I google around for the solution and found a Yahoo! Answers page which says that the sum of all primes below 2 million is 142,913,828,922. That’s good. coz, now at least I’m confident that it won’t overflow and keep looping forever.

I knew that the Sieve of Eratosthenes can be used to calculate primes, but always took it lightly. I mean, how often do you go about calculating an entire series of primes? Turns out, this is one of those times

I realized that Sieve of Eratosthenes is probably the best solution for this problem, but since my code has already been running for over 10 min, I was hoping to get an answer anytime soon, so didn’t bother implementing the sieve. When I didn’t get the answer for another 20 mnutes, I had given up all hopes on my solution and I knew it was time I implemented the sieve. But just for curiosity, I tried estimating how long it’d take to get to the solution with my current method.

Assuming 1 sec per primality check, that’s about 2 million seconds = 23.1481481 days. Not good. Not good at all I thought that must be ridiculously wrong, since 2 million still didn’t seem like that large a number to handle. So, I tried running my code for 2000 (two thousand) and that took about a second. Then I ran it for 20000 (twenty thousand) and that took about 30 seconds. hmm.. That’s about a 30 times increase for a 10 times increase in the input size. So, for 200000 (two hundred thousand), it should take approximately 900 sec which’s 15 minutes. But well, I must’ve been estimating it completely wrong since even after 30 minutes, it was still calculating! But, even considering just 15 minutes for the two hundred thousand and extrapolating it, it’d have taken at least 7.5 hours! (which I did test and that estimate’s wrong too I left it overnight and woke up to see it still calculating.. )

So, finally I decided to generate primes with the sieve method and sum them up for the result. So, I ended up with this:

 
let prime_series_sieve (limit:bigint) =
    let series = List.to_array [0I..limit]
    series.SetValue(0I, 1)
 
    let rec eliminate_multiples (n:bigint) (i:bigint) =
        let index = (i * n) // Just to reduce as many calculations as possible
        if index < bigint.Parse(series.Length.ToString()) then
            series.SetValue(0I, (bigint.ToInt64(index)))
            eliminate_multiples n (i + 1I)
 
    for n in [2I..(limit/2I)] do
        eliminate_multiples n 2I
 
    series;;
 
let sum_of_primes_under (limit:bigint) =
    Array.sum (prime_series_sieve limit);;

After a few quick tests for the some smaller numbers, I let it calculate the for 2 million and hurray! It gave me the right answer! It took about 2.5 minutes and had a memory footprint of around 250 M, but I was happy just to get the answer

Of course it can still be improved. The wikipedia page suggests a few optimizations like Wheel Factorization. But I’m not gonna worry about that for now. I’ve got F# to learn and a whole lotta problems to solve

You’ve probably heard of Project Euler (http://projecteuler.net/). If you haven’t, I suggest you check it out. It’s an amazing collection of interesting mathematical and programming problems. Nowhere else have I seen such a quality collection of problems.

I had known of Project Euler for a long time, but never found a good reason to actually try it out. Recently (3 days back) I thought of getting comfortable with F#. I believe that the best way to learn a language is to use it to solve some real problems. That’s when I remembered Project Euler.

Some of the problems over there can be answered with just pen and paper. But most of them require you to write some code in order to get to the solution. That’s not to say you can ignore the math behind it (hmm.. of course you can, but I wouldn’t suggest it )  Understanding the underlying math concepts for a problem helps you devise better solutions (instead of going the brute-force way).

I’ve been sorta doing it the other way around. I look at a problem, chart out a quick solution. Google if needed to understand some background, but try to arrive at the solution by some means. Once I have the answer, I go thru solution thread which generally has some good insights into the problem.

I was almost scared when I spent 2 evenings to solve the just the first two problems. But that was mostly getting to know the language than getting to the solution itself. Now that I know F# a little better, I’m going much faster. Today I solved 4 of them ( ) and I definitely feel good about it (and that’s why this post )

One interesting thing is that there arent a lot of members in Project Euler who’re using F#. The count (as of today) is just around 160. And from India, I am the only member using F#

Btw, my handle on Project Euler is CodeMangler (my standard online handle, except in games)

Some of the later problems sound pretty interesting. Can’t wait to get to them. Nope, they arent locked or anything. I’m just forcing myself to solve them in order   Anyways, I just hope to solve the remaining 220ish problems asap and get to the top of the list soon (overambitious.. I know)