Get all subsets of the given number's divisors and check if they don't violate the conditions

Question

So I have this question, which I don't quite understand.

I would like to understand the approach of the problem

Imagine the following scenario:

You are the HR manager of a company with 1000 employees numbered for 1 to 1000. Your boss told you to give a big Christmas bonus to employees, but didn’t tell you their names. Instead they gave you two indications:

1) the sum of the proper divisors (including 1 but not itself) of the employee number is greater than the employee number itself

2) no subset of those divisors sums to the employee number itself.

How many employees are eligible for the bonus and what are their number?

For example: - Number 12: the proper divisors are 1, 2, 3, 4 and 6. The sum is 1+2+3+4+6 = 16 which is greater than 12 and matches the first condition. However, the subset 2+4+6=12 which violates the second condition.

My conclusion is: I have to get those numbers from 1 to 1000, where the sum of the number's divisors are greater than the number itself (including 1 but not itself), but none of the divisors' subsets can be added to be equal with the number itself?

My steps would be:

• Put the divisors of the numbers from 1 to 1000 into an array
• Get those numbers, when the divisors' sum (including 1 but not itself) are greater than the number itself and resize the array to only those numbers.
• I have to check every subset of the remaining number's divisors and remove those when a subset of the divisors can be equal with the number itself.

Could you help me if it's a good approach or do any of you know a more efficient/better way?

Any help would be appreciated!

NOTE: I don't want you to solve it, I want to understand it!

Answer 1

My code in python:

def getDivisors(n):
    div = []
    for i in range(1, n-1):
        if(n%i == 0):
            div.append(i)
    return div

def sumDivisors(arr):
    div_sum = 0
    for i in arr:
        div_sum += i
    return div_sum

def subLists(arr):
    lists = [[]]
    for i in range(len(arr)):
        orig = lists[:]
        new = arr[i]
        for j in range(len(lists)):
            lists[j] = lists[j] + [new]
        lists = orig + lists
    return lists

def sumSublists(lists, n):
    for i in range(len(lists)):
        sum_list = sum(lists[i])
        if (sum_list == n):
            return False
    return True

for num in range(100):
    arr = getDivisors(int(num))
    lists = subLists(arr)
    if ((sumDivisors(arr) > int(num))and(sumSublists(lists, int(num)))):
        print(str(num) + '/n')

Answer 2

PHP approach:

$empList = [];

        for ($emp = 1; $emp <= 100; $emp++) {

            $multiples = [];
            $subset = [];
            $cond1 = false;
            $cond2 = false;

            // Get multiples.
            for ($i = 1; $i < $emp; $i++) {
                if ($emp % $i == 0) $multiples[]= $i;
            }

            // Condition 1
            if (array_sum($multiples) > $emp) $cond1 = true;


            foreach ($multiples as $num) {
                if ($num % 2 == 0) $subset[]= $num;
            }

            // Condition 2
            if (array_sum($subset) > $emp) $cond2 = true;

            if ($cond1 && $cond2) $empList[] = $emp;
        }

        echo "<pre>";
        var_dump($empList);
        echo "</pre>";

Output:

Array
(
    [0] => 24
    [1] => 36
    [2] => 40
    [3] => 48
    [4] => 60
    [5] => 72
    [6] => 80
    [7] => 84
    [8] => 96
)

Answer 3

I have made this so far, which covers the first two steps that I intended to do. Last step is beyond my knowledge, but I have the solution for that also.

This is my code:

<script type="text/javascript">
  function getDivisors(n){
    var divisors=new Array();

    for(var x=1;x<n;x++){
      if(n%x==0) divisors.push(x);
    }
    return divisors;
  }


  function getNumbers(n){
    var numbers=new Array(),
    sum=0;

    for(var x=1;x<=n;x++){
      sum=getDivisors(x).reduce((a, b) => a + b, 0);
      if(sum>x) numbers.push(x);
      // console.log("Number: "+x+" sum:"+sum);
    }
    return numbers;
  }

  var remainingNumbers = getNumbers(1000);
  console.log(remainingNumbers);

</script>

This is the answer for the question:

var out = document.getElementById('outLine');
out.innerHTML += "X\t»\tSUM\tSUM-X\tLIST\r\n";
function isSubsetSum(set, n, sum)  { 
	if (sum == 0) { return true; }
	if (n == 0 && sum != 0) { return false; }
	if (set[n - 1] > sum) { return isSubsetSum(set, n - 1, sum); }
	return isSubsetSum(set, n - 1, sum) ||
		isSubsetSum(set, n - 1, sum - set[n - 1]); 
} 
function v1chNum(x) {
	var r = [1];
	var n = 0;
	var m = x/2;
	for(var i = 2; i <= m; i++ ) {
		if(x%i==0) {
			if(r.indexOf(i)==-1) {
				r.push(i);
				n += i;
			}
			m = x/i;
			if(r.indexOf(m)==-1) {
				r.push(m);
				n += m;
			}
		}
	}
	if( n > x ) {
		r.sort(function(a, b) {return b - a;});
		if(!isSubsetSum(r,r.length,x)) {
			out.innerHTML += x+"\t»\t"+n+"\t"+(n-x)+"\t"+r+"\r\n";
		} else { return false; }
	} else { return false; }
}
for(var x = 1; x<1000; x++) {
	v1chNum(x);
}

<pre id="outLine"></pre>