Is there a fast way to find all multiple pairs in a list?

Questions
1

On small lists of numbers using subsets and cases works reasonably well, but is slow when the list contains a few million entries.

list = {616, 720, 1352, 1504, 2288, 3136, 3744, 4600, 4752, 5720, 
   7000, 7280, 8568, 8800, 10296, 12312, 13832, 16456, 20224, 23400, 
   27056, 27720, 32032, 37904, 39208, 46376, 61272, 70720, 83600, 
   102200, 117936, 139392, 184016, 306720, 353912, 418264, 511216, 
   920200, 1533672, 4601024};

Cases[Subsets[list, {2}], {a_, b_} /; Mod[b, a] == 0]

{{616, 27720}, {616, 32032}, {616, 418264}, {720, 306720}, {1352, 
  39208}, {2288, 32032}, {8568, 1533672}}
2

I’m pretty sure it’s the Subsets that really slows that down, I think that would try (and presumably fail) to create a list in memory of 10^{12} pairs, if you’re using a set with a million numbers.

Anyway, depends how fast you’re looking for. My first stab is

s = Sort[RandomInteger[{2, 100000000}, 100000]];
Timing[r = 
  Flatten[Table[{s[[i]], #} & /@ 
     Pick[s[[;; i - 1]], Mod[s[[i]], s[[;; i - 1]]], 0], {i, 2, 
     Length@s}], 1]; r[[{1, 2, 3, -3, -2, -1}]]]

which takes about 30 seconds on my machine for 100k numbers:
{30.1719, {{194616, 194616}, {348102, 498}, {355572, 498}, {99883982, 4540181}, {99889338, 498}, {99950842, 49975421}}}

3

Trevor,

Thank you for your quick reply, your code is certainly faster without the subsets. here are a few results showing how much faster on the following length of list

1097 is x 39
3280 is x 78
9841 is x 2.68
29524 is x 2.66

There are some quite large numbers in the latter lists. The big difference is that last list used up almost 32gb memory using subsets and hardly anything with your code, so is a definite winner.