Recientemente ha habido muchos desafíos relacionados con la factorización prima / prima, por lo que pensé que podría ser interesante ir para otro lado.

Dado:

• un entero positivo n, y
• una lista no vacía de enteros positivos f

escribir un programa completo o una función para encontrar el menor entero ital que i >= ny ies un producto de no negativos, potencias enteras de elementos f.

Ejemplos:

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

  Los primeros productos son:

  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
  

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

  De nuevo, los primeros productos:

  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 prueba:

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

Reglas

• Puede suponer que fcontendrá al menos un elemento, y que todos los elementos fserán mayores que 1.
• Si lo desea, puede suponer que festá ordenado en orden decreciente / creciente (pero especifique).
• Opcionalmente, puede tomar el número de elementos de fsi lo desea.
• Se permite la salida como una cadena.
• Este es el código de golf , por lo que gana la respuesta más corta en bytes en cada idioma.
• Se aplican las reglas de E / S predeterminadas y las lagunas estándar están prohibidas.
• Se alientan las explicaciones.

Casco , 8 bytes

ḟṠ€ȯmΠṖṘ

Extremadamente lento Pruébalo en línea!

Explicación

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

Pruébalo en línea!

Cómo funciona

Toma la entrada como [n,k,f1,f2,f3,...,fk](p. Ej. [11,3,2,3,5]): El primer valor es el objetivo n, el segundo es el número de factores y todos los factores siguen.

Los otros desafíos de la teoría de números recientemente se incorporaron a complementos sofisticados (como mínimo, que usaban FactorInteger), así que pensé en probar algo que usaba solo herramientas básicas. Esta solución básicamente dice que para escribir ncomo producto de los factores, usamos el primer factor f1(y recurrimos n/f1, luego lo multiplicamos por f1) o no (y recurrimos en una lista más corta de factores), luego tomamos el mínimo.

La recursión toca fondo cuando el objetivo es menor que 1 o cuando el número de factores es 0, lo cual verificamos con #^#2<=1una vez, y luego generamos 1 en el primer caso y Infinityen el último con 1~Max~-Log@#2.

La función ofrece una gran cantidad de advertencias (pero aún funciona) a menos que la ejecute Quiet, porque eventualmente se repite en casos donde #3no existe, lo que hace que la segunda rama no utilizada sea Iftriste.

-3 bytes: toma el número de factores como entrada.

-3 bytes gracias a @ngenisis: utilizando ∞ .

-1 byte, y sin ∞ambigüedad: el #^#2cheque.

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)

Pruébalo en línea!

La función fverifica recursivamente si nes un producto de potencias de elementos l, ges solo un contenedor para controlar la iteración

Python, 55 bytes

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

Pruébalo en línea!

Copió descaradamente el guión de pie de página de Rod para probar

Jalea , 13 bytes

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

Un enlace diádico que toma la lista, fa la izquierda y el número n, a la derecha que produce un número.

Pruébalo en línea! Golfily ineficiente: se agotará el tiempo de espera para entradas con mayorno mayorduraciónf.

¿Cómo?

Sabemos que los poderes de los factores individuales (estrictamente positivos) nunca tendrán que excederse n-1
... ¡así que inspeccionemos todas las formas posibles!

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

Pruébalo en línea! Link excluye los casos de prueba más lentos, pero aún es un poco lento, así que trate de no martillar el servidor de @ Dennis.

Pyth - 10 bytes

Se queda sin memoria muy rápidamente.

f}T*My*QTE

Pruébelo en línea aquí .

Respuesta razonable 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]

Japt , 10 bytes

_k e!øV}aU

¡Pruébelo en línea!

No funciona en el último caso de prueba debido a un límite de iteración diseñado para evitar que el intérprete se ejecute para siempre (no ayudó mucho aquí, ya que congeló mi navegador durante una hora ...)

Explicación

_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

Jalea , 9 bytes

xŒPP€ḟḶ}Ṃ

El tiempo de ejecución de O (2 ^{n • length (f)} ) y el uso de memoria hacen de esta una solución teórica.

Pruébalo en línea!

Haskell , 46 bytes

Este es un puerto de la excelente respuesta de Python de KSab . Gracias a Laikoni por su ayuda en la depuración y el golf de esta respuesta en la sala de chat PPCG Haskell, Of Monads and Men . Sugerencias de golf bienvenidas! Pruébalo en línea!

(#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&]

Esencialmente un puerto de la respuesta Python de Rod . Define dos operadores binarios y . devuelve si es un producto de elementos de y de otra manera. da el entero más pequeño . Si alguien puede encontrar una manera de eliminar la prueba de divisibilidad, podría ahorrar 10 bytes utilizando la codificación ISO 8859-1.±·n±fTruenfFalsen·fi

Explicación

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])

Pruébalo en línea!

Han pasado 3 semanas, así que pensé que finalmente publicaría mi propia solución. Este es un enfoque de fuerza bruta.

Hay, sin embargo, un incorporado:

R , 5 bytes

nextn

Pruébalo en línea!

De los documentos R:

nextndevuelve el entero más pequeño, mayor o igual que n, que se puede obtener como producto de potencias de los valores contenidos en factors. nextnestá destinado a usarse para encontrar una longitud adecuada para rellenar con ceros el argumento de ffta para que la transformación se calcule rápidamente. El valor predeterminado para factorsasegura esto.

Sin embargo, algunas pruebas revelaron un error en la implementación, como se muestra en el enlace TIO anterior.

nextn(91,c(2,6))debería devolver 96, pero devuelve 128 en su lugar. Obviamente, esto solo ocurre cuando factorsno todos son relativamente primos entre sí. De hecho, el código C subyacente revela que con nextnavidez trata de dividir cada uno factora su vez hasta que 1se alcanza:

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

Esto se puede resolver tomando la entrada en orden decreciente.

JavaScript (ES6), 53 50 bytes

Guardado 3 bytes gracias a @DanielIndie

Toma entrada en la sintaxis de curry (n)(a).

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

Casos de prueba

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

¿Cómo?

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