17
\$\begingroup\$

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 , so shortest answer in bytes in each language wins!
  • Default I/O rules apply, and standard loopholes are forbidden.
  • Explanations are encouraged.
\$\endgroup\$

14 Answers 14

10
\$\begingroup\$

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.
\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Very nice! saves 3 bytes over -Log@0 (doesn't work on TIO, but works fine on desktop Mathematica). Also, Tr[1^{##}]` is a byte shorter than Length@{##}. \$\endgroup\$ – ngenisis Oct 9 '17 at 20:52
  • \$\begingroup\$ I'm not entirely sure how I feel about using optimizations TIO doesn't like, but sure, I'll add that. And #2 is even shorter than Tr[1^{##}]. :) \$\endgroup\$ – Misha Lavrov Oct 9 '17 at 20:54
  • 1
    \$\begingroup\$ I think you should incude Quiet in your main code.This answer outputs too many wrong messages. At least ask OP if he is ok with it \$\endgroup\$ – J42161217 Oct 9 '17 at 22:06
  • 2
    \$\begingroup\$ It seems much the same as ignoring STDERR would be in another language, which is accepted practice. \$\endgroup\$ – Misha Lavrov Oct 9 '17 at 22:16
  • 2
    \$\begingroup\$ The problem appears to be a bug. I'll try to fix that. \$\endgroup\$ – Dennis Oct 10 '17 at 23:11
6
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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]

\$\endgroup\$
  • \$\begingroup\$ {d,s}Min@Select[Flatten[1##&@@(s^#)&/@0~Range~9~Tuples~Tr[1^s]],#>=d&] \$\endgroup\$ – ngenisis Oct 9 '17 at 20:05
  • \$\begingroup\$ @ngenisis what is the symbol that is not displayed? Can you make a TIO link instead? \$\endgroup\$ – J42161217 Oct 9 '17 at 20:20
  • \$\begingroup\$ Never thought I'd see the day where "Mathematica" and "TIO" were used in the same post :P \$\endgroup\$ – caird coinheringaahing Oct 9 '17 at 20:43
  • \$\begingroup\$ @Jenny_mathy It's U+F4A1, long name \[Function]. \$\endgroup\$ – ngenisis Oct 9 '17 at 20:46
  • \$\begingroup\$ Using 0~Range~9 seems very conservative. Should g[{2,3,5},1001] really skip over 1024 and return 1080? This isn't a particularly large input. \$\endgroup\$ – Misha Lavrov Oct 9 '17 at 21:17
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Jelly, 9 bytes

xŒPP€ḟḶ}Ṃ

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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. *)
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ n=>m=a=>(g=k=>k<n?a.map(x=>g(k*x)):k>m?0:m=k)(1)|m m= function always produces false on the first run, so it basically the same as putting +a , this is 51 bytes now \$\endgroup\$ – DanielIndie Oct 31 '17 at 4:58
  • \$\begingroup\$ @DanielIndie That's actually 50 bytes. Thanks a lot! \$\endgroup\$ – Arnauld Oct 31 '17 at 17:46

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.