Finding Weird Number in Javascript-CodePudding

A weird number is a number that the sum of proper divisors is greater than the number itself and no subset of proper divisors sum to that number.

Examples:

70 is a weird number because its proper divisors (1, 2, 5, 7, 10, 14, and 35) sum to 74, which is greater than 70, and no combination of these numbers sum to 70.

18 is not a weird number because its proper divisors (1, 2, 3, 6, 9) sum to 21, which is greater than 18, but 3, 6, and 9 sum to 18.

I am trying to write a JavaScript function that gets this weird number from 1 to 100

I am struggling at condition #2 no subset of proper divisors sum to that number.

UPDATE : I could get this much logic for condition #2

 // assuming we put all the divisiors in an array.
36 => [1,2,3,4,6,9,12,18]

// we take first two numbers
[1,2] 
// are they less than 36?
yes

arr.forEach(n,idx){
  let k = arr[idx]   arr[idx 1]
  if(k<36){
    let sum = 0
    sum = k   arr[idx 2]
  }
}

I could figure the logic behind it but I couldn't solve it.

function magicNum(){
  let arr = []
  for(let i =0;i<=100;i  ){
    arr.push(i)
  }
  arr.forEach(n=>{
  let sum = 0
  for(let i = 1 ; i<n ; i  ){
    if(n%i===0){
      sum =i
      }
    }
  if(sum > n){
      console.log(n) // I could get the first condition
    }
  })
}

magicNum()

CodePudding user response：

You could check each possible combination by using a bitmask for the values.

const
    check = (value, array) => {
        let n = 1 << array.length;
        while (n--) {
            if (value === array.reduce((s, v, i) => s   v * !!(1 << i & n), 0)) {
                return true;
            }
        }
        return false;
    };

console.log(check(18, [1, 2, 3, 4, 6, 9]));
console.log(check(70, [1, 2, 5, 7, 10, 14, 35]));

CodePudding user response：

I would do this with three reusable functions. divisors lists all the divisors of a number, powerset lists all the subsets (as arrays) of a set (also given as an array), and sum adds a list of numbers.

Then we can combine them by taking the divisors, removing the final one (the original number), and then taking all subsets of that set, and checking whether any of these subsets sums to the initial number. It would look like this:

const divisors = (n, i = 1, inc = [], dec = []) =>
  i * i > n 
    ? [...inc, ...dec .reverse ()]
  : n % i == 0 
    ? divisors (n, i   1, [...inc, i], i * i == n ? dec : [...dec, n / i])
  : divisors (n, i   1, inc, dec)

const powerset = ([x, ...xs]) =>
  x == undefined
    ? [[]]
    : powerset (xs) .flatMap (ss => [ss, [x, ...ss]])
    
const sum = (ns) => 
  ns .reduce ((a, b) => a   b, 0)

const weirdNumber = (n) =>
  ! powerset (divisors (n) .slice (0, -1)) .some (ss => sum (ss) == n)

console .log (weirdNumber (70))
console .log (weirdNumber (18))

sum is trivial, and powerset is a simple enough recursion. divisors is a little more tricky, as we simultaneously accumulate the increasing small divisors and the decreasing large one, merging them together at the end. Thus when checking divisors (72) we will have these values in the recursive steps:

i	inc	dec
1	[1]	[72]
2	[1, 2]	[72, 36]
3	[1, 2, 3]	[72, 36, 24]
4	[1, 2, 3, 4]	[72, 36, 24, 18]
5	[1, 2, 3, 4]	[72, 36, 24, 18]
6	[1, 2, 3, 4, 6]	[72, 36, 24, 18, 12]
7	[1, 2, 3, 4, 6]	[72, 36, 24, 18, 12]
8	[1, 2, 3, 4, 6, 8]	[72, 36, 24, 18, 12, 9]

and then, because 9 * 9 is greater than 72, we are done and reverse dec and return its concatenation with inc.

The special processing i * i == n ? ... is to handle the case where the number is a perfect square. In divisors (49) for instance, we wouldn't want to include 7 in both inc and dec.

The main function is simple enough, using some to test if any subset has a matching sum, and negating the result.

Note that divisors, powerset, and sum are all reusable functions. Only weirdNumber is specific to this problem.

CodePudding user response：

function magicNum(){
  function checkSubsets(idx, arr, curr, target) {
    if (curr === target) return true

    for (let i = idx; i < arr.length; i  ) {
      if (checkSubsets(i 1, arr, curr arr[i], target)) return true
    }
    return false
  }
  let arr = []
  for(let i =0;i<=100;i  ){
    arr.push(i)
  }
  arr.forEach(n=>{
  const divisors = []
  let sum = 0
  for(let i = 1 ; i<n ; i  ){
    if(n%i===0){
      divisors.push(i)
      sum  = i
      }
    }
  if(sum > n){
      console.log(n) // I could get the first condition
    }
  if (checkSubsets(0, divisors, 0, n)) {
    console.log("One of the subsets of "   n   "equals "   n)
  }
  })
}

magicNum()

I don't know much JavaScript, so sorry if this is not very clean. The bulk of the subset checking algorithm is in checkSubsets.

  function checkSubsets(idx, arr, curr, target) {
    if (curr === target) return true

    for (let i = idx; i < arr.length; i  ) {
      if (checkSubsets(i 1, arr, curr arr[i], target)) return true
    }
    return false
  }

As you can see, it takes the index of the current item idx, the array of all proper divisors arr, the sum of the current subset curr, and the target which is the n we are currently examining.

It the recursively calls itself by incrementing the index by one and adding the current item to the current total sum. If it finds curr == target it returns true. After checking all combinations, if it doesn't find anything, it returns false.

To make sure the number is weird, you need to make a test like follows:

if (sum <= n && !checkSubsets(0, divisors, 0, n) {
  console.log(n   " is weired, because the sum of its proper divisors was smaller or equal to itself and no subset of its divisors was equal to it")... }

CodePudding user response：

This page stated:

A "weird number" is a number that is abundant (i.e., the sum of proper divisors is greater than the number) without being pseudoperfect (i.e., no subset of the proper divisors sums to the number itself). The pseudoperfect part of the definition means that finding weird numbers is a case of the subset sum problem.

My code below doesn't take pseudoperfect subsets into mind.

How I went about to solve this:

1 will always be added: in code, sum starts on 1.
you only need to loop the lower half the possibly weird number, and instead add both the divider and the result to the sum: in code, will only loop to half.
you need to keep track if the number have already been added, because 5 * 14 is lower than (70/2=) 35 and will be calculated twice (5 14, 14 5) in the lower part of the possibly weird number: in code, addedNumbers keeps track on that.

You could write this in a shorter way, but I prefer to have readable code.

function isWeird(number) {
  let half = parseInt(number / 2) - 1,
      sum = 1,
      evenNumber = -1,
      addedNumbers = new Set();
  
  for (let divider = sum 1; divider < half; divider  ) {
    evenNumber = parseInt(number/divider);
    
    if (!addedNumbers.has(divider) && number / divider == evenNumber) {
      sum  = divider   evenNumber;
      addedNumbers.add(divider);
      addedNumbers.add(evenNumber);
    }
  }
  
  let isWeird = sum > number;
  
  return {number, sum, isWeird}; 
}


let value = 70;

console.log(isWeird(value));

value = 10;

console.log(isWeird(value));