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.

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

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.

Counting (Number theory / Factors)

Related

Recent Posts