Ostatnio pojawiło się wiele wyzwań związanych z pierwszorzędnymi / pierwszymi czynnikami, więc pomyślałem, że może być interesujące pójście w drugą stronę.

Dany:

• dodatnia liczba całkowita noraz
• niepusta lista dodatnich liczb całkowitych f

napisać pełny program lub funkcję, aby znaleźć najmniejszą liczbę całkowitą itakie, że i >= ni ijest produktem, uprawnień nieujemnych liczb całkowitych z elementów f.

Przykłady:

• Załóżmy n = 11, f = [2, 3, 5].

  Pierwsze kilka produktów to:

  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
  

• Załóżmy n=14, f=[9, 10, 7].

  Ponownie kilka pierwszych produktów:

  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
  

Przypadki testowe:

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

Zasady

• Możesz założyć, że fbędzie zawierać co najmniej jeden element i że wszystkie elementy fbędą większe niż 1.
• Możesz opcjonalnie założyć, że fjest sortowany w porządku malejącym / rosnącym, jeśli chcesz (ale proszę określić).
• Opcjonalnie możesz wziąć liczbę elementów, fjeśli chcesz.
• Wyjście jako ciąg jest dozwolone.
• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach w każdym języku!
• Obowiązują domyślne reguły we / wy, a standardowe luki są zabronione.
• Wyjaśnienia są zachęcane.

Łuska , 8 bajtów

ḟṠ€ȯmΠṖṘ

Niezwykle wolno. Wypróbuj online!

Wyjaśnienie

ḟṠ€ȯ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 bajtów

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

Wypróbuj online!

Jak to działa

Przyjmuje dane wejściowe jako [n,k,f1,f2,f3,...,fk](np. [11,3,2,3,5]): Pierwsza wartość jest celem n, druga to liczba czynników, a wszystkie wskaźniki następują.

Inne wyzwania teorii liczb ostatnio spasowały do ​​fantazyjnych wbudowanych (przynajmniej ich FactorInteger), więc pomyślałem, że spróbuję czegoś, co wykorzysta tylko podstawowe narzędzia. To rozwiązanie zasadniczo mówi, że aby napisać njako iloczyn czynników, albo używamy pierwszego czynnika f1(i rekurencyjnie n/f1, a następnie mnożymy przez f1), albo nie (i powtarzamy na krótszej liście czynników), a następnie bierzmy min.

Rekurencja kończy się, gdy cel jest mniejszy niż 1 lub gdy liczba czynników wynosi 0, co sprawdzamy od #^#2<=1razu, a następnie generujemy 1 w pierwszym przypadku, a Infinityw drugim z 1~Max~-Log@#2.

Ta funkcja daje całą masę ostrzeżeń (ale nadal działa), chyba że ją uruchomisz Quiet, ponieważ w końcu powtarza się w przypadkach, w których#3 nie istnieje, co powoduje, że niewykorzystana druga gałąź jest Ifsmutna.

-3 bajty: przyjmowanie liczby czynników jako danych wejściowych.

-3 bajty dzięki @ngenisis: using ∞ .

-1 bajt i brak ∞dwuznaczności: #^#2czek.

Python 2 , 91 88 84 bajtów

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)

Wypróbuj online!

Funkcja fsprawdza rekurencyjnie, czy njest iloczynem mocy elementów w l, gjest tylko opakowaniem do kontrolowania iteracji

Python, 55 bajtów

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

Wypróbuj online!

Bezwstydnie skopiowałem stopkę Rod do testowania

Galaretka , 13 bajtów

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

Dynamiczny link prowadzący do listy fpo lewej stronie i liczby,n po prawej stronie, która daje liczbę.

Wypróbuj online! Golfly nieefektywne - przekroczy limit czasu dla danych wejściowych z wyższymn i / lub dłuższej f.

W jaki sposób?

Wiemy, że moce indywidualnych (ściśle pozytywnych) czynników nigdy nie będą musiały przekraczać n-1
... więc zbadajmy wszystkie możliwe sposoby!

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

Siatkówka , 76 bajtów

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

Wypróbuj online! Link wyklucza najwolniejsze przypadki testowe, ale wciąż jest trochę powolny, więc staraj się nie hamować serwera @ Dennis.

Pyth - 10 bajtów

Bardzo szybko kończy się pamięć.

f}T*My*QTE

Wypróbuj online tutaj .

Rozsądna odpowiedź dla 16 bajtów: fsm.A}RQ*Md./PTE

Mathematica, 85 bajtów

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

Wejście

[{lista f}, n, liczba elementów f]
[{57, 34, 12, 21}, 12532159, 4]

Japt , 10 bajtów

_k e!øV}aU

Przetestuj online!

Nie działa w ostatnim przypadku testowym z powodu limitu iteracji zaprojektowanego, aby uniemożliwić działanie interpretera na zawsze (nie pomogło to tutaj, ponieważ zamroził moją przeglądarkę na godzinę ...)

Wyjaśnienie

_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

Galaretka , 9 bajtów

xŒPP€ḟḶ}Ṃ

Zastosowanie środowiska wykonawczego O (2 ^{n • length (f)} ) i pamięci powoduje, że jest to rozwiązanie teoretyczne.

Wypróbuj online!

Haskell , 46 bajtów

To jest część doskonałej odpowiedzi KSab na Python . Podziękowania dla Laikoni za ich pomoc w debugowaniu i grze w golfa w odpowiedzi na czacie PPCG Haskell, Of Monads and Men . Zapraszamy do gry w golfa! Wypróbuj online!

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

Mathematica, 73 bajty

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

Zasadniczo port odpowiedzi Pytona na Rod . Definiuje dwa operatory binarne i . zwraca if jest iloczynem elementów±·n±fTruenf iFalse innych . n·fdaje najmniejszą liczbę całkowitąi . Jeśli ktoś wymyśli sposób na wyeliminowanie testu podzielności, mógłbym zaoszczędzić 10 bajtów, stosując kodowanie ISO 8859-1.

Wyjaśnienie

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 bajty

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

Wypróbuj online!

Minęły 3 tygodnie, więc pomyślałem, że w końcu opublikuję własne rozwiązanie. To podejście z użyciem brutalnej siły.

Istnieje jednak wbudowane:

R , 5 bajtów

nextn

Wypróbuj online!

Z dokumentów R:

nextnzwraca najmniejszą liczbę całkowitą, większą lub równą n, którą można uzyskać jako iloczyn potęg wartości zawartych w factors. nextnjest przeznaczony do użycia w celu znalezienia odpowiedniej długości do zerowania argumentu argumentu, fftaby transformacja była obliczana szybko. Wartość domyślna dlafactorsZapewnia to .

Niektóre testy ujawniły jednak błąd w implementacji, jak pokazuje powyższy link TIO.

nextn(91,c(2,6))powinien zwrócić 96, ale zamiast tego zwraca 128. Dzieje się tak oczywiście tylko wtedy, gdy factorsnie wszystkie są względnie pierwsze względem siebie. Rzeczywiście, kod C leżący u jego podstaw ujawnia, że nextnzachłannie próbuje podzielić każdy factorz nich, dopóki nie 1zostanie osiągnięty:

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

Można to rozwiązać, przyjmując dane wejściowe w malejącej kolejności.

JavaScript (ES6), 53 50 bajtów

Zaoszczędź 3 bajty dzięki @DanielIndie

Pobiera dane wejściowe w składni curry (n)(a).

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

Przypadki testowe

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

W jaki sposób?

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