与えられた因子の積としての最小整数

最近の素因数分解や素因数分解関連の問題はたくさんありましたので、別の方法をとってみると面白いかもしれないと思いました。

与えられた:

  • 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.

例:

  • 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
    

テストケース:

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

ルール

  • 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 ルール apply, and standard loopholes are
    forbidden.
  • Explanations are encouraged.
ベストアンサー

Husk, 8 bytes

ḟṠ€ȯmΠṖṘ

Extremely slow. Try it
online!

説明

ḟṠ€ȯ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.

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です