# 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.

-

## migrated from stackoverflow.comJan 27 '12 at 15:45

This question came from our site for professional and enthusiast programmers.

is N ∈ N ? lol. –  L7ColWinters Jan 26 '12 at 17:52
How huge is "a huge value?" –  templatetypedef Jan 26 '12 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 '12 at 18:45
This should be on math.SE, rather than SO - it relates to mathematics, rather than programming. –  Iterator Jan 26 '12 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 '12 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 '12 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 '12 at 6:22
@Kaganar -Thank you for walking me through with this. –  srbh.kmr Jan 27 '12 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 '12 at 11:56
You should not add "two" to primes, but multiply by "two" or add "twice". –  ralu Jan 28 '12 at 6:29

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!*N!. That is q = max v such that N!*N!/p^v is a whole number. Now, once you have these (p,q) tuples, it should be possible to enumerate all the values v = p1^r1 * p1^r1 *...*pk^rk such that 0<=ri<=qi (assume |P|=k). Now, it is possible to search for different (r1,r2,..., rk) such that v <= N!.

The range of each ri can be further reduced. 0 <=r_i<=max_i where max_i = maximum j such that pi^j <= N!.

Different values of v = p1^r1 * p1^r1 *...*pk^rk, provide cases where the resulting division N!*N!/v is a whole number.

-

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 '12 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 '12 at 12:45