Houve muitos desafios relacionados à fatoração prime / prime recentemente, então achei que poderia ser interessante seguir o outro caminho.

Dado:

• um número inteiro positivo ne
• uma lista não vazia de números inteiros positivos f

escrever um programa completo ou uma função para encontrar o menor inteiro ital que i >= ne ié um produto de não-negativos, potências inteiras de elementos f.

Exemplos:

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

  Os primeiros produtos são:

  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
  

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

  Novamente, os primeiros produtos:

  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
  

Casos de teste:

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

Regras

• Você pode assumir que fconterá pelo menos um elemento e que todos os elementos de fserão maiores que 1.
• Opcionalmente, você pode assumir que festá classificado em ordem decrescente / crescente, se desejar (mas especifique).
• Opcionalmente, você pode obter o número de elementos, fse desejar.
• A saída como uma sequência é permitida.
• Isso é código-golfe , então a resposta mais curta em bytes em cada idioma vence!
• As regras de E / S padrão se aplicam e as brechas padrão são proibidas.
• As explicações são incentivadas.

Casca , 8 bytes

ḟṠ€ȯmΠṖṘ

Extremamente lento. Experimente online!

Explicação

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

Wolfram Language (Mathematica) , 68 65 62 61 bytes

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

Experimente online!

Como funciona

Toma entrada como [n,k,f1,f2,f3,...,fk](por exemplo, [11,3,2,3,5]): o primeiro valor é o objetivo n, o segundo é o número de fatores e todos os fatores seguem.

Os outros desafios da teoria dos números recentemente foram dobrados para criar os built-ins (pelo menos, eles usaram FactorInteger), então pensei em experimentar algo que usasse apenas ferramentas básicas. Essa solução basicamente diz que, para escrever ncomo um produto dos fatores, usamos o primeiro fator f1(e recorremos a n/f1, depois multiplicamos por f1) ou não (e recorremos a uma lista mais curta de fatores), e então tomamos o mínimo.

A recursão termina quando o alvo é menor que 1 ou quando o número de fatores é 0, com o qual verificamos #^#2<=1uma vez e depois geramos 1 no primeiro caso e Infinityno último com 1~Max~-Log@#2.

A função fornece vários avisos (mas ainda funciona), a menos que você a execute Quiet, porque eventualmente retorna para casos em #3que não existe, deixando Iftriste o segundo ramo não utilizado .

-3 bytes: usando o número de fatores como entrada.

-3 bytes graças a @ngenisis: using ∞.

-1 byte e sem ∞ambiguidade: a #^#2verificação.

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)

Experimente online!

A função fverifica recursivamente se né um produto da potência dos elementos l, gé apenas um invólucro para controlar a iteração

Python, 55 bytes

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

Experimente online!

Copiava descaradamente o script de rodapé de Rod para teste

Gelatina , 13 bytes

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

Um link diádico com a lista, fà esquerda e o número, nà direita, que gera um número.

Experimente online! Golfily ineficiente - o tempo limite para entradas com maisne / ou mais tempof.

Quão?

Sabemos que os poderes dos fatores individuais (estritamente positivos) nunca precisarão exceder n-1
... então, vamos apenas inspecionar todas as formas possíveis!

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

Retina , 76 bytes

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

Experimente online! O link exclui os casos de teste mais lentos, mas ainda é um pouco lento, portanto, tente não martelar o servidor de @ Dennis.

Pitão - 10 bytes

Fica sem memória muito rapidamente.

f}T*My*QTE

Experimente online aqui .

Resposta razoável para 16 bytes: fsm.A}RQ*Md./PTE

Mathematica, 85 bytes

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

Entrada

[{list f}, n, número de elementos de f]
[{57, 34, 12, 21}, 12532159, 4]

Japonês , 10 bytes

_k e!øV}aU

Teste online!

Não funciona no último caso de teste devido a um limite de iteração criado para impedir que o intérprete funcione para sempre (não ajudou muito aqui, pois congelou o navegador por uma hora ...)

Explicação

_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

Geléia , 9 bytes

xŒPP€ḟḶ}Ṃ

O (2tempo de execução e o uso de memória de ^{n • length (f)} ) fazem desta uma solução teórica.

Experimente online!

Haskell , 46 bytes

Esta é uma porta da excelente resposta Python do KSab . Agradeço a Laikoni por sua ajuda na depuração e golfe desta resposta na sala de chat do PPCG Haskell, Of Monads and Men . Sugestões de golfe são bem-vindas! Experimente online!

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

Mathematica, 73 bytes

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

Essencialmente, um exemplo da resposta de Rod em Python . Define dois operadores binários e . retorna if é um produto de elementos de e de outra forma. dá o menor número inteiro . Se alguém puder descobrir uma maneira de eliminar o teste de divisibilidade, eu poderia economizar 10 bytes usando a codificação ISO 8859-1.±·n±fTruenfFalsen·fi

Explicação

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. *)

R , 52 bytes

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

Experimente online!

Já se passaram três semanas, então pensei em finalmente publicar minha própria solução. Esta é uma abordagem de força bruta.

Existe, no entanto, um builtin:

R , 5 bytes

nextn

Experimente online!

Dos documentos R:

nextnretorna o menor número inteiro, maior ou igual a n, que pode ser obtido como um produto das potências dos valores contidos em factors. nextndestina-se a ser usado para encontrar um comprimento adequado para zerar o argumento de fftpara para que a transformação seja calculada rapidamente. O valor padrão para factorsgarante isso.

Alguns testes revelaram um erro na implementação, no entanto, como mostra o link TIO acima.

nextn(91,c(2,6))deve retornar 96, mas retorna 128. Obviamente, isso só ocorre quando factorsnem todos são relativamente primos um com o outro. De fato, o código C subjacente revela quenextn avidamente tenta dividir cada uma delas factoraté que 1seja alcançado:

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;
}

Isso pode ser resolvido com a entrada em ordem decrescente.

JavaScript (ES6), 53 50 bytes

Guardado 3 bytes graças a @DanielIndie

Recebe entrada na sintaxe de currying (n)(a).

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

Casos de teste

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

Quão?

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