Учитывая положительное целое число n, выведите целые числа a и b (образуя сокращенную дробь a / b ), так что:

Где p _k - это k- е простое число (с p ₁ = 2).

Примеры:

1   -> 3, 5
2   -> 12, 25
3   -> 144, 325
4   -> 3456, 8125
5   -> 41472, 99125
15  -> 4506715396450638759507001344, 11179755611058498955501765625
420 -> very long

Допустимы вероятностные простые проверки, и это нормально, если ваш ответ не удался из-за ограничений в целочисленном типе вашего языка.

Самый короткий код в байтах побеждает.

М , 9 байт

RÆN²‘İḤCP

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

пустяки

Знакомьтесь, М!

М - это вилка Желе, нацеленная на математические задачи. Основное различие между Jelly и M состоит в том, что M использует бесконечную точность для всех внутренних вычислений, символически представляя результаты. Как только M станет более зрелым, Jelly постепенно станет более универсальным и менее ориентированным на математику.

M очень много работы в прогрессе (полной ошибок, а не на самом деле , что отличается от молочка прямо сейчас), но он работает как шарм для этой проблемы , и я просто не мог устоять.

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

RÆN²‘İḤCP  Main link. Argument: n

R          Range; yield [1, ..., n].
 ÆN        Compute the kth primes for each k in that range.
   ²‘      Square and increment each prime p.
     İ     Invert; turn p² + 1 into the fraction 1 / (p² + 1).
      Ḥ    Double; yield 2 / (p² + 1).
       C   Complement; yield 1 - 2 / (p² + 1).
        P  Product; multiply all generated differences.

Mathematica, 32 байта

1##&@@(1-2/(Prime@Range@#^2+1))&

Неименованная функция, которая принимает целочисленный ввод и возвращает фактическую дробь.

Это использует тот факт, что . Код затем обрабатывается благодаря тому, что Mathematica продвигает всю основную арифметику над списками. Итак, мы сначала создаем список , затем извлекаем все эти простые числа и вставляем этот список в вышеприведенное выражение. Это дает нам список всех факторов. Наконец, мы умножаем все вместе, применяя к списку, к которому можно прибегнуть .(p2-1)/(p2+1) = 1-2/(p2+1){1, 2, ..., n}Times1##&

В качестве альтернативы мы можем использовать Arrayдля того же количества байтов:

1##&@@(1-2/(Prime~Array~#^2+1))&

Python 2, 106 байт

from fractions import*
n=input()
F=k=P=1
while n:b=P%k>0;n-=b;F*=1-Fraction(2*b,k*k+1);P*=k*k;k+=1
print F

Первая и четвертая строки очень больно ... оказалось, что использование Fractionбыло лучше, чем умножение по отдельности и использование gcd, даже в Python 3.5+, где gcdнаходится math.

Премьер - поколение адаптировано из ответа @ XNOR в здесь , который использует теорему Вильсона.

Рубин, 122 77 65 байт

Спасибо Шерлоку за то, что он сбрил 10 байтов.

require'prime'
->n{Prime.take(n).map{|x|1-2r/(x*x+1)}.reduce(:*)}

Определяет анонимную функцию, которая принимает число и возвращает a Rational.

PARI / GP , 33 байта

n->prod(i=1,n,1-2/(prime(i)^2+1))

Альтернативная версия (46 байт):

n->t=1;forprime(p=2,prime(n),t*=1-2/(p^2+1));t

Неконкурентная версия, дающая результат с плавающей точкой ( t_REAL) (38 байт):

n->prodeuler(p=2,prime(n),1-2/(p^2+1))

Желе , 14 13 байтов

RÆN²µ’ż‘Pµ÷g/

Попробуйте онлайн! Спасибо @Dennis за -1 байт.

R                       Range [1..n]
 ÆN                     Nth prime
   ²                    Square
    µ                   Start new monadic chain
     ’ż‘                Turn each p^2 into [p^2-1, p^2+1]
        P               Product
         µ              Start new monadic chain
          ÷             Divide by...
           g/           Reduce GCD

Pyth, 26 25

/RiFN=N*MCm,tdhd^R2.fP_ZQ

Попробуйте здесь или запустите Test Suite .

1 байт сохранен благодаря Якубе!

