В последнее время было много первоочередных проблем, связанных с факторизацией, поэтому я подумал, что было бы интересно пойти другим путем.

Данный:

целое положительное число n и
непустой список натуральных чисел f

написать полную программу или функцию , чтобы найти наименьшее целое число iтакое , что i >= nи iявляется продуктом неотрицательных, целых степеней элементов f.

Примеры:

Пусть n = 11, f = [2, 3, 5].

Первые несколько продуктов:

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

Пусть n=14, f=[9, 10, 7].

Опять же, первые несколько продуктов:

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

правила

Вы можете предположить, что он fбудет содержать хотя бы один элемент, и что все элементы fбудут больше 1.
Вы можете при желании предположить, что fсортируется в порядке убывания / увеличения, если вы хотите (но, пожалуйста, укажите).
Вы можете по желанию взять количество элементов, fесли хотите.
Вывод в виде строки разрешен.
Это код-гольф , поэтому выигрывает самый короткий ответ в байтах на каждом языке!
Применяются правила ввода / вывода по умолчанию, а стандартные лазейки запрещены.
Пояснения приветствуются.

code-golf arithmetic integer Giuseppe
источник

10

Шелуха , 8 байт

ḟṠ€ȯmΠṖṘ

Очень медленно Попробуйте онлайн!

объяснение

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

Zgarb
источник

7

Wolfram Language (Mathematica) , 68 65 62 61 байт

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

Попробуйте онлайн!

Как это устроено

Принимает ввод как [n,k,f1,f2,f3,...,fk](например, [11,3,2,3,5]): первое значение является цельюn , второе - количество факторов, и следуют все факторы.

Другие проблемы теории чисел, недавно все сложенные в причудливые встроенные модули (по крайней мере, они использовали FactorInteger), так что я решил попробовать что-то, что использует только основные инструменты. Это решение в основном говорит о том, что для записи nв виде произведения факторов мы либо используем первый фактор f1(и вычисляем n/f1, а затем умножаем наf1 ), либо нет (и рекурсируем по более короткому списку факторов), а затем принимаем мин.

Рекурсия заканчивается, когда цель меньше 1 или когда число факторов равно 0, что мы проверяем #^#2<=1сразу, а затем генерируем 1 в первом случае и Infinityво втором с1~Max~-Log@#2 .

Функция выдает целую кучу предупреждений (но все еще работает), если вы не запускаете ее Quiet, потому что в конечном итоге она возвращается к случаям, когда #3не существует, что делает неиспользованную вторую ветвь Ifгрустной.

-3 байта: принимая количество факторов в качестве входных данных.

-3 байта благодаря @ngenisis: использование ∞.

-1 байт, и нет ∞двусмысленности: #^#2проверка.

Миша лавров
источник

2

Очень хорошо! ∞сохраняет 3байты более -Log@0 (doesn't work on TIO, but works fine on desktop Mathematica). Also, Tr [1 ^ {##}] `на байт короче Length@{##}.

ngenisis

Я не совсем уверен, что я думаю об использовании оптимизаций, которые не нравятся TIO, но уверен, я добавлю это. И #2даже короче чем Tr[1^{##}]. :)

Миша Лавров

1

Я думаю, что вы должны включить Quietв свой основной код. Этот ответ выводит слишком много неправильных сообщений. По крайней мере, спросите OP, если он в порядке с этим

J42161217

2

Это выглядит почти так же, как игнорирование STDERR на другом языке, что является общепринятой практикой .

Миша Лавров

2

∞Проблема , как представляется, ошибка. Я постараюсь это исправить.

Деннис

6

Python 2 , 91 88 84 байта

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)

Попробуйте онлайн!

Функция fрекурсивно проверяет, nявляется ли произведение степеней элементов в l, gпросто оболочкой для управления итерацией

прут
источник

6

Python, 55 байт

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

Попробуйте онлайн!

Бесстыдно скопировал нижний колонтитул Рода для тестирования

KSab
источник

4

Желе , 13 байт

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

Двоичная ссылка, содержащая список fслева и число nсправа, которое дает число.

Попробуйте онлайн! Golfily неэффективно - истечет время ожидания для входов с более высокимnи / или более длительнымf .

Как?

Мы знаем, что силы отдельных (строго положительных) факторов никогда не нужно будет превышать n-1
... поэтому давайте просто проверим все возможные пути!

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

Джонатан Аллан
источник

2

Сетчатка , 76 байт

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

Попробуйте онлайн! Ссылка исключает самые медленные тестовые случаи, но все еще немного медленная, поэтому старайтесь не забивать сервер @ Dennis.

Нил
источник

2

Pyth - 10 байт

Не хватает памяти очень быстро.

