# Counting (Number theory / Factors)

I'm stuck with this counting problem: I have an expression: $T = (N!) \times (N!) / D$ where, $D \in [1 - N!]$, i.e. $D$ takes all values from $1$ to $N!$ and I'm to count the number of points where $T$ comes out to be a whole number (a positive integer).

For example, for $N=3$: $$D \in \{1, 2, 3, 4, 5, 6\}$$ and $T$ comes out to be a whole number for $D \in \{1, 2, 3, 4, 6\}$, i.e. for 5 values.

I'd like to develop an efficient algorithm to count, since $N$ can be a large number.

I believe in the numerator we have the possible factors broken up as $N!$ 's and we have to start making products up till $N!$ from them and count all the distinct ones. That seems about one way to do it. Please help me unwrap it or provide any hints/pointers in the right directions to do it as efficiently as possible as $N$ here happens to be a huge value.

• is N ∈ N ? lol.
– L7ColWinters
Jan 26, 2012 at 17:52
• How huge is "a huge value?" Jan 26, 2012 at 18:32
• 1 <= N <= 10^6 (1 million) and I'm interested in count%10^6 i.e. count in the multiples of 1 million.
– srbh.kmr
Jan 26, 2012 at 18:45
• This should be on math.SE, rather than SO - it relates to mathematics, rather than programming. Jan 26, 2012 at 22:10
• Sorry I'm new to SO so excuse me for posting it in some wrong section. I'll keep that in mind the next time.
– srbh.kmr
Jan 27, 2012 at 11:45

This is quite approachable with the technique you suggest and the size of N suggested.

Let us note that this problem is virtually the same as counting all positive numbers which divide N!N! -- just add one and divide the answer by two. (The square root of N!N! is N!. For each number p less than the square root of N!N! that divide N!N! there is precisely one number q above the square root of N!N! that divides N!N!. This should be clear because pq=N!N!. The only divisor without a different match is N! itself, so we need to count it twice before dividing by two -- hence the plus one).

As for generating the number of prime factors in N!, that's also relatively easy with computers for numbers up to a million. Blitz through the numbers one through a million. For each number, do trial division (dividing that number whenever you can) until you've reached 1. Add 'two' to the count for the primes (and they will be primes) you find -- you're adding two because you've got N! twice (N!N!).

The result of this is a prime factorization of N!N!. Note that this wasn't so bad because you only had to do at most 1000 trial divisions per number (actually far less), and a thousand trial divisions for a million numbers is a billion trials. That's not fast, but it's not too slow for modern processors. (If you're writing this in C/C++/C# it'll be fast enough.)

Now to compute the count of numbers that divide N!N!... To do so, note that you can pick up to the number of two's that the prime factorization of N!N! to be factors of a divisor. Or three's. Or four's. And you can multiply them together. You can skip some prime factors, and you can choose some or all of the others.

The fundamental theorem of counting applies: we can pick the number of two's in X many ways (no twos, 1 two, 2 twos, ..., X - 1 twos), the number of three's in Y many ways, ... So the number of ways we could pick is X * Y * ...

So, your answer is ((X * Y * ...) + 1)/2

• This can, of course, be optimized with a better way of counting primes in the first million numbers, but honestly for a number that small (1 million) killing it with iron is fast, cheap, and effective.
– Kaganar
Jan 26, 2012 at 22:31
• Could you explain how ((X * Y * ...) + 1)/2 finds total no of positive ints within N! that divides N!*N!
– Rajendran T
Jan 27, 2012 at 6:22
• @Kaganar -Thank you for walking me through with this.
– srbh.kmr
Jan 27, 2012 at 11:49
• @RajendranT - Think of it as finding the divisors of a number (say) A which is a perfect square of B. You find the no. of divisors of A, half of them would lie below B..
– srbh.kmr
Jan 27, 2012 at 11:56
• You should not add "two" to primes, but multiply by "two" or add "twice".
– ralu
Jan 28, 2012 at 6:29

