Amicable Numbers

05Oct13

In the twelve months from March 2013 to March 2014, I programmed solutions to the problems posted on the Contest Coding blog run by Lewis Cornwall, solving 33 problems (out of 47) and achieving a position of 4th on the leaderboard (out of 23).

As that blog has now been discontinued, I’m posting here the solutions I programmed to those problems.

Amicable Numbers

A pair of amicable numbers contain two numbers such that the sum of the divisors of the first number comes to the second number and that the sum of the divisors of the second number comes to the first number (220, 284 for example). Find the sum of the two pairs of the third amicable pair.

Solution and answer (Amicable_Numbers.java):

/*
Solution and answer for problem "Amicable Numbers" (5th October 2013) of http://ContestCoding.WordPress.com/

Sat Oct 05 09:00:00 GMT+01:00 2013

5544

Sat Oct 05 09:00:05 GMT+01:00 2013

Solution programmed in Java using Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition); solution took ~5s to run on a 80MHz PowerPC 601.
*/

import java.util.Date;

public class Amicable_Numbers
{
  public static void main( String p[] )
  {
    System.out.println( new Date());

    NumberList numberList = new NumberList();
    int a = 0, number_of_amicable_pairs_found = 0, sum_of_amicable_pair = 0 /* The value assigned to sum_of_amicable_pair is irrelevant, and is assigned only to suppress the compile-time error. */;
    do
    {
      int b = sumOfDivisors( ++ a );
      int a_from_b = sumOfDivisors( b );
      if(( a == a_from_b ) && ( a != b ) && !numberList.contains( a ) && !numberList.contains( b ))
      {
        number_of_amicable_pairs_found ++;
        sum_of_amicable_pair = a + b;
        numberList.add( a );
        numberList.add( b );
      }
    }
    while( number_of_amicable_pairs_found < 3 );
    System.out.println( "\n" + sum_of_amicable_pair + "\n" );

    System.out.println( new Date());
  }

  private static int sumOfDivisors( int p )
  {
    int sum_of_divisors = 0;
    for( int divisor = p / 2; divisor > 0; divisor -- )
      if( p % divisor == 0 )
        sum_of_divisors += divisor;
    return sum_of_divisors;
  }
}

class NumberListNode
{
  public NumberListNode m_n = null;
  public int m_number;

  NumberListNode( int p )
  {
    m_number = p;
  }
}

class NumberList
{
  private NumberListNode m_first = null, m_last;

  public void add( int p )
  {
    NumberListNode n = new NumberListNode( p );
    if( m_first == null )
      m_first = n;
    else
      m_last.m_n = n;
    m_last = n;
  }

  public boolean contains( int p )
  {
    NumberListNode n = m_first;
    while( n != null )
    {
      if( n.m_number == p )
        return true;
      n = n.m_n;
    }
    return false;
  }
}
Advertisements


No Responses Yet to “Amicable Numbers”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: