CODEWITHSUNDEEP
algorithmmathfactorial
hasan
hasan

Reputation: 24185

Find n, where its factorial is a product of factorials

Stackoverflow promoted this mathematics question at the right pane from stackexchange mathematics site.

I got curious to see the answers. Turned out that the question was about a specfic case (3!⋅5!⋅7!=n!) and the answers were for this specfic case too.

From a programmer/programming point of view I wonder what would be the most suffecient algorithm to solve the problem.

We have two situation though. One that the problem always have an answer and the other doesn't.

Input is 3, 5, 7 and output is 10 as in the linked question.

Upvotes: 1

Views: 419

Answers (2)

IVlad
IVlad

Reputation: 43477

Factor a!, b!, c!, .... For a given prime p of a, it appears in a! this many times:

floor(a / p) + floor(a / p^2) + ...

For example, 5 appears in 26!:

26 / 5 + 26 / 25 = 5 + 1 = 6 times

Now you can binary search your n and check if each of the prime factors in a!*b!*c!*... occurs exactly as many times in m!, where m is the middle point of one of your binary search iterations.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726809

The algorithm would be reasonably straightforward:

  • Order inputs a, b, and c so that a <= b <= c
  • c! can be divided out from n!
  • This makes a! * b! equal to the product of numbers between c+1 and n, inclusive
  • Find the next prime p > c. This number cannot be produced by multiplying a! * b!, because both a and b are strictly less than p, hence they do not contain p among their factors
  • Try all candidate n between c+1 and p-1, inclusive
  • If you do not find an answer, there is no solution

In case of a=3, b=5, and c=7 you find the next prime above 7, which is 11, and try all numbers between 7+1 and 11-1, inclusive (i.e. 8, 9, and 10) as candidates for n.

Upvotes: 2

Related Questions