Least integer as a product of given factors

Question

There have been a lot of prime-/prime factorization-related challenges recently, so I thought it might be interesting to go the other way.

Given:

• a positive integer n, and
• a non-empty list of positive integers f

write a full program or a function to find the smallest integer i such that i >= n and i is a product of nonnegative, integer powers of elements in f.

Examples:

• Suppose n = 11, f = [2, 3, 5].

  The first few products are:

  1   = 2^0 * 3^0 * 5^0
  2   = 2^1 * 3^0 * 5^0
  3   = 2^0 * 3^1 * 5^0
  5   = 2^0 * 3^0 * 5^1
  4   = 2^2 * 3^0 * 5^0
  6   = 2^1 * 3^1 * 5^0
  10  = 2^1 * 3^0 * 5^1
  9   = 2^0 * 3^2 * 5^0
  15  = 2^0 * 3^1 * 5^1
  25  = 2^0 * 3^0 * 5^2
  8   = 2^3 * 3^0 * 5^0
  12  = 2^2 * 3^1 * 5^0 => smallest greater than (or equal to) 11, so we output it.
  20  = 2^2 * 3^0 * 5^1
  18  = 2^1 * 3^2 * 5^0
  30  = 2^1 * 3^1 * 5^1
  50  = 2^1 * 3^0 * 5^2
  27  = 2^0 * 3^3 * 5^0
  45  = 2^0 * 3^2 * 5^1
  75  = 2^0 * 3^1 * 5^2
  125 = 2^0 * 3^0 * 5^3
  

• Suppose n=14, f=[9, 10, 7].

  Again, the first few products:

  1 = 7^0 * 9^0 * 10^0
  7 = 7^1 * 9^0 * 10^0
  9 = 7^0 * 9^1 * 10^0
  10 = 7^0 * 9^0 * 10^1
  49 = 7^2 * 9^0 * 10^0  => smallest greater than (or equal to) 14, so we output it.
  63 = 7^1 * 9^1 * 10^0
  70 = 7^1 * 9^0 * 10^1
  81 = 7^0 * 9^2 * 10^0
  90 = 7^0 * 9^1 * 10^1
  100 = 7^0 * 9^0 * 10^2
  

Test cases:

n, f -> output
10, [2, 3, 5]              -> 10
17, [3, 7]                 -> 21
61, [3,5,2,7]              -> 63
23, [2]                    -> 32
23, [3]                    -> 27
23, [2, 3]                 -> 24
31, [3]                    -> 81
93, [2,2,3]                -> 96
91, [2,4,6]                -> 96
1,  [2,3,5,7,11,13,17,19]  -> 1
151, [20,9,11]             -> 180
11616, [23,32]             -> 12167
11616, [23,32,2,3]         -> 11664 = 2^4 * 3^6
5050, [3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210] -> 5103 = 3^6 * 7
12532159, [57, 34, 12, 21] -> 14183424 = 12^5 * 57

Rules

• You may assume that f will contain at least one element, and that all elements of f will be greater than 1.
• You may optionally assume that f is sorted in decreasing/increasing order if you would like (but please specify).
• You may optionally take the number of elements of f if you would like.
• Output as a string is allowed.
• This is code-golf, so shortest answer in bytes in each language wins!
• Default I/O rules apply, and standard loopholes are forbidden.
• Explanations are encouraged.

Answer 1

Husk, 8 bytes

ḟṠ€ȯmΠṖṘ

Extremely slow. Try it online!

Explanation

ḟṠ€ȯmΠṖṘ  Implicit inputs, say L=[3,4] and n=5.
ḟ         Find the lowest integer k≥n that satisfies:
       Ṙ   Replicate L by k: [3,3,3,3,3,4,4,4,4,4]
      Ṗ    Powerset: [[],[3],[4],..,[3,3,3,3,3,4,4,4,4,4]]
    mΠ     Product of each: [1,3,4,..,248832]
 Ṡ€ȯ       k is in this list.

Answer 2

Wolfram Language (Mathematica), 68 65 62 61 bytes