Довольно наивная реализация спецификаций. Использует элегантное «новое» (я понятия не имею, когда это было добавлено, но я никогда не видел его раньше), P<neg>которое возвращает, является ли положительное значение отрицательного числа простым или нет. Некоторые из карт и т. Д., Вероятно, можно сыграть в гольф ...

Юлия, 59 42 байта

n->prod(1-big(2).//-~primes(2n^2)[1:n].^2)

Это анонимная функция , которая принимает целое число и возвращает Rationalс BigIntчислителем и знаменателем.

Мы начинаем с генерации списка простых чисел, меньших 2 n ^2, и выбора первых n элементов. Это работает, потому что n- е простое число всегда меньше, чем n ² для всех n > 1. ( см. Здесь .)

Для каждого p из n выбранных простых чисел мы возводим в квадрат p, используя поэлементную степень ( .^2), и строим рациональное 2 / ( p + 1), где 2 сначала преобразуется в a, BigIntчтобы обеспечить достаточную точность. Мы вычитаем это из 1, берем произведение полученного массива рациональных чисел и возвращаем полученное рациональное.

Пример использования:

julia> f = n->prod(1-big(2).//-~primes(2n^2)[1:n].^2)
(anonymous function)

julia> f(15)
4506715396450638759507001344//11179755611058498955501765625

Сохранено 17 благодаря Sp3000!

Выпуклый, 28 байт

Convex - это новый язык, который я разрабатываю и который основан на CJam и Golfscript. Интерпретатор и IDE можно найти здесь . Ввод - это целое число в аргументах командной строки. Индексы основаны на одном. Использует кодировку CP-1252.

,:)_{µ²1-}%×\{µ²1+}%׶_:Ðf/p

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

MATL , 18 байт

:Yq2^tqpwQpZd1Mhw/

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

Сбой для больших входных данных, потому что только целые числа до 2^52могут быть точно представлены внутри.

объяснение

:     % implicitly take input n. Generate range [1,...,n]
Yq    % first n prime numbers
2^    % square
tqp   % duplicate. Subtract 1. Product
wQp   % swap. Add 1. Product
Zd    % gcd of both products
1M    % push the two products again
h     % concatenate horizontally
w/    % swap. Divide by previously computed gcd. Implicitly display

Mathematica, 45 байт

Times@@Array[(Prime@#^2-1)/(Prime@#^2+1)&,#]&

Штрихи? Фракции? Mathematica.

Haskell, 53 байта

Анонимная функция, 53 символа:

(scanl(*)1[1-2%(p*p+1)|p<-nubBy(((>1).).gcd)[2..]]!!)

Попробуйте это здесь (примечание: в стандартном GHCi сначала нужно убедиться Data.Ratioи Data.Listимпортироваться):

λ (scanl(*)1[1-2%(p*p+1)|p<-nubBy(((>1).).gcd)[2..]]!!) 5
41472 % 99125
:: Integral a => Ratio a

Индекс списка Хаскелла !!основан на 0. (___!!)является операторским разделом , формирующим анонимную функцию, так что (xs !!) n == xs !! n.

Это меньше на четыре байта для генерации всей последовательности:

λ mapM_ print $ take 10 $     -- just for a nicer output
    scanl(*)1[1-2%(n*n+1)|n<-[2..],all((>0).rem n)[2..n-1]]
1 % 1
3 % 5
12 % 25
144 % 325
3456 % 8125
41472 % 99125
3483648 % 8425625
501645312 % 1221715625
18059231232 % 44226105625
4767637045248 % 11719917990625
:: IO ()

Серьезно, 25 байт

,r`PªD;⌐k`M┬`π`Mi│g;)@\)\

Выходы a\nb( \nэто новая строка). Большие входные данные займут много времени (и могут потерпеть неудачу из-за нехватки памяти), потому что простое генерирование довольно медленное.

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

Объяснение:

,r`PªD;⌐k`M┬`π`Mi│g;)@\)\
,r                         push range(input)
  `PªD;⌐k`M                map:
   P                         k'th prime
    ª                        square
     D                       decrement
      ;                      dupe
       ⌐                     add 2 (results in P_k + 1)
        k                    push to list
           ┬               transpose
            `π`M           map product
                i│         flatten, duplicate stack
                  g;)      push two copies of gcd, move one to bottom of stack
                     @\    reduce denominator
                       )\  reduce numerator