f}T*My*QTE

Попробуйте это онлайн здесь .

Разумный ответ для 16 байтов: fsm.A}RQ*Md./PTE

Maltysen
источник

2

Mathematica, 85 байт

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

вход

[{list f}, n, количество элементов f]
[{57, 34, 12, 21}, 12532159, 4]

J42161217
источник

{d,s}Min@Select[Flatten[1##&@@(s^#)&/@0~Range~9~Tuples~Tr[1^s]],#>=d&]

ngenisis

@ngenisis какой символ не отображается? Можете ли вы вместо этого сделать ссылку TIO?

J42161217

Никогда не думал, что увижу день, когда «Mathematica» и «TIO» использовались в одном и том же посте: P

caird coinheringaahing

@Jenny_mathy Это U+F4A1длинное имя \[Function].

ngenisis

Использование 0~Range~9кажется очень консервативным. Должны ли g[{2,3,5},1001]действительно пропустить 1024и вернуться 1080? Это не особенно большой вклад.

Миша Лавров

2

Japt , 10 байт

_k e!øV}aU

Проверьте это онлайн!

Не работает в последнем тестовом примере из-за лимита итераций, созданного для того, чтобы не дать интерпретатору работать вечно (хотя здесь это не сильно помогло, так как оно заморозило мой браузер на час ...)

объяснение

_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

ETHproductions
источник

2

Желе , 9 байт

xŒPP€ḟḶ}Ṃ

O (2 ^{n • length (f)} ) время выполнения и использование памяти делают это теоретическим решением.

Попробуйте онлайн!

Деннис
источник

2

Haskell , 46 байтов

Это порт отличного ответа Python от KSab . Спасибо Лайкони за помощь в отладке и игре в гольф этот ответ в чате PPCG Haskell, Of Monads and Men . Предложения по игре в гольф приветствуются! Попробуйте онлайн!

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

Sherlock9
источник

1

Mathematica, 73 байта

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

По существу порт Rod «S Python ответа . Определяет два бинарных оператора ±и ·. n±fвозвращает Trueif nявляется продуктом элементов fи Falseиным образом. n·fдает наименьшее целое числоi . Если кто-то может найти способ устранить тест на делимость, я мог бы сэкономить 10 байтов, используя кодировку ISO 8859-1.

объяснение

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

ngenisis
источник

1

р , 52 байта

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

Попробуйте онлайн!

Прошло 3 недели, поэтому я решил опубликовать собственное решение. Это подход грубой силы.

Однако есть встроенная функция:

R , 5 байт

nextn

Попробуйте онлайн!

Из R документов:

nextnвозвращает наименьшее целое число, большее или равное n, которое может быть получено как произведение степеней значений, содержащихся в factors. nextnпредназначен для нахождения подходящей длины для заполнения нуля аргумента fftto, чтобы преобразование вычислялось быстро. Значение по умолчанию дляfactors обеспечения этого.

Однако некоторые тесты выявили ошибку в реализации, как показано выше по ссылке TIO.

nextn(91,c(2,6))должен вернуть 96, но вместо этого возвращает 128. Это, очевидно, происходит только тогда, когда factorsне все относительно взаимно просты. Действительно, код C, лежащий в его основе, показывает, что nextnжадно пытается разделить каждый factorпо очереди, пока не 1будет достигнут:

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

Это может быть решено путем ввода данных в порядке убывания.

Giuseppe
источник

1

JavaScript (ES6), 53 50 байт

Сохранено 3 байта благодаря @DanielIndie

Принимает ввод в синтаксис карри (n)(a).

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

Контрольные примеры

Показать фрагмент кода

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

Развернуть фрагмент

Как?

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

Arnauld
источник

n => m = a => (g = k => k <n? a.map (x => g (k * x)): k> m? 0: m = k) (1) | mm = функция всегда выдает false при первом запуске, так что это в основном то же самое, что положить + a, теперь это 51 байт

DanielIndie

@DanielIndie Это на самом деле 50 байтов. Большое спасибо!

Арно

Наименьшее целое число как произведение заданных факторов

Примеры:

Тестовые случаи:

правила

Ответы:

Шелуха , 8 байт

объяснение

Wolfram Language (Mathematica) , 68 65 62 61 байт

Как это устроено

Python 2 , 91 88 84 байта

Python, 55 байт

Желе , 13 байт

Как?

Сетчатка , 76 байт

Pyth - 10 байт

Mathematica, 85 байт

Japt , 10 байт

объяснение

Желе , 9 байт

Haskell , 46 байтов

Mathematica, 73 байта

объяснение

р , 52 байта

R , 5 байт

JavaScript (ES6), 53 50 байт

Контрольные примеры

Как?