Problem 21: Amicable numbers

*Difficulty: Easy

Problem:

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where ab, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

How to solve:

What is AMICABLE NUMBERS : https://en.wikipedia.org/wiki/Amicable_numbers

I can only think of two ways

  1. Brute force

Assume  we got a method calculates sum of proper divisors of number, called sumDivisorsOf, then what we have to do is

 

Screen Shot 2016-06-30 at 6.09.18 PM

The runtime heavily depends on how you build the sumDivisorsOf method

This is the most easiest (but runs slowest)

Screen Shot 2016-06-30 at 6.12.17 PM

Combine with the above code, the solution took 385ms

To increase the speed, you need to modify the sumOfDivisors method, like using prime factorization, calculate sum of divisors of n, and then minus it from n (sum-=n) in order to get sum of proper divisors of n.

Screen Shot 2016-06-30 at 6.18.59 PM

You can you sieve Eratosthenes, or a method to check primality, for example

naive primality test

Screen Shot 2016-06-30 at 6.21.27 PM

2. Thābit ibn Qurra theorem

The Thābit ibn Qurra theorem is a method for discovering amicable numbers invented in the ninth century by the Arab mathematician Thābit ibn Qurra

It states that if

p = 3 × 2n − 1 − 1,
q = 3 × 2n − 1,
r = 9 × 22n − 1 − 1,

where n > 1 is an integer and p, q, and r are prime numbers, then 2n×p×q and 2n×r are a pair of amicable numbers. This formula gives the pairs (220, 284) for n=2, (17296, 18416) for n=4, and (9363584, 9437056) for n=7, but no other such pairs are known.

Unfortunately, this method cannot be applied to solve this problem, but here is the code for ones who’s curious.

import java.math.BigInteger;

import java.util.Scanner;

public class Prob21 {

 

publicstaticvoidmain(String[] args) {

Scannerinput = new Scanner(System.in);

BigIntegersum = BigInteger.ZERO;

int i = 1;

int n = input.nextInt();

long cur = System.currentTimeMillis();

while(i < n) {

BigIntegertwoPower_N_1 = BigInteger.valueOf(2l).pow(i1);

BigIntegertwoPower_N = BigInteger.valueOf(2l).pow(i);

BigIntegertwoPower_2N_1 = BigInteger.valueOf(2l).pow(2*i1);

BigIntegerp = BigInteger.valueOf(3l).multiply(twoPower_N_1).subtract(BigInteger.ONE);

BigIntegerq = BigInteger.valueOf(3l).multiply(twoPower_N).subtract(BigInteger.ONE);

BigIntegerr = BigInteger.valueOf(9l).multiply(twoPower_2N_1).subtract(BigInteger.ONE);

System.out.println(p+“-“+q+“-“+r);

if(isPrime(p)&&isPrime(q)&&isPrime(r)) {

BigIntegeran1 = BigInteger.valueOf(2l).pow(i).multiply(p).multiply(q);

BigIntegeran2 = BigInteger.valueOf(2l).pow(i).multiply(r);

System.out.println(an1 + ” – “ + an2);

sum= sum.add( an1.add(an2) );

}

i+=1;

}

System.out.println(sum);

System.out.println(“Took “ + (System.currentTimeMillis()cur) + ” ms”);

}

privatestaticbooleanisPrime(BigInteger bigN) {

if(bigN.compareTo(BigInteger.ONE) <= 0)

returnfalse;

else if(bigN.compareTo(BigInteger.valueOf(3l))<=0)

returntrue;

else if(bigN.mod(BigInteger.valueOf(2l)).compareTo(BigInteger.ZERO)==0

||bigN.mod(BigInteger.valueOf(3l)).compareTo(BigInteger.ZERO)==0)

returnfalse;

BigIntegerbigI = BigInteger.valueOf(5l);

while(bigI.multiply(bigI).compareTo(bigN)<=0){

if(bigN.mod(bigI).compareTo(BigInteger.ZERO)==0

||bigN.mod(bigI.add(BigInteger.valueOf(2))).compareTo(BigInteger.ZERO)==0)

returnfalse;

bigI = bigI.add(BigInteger.valueOf(6));

}

returntrue;

}

}

 

Advertisements