# In Dementia2014/Mulfact how does one arrive at conclusion that that superfactorial(n)%329885391853=0 for all n>=999983

I got the concept(after the event ) but what I couldn’t understand was as to how coders get to conclusion that after n=999983 all numbers will have their superfactorial == 0(mod 329885391853)

A number N will be 0 (modulo M) only if N = k * M where k is some integer constant.There are 2 possibilities in this question :

1. M is a prime > all N : In this case there is no option but to calculate the answer by brute force. Pre-computation is also not feasible as n can be upto 10^9.Hence we look at the next possibbilty.

2. M is not a prime. In this case M = p * q. If you are write a simple brute force script like :

for i in range(3,1000000,2):
if(329885391853 % i == 0):
print 329885391853/i, i
break
This gives result as 999983 329891. Now for any number N greater than or equal to 999983, N! will have both 329891 and 999983 as factors i.e M will be a divisor of N! for all N>=999983. Hence the conclusion.

2 Likes

I realized it today when I saw that crazy looking MOD instead of 10^9 + 7

1 Like