Amicable Number Calculator

Introduction

What are Amicable numbers? The answer can be found here in Wikipedia.

Someone asked me to help him for school to write an application that generates the first Amicable numbers pair, greater than 1,000,000 (one million). I wrote a small program that calculates this.

Amicable numbers are two numbers related such that the sum of the proper divisors of the one is equal to the other, unity being considered as a proper divisor but not the number itself. Such a pair is (220, 284); for the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110, of which the sum is 284; and the proper divisors of 284 are 1, 2, 4, 71, and 142, of which the sum is 220. Amicable numbers were known to the Pythagoreans, who credited them with many mystical properties.

The function that calculates the sum of the proper divisors is this:

public static int FastSum(int n)
{
    int sum = 1;
    int sqrt = (int)Math.Sqrt(n);
    for (int i = 2; i <= 1 + sqrt; i++)
        if (n % i == 0) sum = sum + i + n / i;
            return sum;
}

I'll explain this function a little bit. All divisors (in my function it is i) of a number are between 1 and sqrt of that number and each divisor has a pair at n / i. When I compute the sum, I need to add at sum i and n / i.

In the Main function, I have for between 1,000,000 and 2,000,000 - and also a time counter, because I want to know how long it takes for the execution (for each pair, and for full interval).

The Main function is as follows:

static void Main(string[] args)
{
    DateTime st = DateTime.Now;
    TimeSpan runTime;
    int s1, s2;
    for (int i = 1000000; i < 2000000; i++)
    {
        s1 = FastSum(i);
        s2 = (s1 > i) ? FastSum(s1) : 0;
        if (s2 == i)
            Console.WriteLine("{0} <==> {1} {2}", i, s1, 
            (DateTime.Now - st).TotalSeconds);
    }
    DateTime et = DateTime.Now;
    runTime = et - st;
    Console.WriteLine("Run Time: " + runTime.TotalSeconds);
    Console.WriteLine("Press enter to exit!");
    Console.ReadLine();
}

First, I save the starting time: DateTime st = DateTime.Now; and after this, I start to verify each number greater than 1 million, using a for cycle.

I write for each founded pair Console.WriteLine("{0} <==> {1} {2}", i, s1, (DateTime.Now - st).TotalSeconds); the numbers and the computing time.

The complete program is as given below:

using System;

    class Program
    {
        public static int FastSum(int n)
        {
            int sum = 1;
            int sqrt = (int)Math.Sqrt(n);
            for (int i = 2; i <= 1 + sqrt; i++)
                if (n % i == 0) sum = sum + i + n / i;
            return sum;
        }
        static void Main(string[] args)
        {
            DateTime st = DateTime.Now;
            TimeSpan runTime;
            int s1, s2;
            for (int i = 1000000; i < 2000000; i++)
            {
                s1 = FastSum(i);
                s2 = (s1 > i) ? FastSum(s1) : 0;
                if (s2 == i)
                    Console.WriteLine("{0} <==> {1} {2}", i, s1, 
                    (DateTime.Now - st).TotalSeconds);
            }
            DateTime et = DateTime.Now;
            runTime = et - st;
            Console.WriteLine("Run Time: " + runTime.TotalSeconds);
            Console.WriteLine("Press enter to exit!");
            Console.ReadLine();
        }
    }

This was C# code. If someone needs the C version (translation) of this code, here it is:

#include "stdafx.h"
#include <ctime>
#include <math.h>
#include < iostream>

using namespace std;

int FastSum(int n)
{
   int sum = 1;
   double m = n;
   for (int i = 2; i <= sqrt(m); i++)
      if(n % i == 0) sum += (i + n / i);
   return sum;
}
void main()
{
   int s1 = 0, s2 = 0, i = 1000000;
   bool ok = true;
   clock_t st = clock();
   //for (; ok ; )
   while (ok)
   {
      s1 = FastSum(i);
      s2 = (s1 > i) ? FastSum(s1) : 0;
      if (s2 == i++) cout << i - 1 << " <==> " << s1 << "  " << 
            (clock() - st)/1000.0 << (ok = false) <<endl;
   }

   clock_t et = clock();
   cout << "Time: " << (et-st)/1000.0 << endl;
   system("pause");
}

English is not my first language, so I apologize for any language mistakes!

History

• 14^th January, 2007: Initial post