2

I'm not a mathematician, so I may be asking this in an ambiguous way. I'll restate in a way that makes sense to me just in case.

In the set [2, 5, 9] there are no pairs that can divide evenly.

In the set [2, 4, 16] 2/4, 2/16, and 4/16, so there are 3 pairs that can divide evenly.

Is there a way to calculate this value without having to brute force through every combination?

If there's not a way to work out the exact value, is there a way compare two sets and work out which one has the higher value according to this property without knowing the exact value?

Thanks!

user1131308
  • 121
  • 1
    If the set is big, you can do better by constructing a directed graph whose nodes are the numbers and where there is an edge A→B if A divides B and there is no X such that A→X→B. Then you can compute the number of paths through the graph. For a large set of numbers this could be much faster than trying every pair. But for a small set, it's probably a waste of time. – MJD Jan 02 '18 at 23:07
  • Is there a good way to build the graph without trying to divide each pair of numbers? – Ward Beullens Jan 02 '18 at 23:36
  • I'm not mathematically literate enough to understand this approach. Could you possibly explain in more detail? – user1131308 Jan 03 '18 at 00:12
  • What is you concern? The number of comparisons? Or the brain power of doing the division? Translate each number into it's unique prime factorization. Then "division" is just a matter of comparing which numbers have solely equal or larger powers than the other. Much less brain power. ANd you only have to make the list once. But you will still have to compare each pair combinations. – fleablood Jan 03 '18 at 02:08
  • One thing you may not have considered is divisibility is transitive. If a divides b and b divides c then a divides c. So if you get 4|16 and you get 2|4 you know 2|16 without thinking. – fleablood Jan 03 '18 at 02:57
  • @fleablood Computing the prime factorization of all the integers is very expensive and will be more expensive than testing every pair by dividing. – Ward Beullens Jan 03 '18 at 20:38
  • Expensive in what sense? That's why I ask: What is the concern the OP has? And how do you test for divisibility without doing some factoring. As look as you are dividing and getting results you might as well keep track of your progress. – fleablood Jan 03 '18 at 21:07
  • If the OP wishes to do this by computer, it is computationally expensive. Even if doing this by hand, factoring is unnecessary. – theyaoster Jan 03 '18 at 21:32

0 Answers0