Codegolf - Запись Рациональных Чисел Как Отношения Факториалов Простых Чисел

Примечание: это задание было опубликовано. в песочнице.

Введение

Этот вызов вдохновлен 2009 Патнэм Б1, задача на олимпиаде по математике среди студентов. Проблема заключается в следующем:

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

Испытание

Ваша задача состоит в том, чтобы взять в качестве входных данных пару относительно простых положительных целых чисел, представляющих числитель и знаменатель положительного рационального числа (или просто само рациональное число), и вывести два списка (или массивов и т. д.) простых чисел так, чтобы введенное рациональное число равно отношению произведения факториалов простых чисел в первом списке к произведению факториалов простых чисел во втором списке.

Примечания

• Не может быть простых чисел, содержащихся как в первом списке, так и во втором списке; однако простое число может появляться в любом списке столько раз, сколько пожелает.
• Можно предположить, что каждый входной сигнал находится в диапазоне (нестрого) от 1 до 65535; однако нельзя предполагать, что факториалы чисел, которые вам нужно будет вывести, будут находиться в этом диапазоне.

Пример ввода и вывода

Вот примеры правовых входов и выходов.

 
 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)
 
 

Входные данные (2,2), (0,3), (3,0), (3,6) и (1,65536) являются недопустимыми входными данными (т. е. ваша программа не должна вести себя с ними каким-либо особым образом). ). Вот несколько примеров незаконных выходных данных:

Подсчет очков

Это , поэтому побеждает наименьшее количество байтов!

#код-гольф #код-гольф #математика #теория чисел #простые числа #рациональные числа

05AB1E, 54 53 48 46 40 35 33 32 28 байт

 
 
 
 
 
 
 g=lambda a,b:a and g(b%a,a)or b;n,d=input();m=c=()
while n+d>2:

t=n*d;f=p=2

while t>p:
	if t%p:p+=1;f*=p
	else:t/=p

if n%p:c+=p,;n*=f

else:m+=p,;d*=f

t=g(n,d);n/=t;d/=t
print m,c
 
 
 
 
 
 
 

Попробуйте онлайн! Изменить: сохранено 2 байта только благодаря @ASCII. Сэкономлено 1 2 3 4 байта благодаря @Emigna. (Мне нужно сохранить только один, и у меня останется половина исходного количества байт!) Пояснение:

Mathematica, 175 177 169 154 108 байт

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

Как это работает

Это композиция двух функций. Первый, который отменяет гольф

— это рекурсивная функция для фактического вычисления желаемой факторизации. В частности, при наличии рациональных входных данных (∇2*∇5)/(∇3)^3 , we compute the primes whose factorials should be in the numerator and denominator, and return the fraction with all of those primes multiplied together. (For example, on input 10/9 , мы возвращаемся If[#==1,∇1=1,{p,e}=Last@FactorInteger@#;(∇p)^e#0[p!^-e#]]& .)

Мы делаем это, имея дело с наибольшим простым множителем на каждом шаге: если p^е происходит при факторизации x, мы убеждаемся, что p!^е происходит при факториале-факторизации и рекурсии по x, делённому на p!^е.

(Раньше у меня была более хитрая стратегия, позволяющая избежать больших чисел, глядя на предыдущее простое число перед p, но Mathematica может легко обрабатывать числа до 65521!, так что в этом нет смысла. Старую версию, которую вы можете найти в истории, является намного быстрее: на моем компьютере входные данные заняли 0,05 секунды, а эта версия обрабатывает за 1,6 секунды.)

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

Для prime (positive powers) and r@# (отрицательные степени), и для каждого члена {prime,exponent} in the factorization s=-1 , повторяем простое число s=1 Join @@@ Table[x[[1]], {s,{1,-1}}, {x,FactorInteger[#]}, x[[2]]*s ]& много раз.

Неконкурирующая версия с 109 62 байтами

То же, что и выше, но вместо вывода в виде списка выдает вывод в виде выражения, используя оператор ∇ (поскольку он не имеет встроенного значения) в качестве замены факториалов. Таким образом, ввод 10/9 = 2!*5!/(3!*3!*3!) gives an output of x представлять If[# == 1, 1, {p,e} = Last[FactorInteger[#]]; p^e * #0[p!^-e * #] ]& .

Это короче, потому что мы пропускаем вторую часть функции.

+2 байта: назначение Join@@@Table[x[[1]],{s,{1,-1}},{x,r@#},x[[2]]s]&@*(If[#==1,1,{p,e}=Last@(r=FactorInteger)@#;p^e#0[p!^-e#]]&) has to be done in the right place to keep Mathematica from getting upset.

-8 байт: исправлена ​​ошибка для целочисленных выходных данных, из-за которой код фактически стал короче.

-15 байт: [ Begin an infinite loop D¿÷ Reduce to lowest terms Z# Exit the loop if the (largest) value is 1 DÓ€g Find the index of the largest prime factor of each value Z Take the maximum D<ØŠ Convert index back to prime and save for later Q Convert to an pair of which value had the largest prime factor * Convert to an pair with that prime factor and zero Dˆ Save the pair in the global array for later R!* Multiply the other input value by the factorial of the prime ] End of infinite loop ¯ø Collect all the saved primes εʒĀ Forget all the saved 0s returns sorted output, which we can take advantage of.

-46 байт: на самом деле нам не нужно быть умными.

Python 2, 220 202 195 183 байта

Попробуйте онлайн! Изменить: сохранено 18 25 байт благодаря @Mr.Xcoder. Сэкономлено 12 байт благодаря @JonathanFrech.