素数の階乗の比として有理数を書く

注:この問題は、サンドボックスに掲載されています。

前書き

この課題は、学部の数学の競争の問題である 2009 Putnam B1 に触発されています。問題は次のとおりです。

すべての正の有理数は、必ずしも別個の素数の階乗の積の商として書くことができることを示します。たとえば、

     

チャレンジ

Your チャレンジ is to take a pair of relatively prime positive
integers, representing the numerator and denominator of a positive
rational number (or just the rational number itself) as input, and
output two lists (or arrays, etc.) of prime numbers so that the
inputted rational number is equal to the ratio of the product of
the factorials of the primes in the first list to the product of
the factorials of the primes in the second list.

ノート

  • 最初のリストと2番目のリストの両方に含まれる素数は存在しないかもしれません。しかし、素数はいずれかのリストに希望する数だけ表示されることがあります。
  • 入力はそれぞれ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)

スコアリング

This is ,
so the lowest score in bytes wins!

ベストアンサー

Mathematica、 175 177 169 154 108バイト

[email protected]@@Table[x[[1]],{s,{1,-1}},{x,[email protected]#},x[[2]]s]&@*(If[#==1,1,{p,e}[email protected](r=FactorInteger)@#;p^e#0[p!^-e#]]&)

(Mathematica)は、試してみてください!

使い方

これは2つの関数の構成です。一番目は、

If[# == 1,
  1,
  {p,e} = Last[FactorInteger[#]];
  p^e * #0[p!^-e * #]
]&

は、所望の因数分解を実際に計算するための再帰関数である。具体的には、合理的な入力 x
が与えられれば、階乗が分子と分母にあるべき素数を計算し、これらの素数をすべて乗算した分数を返します。たとえば、 10/27
= 2 * 5 /(3 * 3!* 3!)
3 * 3)。)

すべてのステップで最大の素因数を扱うことでこれを行います.xの因数分解でp e が発生した場合、p!
e が階乗分解、p! e で区切られたxで繰り返されます。

(以前はpより前の素数を見ることで大量の数字を避けるより巧妙な戦略がありましたが、Mathematicaは65521という大きな数字を扱うことができますので、これは意味がありません。はるかに高速:私のコンピュータでは、このバージョンが1.6秒で処理する入力で0.05秒かかりました。)

2番目の関数は、最初の関数の出力を素数のリストに変換します。

Join @@@ 
  Table[x[[1]],
    {s,{1,-1}},
    {x,FactorInteger[#]},
    x[[2]]*s
  ]&

s = 1 (正の累乗)と s = -1 (負の累乗)の場合は、それぞれ
{prime、exponent} 素因数 r @#で、素数
prime 指数* s を何度も繰り返します。

109 62バイトの非コンパチブルバージョン

If[#==1,∇1=1,{p,e}[email protected]

上記と同じですが、出力をリストとして与える代わりに、階乗のためのスタンドとして∇演算子(組み込みの意味を持たないため)を使用して、出力を式として出力します。したがって、
10/9 の入力は(2!* 5)を表す(∇2*∇5)/(∇3)^ 3
!)/(3!)^ 3

関数の2番目の部分をスキップするので、これは短くなります。


+2バイト:Mathematicaが動揺しないようにするには、 f = First
という割り当てを適切な場所で実行する必要があります。

-8バイト:整数出力のバグを修正しました。実際にはコードが短くなりました。

-15バイト: FactorInteger
はソートされた出力を返します。これを利用できます。

-46バイト:私たちは実際に巧みにする必要はありません。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です