2006/07/11
Document Actions
キミならどう書く 2.0 - ROUND 2 -
お待たせしました！
キミならどう書く 2.0 ROUND 2の開催です！！
今回のLL Ringでは「LLで関数プログラミング」のセッションをはじめとし，関数型言語の活躍が期待されます．そこで，前哨戦にも関数型のお題を用意しました．
お題は「Collatz予想」（角谷予想，3x+1問題）についての問題です．
Collatz予想の収束までのステップ数の最大値を求めよ．
Collatz予想とは，1以上の自然数 n に対して，次の関数 f(n) が必ず1を返すものとする．
f(n)
= 1 , n = 1 のとき
= f (n/2) , n が偶数のとき
= f (3*n + 1) , n が奇数のとき
たとえば，f(3)が 1 になるまでの経緯は，
f(3) -> f(10) -> f(5) -> f(16) -> f(8) -> f(4) -> f(2) -> f(1) -> 1
となり， f(n) の呼出は8回である．これをステップ数と呼ぶことにする．
ここで f(n) が 1 になるまでのステップ数を g(n) とする．つまり，g(3) = 8 である．
このとき
h(n) = k, 1 ≦ k ≦ n ∧ g(k) = max (g(1),g(2),…,g(n))
について h(100) を求めよ．
また，余力のある者は大きな n についても h(n) を求めよ．
関数型言語でも，そうでない言語でも，ぜひ回答をお寄せください！
人気投票の対象となる回答をされたい方はURLのある形での回答をお願いします（トラックバックできない場合はコメント欄にURLを記述する形でもよいです）．
締め切りは7月24日（月）とさせていただきます．よろしくお願いします．
- Category(s)
- キミならどう書く2.0
[PHP]LL Ring[キミならどう書く 2.0 - ROUND 2 - ]がはじまっていた。
http://ll.jus.or.jp/2006/blog/doukaku2 で、Collazt予想なるお題が出ていた。 ネットサーフ中に見つけたので、素人ながらも、ちょっとPHPで書いてみた。 問題設定に従って$n=100になっているけれど、$nを換えればいくらでも上まで行く。 <?php $n = 100; $max_count =
[プログラミング]コラッツ
http://jijixi.azito.com/cgi-bin/diary/index.rb?date=20060711#p02 経由で、 http://ll.jus.or.jp/2006/blog/doukaku2 class Collatz include Enumerable def initialize( n ) @n=n @cache={1=>1} end def calc(n) @cache[n]=_calc(n) unless @cache.include?(n) @cac
Collatz予想step数の最大値
キミならどう書く 2.0 ROUND 2が出題された。なんか、Rubyの回答は...
[PRO] Io で Collatz 予想
お題は「Collatz予想」についての問題です． 関数型言語でも，そうでない言語でも，ぜひ回答をお寄せください！ キミならどう書く 2.0 - ROUND 2 - ? Lightweight Language Ring 例によって、Io で書くとこんな感じに。 collatz.io result := 0 max_step := 0 collatz := Ob
[ruby]Collatz予想の収束までのステップ数の最大値
http://ll.jus.or.jp/2006/blog/doukaku2 LLRingの「キミならどう書く 2.0」でお題がでてたので、rubyで書いてみた。素朴なメモ化以外の工夫なし。コメントはずすとメモした値が見れます。 @memo = {1=>1} def g(n) @memo[n] ||= 1 + if (n % 2) == 0 then g(n/2) else
Collatz予想のRubyによる実装と言い替え
LL Ringのキミならどう書く 2.0 ROUND 2だけど、昨日は別の言語で...
キミならどう書く 2.0 - ROUND 2 -
与えられた範囲の中でCollatz予想の収束までのステップ数が最大となる値を求める問題。とりあえず、Haskellで超素朴なコードで試してみたら「h 1000000」に40秒くらいかかった。
import List
g 1 = 1
g n = 1 + g (if even n then n `div` 2 else 3*n + 1)
h n = fst $ maximumBy c [(k, g k) | k <- [1..n]]
where c (_,x) (_,y) = x `compare` y
実行結果。
Main> h 100
97
Main> h 1000000
837799
以下のようにして100000までの値をテーブル化すると7秒まで縮んだ。
更に効率化するにはどうすれば良いだろう?
import List
import Array
tableMax = 100000
table = array (1, tableMax) [(i, g' i) | i <- [1..tableMax]]
g n = if n <= tableMax then table ! n else g' n
g' 1 = 1
g' n = 1 + g (if even n then n `div` 2 else 3*n + 1)
h n = fst $ maximumBy c [(k, g k) | k <- [1..n]]
where c (_,x) (_,y) = x `compare` y
LL2006 君ならどう書く ROUND2
Round2はCollatz予想というものらしい. で、早速 #!perl # ...
collatz予想 in Haskell (State and HashTable example)
http://ll.jus.or.jp/2006/blog/doukaku2 とりあえずこうかなあ。 ふつうすぎてつまらんので、State をつかって効率化を図ってみよう。 効率化の差は？ さすがに顕著に速い。ちなみに IntMap というのは、 Map に似て木構造を使って高速に索引可能な連想コンテナですが、キーには Int しか使えません。かわりに高速に動作するらしい。内部構造にはパトリシア木が使われているらしい。そんな感じのブツです。 IO を使った場合。 だいぶふつうの ...
Collatz予想 in Haskell (Stack Overflow回避)
昨日のものを使って、引数があまりに大きい(1000000 とか)ケースではスタックオーバフローになってしまった。 理由は2つある。第一に、 hState のケースなどだが、値が大きくなりすぎて Int がオーバフローしてしまい負値になり、 g の計算がおかしくなってしまう場合。こういう場合には IntMap を使うことができない。あるいは maxBound までは IntMap を使い、それ以外の場合には計算結果を保持しないようにするべきか……。 第二の理由は、 maximum の評価が lazy ...
Collatz予想(Mathematica, Lisp)
f[1] = 1; f[n_?EvenQ] := Hold[f[n/2]]; f...
Collatz 予想
キミならどう書く 2.0 - ROUND 2 - が発表されました。前回の問題「100までの整数から素数を列挙せよ」にもPerl で答えたので、今回も Perl で自分なりに挑戦してみます。(^_^) ちょっと長いですが、以下問題の引用です。 Collatz予想の収束までのステップ数の最大値を求め
Collatz予想(MySQL)
WHILE EXISTS (SELECT * FROM integers WHE...
LL2006 君ならどう書く ROUND2 C++編
これのC++版です。LLじゃないけど 特に変わったことはしてないけど、 h(10...
Collatz予想 in Haskell 別解 (逆に展開する編)
逆に考えてみた。 Collatz 予想というのは、ようするに f は最終的に 1 になるっていうことだ。ということはその前に 2 がある。その前には 4 で、さらにその前は 8。その前は 16 。その前は 5 か 32。……という風にずーっと展開していくことができる。 この結果、1〜nまでのすべての整数が登場したときに打ち切ったとする。すると、最後に出てきた数がまさに求める k の値であるはずだ。 これを次のように書く。 ここで 1, 2, 4 を特別扱いしているのは、 4 から 1 も出てき ...
LLR2006 - Collatz予想は113383に気をつけろ!
いつの魔にRound 2がはじまっている。
キミならどう書く 2.0 - ROUND 2 - ? Lightweight Language Ringお題は「Collatz予想」（角谷予想，3x+1問題）についての問題です．
[中略]
また，余力のある者は大きな n についても h(n) を求めよ．
これまたtrivialな問....
Pythonで75文字でCollatz角谷問題の(以下略
f = lambda x: x == 2 and 1 or f(x % 2 an...
Pythonで75文字でCollatz角谷問題の(以下略
f = lambda x: x == 2 and 1 or f(x % 2 an...
[Program][D] Collatz 予想を D _インタプリタ_ で
例のごとくコンパイルエラーで結果出力ですが、なるべくすなおーに書いてみました。 D のコンパイル時プログラミングはなかなか悪くないとわかるのではないでしょうか。 template g(int n) { const int result = n; static if (n == 1) { const int step = 1; } else static
Collatz 予想
キミならどう書く 2.0 - ROUND 2 - について。 いきなり br...
[プログラミング][Haskell]キミならどう書く 2.0 - ROUND 2 -
日記のネタによさげなものがあったので書いてみる。 とりあえず何も考えずに書いてみたバージョン。 import System import List main = do args <- getArgs print $ h $ read (head args) h :: Int -> Int h n = let gs = concatMap (￥x -> [g(x)]) [1 .. n] in ca
[Squeak][Smalltalk] 「Collatz予想」（角谷予想，3x+1問題）のお題を Squeak の Smalltalk で
キミならどう書く 2.0 - ROUND 2 - ― Lightweight Language Ring を受けて。 前回、いろいろな（変なｗ）言語でたくさん書き散らかしてしまったのを反省して、今回は、知らない人でも Smalltalk がどんな言語だかが分かるように、オーソドックスなのをひとつだけ。 クラス
[Python][Programming]どう書く2
参考： キミならどう書く 2.0 - ROUND 2 - — Lightweight Language Ring 取り敢えず、まずはシンプルに。 Collatz予想(角谷予想) #! /usr/bin/python def g(i, r): r = r + 1 if i == 1: return r if i % 2 == 0: return g(i / 2, r) if i % 2 == 1: return g(3 *
LLR2006: HaskellでCollatz予想に挑戦
お待たせしました！ キミならどう書く 2.0 ROUND 2の開催です！！ 今回のLL Ringでは「LLで関数プログラミング」のセッションをはじめとし，関数型言語の活躍が期待されます．そこで，前哨戦にも関数型のお題を用意しました． お題は「Collatz予想」（角谷予想，3x+1問題）
LLR2006 - まだまだいくよ〜
Round 2、まだまだ続く。
キミならどう書く 2.0 - ROUND 2 - ? Lightweight Language Ring
このとき
h(n) = k, 1 ≦ k ≦ n ∧ g(k) = max (g(1),g(2),…,g(n))
について h(100) を求めよ．
[OCaml]せっかくなので
http://ll.jus.or.jp/2006/blog/doukaku2 1回目はずいぶんベタだったが、2回目もなんかあんまり違いの出なさそうなお題がでるなぁと。 まだ、OCaml な回答を書いている人がすくなさそうなので。というほど気の利いたプログラムを書いたわけじゃありませんが。それにしても、
キミならどう書く
さて、LightweightLanguageLingからのお題、「キミならどう書く」が話題になっているので載ってみることに。今回はコラッツ予想に関連した問題だが、特に数学的な知識が必要なわけではない。 問題文はこちら。 http://ll.jus.or.jp/2006/blog/doukaku2 まずはHaskellでその
[Squeak][Smalltalk] 「Collatz予想」（角谷予想，3x+1問題）のお題を AspectS で
前回、いろんな変な処理系で書き散らかしてしまったのを反省したつもりだったのですが…。つい、また。ｗ f の定義を記述してから、同じような g を、しかし、今度はステップ数を出力するように再び記述するのは何か違うよな…と感じて思い出したのはアスペクト指向です。ま
[理系ネタ][J] 3n+1 問題
http://ll.jus.or.jp/2006/blog/doukaku2 あ、これ去年某大学の並列計算の講義でネタにしました。簡単な整数演算を大量にやって何か面白いことが出来る話の一つとして、2CH のトリップや/etc/passwd のクラックなどと共に紹介しました。 高速化の方法として考えられるのは、
[Python Memo]「Collatz予想」（角谷予想，3x+1問題）
「Collatz予想」（角谷予想，3x+1問題）についての問題ですか。初耳です。Pythonで参加したいと思います。 Lightweight Language Ring : キミならどう書く 2.0 - ROUND 2 - となり， f(n) の呼出は8回である．これをステップ数と呼ぶことにする． ここで f(n) が 1 になるま
Collatz予想
LLRingのお題ROUND2。 javascriptで書いてみました。「短く」とか「エレガントに」とか「javascriptっぽく」とかは全く意識していません。ポイントは…とくにないかな。トラックバックは…まだやめときます。応募者数が増えてきたらするかも。やってみました(7/13 6:30)。恥
h(4294967295) = 2610744987 where g = 1051
itaさんの追記を読んでいたら、私も行き着くところまで行きたくなった。
キミならどう書く 2.0 - ROUND 2 - ? Lightweight Language Ring
このとき
h(n) = k, 1 ≦ k ≦ n ∧ g(k) = max (g(1),g(2),…,g(n))
について h(100) を求めよ．
JGeek Log - 3n+1 問...
[D言語] Collatz予想
キミならどう書く 2.0 - ROUND 2 - private import std.stdio; template f(uint t){ static if(t==1) const uint f=1; else static if(t%2==0) const uint f=f!(t/2)+1; else const uint f=f!(t*3+1)+1; } template max(uint i,uint n){ static if(i>n) const uint max=i
[プログラミング]Concurrent Clean : L.L.Ring : Collatz予想の収束問題 : メモ化
せっかくなので、メモ化もしてみる。 先に作った構造をそのまま残したまま、関数 y をメモ化版に書き換える方針で。 まず、再掲。 f` y = y \e f n = if (n==1) (e 1) if (isEven n) (f (n/2)) (f (3*n+1)) g = f` y where y p = let q n = 1 + (p (const 0) q n) i
[プログラミング]コラッツ逆展開
http://ll.jus.or.jp/2006/blog/doukaku2 の話。3回目。 g:haskell:id:jmk:20060712:1152721034 でやっていた逆展開を私もやってみる。 ただし、そのまんまやると h(100)の計算が終わらないようなので、終わるように工夫して： def collatz( n ) done=3 # 1,2,4 は計算済み
[理系ネタ][J] 3n+1 問題：まだまだ高速化
http://ll.jus.or.jp/2006/blog/doukaku2 記号 g(k):k からスタートして1に行くステップ数 G(n): max g(k) h(n): g(k)=G(n)となる k 定理：2 h(n) ＞ n 証明：2 h(n) ≦ n とすると、2 h(n) から 1+G(n)ステップで1に行くので、g(2h(n)) ＞G(n) で最大値の定義に反する。 高
PythonとXML-RPCとグラフ可視化ソフトGRINEditを使ったCollatz角谷問題の計算ステップが最大になる数の求め方
GRINEditを使って解いてみました。 Flashで動画にしたのでこちらをご...
キミならどう書く Scheme編
「キミならどう書く」の問題。 http://ll.jus.or.jp/2006/blog/doukaku2 先日はC++で書いたわけだが、今回はScheme版を考えてみた。ハッシュテーブルはGaucheの拡張を使っている。メモ化関数が汎用的でない形に変形せざるを得なかったのが多少残念だが、分離できただけでも
キミならどう書く 2.0 - ROUND 2 - 「collatz問題」(第1回)
http://ll.jus.or.jp/2006/blog/doukaku2 まぁなぜか関数型言語に触れられているので、ひとまず、gをCPS変換することで実装することを考える。実装言語はML。実際に使った処理系はSML.NET。
[数学][プログラミング]Collatz算法 ステップ数
[http://ll.jus.or.jp/2006/blog/doukaku2:title] [d:id:shinichiro_h]さん経由。 オフにしていたはずでしたが、メールチェックの隙に覗いてみたら、なにやら面白そうな問題を発見。 有名なコラッツ算法(コラッツ予想、3n+1予想とも)に関するもので、コラッツ算法とは、 任意の自然数nについて、 (1)nが偶数ならn/2 (2)奇数なら3n+1 を繰り返していくと、必ず1になる。 と言うものです。 一見簡単に見える問題ですが、実はまだだれも証 ...
[scheme] Collatz 予想 (キミならどう書く 2.0 - ROUND 2 -)
時間ができたので考えてみた。そのまま素直に書いてみた。 #!/usr/bin/env gosh (define (g n) (define (f n step) (cond ((= n 1) step) ((even? n) (f (/ n 2) (+ step 1))) ((odd? n) (f (+ (* n 3) 1) (+ step 1))))) (f n 1)) (define (h n) (let loop ((i 1) (k 1
Collatz 予想 - ピタゴラ機械もどき版
前回の素数列挙 OpenGL 版に引続き，「Collatz 予想の h(n) を求めるピタゴラ機械もどき」という色物ネタを考えていたのだが，時間がないのと，いざ実装しようと思うとあまり面白くなさそうだったのでやめた．そのうち気が向いたら書くかも．
Colla*tz*予想ね。人名間違えるのはよくない。
AUさん，ご指摘ありがとうございます．
修正させていただきました．
Haskellで解いてみました。
http://study-func-prog.blogspot.com/2006/07/haskell-ll-ring-round-2.html
またトラックバックを2つ送ってしまいました。すみません。
http://www.nishiohirokazu.org/blog/2006/07/python75collatz.html
こちらの記事にSchemeでdefineを使わずに166文字で書くバージョンを追加しました。
そろそろ 1 週間経過するので私も awk で書いておきます。
http://gauc.no-ip.org/wiki.cgi/private?page=Blog%2F2006%2D7%2D16#p1
関数型言語どころかそもそもプログラム言語ですらないマクロプロセッサ m4 で書いてみたです。
http://ya.maya.st/d/200607b.html#s20060716_2