Примечание: этот вызов был размещен в песочнице .
Вступление
Эта задача вдохновлена 2009 Putnam B1 , проблемой в конкурсе математики для студентов. Проблема заключается в следующем:
Покажите, что каждое положительное рациональное число может быть записано как частное от произведений факториалов (не обязательно различных) простых чисел. Например,
Вызов
Ваша задача состоит в том, чтобы взять в качестве входных данных пару относительно простых натуральных чисел, представляющих числитель и знаменатель положительного рационального числа (или только самого рационального числа), и вывести два списка (или массива и т. Д.) Простых чисел так, чтобы введенное рациональное число равно отношению произведения факториалов простых чисел в первом списке к произведению факториалов простых чисел во втором списке.
Примечания
- Там не может быть никаких простых чисел, которые содержатся как в первом списке, так и во втором списке; однако, простое число может появляться столько раз, сколько нужно в любом списке.
- Можно предположить, что каждый из входов (не строго) находится между 1 и 65535; однако нельзя предположить, что факториалы чисел, которые вам нужно вывести, будут в этом диапазоне.
Пример ввода и вывода
Вот примеры юридических входов и выходов.
input=>output
10,9 => [2,5],[3,3,3]
2,1 => [2],[]
3,1 => [3],[2]
1,5 => [2,3,2],[5] (elements of a list may be in any order)
3,2 => [3],[2,2]
6,1 => [3],[]
Входы (2,2), (0,3), (3,0), (3,6) и (1,65536) являются недопустимыми (т. Е. Ваша программа не должна вести себя по-своему) ). Вот несколько примеров незаконных выводов:
1,2 => [2],[2,2] (2 is in both returned lists)
5,2 => [5],[2,4] (4 is not prime)
2,1 => [2],[1] (1 is not prime either)
3,2 => [3],[2] (3!/2! = 3, not 3/2)
счет
Это код-гольф , поэтому выигрывает самая низкая оценка в байтах!
источник
10/9
=[2*5]/[3*3]
=[(2!/1!) * (5!/4!)] / [(3!/2!) * (3!/2!)]
=[2! * 5! * 2! * 2!] / [3! * 3! * 1! * 4!]
=(2! * 2! * 2! *5!) / (3! * 3! * 4!)
.10/9
а не пары чисел10
и9
?Ответы:
05AB1E ,
545348464035333228 байтПопробуйте онлайн! Редактировать: Сохранено 2 байта благодаря @ ASCII-only. Сохранено
1234 байта благодаря @Emigna. (Мне нужно только сохранить еще один, и я уменьшил до половины моего первоначального числа байтов!) Объяснение:источник
¦D
Mathematica,
175177169154108 байтПопробуйте онлайн!
Как это устроено
Это композиция из двух функций. Первое, которое развязывает
является рекурсивной функцией для фактического вычисления желаемой факторизации В частности, при рациональном вводе
x
мы вычисляем простые числа, чьи факториалы должны быть в числителе и знаменателе, и возвращаем дробь со всеми этими простыми числами, умноженными вместе. (Например, при вводе10/9 = 2!*5!/(3!*3!*3!)
мы возвращаемся10/27 = 2*5/(3*3*3)
.)Мы делаем это, имея дело с наибольшим простым множителем на каждом шаге: если p e возникает при факторизации x, мы проверяем p! e происходит в факториализационной факторизации, и рекурсивный на x делится на p! эл .
(Ранее у меня была более умная стратегия, которая избегает больших чисел, просматривая предыдущее простое число перед p, но Mathematica может легко обрабатывать числа размером до 65521!, Так что нет никакого смысла. Старая версия, которую вы можете найти в истории, это намного быстрее: на моем компьютере потребовалось 0,05 секунды на входы, которые эта версия обрабатывает за 1,6 секунды.)
Вторая функция превращает вывод первой функции в списки простых чисел.
Для
s=1
(положительных степеней) иs=-1
(отрицательных степеней) и для каждого члена{prime,exponent}
факторизацииr@#
мы повторяем простое числоprime
exponent*s
много раз.Неконкурентная версия с
10962 байтамиТо же, что и выше, но вместо выдачи вывода в виде списка, вывод выводится в виде выражения, используя оператор ((поскольку он не имеет встроенного значения) в качестве замены для факториалов. Таким образом, вход
10/9
дает выход(∇2*∇5)/(∇3)^3
для представления(2!*5!)/(3!)^3
.Это короче, потому что мы пропускаем вторую часть функции.
+2 байта: назначение
f=First
должно быть выполнено в нужном месте, чтобы Mathematica не расстраивалась.-8 байт: исправлена ошибка для целочисленных выходных данных, которая фактически делала код короче.
-15 байт:
FactorInteger
возвращает отсортированный вывод, которым мы можем воспользоваться.-46 байт: нам не нужно быть умным.
источник
Python 2,
220202195183 байтаПопробуйте онлайн! Изменить: Сохранено
1825 байт благодаря @ Mr.Xcoder. Сохранено 12 байтов благодаря @JonathanFrech.источник