2
$\begingroup$

How can we find the list of natural numbers between 100 to 10000, whose positive divisors can be partitioned into three subsets such that sum of all the elements in three subsets will be equal?

$\endgroup$

1 Answer 1

6
$\begingroup$

Since the number itself is a divisor the divisors must sum to at least 3 times the number:

list = Range[100, 10000];
list = Pick[list, DivisorSigma[1, list] - 3 list // Negative, False]

and the divisor sum must be divisible by 3

list = Pick[list, Mod[DivisorSigma[1, list], 3], 0]

For the remaining integers LinearProgramming can attempt to make 3 equal disjoint subsets

getPartition = divs  Quiet[LinearProgramming[
     ConstantArray[0, 3 Length[divs]],
     Join[
          NestList[RotateRight, Join[#, #, #] &[UnitVector[Length[divs], 1]], Length[divs] - 1],
          {Join[divs, -divs, 0 divs], Join[0 divs, divs, -divs]}
     ],
     Join[
          ConstantArray[{1, 0}, Length[divs]],
          ConstantArray[{0, 0}, 2]
     ],
     ConstantArray[{0, 1}, 3 Length[divs]],
     ConstantArray[Integers, 3 Length[divs]]]];

For numbers between 100 and 10000 a solution is found everytime:

ConstantArray[Total[#]/3, {3, 1}] ===
 Partition[getPartition[#], Length[#]].Transpose[{#}] & /@ Divisors[list] // Tally
(* {{True, 169}} *)
$\endgroup$
1
  • $\begingroup$ So is there some property that guarantees a solution if it satisfies your two constraints? Sure seems like it. $\endgroup$
    – MikeY
    Apr 8, 2022 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.