smallest K such that number of arrangements of prime factors of K equals N?

Revision en6, by pabloskimg, 2018-10-29 20:56:46

Basically the title. The problem statement can be found here. No idea how to solve it efficiently.

UPDATE 1: why the downvotes?

UPDATE 2: based on the answers so far, the solution would be to exhaustively explore all combinations of exponents k1, k2, ..., kr (ki ≥ kj for all i < j) such that and k = 2k1 * 3k2 * 5k3 * 7k4 * 11k5 * ... < 263. During the exhaustive search one can map each n to its minimum k found (for instance, using an unordered_map) and then the queries can be answered in O(1). The problem is: how can you estimate the complexity of the exhaustive search? Any easy way to estimate an upperbound for it?

UPDATE 3: pshishod2645 says there are around 2 * 106 valid combinations of exponents, where did he get that number from?

Tags #math, #combinatorics, #primes

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English pabloskimg 2018-10-29 20:56:46 125
en5 English pabloskimg 2018-10-29 20:46:41 4 Tiny change: 'r)!}{k_1! + ... + k_r!} < 2' -> 'r)!}{k_1! * ... * k_r!} < 2'
en4 English pabloskimg 2018-10-29 20:45:40 605 Tiny change: '_r$ ($k_i >= k_j$ for ' -> '_r$ ($k_i \geq k_j$ for '
en3 English pabloskimg 2018-10-28 19:15:30 30 Tiny change: 'ficiently.' -> 'ficiently.\n\nUPDATE: why the downvotes?'
en2 English pabloskimg 2018-10-27 17:43:02 1
en1 English pabloskimg 2018-10-27 17:41:36 227 Initial revision (published)