ну да, это приближение при малых k: k^k<N. я имел в виду, что большая таблица получается. рассуждал я так : посмотрим, с какой вероятностью подойдет модуль l. если N велико(или кратно l), то это вероятность того, что k шаров, разложенных по l ячейкам, не попадут вдвоем в одну ячейку. это (l!/(k!*(l-k)!))/l^k. если l = Ak, где A-это некоторая константа, то, применяя формулу Стирлинга(забивая на корень из 2*pi*n и прочую мелочь), получаем (Ak)^(Ak)/(k^k*((A-1)k)^((A-1)k)*(Ak)^k)=(A/(A-1))^((A-1)k)*1/k^k,
что примерно равно 1/(k/e)^k. соответственно, если считать разные модули независимыми (что неверно, но не думаю, что это очень сильно влияет), вопрос встает так : сколько раз нужно умножить (1-1/(k/e)^k) на себя, чтобы получить маленькое число - вероятность, что все эти модули плохими не окажутся. это примерно (k/e)^k.
впрочем, есть натяжки(с независимостью модулей), я, пожалуй, проведу компьютерный эксперимент.