13
$\begingroup$

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.

  • 0
    is N ∈ N ? lol.2012-01-26
  • 0
    How huge is "a huge value?"2012-01-26
  • 0
    1 <= N <= 10^6 (1 million) and I'm interested in count%10^6 i.e. count in the multiples of 1 million.2012-01-26
  • 1
    This should be on math.SE, rather than SO - it relates to mathematics, rather than programming.2012-01-26
  • 0
    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.2012-01-27
  • 0
    Thank you guys for all the insight and solutions. yes, neatly put, I'm looking for d(N!*N!) in teh range upto N! which seems to be quite achievable by counting the number of divisors of N! first, and "scaling" the count for other half of (N!*N!) and then due to symmetry bringing the count to half for the range N!. more details with Kaganar and @ralu2012-01-27

4 Answers 4