You are here: Home Blog Categories キミならどう書く2.0

Personal tools

Document Actions

キミならどう書く2.0

Up one level

Document Actions

キミならどう書く 2.0 - ROUND 1 -

by takano32 posted at 2006-06-16 18:00 last modified 2006-06-27 00:57
LL Ring の前哨戦として「キミならどう書く 2.0」の開催です!

今回は読者も参加しての大乱闘!!

お題は「100までの整数から素数を列挙せよ」です.

ぜひ,みなさんの解答をコメントやトラックバックでお寄せください!

解答の締切は6月26日(月)とします.締切後には投票による人気の集計を行います.

Re:キミならどう書く 2.0 - ROUND 1 -

Posted by mrwk at 2006-06-16 18:30

print "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97";

問題: これを期待通りに実行できる言語をあげよ。
解答例: Perl, Ruby, Python, AWK

Re:キミならどう書く 2.0 - ROUND 1 -

Posted by Anonymous User at 2006-06-16 18:47

def primegen(maximum):
v = range(2, maximum)
while v:
p = v[0]
v = filter(int(p).__rmod__, v)
yield p

Re:キミならどう書く 2.0 - ROUND 1 -

Posted by Anonymous User at 2006-06-16 18:50

# grrr, 圧倒的にPythonに不利な設定ですね!
def primegen(maximum):
 v = range(2, maximum)
 while v:
  p = v[0]
  v = filter(int(p).__rmod__, v)
  yield p

Re: キミならどう書く 2.0 - ROUND 1 -

Posted by Dubhead at 2006-06-16 19:02

Pythonで、スライスと集合をむりやり使ってみる

MAX = 100 + 1

multiples = []
for n in range(2, MAX):
  multiples.extend(range(0, MAX)[2*n:MAX:n])
print set(range(2, MAX)) - set(multiples)

Re:キミならどう書く 2.0 - ROUND 1 -

Posted by Anonymous User at 2006-06-16 23:57

Pythonです。。
[p for p in range(2,100) if 0 not in [p%d for d in range(2,p)]]

Re:キミならどう書く 2.0 - ROUND 1 -

Posted by nobsun at 2006-06-17 01:58

sieve (p:ps) = p:sieve [q|q<-ps,q`mod`p/=0]
take 100 $ sieve [2..]

100までの素数@C++テンプレート

Posted by MZK at 2006-06-17 04:01

面白そうなのでついカッとなってC++テンプレートで書いてみました。
コードが長くなってしまったので自分のページの↓のURLに置いておきます。
http://www.3jikai.to/mzk/junk/prime.cpp

C++はLLじゃないと言われそうだけど、
実行がLightWeightなバイナリを吐けるLanguage
ということで勘弁してください。

Re:キミならどう書く 2.0 - ROUND 1 -

Posted by shiro at 2006-06-17 04:37

Gaucheで。

(use srfi-42)
(list-ec(: n 2 101)(if(not(any?-ec(: j 2 n)(zero?(modulo n j)))))n)

Oracle の PL/SQL でやってみました。

Posted by はやまった at 2006-06-17 08:58

トラックバックできないので、コメントにて失礼

http://nyaos.org/d/?p=(2006.06.17)

あえて、LL でない言語で挑戦。その分、ひねり成分不足

x86アセンブラ版

Posted by koguro at 2006-06-17 12:57

ある意味最も軽量な言語であるアセンブラで書いてみました。以下のURLからソースを取得できます(Linux, FreeBSD, MacOSXで確認)。
http://homepage.mac.com/naoki.koguro/prog/prime.s

なお、コンパイルは
% gcc -o prime prime.s
として、実行確認はgdbを使って
% gdb prime
(gdb) break b
(gdb) run
(gdb) x/100bd &amp;prime
としてください。

Re:キミならどう書く 2.0 - ROUND 1 -

Posted by Rocco at 2006-06-18 00:29

小飼さんのところの以下のページを参考に awk で記述してみました。
http://blog.livedoor.jp/dankogai/archives/50534572.html
長いので、以下の URL に速度比較も含めて書きました。
http://gauc.no-ip.org/wiki.cgi/private?page=Blog%2F2006%2D6%2D17

Re:キミならどう書く 2.0 - ROUND 1 -

Posted by Anonymous User at 2006-06-18 05:58

昔ながらのBASICで。
すぐに使える実行環境が無いので机上デバッグしかしていません。
10 'SAVE "PRIME.BAS"
20 DIM A(100):I=2
30 FOR P=I*2 TO 100 STEP I:A(P)=1:NEXT P
40 I=I+1:IF I=101 THEN GOTO 60
50 IF A(I)=0 THEN GOTO 30 ELSE GOTO 40
60 FOR I=2 TO 100
70 IF A(I)=0 THEN PRINT I," ";
80 NEXT I

Re:キミならどう書く 2.0 - ROUND 1 -

Posted by みずしま at 2006-06-18 18:46

間違って、トラックバックを2回送ってしまいました。すみません。

shスクリプト

Posted by maeda at 2006-06-19 01:18
#!/bin/sh

filter() { read p && ( echo $p; awk "\$1 % $p != 0" | filter ) }

seq 2 100 | filter

#seqやawkを使うのはズルかもしれませんが、どうせshだとexprやtestも外部コマンドなわけだし...
#zshやbashの拡張機能を使うのと同程度のズルですよね。

効率無視

Posted by [1..100]>>=pen at 2006-06-19 16:59

filter (\x -> (product [1..x-1]+1) `mod` x == 0) [2..100]

なるほど!じゃあPythonで

Posted by Anonymous User at 2006-06-19 22:52

filter(lambda i:reduce(lambda x,y: x*(i%y), range(2,i), 1), range(2, 100))

Re:キミならどう書く 2.0 - ROUND 1 -

Posted by NANRI at 2006-06-21 23:45

