PHP array product combinations

Question

I have produced an array of prime factors of a number - this is supposed to be the hard part! However, in order to create a list of the divisors of the same number the prime factors need to be combined in every which possible way. Something that I'm struggling to do with php.

For example I have an array of:

2
2
2
3
3
41
53

...for the number 156456; multiply them all together and you get back to the number. What I need to do is to multiply all of the duos together e.g. 2x2, 2x3, 2x53 etc and then all of the triplets together and so on until I finally multiply the 7 blocks of six together.

As you can see this will give a very large array with all of the divisors in, 4, 6, 8, 9, 12 etc. with many duplicates. I just can't seem to get from the array I have above to this array of divisors that I want. It's a case of multiplying out every possible combination of elements in the array, is there a php function for this, my search so far has been fruitless?

• MarcDefiant: use array_unique to remove duplicates
• Tarandeep Gill: There is no such official PHP function. You will have to write your own algorithm. Or you can try finding an open source implementation.
• user1967034: Can anyone give me a point in the right direction, my guess is that I find out how many elements are in the array and then loop through so for the above I would have 6 loops where I brought duos in and then triplets in etc, but still not sure how to implement
• David Newcomb: I can't see what you want. What do you mean duos, triplets, 7 blocks of six? Maybe you could clarify that paragraph?

Answer 1

After reading this page: http://mathcentral.uregina.ca/QQ/database/QQ.02.06/joe1.html, I tried to build something that might work, It may not be the most efficient solution and its also limited to count($primes) <= 32 on 32 bit systems. If you need more, feel free to use a Bitset:

$primes = Array(2, 2, 2, 3, 3, 41, 53);
$num_primes = count($primes); // 7, if this is over 32, it won't work on 32bit systems
$divisors = Array();
// number of possible combinations
$limit = pow(2, $num_primes) - 1; // 127
// count a number up and use the binary 
// representation to say which index is
// part of the current divisor
for($number = 0; $number <= $limit; $number++) {
 $divisor = 1;
 // only multiply activated bits in $number to the divisor
 for($i = 0; $i < $num_primes; $i++) {
 $divisor *= ($number >> $i) & 1 ? $primes[$i] : 1;
 }
 $divisors[] = $divisor;
}
echo implode(", ", array_unique($divisors));

This results into the following divisors:

1, 2, 4, 8, 3, 6, 12, 24, 9, 18, 36, 72, 41, 82, 164, 328, 123, 246, 492,
984, 369, 738, 1476, 2952, 53, 106, 212, 424, 159, 318, 636, 1272, 477,
954, 1908, 3816, 2173, 4346, 8692, 17384, 6519, 13038, 26076, 52152, 19557,
39114, 78228, 156456

To find all divisors you need to multiply each prime factor with each other in every possible combination. To do this I calculate the number of possible combinations ($limit). If you now count a number up to this limit the binary representation looks something like this:

7 bit
<----->
0000000 0
0000001 1
0000010 2
0000011 3
0000100 4
0000101 5
0000110 6
0000111 7
0001000 8
0001001 9
...
1111110 126
1111111 127

The current binary representation of $number represents which indexes of $primes are used to calculate the current $divisor. To show this better let's say $number = 5, which is 0000101 in binary. And the calculation for $divisor would be 2 * 1 * 2 * 1 * 1 * 1 * 1 = 4. Only the first and the third bit is set, so only the first and the third element in the array is used for the calculation.

I hope this makes it a little bit clearer.

• user1967034: What can I say, perfection. I'll have a look to see what the first number is with more than 32 prime factorials but otherwise it has answered the question very well. Thank you.
• user1967034: ...actually it must be 2^33 which is 8,589,934,592 which is as high as I need to go, problem solved.