If[#^#2<=1,1~Max~-Log@#2,Min[#0[#,#2-1,##4],#0[#/#3,##2]#3]]&

Try it online!

How it works

Takes input as [n,k,f1,f2,f3,...,fk] (e.g., [11,3,2,3,5]): the first value is the target n, the second is the number of factors, and all the frctors follow.

The other number-theory challenges recently all folded to fancy built-ins (at the very least, they used FactorInteger) so I thought I'd try something that used only basic tools. This solution basically says that to write n as a product of the factors, we either use the first factor f1 (and recurse on n/f1, then multiply by f1) or don't (and recurse on a shorter list of factors), then take the min.

The recursion bottoms out when the target is less than 1 or when the number of factors is 0, which we check for with #^#2<=1 at once, and then generate 1 in the first case and Infinity in the latter with 1~Max~-Log@#2.

The function gives a whole bunch of warnings (but still works) unless you run it with Quiet, because it eventually recurses to cases where #3 doesn't exist, making the unused second branch of If sad.

---

-3 bytes: taking the number of factors as input.

-3 bytes thanks to @ngenisis: using ∞.

-1 byte, and no ∞ ambiguity: the #^#2 check.

Answer 3

Python 2, 91 88 84 bytes

f=lambda n,l:n<2or any(n%x<1and f(n/x,l)for x in l)
g=lambda n,l:n*f(n,l)or g(n+1,l)

Try it online!

The function f checks recursively if n is a product of powers of elements in l, g is just a wrapper to control the iteration

Answer 4

Python, 55 bytes

f=lambda n,l,x=1:min(f(n,l,x*e)for e in l)if x<n else x

Try it online!

Shamelessly copied Rod's footer script for testing

Answer 5

Jelly, 13 bytes

L⁹ṗ’⁸*P€ḟ⁹Ḷ¤Ṃ

A dyadic link taking the list, f, on the left and the number, n, on the right which yields a number.

Try it online! Golfily inefficient - will time out for inputs with higher n and/or longer f.

How?

We know that the powers of the individual (strictly positive) factors will never need to exceed n-1
...so let's just inspect all the possible ways!

L⁹ṗ’⁸*P€ḟ⁹Ḷ¤Ṃ - Link: list, f; number, n
 ⁹            - chain's right argument, n
L             - length of f
  ṗ           - Cartesian power  ...e.g.: len(f)=2; n=3 -> [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
   ’          - decrement (vectorises)
    ⁸         - chain's left argument, f
     *        - exponentiate (vectorises) - that is [f1^a, f2^b, ...] for each [a, b, ...] in the list formed from the Cartesian power
      P€      - product for €ach - that is f1^a * f2^b * ... for each [a, b, ...] in the list formed from the Cartesian power
           ¤  - nilad followed by link(s) as a nilad:
         ⁹    -   chain's right argument, n
          Ḷ   -   lowered range -> [0,1,2,3,...,n-1]
        ḟ     - filter discard - that is remove values less than n
            Ṃ - minimum

Answer 6

Mathematica, 85 bytes

Min@Select[Flatten[1##&@@(s^#)&/@Tuples[0~Range~⌈Log[Min[s=#],d=#2]⌉,#3]],#>=d&]&

Input

[{list f},n,number of elements of f]
[{57, 34, 12, 21}, 12532159, 4]

Answer 7

Retina, 76 bytes

\d+
$*
1+;
$&$&
{+`;(1+)(\1)*(?=;.*\b\1\b)
;1$#2$*1
}`(1+);11+;
1$1;1$1;
\G1

Try it online! Link excludes the slowest test cases, but it's still a little slow, so try not to hammer @Dennis's server.

Answer 8

Pyth - 10 bytes

Runs out of memory very quickly.

f}T*My*QTE

Try it online here.

Reasonable answer for 16 bytes: fsm.A}RQ*Md./PTE

Answer 9

Japt, 10 bytes

_k e!øV}aU

Test it online!

Doesn't work on the last test case due to an iteration limit designed to keep the interpreter from running forever (didn't help much here though, as it froze my browser for an hour...)

Explanation

_k e!øV}aU    Implicit: U = input integer, V = array of factors
_      }aU    Starting at U, find the next integer Z where
 k              the factors of Z
   e            are such that every factor
    !øV         is contained in V (e!øV -> eX{VøX}, where VøX means "V contains X").
              Implicit: output result of last expression

Answer 10

Jelly, 9 bytes

xŒPP€ḟḶ}Ṃ

O(2^{n•length(f)}) runtime and memory usage make this a theoretical solution.

Try it online!

Answer 11

Haskell, 46 bytes

This is a port of KSab's excellent Python answer. Thanks to Laikoni for their help in debugging and golfing this answer in the PPCG Haskell chatroom, Of Monads and Men. Golfing suggestions welcome! Try it online!