This is related to the divisor function. Let d(n) be the number of (positive) divisors of the integer n. For example,

  n  = 1 2 3 4 5 6 7 8 9
d(n) = 1 2 2 3 2 4 2 4 3


Your question almost equivalent to determining d(N!*N!), with the caveat that you consider only divisors up to N!.

Because you are considering only special values of n for input, specifically factorials squared, that the answer may simplify. For example, if you considered as input only factorials, then the answer is

  N   =  1  2  3  4  5  6  7  8  9
d(N!) =  1  2  4  8 16 30 60 96 160


Assuming you can (efficiently) compute prime numbers less than N, then you can calculate d(N!) as follows. Let p1,p2,...,pm be the primes less than N. Then define Qk by

Qk = sum{i >= 1} floor(N/pk^i)


Then we have

d(N!) = Q1 * Q2 * ... * Qm


Some asymptotics are known, the simplest of which is d(N!) <= 2^N. Erdos, Graham, Ivic, and Pomerance have a paper on this entitled On the number of divisors of n!.

Letting T(N) be the number of integers between 1 and N! that divide N! * N!, the first few terms of this series are

  N  =  1  2  3  4  5  6  7
T(N) =  1  2  5 11 32 88 203


Clearly T(N) >= d(N!), so the analysis above gives a lower bound. I don't see how to extend the results of N! to this case explicitly, but if I think of anything useful, I'll update this answer. In the mean time, this may give you other ideas for how to approach this problem.

1 count number of times each prime divide N!²
2 now you have factorization of N!², count out combinations that represents number of solutions for D in interval [1,(N!)²]
3 Divide this result by 2 and add 1 to get final solution (thanx Kaganar).

r=1
for i in primes_less_than(N):
r=r*(1+numberofdivisorsinfaculty(N,i)*2)
#r at this point is numer of solutions fro D element [1-N!*N!]
print(r/2+1) # Kangar explaind this extra trick


where

numberofdivisorsinfaculty(N,i):
# this func returns highest power r
# as i^r that is divisible by N!
# complexity is log(N)/log(i)
r=0
while(N>0):
r+=N/i
N=N/i
return r


All you need to add is prime number generator.

EDIT:
It took 0.35s in python for N = 10^6 and solution modulo 10^8 (i have checked function whith naive searching for N from 3-12 and seems ok)
So here is full source
http://ideone.com/7v0RV

• Initially I was under the impression that I'd have to go for primes upto N! which scared me. Thanks for summing it up nicely and your python code is qquick and precise, although I'd be using C++.
– srbh.kmr
Jan 27, 2012 at 12:01
• Yes N! is not divisible by primes greater than N and factorising N! is approx in same complexity than finding primes less than N.
– ralu
Jan 27, 2012 at 12:45

This is a tough problem! If it is possible to enumerate all the prime numbers between $1$ and $N$ :

Let $P$ be the list of all primes between $1$ and $N$. For every $p$ in $P$ you can maintain a tuple $(p,q)$ where $q$ is the total power of $p$ in $(N!)^2$. That is $q = \max v$ such that $(N!)^2/p^v$ is a whole number. Now, once you have these $(p,q)$ tuples, it should be possible to enumerate all the values $v = p_1^{r_1} p_2^{r_2}\dots p_k^{r_k}$ such that $0\leq r_i\leq q_i$ (assume $|P|=k$). Now, it is possible to search for different $(r_1,r_2,...,r_k)$ such that $v\leq N!$.

The range of each $r_i$ can be further reduced.

$0 \leq r_i \leq \max i$ where $\max i= \max j$ such that $p_i^q \leq N!$.

Different values of $v = p_1^{r_1}p_2^{r_2}\dots p_k^{r_k}$, provide cases where the resulting division $(N!)^2/v$ is a whole number.