This is Perl, but the algorithm is straightforward and should be easy to implement in any language:
#!/usr/bin/perl
sub part {
my ($n, $b, $min) = @_;
$min = 0 unless defined $min;
# base case
if ($b == 0) {
if ($n == 0) { return ( [] ) }
else { return () }
}
my @partitions;
for my $first ($min .. $n) {
my @sub_partitions = part($n - $first, $b-1, $first);
for my $sp (@sub_partitions) {
push @partitions, [$first, @$sp];
}
}
return @partitions;
}
The function part
gets two arguments: $n$ is the total number of beans that you want (5 in your example) and $b$ is the number of buckets (3 in your example). It also gets an auxiliary argument, $min$, which is the smallest permissible bucket value. This defaults to 0 if it is not supplied.
The function is recursive, just as you suggested. The base case is no buckets, $b=0$. If there are no beans to put into the buckets ($n=0$ also) then this can be satisfied in exactly one way, by an empty array of buckets []
. Otherwise there is no solution because there are beans left over but no buckets to put them in.
If $b>0$ then the function will accumulate a list of possible partitions of $n$ beans into $b$ buckets in the array @partitions
. It will do this by selecting the number of beans to go into the first bucket ($first$), recursively allocating the remaining beans into $b-1$ buckets, and assembling the two into a complete solution, which it will append to @partitions
. This is just what you suggested in your question.
The number of the beans in the first bucket must be at least $min$, and at most $n$, the total number of beans.
The function then calls itself recursively: there are $n-first$ beans to allocate to $b-1$ buckets, but no bucket can have fewer than $first$ beans. This last bit is the only tricky part: it ensures that the number of beans never decreases from each bucket to the next, and so that each generated partition is unique. (Without this restriction, [1,2,2]
, [2,1,2]
, and [2,2,1]
would be different solutions. With this restriction, only [1,2,2]
is generated.)
The recursive call returns a number of partitions of $n-first$ beans into $b-1$ buckets. $first$ is appended to each of these (that's [$first, @$sp]
, which makes a single array out of $first
and the contents of $sp
) and the resulting partitions of $n$ beans into $b$ buckets are pushed onto @partitions
. When this has been done for each permissible value of $first$, the complete @partitions
list is returned.
To test your example, I did:
for my $p ( part(5, 3) ) {
print "@$p\n";
}
Which printed:
0 0 5
0 1 4
0 2 3
1 1 3
1 2 2
To get the partitions with largest element first, just change [$first, @$sp]
to [@$sp, $first]
.
Some minor optimization are possible. For example, if $n < b\cdot min$ then one can halt the recursion immediately, returning no solutions.
It depends on your choice of polynomial.
You can't extract even factor using Pollard-Rho algorithm because of your choice of $f(x)=x^2+1$. For any integer $x$ then $f(f(x))-f(x)$ is always odd. Indeed, we have $f(f(x))-f(x)=(x^2+1)^2-x^2$ where $x^2+1$ and $x$ have different parity. Say, if you want to take out factor $2$ of $n$, you can choose $f(x)=x^2+2$ (although it's better if you don't use this method but instead removing all factors of $2$ before applying Pollard-Rho).
There are some odd prime factors you cannot find from your choice of polynomial $f(x)=x^2+1$. The algorithm fails to find prime divisor $p$ of $n$ when $p \nmid f(f(x))-f(x)$ for any $x$. In particular, this is equivalent to $p \nmid [(2x-1)^2+3][(2x+1)^2+3]$. According to Law of quadratic reciprocity, all primes $p$ so $p\equiv 5 \pmod{6}$ satisfies this condition. This follows the algorithm fails to factor primes $p \equiv 5 \pmod{6}$ out of $n$.
Best Answer
The basic idea of Strassen's factorization method is that if you have the product $f_i$ of a consecutive set of integers modulo the number to be factored $n$, and that set of integers contains one the factors of $n$, then $\mathrm{gcd}(f_i, n)$ will be greater than unity. The trick then is to compute $f_i$ for non-overlapping sets of possible factors quickly.
Here is a brute-force example that shows how the 9th block of numbers reveals 293 as a factor of 1000009:
The second for-loop takes $O(n^{1/4}\log n)$, and so the hard work of the algorithm is to compute $f_i$ in faster than the $O(n^{1/2})$ demonstrated in the first for-loop above. How this is done is by using subproduct trees and multipoint evaluation. Here is a slide presentation that describes the details pretty well. Also this paper (search for "Main algorithmic ideas") has a good high level overview of the algorithm. Finally, subproduct trees are given a good treatment in this presentation, Asymptotically fast algorithms for modern computer algebra.