Skip to main content

Betrothed numbers

Betrothed numbers are two positive numbers such that the sum of the proper divisors of either number is one more than (or one plus) the value of the other number. Our task is to find these pairs efficiently.


function betrothed(n)
{
  var res = [];
  for(var num1 = 1; num1 < n; num1++)
  {
    var sum1 = 1;
    for(var i = 2; i * i <= num1; i++)
    {
      if(num1 % i === 0)
      {
        sum1 += i;
        if(i * i != num1) sum1 += num1 / i;
      }
    }
    if(sum1 > num1)
    {
      var num2 = sum1 - 1;
      var sum2 = 1;
      for(var j = 2; j * j <= num2; j++)
      {
        if (num2 % j === 0)
        {
          sum2 += j;
          if(j * j != num2) sum2 += num2 / j;
        }
      }
      if(sum2 === num1+1) res.push([num1, num2]);
    }
  }
  return res;
}