I'm interested in tips for my algorithm that I use to find out the divisors of a very large number, more specifically "n over k" or C(n, k). The number itself can range very high, so it really needs to take time complexity into the 'equation' so to say.
The formula for n over k is n! / (k!(n-k)!) and I understand that I must try to exploit the fact that factorials are kind of 'recursive' somehow - but I havent yet read too much discrete mathematics so the problem is both of a mathematical and a programming nature.
I guess what I'm really looking for are just some tips heading me in the right direction - I'm really stuck.
First you could start with the fact that : C(n,k) = (n/k) C(n-1,k-1).
You can prouve that C(n,k) is divisible by n/gcd(n,k).
If n is prime then n divides C(n,k).
Check Kummer's theorem: if p is a prime number, n a positive number, and k a positive number with 0< k < n then the greatest exponent r for which p^r divides C(n,k) is the number of carries needed in the subtraction n-k in base p.
Let us suppose that n>4 :
if p>n then p cannot divide C(n,k) because in base p, n and k are only one digit wide → no carry in the subtraction
so we have to check for prime divisors in [2;n]. As C(n,k)=C(n,n-k) we can suppose k≤n/2 and n/2≤n-k≤n
for the prime divisors in the range [n/2;n] we have n/2 < p≤n, or equivalently p≤n<2p. We have p≥2 so p≤n < p² which implies that n has exactly 2 digits when written in base p and the first digit has to be 1. As k≤n/2 < p, k can only be one digit wide. Either the subtraction as one carry and one only when n-k< p ⇒ p divides C(n,k); either the subtraction has no carry and p does not divide C(n,k).
The first result is :
every prime number in [n-k;n] is a prime divisor of C(n,k) with exponent 1.
no prime number in [n/2;n-k] is a prime divisor of C(n,k).
in [sqrt(n); n/2] we have 2p≤n< p², n is exactly 2 digits wide in base p, k< n implies k has at most 2 digits. Two cases: only one carry on no carry at all. A carry exists only if the last digit of n is greater than the last digit of p iif n modulo p < k modulo p The second result is :
For every prime number p in [sqrt(n);n/2] p divides C(n;k) with exponent 1 iff n mod p < k mod p p does not divide C(n;k) iff n mod p ≥ k mod p
in the range [2; sqrt(n)] we have to check all the prime numbers. It's only in this range that a prime divisor will have an exponent greater than 1