(#1)
(l#x)n|x<n=minimum[(l#(x*e))n|e<-l]|1>0=x

Answer 12

Mathematica, 73 bytes

1±_=1>0;n_±f_:=Or@@(#∣n&&n/#±f&/@f);n_·f_:=NestWhile[#+1&,n,!#±f&]

Essentially a port of Rod's Python answer. Defines two binary operators ± and ·. n±f returns True if n is a product of elements of f and False otherwise. n·f gives the smallest integer i. If someone can figure out a way to eliminate the divisibility test, I could save 10 bytes by using the ISO 8859-1 encoding.

Explanation

1±_=1>0;                         (* If the first argument is 1, ± gives True. *)
n_±f_:=Or@@(#∣n&&n/#±f&/@f);     (* Recursively defines ±. *)
                                 (* For each element of f, check to see if it divides n. *)
                                 (* For each element # that does, check if n/# is a product of elements of f. *)
n_·f_:=NestWhile[#+1&,n,!#±f&]   (* Starting with n, keep incrementing until we find an i that satisfies i±f. *)

Answer 13

JavaScript (ES6), 53 50 bytes

Saved 3 bytes thanks to @DanielIndie

Takes input in currying syntax (n)(a).

n=>m=a=>(g=k=>k<n?a.map(x=>g(k*x)):k>m?0:m=k)(1)|m

Test cases

let f =

n=>m=a=>(g=k=>k<n?a.map(x=>g(k*x)):k>m?0:m=k)(1)|m

console.log(f(10)([2,3,5]))                // -> 10
console.log(f(17)([3,7]))                  // -> 21
console.log(f(61)([3,5,2,7]))              // -> 63
console.log(f(23)([2]))                    // -> 32
console.log(f(23)([3]))                    // -> 27
console.log(f(23)([2, 3]))                 // -> 24
console.log(f(31)([3]))                    // -> 81
console.log(f(93)([2,2,3]))                // -> 96
console.log(f(91)([2,4,6]))                // -> 96
console.log(f(1,)([2,3,5,7,11,13,17,19]))  // -> 1
console.log(f(151)([20,9,11]))             // -> 180
console.log(f(11616)([23,32]))             // -> 12167
console.log(f(11616)([23,32,2,3]))         // -> 11664 = 2^4 * 3^6
console.log(f(5050)([3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210])) // -> 5103 = 3^6 * 7
console.log(f(12532159)([57,34,12,21]))    // -> 14183424 = 12^5 * 57

How?

n => a => (                 // given n and a
  g = k =>                  // g = recursive function taking k
    k < n ?                 // if k is less than n:
      a.map(x => g(k * x))  //   recursive calls to g with x * k for each x in a
    :                       // else:
      k > m ?               //   if k is greater than m and m is not set to NaN:
        0                   //     ignore this result
      :                     //   else:
        m = k               //     update m to k
  )(                        // initial call to g with:
    1,                      //   k = 1
    m = +a                  //   m = either NaN or the single integer contained in a
  ) | m                     // return m

Answer 14

R, 52 bytes

function(n,f)min((y=(x=outer(f,0:n,"^"))%o%x)[y>=n])

Try it online!

It's been 3 weeks, so I thought I'd finally post my own solution. This is a brute force approach.

There is, however, a builtin:

R, 5 bytes

nextn

Try it online!

From the R docs:

nextn returns the smallest integer, greater than or equal to n, which can be obtained as a product of powers of the values contained in factors. nextn is intended to be used to find a suitable length to zero-pad the argument of fft to so that the transform is computed quickly. The default value for factors ensures this.

Some testing revealed a bug in the implementation, however, as the TIO link above shows.

nextn(91,c(2,6)) should return 96, but returns 128 instead. This obviously only occurs when factors are not all relatively prime with one another. Indeed, the C code underlying it reveals that nextn greedily tries to divide each factor in turn until 1 is reached:

static Rboolean ok_n(int n, int *f, int nf)
{
    int i;
    for (i = 0; i < nf; i++) {
    while(n % f[i] == 0) {
        if ((n = n / f[i]) == 1)
        return TRUE;
    }
    }
    return n == 1;
}

static int nextn0(int n, int *f, int nf)
{
    while(!ok_n(n, f, nf))
    n++;
    return n;
}

This can be solved by taking input in decreasing order.