11
\$\begingroup\$

Inspired by this question over on Math.

Let the prime factorization of a number, n, be represented as P(n) = 2a x 3b x 5c x ....
(Using x as the multiplication symbol.)
Then the number of divisors of n can be represented as D(n) = (a+1) x (b+1) x (c+1) ....
Thus, we can easily say that the number of divisors of 2n is D(2n) = (a+2) x (b+1) x (c+1) ...,
the number of divisors of 3n is D(3n) = (a+1) x (b+2) x (c+1) ...,
and so on.

Challenge:

Write a program or function that uses these properties to calculate n, given certain divisor inputs.

Input:

A set of integers, let's call them w, x, y, z, with all of the following definitions:

  • all inputs are greater than 1 -- w, x, y, z > 1
  • x and z are distinct -- x<>z
  • x and z are prime -- P(x)=x, D(x)=2 and P(z)=z, D(z)=2
  • w is the number of divisors of xn -- D(xn)=w
  • y is the number of divisors of zn -- D(zn)=y

For the problem given in the linked question, an input example could be (28, 2, 30, 3). This translates to D(2n)=28 and D(3n)=30, with n=864.

Output:

A single integer, n, that satisfies the above definitions and input restrictions. If multiple numbers fit the definitions, output the smallest. If no such integer is possible, output a falsey value.

Examples:

(w, x, y, z) => output

(28, 2, 30, 3) => 864
(4, 2, 4, 5) => 3
(12, 5, 12, 23) => 12
(14, 3, 20, 7) => 0 (or some other falsey value)
(45, 13, 60, 11) => 1872
(45, 29, 60, 53) => 4176

Rules:

  • Standard code-golf rules and loophole restrictions apply.
  • Standard input/output rules apply.
  • Input numbers can be in any order - please specify in your answer which order you're using.
  • Input numbers can be in any suitable format: space-separated, an array, separate function or command-line arguments, etc. - your choice.
  • Similarly, if output to STDOUT, surrounding whitespace, trailing newline, etc. are all optional.
  • Input parsing and output formatting are not the interesting features of this challenge.
  • In the interests of sane complexity and integer overflows, the challenge number n will have restrictions such that 1 < n < 100000 -- i.e., you don't need to worry about possible answers outside this range.

Related

\$\endgroup\$
  • \$\begingroup\$ So, if the smallest solution is larger than 100,000, I can choose to return either a solution or zero? \$\endgroup\$ – Dennis Jan 15 '16 at 18:56
  • \$\begingroup\$ @Dennis If it makes your code shorter, sure. Either would be acceptable. \$\endgroup\$ – AdmBorkBork Jan 15 '16 at 19:22
3
\$\begingroup\$

Jelly, 17 16 bytes

×€ȷ5R¤ÆDL€€Z=Ḅi3

This is a brute force solution that tries all possible values up to 100,000. Try it online!

Non-competing version

The latest version of Jelly has a bug fix that allows to golf down the above code to 15 bytes.

ȷ5R×€³ÆDL€€=Ḅi3

Try it online!

How it works

×€ȷ5R¤ÆDL€€Z=Ḅi3  Main link. Left input: x,z. Right input: w,y

     ¤            Combine the two atoms to the left into a niladic chain.
  ȷ5              Yield 100,000 (1e5).
    R             Apply range. Yields [1, ..., 100,000].
x€                Multiply each r in the range by x and z.
                  This yields [[x, ..., 100,000x], [z, ..., 100,000z]].
      ÆD          Compute the divisors of each resulting integer.
        L€€       Apply length to each list of divisors.
                  This counts the divisors of each integer in the 2D array.
           Z      Zip; group the divisors of kx and kz in pairs.
            =     Compare each [divisors(kx), divisors(kz)] with [w, y].
                  This yields a pair of Booleans.
             Ḅ    Convert each Boolean pair from binary to integer.
              i3  Find the first index of 3. Yields 0 for not found.
\$\endgroup\$
  • \$\begingroup\$ Congrats, you win by default! :D \$\endgroup\$ – AdmBorkBork Jan 22 '16 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.