lispの解が少ないので、Common Lispで。
xyzzyでも動作します。
(defun loop-generate-primes (n)
"ループ版"
(let ((prime '()))
(push 2 prime)
(do ((x 3 (+ x 2)))
((> x n))
(if (dolist (i prime t) (if (zerop (rem x i)) (return nil)))
(push x prime)))
(nreverse prime)))

(defun recursive-generate-primes (limit)
"再帰版"
(labels ((check (x prime)
(cond ((endp prime)
t)
((zerop (rem x (car prime)))
nil)
(t
(check x (cdr prime)))))
(main (n x prime)
(cond ((> x n)
(nreverse prime))
((check x prime)
(main n (+ x 2) (cons x prime)))
(t
(main n (+ x 2) prime)))))
(main limit 3 (list 2))))

ワンライナー@シェルスクリプト

Posted by Anonymous User at 2006-06-22 00:02

エラトステネスの篩のようなもので非効率的に素数を列挙します
n=100;for i in `seq 2 $n`;do for j in `seq $i $i $n`;do echo $j;done;done|sort -n|uniq -c|egrep '^ *1[^0-9]'|sed 's/.*[ \t]//'|xargs printf '%d ';echo ''

効率無視PHP版

Posted by [1..100]>>=pen at 2006-06-22 12:19

効率無視 Haskell版と同じくウィルソンの定理を使った PHP版
for ($i = 2; $i <= 100; $i++) if (gmp_mod(gmp_fact($i-1), $i) == $i-1) echo "$i\n";

Re:キミならどう書く 2.0 - ROUND 1 -

Posted by Takumi Iino at 2006-06-23 02:04

gaucheの遅延ストリームでオーソドックスふるいをつかって。
長い。
(use util.stream)
(define ones (stream-cons 1 ones))
(define (add-streams s1 s2) (stream-map + s1 s2))
(define integer (stream-cons 1 (add-streams ones integer)))
(define prime-stream
(let loop ((primes (stream-cdr integer)))
(stream-cons (stream-car primes)
(loop
(stream-filter
(lambda (x)
(not (= (remainder x (stream-car primes)) 0)))
primes)))))
(let loop ((stream prime-stream))
(if (> 100 (stream-car stream))
(cons (stream-car stream) (loop (stream-cdr stream)))
'()))

Re:キミならどう書く 2.0 - ROUND 1 -

Posted by Anonymous User at 2006-06-23 10:17

javaで作成してみました。
public static void main(String[] args) {
int[] s = new int[100];
int x = 0;
boolean bool = false;
for(int i = 1; i <= 100; i ++) {
bool = false;
for (int k = 0; k < x; k++) {
if (i % s[k] == 0 && s[k] != 1) {
bool = true;
break;
}
}
if (!bool) {
s[x++] = i;
System.out.println(i);
}
}
}

シェルで 1-liner

Posted by macks at 2006-06-23 23:43

seq 2 100 | factor | awk 'NF == 2 {print $2}'
# 短さで勝負。GNU coreutils + awk を使用。

マイナー過ぎるか

Posted by Anonymous User at 2006-06-26 18:04

-- Lua
a={}
for i = 2, math.sqrt(100), 1 do
for j = i + i, 99, i do
a[j] = 1
end
end
for i = 2, 99, 1 do
if not a[i] then
print(i)
end
end

m4

Posted by yamaya at 2006-06-26 23:52

m4 で書いてみたです。
http://ya.maya.st/d/200606c.html#s20060626_1

Pythonのジェネレータを使って素数を求める

Posted by TRIVIAL TECHNOLOGIES 2.0 at 2006-06-16 18:53
Python 2.3から(だったっけな?)導入された「ジェネレータ関数」を使って素数を求めてみましょう。 >>> def primegen(x=2): # 素数を返すジェネレータ関数を定義 ... while True:...

perl - 100までの素数

Posted by 404 Blog Not Found at 2006-06-16 22:02
なに前哨戦とな? キミならどう書く 2.0 - ROUND 1 - ? Lightweight Language Ringお題は「100までの整数から素数を列挙せよ」です.

[プログラミング]Concurrent Clean : L.L.Ring : 『キミならどう書く 2.0 - ROUND 1 -』 : 100までの素数を列挙

Posted by lethevert is a programmer at 2006-06-16 23:46
module Primes import StdEnv, OptEnv Start = takeWhile ((>=) 100) primes primes = ps [2..] where ps [n:nr] = [n: ps $ filter (\x = (x rem n) <> 0) nr] たしか、もっとスマートな方法があったような気がするんだけど・・・

エラトステネスのふるい @ Ruby

Posted by 32nd diary at 2006-06-16 23:48
コンセプトは「人と同じ動き」です. 人が紙に書いてエラトステネスのふるいで解いていくのと同じ流れのコードとなっています.

キミならどう書く 2.0 - ROUND 1 -

Posted by mputの日記。 at 2006-06-17 00:26
100までではちょっと上が小さすぎる。「最初の1,000,000個」とかに変更すべき。ここまで大きければHaskellでも素朴なsieveでは表示できなくなる(sieveはやがてメモリを喰い尽くして止まる。やってみればわかる)ので、腕の見せ所となる。

100までの素数@ruby

Posted by 青方偏移 at 2006-06-17 00:52
なにやら面白そうな企画が開催されているようなので、乱入。「100までの素数を列挙するコードを書くべし」だそうです。とりあえずRubyを使って書いてみました。 def generate_prime_numbers(max) (2..max).inject([]) do |list, n| append_if_prime(list, n) end e..

「100までの整数から素数を列挙せよ」

Posted by znzの日記 at 2006-06-17 02:02
http://ll.jus.or.jp/2006/blog/doukaku1 に「キミならどう書く 2.0 - ROUND 1 -」として「100までの整数から素数を列挙せよ」というお題が出ている。 ちゃんと計算するのは面倒なので「0ruby -r mathn -e '(1..100).select{|x|x.prime_division.size == 1}.join(" ").display'」で。 最初は1からではなく0からにしていたら、「0.prime_division」がかえってこなくて悩んでし ...

素数探索@Ruby

Posted by はてなるせだいあり at 2006-06-17 03:44
キミならどう書く 2.0 - ROUND 1 -にて、「100までの整数から素数を列挙せよ」とのお題。 (2..100).select{|i|(2...i).all?{|j|i%j!=0}} とりあえず効率無視で短さ重視。 (2..100).select{|i|/^(11+)\1+$/!~'1'*i} と思ったら、perl - 100までの素数 にある

[Squeak][Smalltalk] 100までの整数から素数を列挙せよ…を Squeak の Smalltalk で

Posted by sumim’s smalltalking-tos at 2006-06-17 03:49
「100までの整数から素数を列挙せよ」:キミならどう書く 2.0 - ROUND 1 - ― Lightweight Language Ring まずはお約束から。 Integer primesUpTo: 100 #(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97) 愚直に。 (2 to: 10) collect: [:nn | (2

エラトステネス/フェルマーテスト

Posted by FlexFrank at 2006-06-17 04:26
LL Gong キミならどう書く 2.0 - ROUND 1 - 100までの素数列挙. 正攻法だとエラトステネスの篩いを使ってこんな感じ.

LLR2006 - 1,000,000(番目|まで)の素数

Posted by 404 Blog Not Found at 2006-06-17 07:15
キミならどう書く 2.0 - ROUND 1 - ? Lightweight Language Ringお題は「100までの整数から素数を列挙せよ」です. に対して mputの日記。 - キミならどう書く 2.0 - ROUND 1 -100までではちょっと上が小さすぎる。「最初の1,000,000個」とかに変更すべき。ここまで....

[LL]キミならどう書く 2.0 - ROUND 1 6月26日(月)締切

Posted by はてなの日記 Akira51 at 2006-06-17 08:43
いい感じでRSSからお題が送られてきました。(この記事は6/25(日)まで更新し続けます。) LL Ring の前哨戦として「キミならどう書く 2.0」の開催 お題は「100までの整数から素数を列挙せよ」です. 解答の締切は6月26日(月)とします.締切後には投票による人気の集計を行

Ruby標準添付ライブラリ - LL Ring

Posted by ratio - rational - irrational at 2006-06-17 08:47
まずは、日本Rubyカンファレンス2006でネタにした関係上、お約束のやつだけ...

[ruby] キミならどう書く 2.0 - ROUND 1 -

Posted by moroの日記 at 2006-06-17 10:13
お題は「100までの整数から素数を列挙せよ」。 via Yuguiさんとこ Rails厨の回答。 #!/usr/bin/env ruby require_gem 'activesupport' require 'active_support' class Fixnum def prime? return false if 1 == self (2..self - 1).all?{|i| (self % i) &#6

[PRO] Io で 100 までの素数を列挙

Posted by SiroKuroPage at 2006-06-17 12:33
お題は「100までの整数から素数を列挙せよ」です. ぜひ,みなさんの解答をコメントやトラックバックでお寄せください! キミならどう書く 2.0 - ROUND 1 - ? Lightweight Language Ring との事なので、力の差にしりごみしながらも参戦してみるテスト。 折角なので今勉強中

[OCaml] キミならどう書く 2.0 - ROUND 1 - &mdash; Lightweight Language Ring

Posted by soutaroにっき at 2006-06-17 12:34
お題は「100までの整数から素数を列挙せよ」です. MLならループ使ってなんぼでしょう。 愚直に。 # exception NotPrime;; exception NotPrime # begin for i = 2 to 100 do try for j = 2 to i / 2 do if i mod j = 0 then raise NotPrime done; Printf.printf "%d &q

[programming] お題は「100までの整数から素数を列挙せよ」

http://ll.jus.or.jp/2006/blog/doukaku1 にて,「キミならどう書く 2.0」というプログラミングスキルを競うコンテストが開催されているみたい.お題は「100までの整数から素数を列挙せよ」.面白そう. とはいえ,100までの素数なんて25個しかないのだから,いちいち計算せ

キミならどう書く 2.0 - ROUND 1 -

Posted by 本当にオタクでも山へ登れるのか? at 2006-06-17 16:02
コンセプトは「人と同じ動き」です.人が紙に書いてエラトステネスのふるいで解いていくのと同じ流れのコードとなっています. エラトステネスのふるい @ Ruby - 32nd diary (2006-06-16) コンセプトは「人と同じ動き」です.人がググって検索上位のサイトを見てみるのと同

[Smalltalk][OOPL] 100までの整数から素数を列挙せよ…を Smalltalk-76 で

Posted by sumim’s smalltalking-tos at 2006-06-17 16:16
1977 年から、時空を越えてのエントリー。w ”Smalltalk-76” limit ← 100. primes ← #() asStream. primes next ← 2. for% i from: (3 to: limit by: 2) do% [ isprime ← true. for% prime from: primes contents do% [ i ¥ prime = 0 ? [isprime ← false]]. ispri

[Ruby] キミならどう書く 2.0 - ROUND 1 -

Posted by Hexaの日記 at 2006-06-17 16:27
LL Ringの前哨戦の「お題」がでていたので, 昔,勉強したフェルマーテストを使って,やってみました. a = 2 max = 100 range = Range.new(a, max) range.each{|num| if(a == num) then print num, " " elsif(1 == (a **(num - 1) % num)) then print nu

100 までの素数を列挙 in JavaScript

Posted by Days on the Moon at 2006-06-17 16:40
「キミならどう書く 2.0 - ROUND 1 - ― Lightweight Language Ring」より。せっかくなので JavaScript 1.7 の新機能である Generator を使って書いてみる。 function countUp(n) { n = n || 0; while (true) yield

素数列をつくろう

Posted by 他人のHaskell日記 at 2006-06-17 21:42
http://ll.jus.or.jp/2006/blog/doukaku1 面白そうなのでミラーテストバージョンを書いてみました http://www.faireal.net/articles/7/03/#d30129 このサイトを参考にしました。 実行結果

[プログラミング]Concurrent Clean : L.L.Ring : キミならどう書く 2.0 - ROUND 1 - 番外編:1,000,000個めの素数

Posted by lethevert is a programmer at 2006-06-17 22:10
チューニングとはCleanのための言葉です!! かどうかは知りませんが、Cleanは、Haskellとは違ってプログラムを効率化するテクニックが多いので、数が多くなっても平気。 もともとの関数定義はこれ。 nth_prime n = primes !! n primes = map hd $ iterate f [2..] where f

[PRO] WhiteSpace でも 100 までの素数を列挙

Posted by SiroKuroPage at 2006-06-18 01:23
「100までの整数から素数を列挙せよ」から色々な人のコードを見ていたら、 brainfuckやwhitespaceで作る人が出てこないかな. 他人のHaskell日記 なんてことを言っている人を発見。 了解です。できましたヽ(≧∀≦)ノ prime.ws 実行結果 $ perl whitespace.pl prime.ws 2 3 5

シェルで素数の列挙

Posted by memolog at 2006-06-18 03:59
こ、これはシェルでやるしかないでしょうってことでやってみた。

[IT]キミならどう書く 2.0 ROUND 1

Posted by kkkkkkkk at 2006-06-18 05:54
お題は「100までの整数から素数を列挙せよ」です. キミならどう書く 2.0 - ROUND 1 - Lightweight Language Ring 世のビジネスシーンで最も多用されているアプリケーションの1つであるExcelのVBAマクロで書いてみよう。 Sub PrimeNum() Dim SUP As Integer: SUP = Cells(1,

[LL]キミならどう書く 2.0 - ROUND 1 6月26日(月)締切

Posted by はてなの日記 Akira51 at 2006-06-18 11:32
いい感じでRSSからお題が送られてきました。(この記事は6/25(日)まで更新し続けます。) LL Ring の前哨戦として「キミならどう書く 2.0」の開催 お題は「100までの整数から素数を列挙せよ」です. 解答の締切は6月26日(月)とします.締切後には投票による人気の集計を行

[Squeak][Smalltalk] 100までの整数から素数を列挙せよ…を Smalltalk-72 で

Posted by sumim’s smalltalking-tos at 2006-06-18 13:28
悪ノリして、今度は 1974 年からのエントリー。 "limit _ 100. "primes _ stream of vector 1. primes _ 2. for i _ 3 to limit by 2 ("isprime _ true. "vec _ primes contents. for idx to vec length ("prime _ vec[idx]. (i mod prime) = 0? (

[プログラミング]Concurrent Clean : L.L.Ring : キミならどう書く 2.0 - ROUND 1 - 高速化編

Posted by lethevert is a programmer at 2006-06-18 14:24
id:lethevert:20060616:p2 : 素直な回答 id:lethevert:20060617:p1 : 頭部非ボックス化正格リスト id:lethevert:20060617:p2 : gccとの速度比較 ここまで、コードの外形には触れずにいましたが、コードの外形を変えて高速化してみましょう。 Start = last $ takeWhile ((&#6

javascriptで素数生成

Posted by Marble Screw at 2006-06-18 16:25
これをJavascriptで。 [http://ll.jus.or.jp/2006/blog/doukaku1:title] *アルゴリズム [g:素数判定 アルゴリズム]で探してみたけど、技術

[Groovy]キミならどう書く 2.0 - ROUND 1 -

Posted by Onion開発日記 at 2006-06-18 18:40
Groovyで書いてみた。まずはこんな感じのコード。 println ((2..100).findAll{x->(2..x/2).every{x%it!=0}}) しかし、実行してみると、何故か2が含まれない。 [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97] たぶん、範囲式の使い方が原因だろうということで、ちょっと調べてみる。 (2..1).each{println it} => 2 1 どうやら、(x .. y)で、x>yの場合は、空の範囲を生成するのではなく、x, x-1,x-2,...,yの範囲を生成するようだ。しかも、Groovyの公式ページのドキュメントを見ても、この仕様に関するきちんとした記述が見当たらないorz 仕方無いので、内側のループは2..x/2ではなく、2...xにすることにした。 println ((2..100).findAll{x->(2...x).every{x%it!=0}}) 今度は、ちゃんと2も出力されるようになった。 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

[Groovy]キミならどう書く 2.0 - ROUND 1 -

Posted by Onion開発日記 at 2006-06-18 18:40
Groovyで書いてみた。まずはこんな感じのコード。 println ((2..100).findAll{x->(2..x/2).every{x%it!=0}}) しかし、実行してみると、何故か2が含まれない。 [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97] たぶん、範囲式の使い方が原因だろうということで、ちょっと調べてみる。 (2..1).each{println it} => 2 1 どうやら、(x .. y)で、x>yの場合は、空の範囲を生成するのではなく、x, x-1,x-2,...,yの範囲を生成するようだ。しかも、Groovyの公式ページのドキュメントを見ても、この仕様に関するきちんとした記述が見当たらないorz 仕方無いので、内側のループは2..x/2ではなく、2...xにすることにした。 println ((2..100).findAll{x->(2...x).every{x%it!=0}}) 今度は、ちゃんと2も出力されるようになった。 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

100までの素数を求める

Posted by T::Yok..... at 2006-06-18 20:56
キミならどう書く 2.0 - ROUND 1面白そうなので参加。ハッシュを使ってみた。my $num = 100;my %a = map {$_, 1} 2..$num; for my $m (2..($num / 2)) { for my $n ($m..$num) {...

上限を決めずに素数を生成(JavaScript版)

Posted by メモ at 2006-06-19 05:18
JavaScriptでも書いてみた。

LL2006 君ならどう書く

Posted by FloralCompany.log at 2006-06-19 15:29
LL2006の、「君ならどう書く」の読者参加版ができていた。 お題は 「100ま...

[Ruby] 100までの整数から素数を列挙せよ

Posted by miyamukoの日記 at 2006-06-19 15:55
お題は「100までの整数から素数を列挙せよ」です. 手垢がついた手法だと思うけど、Google 電卓で計算してみた。 ほんとは はてなのスーパー pre 記法拡張を使ってみたかっただけ。

[Squeak][Smalltalk][OOPL] エラトステネスのふるいをコンパクトにする方法

Posted by sumim’s smalltalking-tos at 2006-06-19 17:13
素数を列挙するにあたって、エラトステネスのふるいは比較的高速で、たとえば、404 Blog Not Found:LLR2006 - 1,000,000(番目|まで)の素数 で、いくつかの言語で例示されているのとほぼ同じことをする Squeak を使った Smalltalk の次のコード… [ | max primes isPrime | m

エラトステネスの篩の改良

Posted by はてなるせだいあり at 2006-06-19 22:28
上のソースでは探索範囲1つにつき true/false を作るので、1億まで探索しようと思うとかなりのメモリが必要となる。どうせ真偽値なのだから、BitArray を用いれば候補一つにつき 1bit で済む。また、偶数はどうせ素数ではないので、奇数のみを探索対象にすることで、テーブ

正規表現で素数探索

Posted by はてなるせだいあり at 2006-06-19 22:31
def sieve_regex(max) table = ' ' + (2..max).map{|i|i.to_s}.join(' ') (2..Math.sqrt(max)).each do |i| 1 while table.gsub!(/^((?:\d* ){#{i-1}}(?:(?:\d* ){#{i}})+)\d+/){$1} end table end perl -le ’$,=” ”; print grep {

上限を決めずに素数を生成の高速化(Ruby版)

Posted by メモ at 2006-06-19 22:34
「上限を決めずに素数を生成」を高速化。

[技術]せっかくだから素数数えとくか

Posted by はこべにっき# at 2006-06-19 23:33
決して落ち着きを取り戻すためにやってるわけではない*1.キミならどう書く 2.0 - ROUND 1 -ネタ. Otsuneのなんでこれで素数判定できるかは、読者の宿題のエラトステネスのふるいがステキだったのでうちもふるいを使いたいと思った.で,せっかくだから一気にふるいをかけ

[tech]数を数えて落ち着くんだ(Pnuts編)

Posted by yojikのブログロ at 2006-06-20 01:26
キミならどう書く 2.0 Pnutsでできる限り簡潔、効率無視で書いてみた。 isPrim = function(p) {list(range(2,p)[function(d) p%d == 0]).size()==1} for(i: range(2, 100)[isPrim]) print(i,",") [実行結果]: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,

100までの整数から素数を列挙せよ(Mathematica)

Posted by inquisitor at 2006-06-20 10:30
キミならどう書く 2.0 - ROUND 1 -から Select[Range@...

100までの素数を求める[APL版]

Posted by T::Yok..... at 2006-06-20 14:17
キミならどう書く 2.0 - ROUND 1APL版も作成してみた。(ただし、このアルゴリズムは昔に本で読んだもので、僕が考えた訳ではない)1~Xまでの数列を...

100までの整数から素数を列挙せよ(LaTeX)

Posted by inquisitor at 2006-06-20 15:34
\documentclass{jarticle} \newif\ifprime ...

100までの整数から素数を列挙 in Io :-|

Posted by [CD]CoffeeDiary at 2006-06-20 19:12
キミならどう書く 2.0 - ROUND 1 - というものが開催されていたことに遅ればせながら気がついたので、 Ioの思い出しを兼ねてやってみた。 (HaskellとかJavaScriptはほかの人がやっていたし) 最も簡単なパターンは、出力しちゃうこと。(ズル)write("2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97")Ioではprintはオブジェクトへのメッセージなので、 こういう場合はwr...

キミならどう書く 2.0 - ROUND 1 - 100までの整数から素数を列挙せよ@AppleScript

Posted by ぐるりうぇぶ at 2006-06-21 01:14
キミならどう書く 2.0 - ROUND 1 -— Lightweight Language Ringより。やっぱり俺が書くならAppleScriptだろうてことで書いてみた。基本はエラトステネスの篩なんだが、AppleScriptでリストを扱うとき、追加するのは簡単だけど取り除くのが面倒くさい上に遅くなるし、100じゃなくもっと多いときは死ぬほど遅くなる(主に最初のリストを作る時点で)ので、『素数リストと探索リスト』ではなく『素数リストと除外リスト』を作り、素数リストの最大値の二乗が探索リストの最大値を超えたら、(素数リストの一番最後の数+1)〜100から除外リストにある数字を除外して終了。なんつーか素朴だなぁw

上限なしで素数生成(ML版)

Posted by メモ at 2006-06-21 05:33
さらに、ML(mosml)でやってみた。

100までの整数から素数を列挙せよ(XSL)

Posted by inquisitor at 2006-06-21 18:13
<?xml version="1.0" encoding="UTF-8" ...

[PHP]PHPな応募ないすね

Posted by Blog::koyhoge at 2006-06-22 02:39
キミならどう書く 2.0 - ROUND 1 - — Lightweight Language Ring でPHPな応募がない件について。(TB全部見てないので、もしあったらごめんなさい) ということでいっちょ書いてみました。 アルゴリズムに凝るのは苦手だし、ワンライナーは端からPHPに向いてないのであ

100までの素数を数えるサンプル

Posted by HotPHPPER News at 2006-06-22 12:41
PHPkoyhogeLightweight Language Ring100PHPkoyhogePHP5

[neta] FORTRANで書いて、100台のスパコンにそれぞれ自然数を割り振って、素数かどうかを判定させた結果を返してもらうというのはどうか

Posted by otsune's SnakeOil at 2006-06-22 14:02

PHPで素数判定

Posted by ハズレ日記 at 2006-06-22 14:06
LL Ring の前哨戦として「キミならどう書く 2.0」の開催です! 今回は...

100までの整数から素数を列挙せよ(SQL)

Posted by inquisitor at 2006-06-22 15:13
SELECT n as prime FROM( SELECT n,COUNT...

[Squeak] 100までの整数から素数を列挙せよ…を Squeak の eToys で

Posted by sumim’s smalltalking-tos at 2006-06-22 15:59
eToys でも id:squeaker さんの Kedama(毛玉)を使って書いてみました。Kedama は、端的には、複数のタートルを使って描くタートルグラフィックス・システムです。 Kedama: A massively-parallel tile-scriptable particle system Yamamoto さんのチュートリアルがわかりや

[Coding] 100までの素数@XQuery

declare function prime($i as xs:integer) as xs:boolean { every $div in (2 to $i - 1) satisfies $i mod $div != 0 }; for $i in (2 to 100) return if(prime($i)) then $i else () XQueryだとこんな感じでしょうか。しょぼーん(´・ω・`)

[OCaml] キミならどう書く 2.0 - ROUND 1 - (L.L.Ring)

Posted by jijixi's diary at 2006-06-22 19:59
スレッドを使ったネタバージョン (言語は OCaml)

1〜100までの素数表示

Posted by らんの日記 at 2006-06-23 23:41
http://ll.jus.or.jp/2006/blog/doukaku1 ary = (2..100).to_a ary.each do |m| ary.delete_if do |n| m != n && n % m == 0 end end p ary 参加資格とか特にないよね? 特に面白いのも思いつかず。既に誰かが書いてそうな気はしたけど(未確認)、書いてみた。

[PHP] 100までの素数

Posted by t_komuraの日記 at 2006-06-25 13:18
<?php $max = 100; $arr = range( 2, $max ); $end = sqrt( $max ); for ( $i = 2; $i < $end; ++$i ) { if ( in_array( $i, $arr ) ) { $arr = array_filter( $arr, create_function( '$v', 'return $v % ' . $i . ' || $v === ' . $i . &

[Ruby] キミならどう書く 2.0 - ROUND 1 -

Posted by Hexaの日記 at 2006-06-25 15:04
フェルマーテストに引き続き,エラトステネスの篩もやってみました. エラストテネスの篩では,検証する数の平方根まで比較すれば, 素数か非素数かの判定は十分といえます. prime = Array.new() max = 100 i = 2 while i <= max @flag = true prime.each{|num| if Mat

[Perl]100までの素数(mapと正規表現で)

Posted by akihitoの日記 at 2006-06-25 18:23
遅ればせながら参戦 for my $i (2..100) { my $n = join ",",map{$i%$_} 2..$i-1; if($n !~ /^0\,/ && $n !~ /\,0/){ print "$i \n"; } } mapと正規表現で作ってみました。

Javaで素数を100万個求める

Posted by minghaiの日記 at 2006-06-25 18:46
LL Ringの素数の話が盛り上がっている。 http://ll.jus.or.jp/2006/blog/doukaku1 Javaで参戦しようかと思ったがネタにも走れず、かといって短さにも走れず、速さだけなら前回のたらいの2番煎じになってしまう。 芸が無いので今回は見てるだけにしようと思った。 しかし色々

[prog] キミならどう書く 2.0 - ROUND 1 -

Posted by Greenbear Diary at 2006-06-25 23:57
Befungeで書いてみました。 >v >125*25*pv v < > v >25*25*g 1+:25*`| > v >:25*25*p >25*25*g + :55*4*`| ^ < ^ < >:::25*%\25*/p ^ >25*,@ ^ < v < >0>1+:55*4*`| v < > ^ >::25*%\25*/g 48*-| >:.v ^ < < yhara@cosmos:~/src/befunge % ./a.out primes.bf Befunge-93 Interpreter/Debugger v2.12 2 3 5 7 11 13 17 19 23 29 31 32 37 41 43 47 53 59 61 67 71 73 79 83 89 97 Befungeについては、こちらを参照。 自分で動かしてみたいという奇特な方は、http://quadium.net/funge/downloads/ から処理系(Cのソースコードと、Windows用EXE入り)を入手してください。

[Perl] 100までの素数 (キミならどう書く 2.0 - L.L. Ring)

Posted by 酒日記 はてな支店 at 2006-06-26 14:30
http://ll.jus.or.jp/2006/blog/doukaku1/ http://d.hatena.ne.jp/t-akihito/20060625/1151227410 LL Ring のチケット発売今日からだ。買ってこなくちゃ。 List::MoreUtils から all と before_incl を使って、リスト操作っぽく書いてみた。List::MoreUtils は標準モジュー

Brainf*ckで100までの素数を列挙してみるテスト

Posted by TAKESAKO @ Yet another Cybozu Labs at 2006-06-26 17:45
キミならどう書く 2.0 - ROUND 1 - LL Ring の前哨戦として...

[Perl][pugs] 100までの素数 Perl6 / pugs 版

Posted by 酒日記 はてな支店 at 2006-06-26 22:50
Perl6 (pugs) で動くようにしてみた。 #!/usr/bin/pugs my $max = @*ARGS.pop || 100; my @primes = (2); for (3..$max) -> $n { @primes.push($n) if @primes.before_incl:{ sqrt $n <= $_ }.all:{ $n % $_ }; } @primes.join(' ').say; sub all (@lis

キミならどう書く 2.0 - ROUND 1

Posted by 西尾泰和のブログ at 2006-06-26 23:42
おおっと、今知りました。(via 竹迫さん) キミならどう書く 2.0 - R...

キミならどう書く 2.0 - ROUND 1

Posted by 西尾泰和のブログ at 2006-06-26 23:56
Pythonでdefもifもwhileもforも使わずに1行(126文字)で作...

100までの素数(キミならどう書く 2.0 - ROUND 1 -)

Posted by 最近のちょっ得 at 2006-06-27 00:14
もう遅いか。うち着いたの45分ぐらいだもんな。。。 ルートnが必要だと思って、mathn.rb のヘルプ見たら、素数もあるじゃん。 あるものは使えばいいのさってことで、ヘルプそのまま。 require 'mathn' pp = Prime.new; pp.each {|x| break if x >...

キミならどう書く 2.0 - ROUND 1 - の解答を締め切りました

by takano32 posted at 2006-06-27 00:00 last modified 2006-06-27 01:00

キミならどう書く 2.0 - ROUND 1 - の解答を締め切りました.

現在,アンケートの準備とROUND 2の準備を進めています.

しばらくお待ちください.

The URL to Trackback this entry is:

キミならどう書く 2.0 - ROUND 1 - 人気投票

by takano32 posted at 2006-07-11 19:00 last modified 2006-07-11 17:59
LL Ringの前哨戦として開催させていただきました「キミならどう書く 2.0 - ROUND 1 -」は予想以上の盛り上がりを見せ,盛況のうちに終了しました.

みなさんのご回答,ありがとうございます.

このエントリでは集まったみなさんの回答について人気投票を行います!
  • 回答を一意に判別する都合上,URLごとの集計となりましたことをご了承ください.
  • 回答数が思いのほか多かったため,コメントのみの解答は一意に特定するのが困難であり,残念ながら人気投票の対象外とさせていただきましたことをお詫び申し上げます.
  • 人気投票の項目となる回答をされたい方はROUND 2以降ではURLのある形での回答をよろしくお願いします(トラックバックできない場合はコメント欄にURLを記述する形でも可).
  • 今回の人気投票の項目に含まれておらず,投票したい項目がある場合はコメント欄でその旨をお伝えください.対応させていただきます.

The URL to Trackback this entry is:

キミならどう書く 2.0 - ROUND 2 -

by takano32 posted at 2006-07-11 20:00 last modified 2006-07-25 14:07

お待たせしました!
キミならどう書く 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日(月)とさせていただきます.よろしくお願いします.

Re:キミならどう書く 2.0 - ROUND 2 -

Posted by Anonymous User at 2006-07-11 22:37

Colla*tz*予想ね。人名間違えるのはよくない。

Re:キミならどう書く 2.0 - ROUND 2 -

Posted by takano32 at 2006-07-12 01:35

AUさん,ご指摘ありがとうございます.
修正させていただきました.

Re:キミならどう書く 2.0 - ROUND 2 -

Posted by tmiya at 2006-07-12 02:49

Haskellで解いてみました。
http://study-func-prog.blogspot.com/2006/07/haskell-ll-ring-round-2.html

Re:キミならどう書く 2.0 - ROUND 2 -

Posted by 西尾 at 2006-07-13 14:46

またトラックバックを2つ送ってしまいました。すみません。
http://www.nishiohirokazu.org/blog/2006/07/python75collatz.html
こちらの記事にSchemeでdefineを使わずに166文字で書くバージョンを追加しました。

Re:キミならどう書く 2.0 - ROUND 2 -

Posted by Rocco at 2006-07-16 21:14

そろそろ 1 週間経過するので私も awk で書いておきます。
http://gauc.no-ip.org/wiki.cgi/private?page=Blog%2F2006%2D7%2D16#p1

m4

Posted by yamaya at 2006-07-17 02:16

関数型言語どころかそもそもプログラム言語ですらないマクロプロセッサ m4 で書いてみたです。
http://ya.maya.st/d/200607b.html#s20060716_2

[PHP]LL Ring[キミならどう書く 2.0 - ROUND 2 - ]がはじまっていた。

Posted by ゆどうふの湯豆腐ろぐ at 2006-07-12 00:03
http://ll.jus.or.jp/2006/blog/doukaku2 で、Collazt予想なるお題が出ていた。 ネットサーフ中に見つけたので、素人ながらも、ちょっとPHPで書いてみた。 問題設定に従って$n=100になっているけれど、$nを換えればいくらでも上まで行く。 <?php $n = 100; $max_count =

[プログラミング]コラッツ

Posted by [鍋]鍋あり谷あり at 2006-07-12 00:15
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数の最大値

Posted by ratio - rational - irrational at 2006-07-12 00:46
キミならどう書く 2.0 ROUND 2が出題された。なんか、Rubyの回答は...

[PRO] Io で Collatz 予想

Posted by SiroKuroPage at 2006-07-12 02:34
お題は「Collatz予想」についての問題です. 関数型言語でも,そうでない言語でも,ぜひ回答をお寄せください! キミならどう書く 2.0 - ROUND 2 - ? Lightweight Language Ring 例によって、Io で書くとこんな感じに。 collatz.io result := 0 max_step := 0 collatz := Ob

[ruby]Collatz予想の収束までのステップ数の最大値

Posted by sshi.Continual at 2006-07-12 04:47
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による実装と言い替え

Posted by ratio - rational - irrational at 2006-07-12 10:18
LL Ringのキミならどう書く 2.0 ROUND 2だけど、昨日は別の言語で...

キミならどう書く 2.0 - ROUND 2 -

Posted by ヒビルテ at 2006-07-12 11:37
与えられた範囲の中で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

Posted by FloralCompany.log at 2006-07-12 14:01
Round2はCollatz予想というものらしい. で、早速 #!perl # ...

collatz予想 in Haskell (State and HashTable example)

Posted by haskellのある暮らし at 2006-07-12 15:10
http://ll.jus.or.jp/2006/blog/doukaku2 とりあえずこうかなあ。 ふつうすぎてつまらんので、State をつかって効率化を図ってみよう。 効率化の差は? さすがに顕著に速い。ちなみに IntMap というのは、 Map に似て木構造を使って高速に索引可能な連想コンテナですが、キーには Int しか使えません。かわりに高速に動作するらしい。内部構造にはパトリシア木が使われているらしい。そんな感じのブツです。 IO を使った場合。 だいぶふつうの ...

Collatz予想 in Haskell (Stack Overflow回避)

Posted by haskellのある暮らし at 2006-07-12 15:11
昨日のものを使って、引数があまりに大きい(1000000 とか)ケースではスタックオーバフローになってしまった。 理由は2つある。第一に、 hState のケースなどだが、値が大きくなりすぎて Int がオーバフローしてしまい負値になり、 g の計算がおかしくなってしまう場合。こういう場合には IntMap を使うことができない。あるいは maxBound までは IntMap を使い、それ以外の場合には計算結果を保持しないようにするべきか……。 第二の理由は、 maximum の評価が lazy ...

Collatz予想(Mathematica, Lisp)

Posted by inquisitor at 2006-07-13 00:02
f[1] = 1; f[n_?EvenQ] := Hold[f[n/2]]; f...

Collatz 予想

Posted by ぱるも日記 at 2006-07-13 00:05
キミならどう書く 2.0 - ROUND 2 - が発表されました。前回の問題「100までの整数から素数を列挙せよ」にもPerl で答えたので、今回も Perl で自分なりに挑戦してみます。(^_^) ちょっと長いですが、以下問題の引用です。 Collatz予想の収束までのステップ数の最大値を求め

Collatz予想(MySQL)

Posted by inquisitor at 2006-07-13 00:22
WHILE EXISTS (SELECT * FROM integers WHE...

LL2006 君ならどう書く ROUND2 C++編

Posted by FloralCompany.log at 2006-07-13 00:55
これのC++版です。LLじゃないけど 特に変わったことはしてないけど、 h(10...

Collatz予想 in Haskell 別解 (逆に展開する編)

Posted by haskellのある暮らし at 2006-07-13 01:35
逆に考えてみた。 Collatz 予想というのは、ようするに f は最終的に 1 になるっていうことだ。ということはその前に 2 がある。その前には 4 で、さらにその前は 8。その前は 16 。その前は 5 か 32。……という風にずーっと展開していくことができる。 この結果、1〜nまでのすべての整数が登場したときに打ち切ったとする。すると、最後に出てきた数がまさに求める k の値であるはずだ。 これを次のように書く。 ここで 1, 2, 4 を特別扱いしているのは、 4 から 1 も出てき ...

LLR2006 - Collatz予想は113383に気をつけろ!

Posted by 404 Blog Not Found at 2006-07-13 02:09
いつの魔にRound 2がはじまっている。 キミならどう書く 2.0 - ROUND 2 - ? Lightweight Language Ringお題は「Collatz予想」(角谷予想,3x+1問題)についての問題です. [中略] また,余力のある者は大きな n についても h(n) を求めよ. これまたtrivialな問....

Pythonで75文字でCollatz角谷問題の(以下略

Posted by 西尾泰和のブログ at 2006-07-13 03:04
f = lambda x: x == 2 and 1 or f(x % 2 an...

Pythonで75文字でCollatz角谷問題の(以下略

Posted by 西尾泰和のブログ at 2006-07-13 03:05
f = lambda x: x == 2 and 1 or f(x % 2 an...

[Program][D] Collatz 予想を D _インタプリタ_ で

Posted by 更新履歴兼雑記 at 2006-07-13 05:11
例のごとくコンパイルエラーで結果出力ですが、なるべくすなおーに書いてみました。 D のコンパイル時プログラミングはなかなか悪くないとわかるのではないでしょうか。 template g(int n) { const int result = n; static if (n == 1) { const int step = 1; } else static

Collatz 予想

Posted by Kazuho@Cybozu Labs at 2006-07-13 11:19
 キミならどう書く 2.0 - ROUND 2 - について。  いきなり br...

[プログラミング][Haskell]キミならどう書く 2.0 - ROUND 2 -

Posted by sadakomaの日記 at 2006-07-13 11:56
日記のネタによさげなものがあったので書いてみる。 とりあえず何も考えずに書いてみたバージョン。 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 で

Posted by sumim’s smalltalking-tos at 2006-07-13 12:30
キミならどう書く 2.0 - ROUND 2 - ― Lightweight Language Ring を受けて。 前回、いろいろな(変なw)言語でたくさん書き散らかしてしまったのを反省して、今回は、知らない人でも Smalltalk がどんな言語だかが分かるように、オーソドックスなのをひとつだけ。 クラス

[Python][Programming]どう書く2

Posted by DiaryException at 2006-07-13 13:57
参考: キミならどう書く 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予想に挑戦

Posted by CMS researcher at 2006-07-13 18:29
お待たせしました! キミならどう書く 2.0 ROUND 2の開催です!! 今回のLL Ringでは「LLで関数プログラミング」のセッションをはじめとし,関数型言語の活躍が期待されます.そこで,前哨戦にも関数型のお題を用意しました. お題は「Collatz予想」(角谷予想,3x+1問題)

LLR2006 - まだまだいくよ〜

Posted by 404 Blog Not Found at 2006-07-13 18:34
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]せっかくなので

Posted by unnonouno at 2006-07-13 21:03
http://ll.jus.or.jp/2006/blog/doukaku2 1回目はずいぶんベタだったが、2回目もなんかあんまり違いの出なさそうなお題がでるなぁと。 まだ、OCaml な回答を書いている人がすくなさそうなので。というほど気の利いたプログラムを書いたわけじゃありませんが。それにしても、

キミならどう書く

Posted by 主題のない日記 at 2006-07-14 00:04
さて、LightweightLanguageLingからのお題、「キミならどう書く」が話題になっているので載ってみることに。今回はコラッツ予想に関連した問題だが、特に数学的な知識が必要なわけではない。 問題文はこちら。 http://ll.jus.or.jp/2006/blog/doukaku2 まずはHaskellでその

[Squeak][Smalltalk] 「Collatz予想」(角谷予想,3x+1問題)のお題を AspectS で

Posted by sumim’s smalltalking-tos at 2006-07-14 02:30
前回、いろんな変な処理系で書き散らかしてしまったのを反省したつもりだったのですが…。つい、また。w f の定義を記述してから、同じような g を、しかし、今度はステップ数を出力するように再び記述するのは何か違うよな…と感じて思い出したのはアスペクト指向です。ま

[理系ネタ][J] 3n+1 問題

Posted by JGeek Log at 2006-07-14 03:40
http://ll.jus.or.jp/2006/blog/doukaku2 あ、これ去年某大学の並列計算の講義でネタにしました。簡単な整数演算を大量にやって何か面白いことが出来る話の一つとして、2CH のトリップや/etc/passwd のクラックなどと共に紹介しました。 高速化の方法として考えられるのは、

[Python Memo]「Collatz予想」(角谷予想,3x+1問題)

Posted by 二十代は模索のときブログ at 2006-07-14 06:13
「Collatz予想」(角谷予想,3x+1問題)についての問題ですか。初耳です。Pythonで参加したいと思います。 Lightweight Language Ring : キミならどう書く 2.0 - ROUND 2 - となり, f(n) の呼出は8回である.これをステップ数と呼ぶことにする. ここで f(n) が 1 になるま

Collatz予想

Posted by いつものこと at 2006-07-14 06:28
LLRingのお題ROUND2。 javascriptで書いてみました。「短く」とか「エレガントに」とか「javascriptっぽく」とかは全く意識していません。ポイントは…とくにないかな。トラックバックは…まだやめときます。応募者数が増えてきたらするかも。やってみました(7/13 6:30)。恥

h(4294967295) = 2610744987 where g = 1051

Posted by 404 Blog Not Found at 2006-07-14 14:40
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予想

Posted by 暇つぶし文@謎 at 2006-07-14 16:05
キミならどう書く 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予想の収束問題 : メモ化

Posted by lethevert is a programmer at 2006-07-14 22:57
せっかくなので、メモ化もしてみる。 先に作った構造をそのまま残したまま、関数 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

[プログラミング]コラッツ逆展開

Posted by [鍋]鍋あり谷あり at 2006-07-14 23:29
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 問題:まだまだ高速化

Posted by JGeek Log at 2006-07-15 09:10
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角谷問題の計算ステップが最大になる数の求め方

Posted by 西尾泰和のブログ at 2006-07-15 14:08
GRINEditを使って解いてみました。 Flashで動画にしたのでこちらをご...

キミならどう書く Scheme編

Posted by 主題のない日記 at 2006-07-15 18:45
「キミならどう書く」の問題。 http://ll.jus.or.jp/2006/blog/doukaku2 先日はC++で書いたわけだが、今回はScheme版を考えてみた。ハッシュテーブルはGaucheの拡張を使っている。メモ化関数が汎用的でない形に変形せざるを得なかったのが多少残念だが、分離できただけでも

キミならどう書く 2.0 - ROUND 2 - 「collatz問題」(第1回)

Posted by メモ at 2006-07-16 05:43
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 -)

Posted by tomapd == 22% at 2006-07-17 15:20
時間ができたので考えてみた。そのまま素直に書いてみた。 #!/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 予想 - ピタゴラ機械もどき版

Posted by swk's log at 2006-07-25 00:00
前回の素数列挙 OpenGL 版に引続き,「Collatz 予想の h(n) を求めるピタゴラ機械もどき」という色物ネタを考えていたのだが,時間がないのと,いざ実装しようと思うとあまり面白くなさそうだったのでやめた.そのうち気が向いたら書くかも.

勝手にどう書く0.0

by ENDO Yasuyuki posted at 2006-07-27 10:38 last modified 2006-07-27 10:38
手前味噌ですが今日の一行というコーナーを2004年からやっていて、「どう書く」的なネタがかなり溜まっています。

たとえば、7/10には、

各要素が「0または1をとる乱数」から成る長さnのリストを得よ。

ex.

 gosh> (make-binary-random-list 24)
(1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 1 0 1 0 1)
という問題があり、Gaucheではこう書けます。(7/11)
(use srfi-27)
(use srfi-42)

(define (make-binary-random-list length)
(list-ec (: i length) (random-integer 2)))
PythonやHaskellでは簡単そうですね。

The URL to Trackback this entry is:

[awk]Re:勝手にどう書く0.0

Posted by Rocco at 2006-08-07 00:31

awk だと一行野郎でこんな感じでしょうか。

BEGIN{srand();for(;i<=24;i++){printf int(2*rand())" "}print}

http://gauc.no-ip.org/wiki.cgi/private?page=Blog%2F2006%2D7%2D29#p2

愚直すぎ?

Pythonで特定の何種類かの値からランダムに選んでリストを作る方法

Posted by 西尾泰和のブログ at 2006-07-27 13:06
勝手にどう書く0.0を読んで、勝手に抽象化しました。 >>> from ran...

[Squeak][Smalltalk] 各要素が「0または1をとる乱数」から成る長さnのリスト

Posted by sumim’s smalltalking-tos at 2006-07-28 00:10
勝手にどう書く0.0 より。 (1 to: 10) collect: [:i | 2 atRandom - 1] (1 to: 10) collect: [:i | #(0 1) atRandom] (1 to: 10) collect: [:i | 'ACGT' atRandom] use や import がいらないのが Python や Scheme に対して、Smalltalk のよいところでもあり、悪い

各要素が「0または1をとる乱数」から成る長さnのリスト

Posted by ヒビルテ at 2006-07-29 23:12
勝手にどう書く0.0 より。あまり興味を惹かれるお題ではないけど、一応。 Prelude> :module +Random Prelude Random> :module +Monad Prelude Random Monad> xs <- liftM (take 10 . randomRs (0,1)) newStdGen Prelude Random Monad> xs [1,0,0,1,1,0,1,1,0,1]

[プログラミング]Concurrent Clean : 各要素が「0または1をとる乱数」から成る長さnのリストを得よ。

Posted by lethevert is a programmer at 2006-07-31 23:48
CleanJの切りも良いので、ちょっと息抜き。 import StdEnv, OptEnv, MersenneTwister Start = mbrl 10 1 //make binary random list mbrl n seed = take n $ map (\x = (abs x) rem 2) $ genRandInt seed 乱数種を与える方法として、OptEnvライブラリでrandSeedという関

勝手にどう書く0.0 — Lightweight Language Ring

Posted by インプリ at 2006-08-03 19:49
勝手にどう書く0.0 † Lightweight Language Ring 各...

各要素が「0または1をとる乱数」から成る長さnのリスト @ Ruby

Posted by 32nd diary at 2006-08-13 03:23
about 勝手にどう書く0.0 素直に書いてみました. ruby -e 'p (0...24).collect { rand(2) }'   24のとこをARGV[0].to_iとすれば任意の引数が取れます.

キミならどう書く 2.0 - ROUND 3 -

by takano32 posted at 2006-08-20 21:00 last modified 2006-08-21 16:54

LL Ringも開催まであとわずか!

「キミならどう書く 2.0」,前回の開催から少し間が開いてしまいましたが,ROUND 3 を開催します.

今回のお題はグラフです.

いくつかのデータを与えたときにグラフを出力するプログラムを作ってください.細かい仕様はありません.

たとえば以下のようなものです.

% ./graph 2 5 9
  2 : *****
  5 : ************
  9 : ********************

このプログラムでは最大の数値に対応する '*' の数を 20 とし,与えられた数値に応じた数の '*' を出力しています.

余力のある方は派手なグラフを出力したり,数値以外のデータを扱ってみるのも面白いかもしれません.また,ディスク容量やファイル容量などの値を使ってみるのもよいでしょう.

みなさんのプログラムやグラフをお待ちしています.

The URL to Trackback this entry is:

Re:キミならどう書く 2.0 - ROUND 3 -

Posted by dancerj at 2006-08-20 23:36

Cで

/*BINFMTC:
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define max(a,b) ((a) >= (b) ? (a) : (b))

int main(int ac, char** av)
{
int i, sum=0, maxval=0;
const char* graphstr="************************************************************************";
int graphstrlen=strlen(graphstr);
for (i=1; i<ac; (sum+=atoi(av[i])), ++i, maxval=max(maxval,atoi(av[i]))) if (atoi(av[i])<0) exit(1);
for (i=1; i<ac; ++i)
printf("%.2i/%.2i %s\n", atoi(av[i]), sum, graphstr+graphstrlen-1-atoi(av[i])*graphstrlen/sum);
return 0;
}

Re:キミならどう書く 2.0 - ROUND 3 -

Posted by dancerj at 2006-08-20 23:43

しまった、修正
/*BINFMTC:
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define max(a,b) ((a) >= (b) ? (a) : (b))

int main(int ac, char** av)
{
int i, sum=0, maxval=0;
const char* graphstr="************************************************************************";
int graphstrlen=strlen(graphstr);
for (i=1; i<ac; (sum+=atoi(av[i])), (maxval=max(maxval,atoi(av[i]))), ++i) if (atoi(av[i])<0) exit(1);
for (i=1; i<ac; ++i)
printf("%.2i/%.2i %s\n", atoi(av[i]), sum, graphstr+graphstrlen-atoi(av[i])*graphstrlen/maxval);
return 0;
}

'*' でグラフを描くスクリプト @ Ruby

Posted by 32nd diary at 2006-08-21 00:55
参考までにエントリで例示したグラフは以下のスクリプトで出力したものです. #!/usr/bin/env ruby columns = 20 nums = ARGV.collect {|s| s.to_i}   sum = nums.inject(0) do |sum, i| sum = sum + i end   max = nums.max   nums.each do |i| puts '%3d/%3d : ' % [i, sum] + '*' * (columns * (i.to_f/max) ).ceil end   % ./graph.rb 4 6 4 9 4/ 23 : ********* 6/ 23 : ************** 4/ 23 : ********* 9/ 23 : ********************

[プログラム][LL] io + OpenGL = ioDesktop でグラフを描く

Posted by SiroKuroPage at 2006-08-21 16:06
例によって iolanguage にて。 ioDesktop では OpenGL を扱えるので、そっちで描画してみました。 graph.io GLGraphApp := OpenGL clone do( width := 440; height := 320 data := nil GW := 12 font := Font clone open("resources/library/fonts/Free/Sans/Bold.ttf&#

グラフを描く(Mathematica)

Posted by inquisitor at 2006-08-21 18:48
コンソールでやれば次のようになる In[1]:= この企画、Mathemat...

グラフを描く(Mathematica)

Posted by inquisitor at 2006-08-21 18:51
<< Graphics`Graphics` BarChart@{2,...

グラフを描く(SQL)

Posted by inquisitor at 2006-08-21 20:16
SELECT d,RPAD('',20*d/m,'*') n FROM dat,...

キミならどう書く 2.0 - ROUND 3 -

Posted by 西尾泰和のブログ at 2006-08-22 02:56
>>> def graph(xs): print "\n".join([st...

ボクならこう書く

Posted by 只今Ruby勉強中 at 2006-08-23 00:38
LL Ringブログでやってる「キミならどう書く」シリーズで、何でも良いからグラフを作ってみやがれって言うお題があったのでおもしろそうだからチャレンジしてみました。 http://ll.jus.or.jp/2

バッチファイルは Lightwight Language なのでしょうか

Posted by ari at 2006-08-23 12:44
ふと、「Windows のバッチファイルは Lightwight Language なのか」と悩み、書いてみました。「キミならどう書く 2.0 - ROUND 3 -」でグラフを出力するプログラムがお題でしたので作ってみました。Windows バッチなので、Windows 以外の環境では動きません。現在、Windows S

[隠密][LLR-R3]グラフを描く!

与えられた数値を元にグラフを描くアプリを作れ!だそうです。 僕のではこんなグラフが出来ます。 $ ./graph 2 5 9 ********************|

[隠密][LLR-R3]続き

別ヴァージョン造りました。 今度はこんな感じです。 $ ./graph2 2 5 9 ** ***** ********* $ ./graph2 22 25 39 ++** ++***** ++***&#

[隠密][LLR-R3]更に続き--省略形続き

略式表示第二形です。 $ ./graph3 2 5 9 +* +**** +******** $ ./graph3 22 25 39 +* +**** +*****************

LLR2006 - Round 3; perl + javascript

Posted by 404 Blog Not Found at 2006-08-25 13:56
いよいよLL Ringは明日開催のようですが、私は欠席です。期待してた方ごめんなさい。 その代わり竹迫さんがPerlのLanguage Updateをやってくれます。 そういえば私の不在中にもう一問出てましたね。 キミならどう書く 2.0 - ROUND 3 - ? Lightweight Language Ring....

キミならどう書く2.0 ROUND3 「お題はグラフ」

Posted by インプリ at 2006-08-25 15:15
これを見て、LL Ringにはいけそうもないのだが、Pythonで、またやってみ...

[Python / LLRing ] re:君ならどう書く2.0 -Round 3-

Posted by Fomalhaut of Piscis Australis at 2006-08-26 02:55
Python で書いてみる。引数として与えられた数値のうち最大の数値を '*'

Tcl(/Tk) でグラフ

Posted by Rainy Day Codings at 2006-08-27 22:52
Lightweight Language のサイトの「キミならどう書く 2.0 - ROUND 3 -」というトラックバック企画 [1] で今回のお題が「いくつかのデータを与えたときにグラフを出力するプログラム」(細かい仕様無し)ということだった。 今までこの企画で Tcl や Tcl/Tk で参加している人は意外にもいないっぽいので書いてみることにしました(それにこのお題はいかにも Tcl/Tk 向き)。 まずちょっと仕様を制限したもの。キャンバスの幅をはみ出すようなデータは考慮しない。 # graph.tcl pack [canvas .canvas -width 200 -height [expr 20*[llength $argv]] -bg white] set ypos 10 foreach num $argv { .canvas create line 0 $ypos [expr $num*10] $ypos -width 18 -fill blue .canvas create text 2 $ypos -text $num -anchor w -fill white incr ypos 20 } 実行するには wish graph.tcl 2 5 9 18 15 などとする。実行結果はこうなる。 次はちゃんとキャンバスの大きさに合わせて伸縮するようにしたもの。 # graph2.tcl set height 150; set width 200; # キャンバスの大きさ set max [lindex [lsort -integer $argv] end]; # 要素の最大値 set lwidth [expr $height/[llength $argv]]; # 線の取れる太さ pack [canvas .canvas -width $width -height $height -bg white] set ypos [expr $lwidth/2] foreach num $argv { set xpos [expr $width*$num/$max] .canvas create line 0 $ypos $xpos $ypos -width [expr $lwidth-2] -fill blue .canvas cre...

キミならどう書く 2.0 - ROUND 3 -

Posted by Haskell はスケるよ at 2006-09-08 14:05
cf. キミならどう書く 2.0 - ROUND 3 - 前のエントリでは話がBrainf*ck(一応伏せ字にする)にいっちゃったけど,こっちが本題。 まったくもって乗り遅れたけど書いてみた。 import System showStar :: Int -> IO () showStar n = do putStrLn $ (show n) ++ " : &#

[参加者募集/ Python]君ならどう書く? -marge sort-

Posted by Fomalhaut of Piscis Australis at 2006-09-16 22:28
本家 LLRing 風にちょっとした問題で遊んでみようと思います。Python