In letzter Zeit gab es viele Herausforderungen im Zusammenhang mit Prim / Prim-Faktorisierung. Ich dachte, es könnte interessant sein, in die andere Richtung zu gehen.

Gegeben:

• eine positive ganze Zahl nund
• eine nicht leere Liste positiver Ganzzahlen f

Schreiben Sie ein vollständiges Programm oder eine Funktion, um die kleinste Ganzzahl iso zu finden, dass i >= nund iein Produkt nichtnegativer ganzzahliger Potenzen von Elementen in ist f.

Beispiele:

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

  Die ersten Produkte sind:

  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
  

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

  Wieder die ersten Produkte:

  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
  

Testfälle:

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

Regeln

• Sie können davon ausgehen, dass fmindestens ein Element enthalten sein wird und dass alle Elemente von fgrößer als 1 sind.
• Sie können optional davon ausgehen, dass fdie Sortierung in absteigender / aufsteigender Reihenfolge erfolgt, wenn Sie dies wünschen (aber bitte angeben).
• Sie können optional die Anzahl der Elemente von nehmen, fwenn Sie möchten.
• Die Ausgabe als String ist zulässig.
• Das ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes in jeder Sprache!
• Es gelten die Standard-E / A-Regeln, und Standard-Regelungslücken sind verboten.
• Erklärungen sind erwünscht.

Schale , 8 Bytes

ḟṠ€ȯmΠṖṘ

Extrem langsam. Probieren Sie es online!

Erläuterung

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

Probieren Sie es online!

Wie es funktioniert

Nimmt die Eingabe als [n,k,f1,f2,f3,...,fk](z. B. [11,3,2,3,5]) an: Der erste Wert ist das Ziel n, der zweite die Anzahl der Faktoren, und alle Fraktoren folgen.

Die anderen Herausforderungen der Zahlentheorie haben sich in letzter Zeit zu ausgefallenen Einbauten entwickelt (zumindest wurden sie verwendet FactorInteger), sodass ich dachte, ich würde etwas ausprobieren, das nur grundlegende Tools verwendet. Diese Lösung besagt im Grunde, dass nwir zum Schreiben als Produkt der Faktoren entweder den ersten Faktor verwenden f1(und n/f1dann mit diesem multiplizieren f1) oder nicht (und dann auf eine kürzere Liste von Faktoren zurückgreifen) und dann die min.

Die Rekursion ist beendet, wenn das Ziel kleiner als 1 ist oder wenn die Anzahl der Faktoren 0 ist, nach denen wir #^#2<=1sofort suchen, und dann im ersten Fall 1 und Infinityim letzteren Fall mit 1 generieren 1~Max~-Log@#2.

Die Funktion gibt eine ganze Reihe von Warnungen aus (funktioniert aber immer noch), es sei denn, Sie führen sie mit aus Quiet, da sie schließlich auf Fälle zurückgreift, in denen #3es keine gibt, was den nicht verwendeten zweiten Zweig von Iftraurig macht.

-3 Bytes: Anzahl der Faktoren als Eingabe nehmen.

-3 Bytes dank @ngenisis: using ∞.

-1 Byte und keine ∞Mehrdeutigkeit: die #^#2Prüfung.

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)

Probieren Sie es online!

Die Funktion f prüft rekursiv, ob nein Produkt von Potenzen von Elementen in l, gnur ein Wrapper ist, um die Iteration zu steuern

Python, 55 Bytes

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

Probieren Sie es online!

Schamlos kopierte Rods Fußzeilenskript zum Testen

Jelly , 13 Bytes

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

Ein dyadischer Link, der die Liste flinks und die Zahl nrechts aufnimmt und eine Zahl ergibt.

Probieren Sie es online!Golf ineffizient - Zeitüberschreitung bei Eingaben mit höheren nund / oder längeren Werten f.

Wie?

Wir wissen, dass die Kräfte der einzelnen (streng positiven) Faktoren niemals überschritten werden müssen n-1
... Untersuchen wir also einfach alle möglichen Möglichkeiten!

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

Netzhaut , 76 Bytes

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

Probieren Sie es online! Link schließt die langsamsten Testfälle aus, ist aber immer noch etwas langsam. Versuchen Sie also nicht, auf den Server von @ Dennis einzusteigen.

Pyth - 10 Bytes

Der Speicher geht sehr schnell zur Neige.

f}T*My*QTE

Probieren Sie es hier online aus .

Angemessene Antwort für 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&]&

Eingang

[{liste f}, n, Anzahl der Elemente von f]
[{57, 34, 12, 21}, 12532159, 4]

Japt , 10 Bytes

_k e!øV}aU

Online testen!

Funktioniert im letzten Testfall aufgrund einer Iterationsbeschränkung nicht, die dafür ausgelegt ist, dass der Interpreter nicht für immer ausgeführt wird (hat hier jedoch nicht viel geholfen, da mein Browser für eine Stunde eingefroren ist ...)

Erläuterung

_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

Gelee , 9 Bytes

xŒPP€ḟḶ}Ṃ

O (2 ^{n • Länge (f)} ) Laufzeit und Speichernutzung machen dies zu einer theoretischen Lösung.

Probieren Sie es online!

Haskell , 46 Bytes

Dies ist eine Portierung von KSabs hervorragender Python-Antwort . Vielen Dank an Laikoni für ihre Hilfe beim Debuggen und Golfen dieser Antwort im PPCG Haskell Chatroom, Of Monads and Men . Golfvorschläge willkommen! Probieren Sie es 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&]

Im Wesentlichen eine Portierung von Rods Python- Antwort . Definiert zwei binäre Operatoren ±und ·. n±fGibt zurück, Trueob nein Produkt aus Elementen von fund Falseandernfalls ist. n·fgibt die kleinste ganze Zahl an i. Wenn jemand einen Weg finden kann, um den Teilbarkeitstest zu eliminieren, könnte ich durch Verwendung der ISO 8859-1-Codierung 10 Bytes einsparen.

Erläuterung

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

Probieren Sie es online!

Es sind 3 Wochen vergangen, also dachte ich, ich würde endlich meine eigene Lösung veröffentlichen. Dies ist ein Brute-Force-Ansatz.

Es gibt jedoch ein eingebautes:

R , 5 Bytes

nextn

Probieren Sie es online!

Aus den R-Dokumenten:

nextngibt die kleinste ganze Zahl größer oder gleich zurück n, die als Produkt der Potenzen der in enthaltenen Werte erhalten werden kann factors. nextnsoll verwendet werden, um eine geeignete Länge zu finden, um das Argument von fftto auf null zu setzen, damit die Transformation schnell berechnet wird. Der Standardwert für factorsstellt dies sicher.

Einige Tests ergaben jedoch einen Fehler in der Implementierung, wie der obige TIO-Link zeigt.

nextn(91,c(2,6))sollte 96 zurückgeben, gibt jedoch 128 zurück. Dies tritt offensichtlich nur dann auf, wenn factorsnicht alle relativ gut miteinander auskommen. Tatsächlich ist der zugrunde liegende C - Code es offenbart , dass nextngierig versucht jeden zu unterteilen factorwiederum , bis 1erreicht ist:

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

Dies kann gelöst werden, indem die Eingaben in absteigender Reihenfolge vorgenommen werden.

JavaScript (ES6), 53 50 Bytes

3 Bytes dank @DanielIndie gespeichert

Übernimmt Eingaben in der Currying-Syntax (n)(a).

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

Testfälle

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

Wie?

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