素数をできるだけ短い論理式で

はぎぉ @hagebooi

【ゆる募】素数をできるだけ短く表現してください ちなみにWikipediaさんの記録は「1 と自分自身以外に正の約数を持たない自然数で、1 でない数」で28字です

はぎぉ @hagebooi

ご協力により様々な素数の表現を戴いたのでランキング形式で発表します

はぎぉ @hagebooi

【簡潔な素数表現ランキング】 1位　素数 2位　Z/pが体 3位　1と合成数以外の自然数 4位　正の約数をただ2つ持つ自然数 5位　1と自身以外を正の約数に持たない自然数 6位　X={x|x∈N, x≠1, x mod y ≠ 0, y ≠ 1,x}

kinaba @kinaba

#素数をできるだけ短く表現してください を見てて勝手に問題を厳密にしたくなったんですが、一階の算術（＋×と0とSucと=と∀∃⇒∨∧￢）の論理式での最短ってなんだろう。式のサイズは先に書いた記号の出現回数とする。普通な ∀y∀z(y×z=n ⇒ y=S(0)∨y=n) に勝てるか

kinaba @kinaba

@kinaba あっこれ n=1 でも真になるじゃん。出直し

Sosuke MORIGUCHI @chiguri

くっ、kinabaさんのに突っ込もうと思いついた瞬間にご自分で訂正を・・・

kikx @kikx

@kinaba 1が除けてなくない？

S (ﾂｲｰﾄはｽﾚｯﾄﾞ全体をご確認ください) @esumii

twitter.com/kinaba/status/… 素数の定義は何度か試験に出したが（別に最短でなくても良い）、意外と間違える（含む自分(^^;）

kikx @kikx

ぎゃー訂正に気付かずにつっこんじゃった

ぽんた @Pontama314

コーディングゴルフ、始まる。

h segawa @dec9ue

denotational predicates golf?

Hideyuki Tanaka @tanakh

そすう(´･_･`)

Sosuke MORIGUCHI @chiguri

∀y∀z(y×S(S(z))=n ⇒ S(S(z))=n)ならまあ・・・

おかゆ @oka_iu_tcan

1が省けてないのはともかくとして、 ∀y∀z(y×z=n ⇒ (y=S(0)∨y=n)) こうじゃないのかな？⇒と∨って優先順位違うんだっけ

kinaba @kinaba

なんか以外と綺麗にいかなくて ￢n=S(0) ∧ ∀y∀z(y×z=n ⇒ y=S(0)∨y=n) みたいな酷いのしか思いついていない。不等号があれば縮むけどゲーム性が減る

Sosuke MORIGUCHI @chiguri

でもこれならばじゃダメなような・・・？

おかゆ @oka_iu_tcan

あと、議論領域は自然数であることを明示しなくてもいいのかな。2=0.5×4とか

Sosuke MORIGUCHI @chiguri

n=1で前件が充足されないな・・・ .

Sosuke MORIGUCHI @chiguri

（つまり空ろに成り立つ）

おかゆ @oka_iu_tcan

まあサクセサ使ってるくらいだから自然数でいいのか

Akihiro Nomura / きつね @sacred_fox

@kinaba y=S(0) のところ、 z=n じゃだめなんでしょうか そして1を排除できてない気が

Sosuke MORIGUCHI @chiguri

案外面倒くさい。

kinaba @kinaba

@sacred_fox z=nだと0が排除できてないです。なんかサボろうとすると意外と0か1が紛れ込んでくる…