最終更新: 2011-02-20T21:45+0900
10%未満
def prime? x return false if x < 2 return true if x == 2 quo, rem = x.divmod(2) return false if rem == 0 t = 1 while t < quo t += 2 quo, rem = x.divmod(t) return false if rem == 0 end return true end x, t = 1, 0 primes_on_diagonals = 0 loop{ t += 2 3.times{ x += t primes_on_diagonals += 1 if prime? x } x += t puts "#{primes_on_diagonals} primes out of #{2*t+1} (#{100*primes_on_diagonals/(2*t+1)}%, side length=#{t+1})" exit if 100 * primes_on_diagonals / (2*t+1) < 10 }
encrypted_text = [79,59,12,...,22,73,0,0] # last 2 elements are padding. text = "" 0.step(encrypted_text.size-1, 3){|i| text += (encrypted_text[i+0] ^ (71 ^ " "[0])).chr text += (encrypted_text[i+1] ^ (79 ^ " "[0])).chr text += (encrypted_text[i+2] ^ (68 ^ " "[0])).chr } text.chop!.chop! # remove padding puts text puts "sum: #{text.bytes.inject(:+)}"
1を満たす素数を発見しながらそれを使
# 寝る前にやる。
寝てしま
ち
def prime? x return false if x < 2 return true if x == 2 quo, rem = x.divmod(2) return false if rem == 0 t = 1 while t < quo t += 2 quo, rem = x.divmod(t) return false if rem == 0 end return true end set012 = [[],[3],[]] require 'mathn' Prime.new.each{|prime| break if 10000 <= prime dmod3 = prime.to_s.bytes.inject(0){|sum,byte| sum+byte-?0 } % 3 set012[dmod3] << prime } set1, set2 = set012[1], set012[2] set2[0] = 3 # set1 = [3,7,13,...] # set2 = [3,5,11,...] make_group_of_two = lambda{|set| pair = {} 0.upto(set.size-2){|i| (i+1).upto(set.size-1){|j| if prime?("#{set[i]}#{set[j]}".to_i) and prime?("#{set[j]}#{set[i]}".to_i) (pair[[set[i]]]||=[]) << set[j] end } } return pair } group1, group2 = make_group_of_two.call(set1), make_group_of_two.call(set2) extend_group = lambda{|g| group = {} g.each_pair{|rest, last1s| # rest + one of last1s = group last1s.each{|last1| next1s = last1s gg, out = rest.clone, last1 gg.size.times{|i| gg[gg.size-1-i], out = out, gg[gg.size-1-i] next1s &= g[gg]||[] } if ! next1s.empty? group[rest+[last1]] = next1s end } } return group } group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 3 primes group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 4 primes group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 5 primes printer = lambda{|rest, last1s| last1s.each{|last1| puts %[#{rest.inject(&:+)+last1}:\t#{rest.join("\t")}\t#{last1}] } } group1.each(&printer) group2.each(&printer)
分単位の時間で答えはでたけどもその五つ組の合計が意外に大きくて、10000以上の素数を組に加えても最小の組み合わせになりうる。計算量の増大の仕方がひどくて、これ以上桁数を増やして試行するのは無理だというのに。
じ
が 3の倍数の整数 qは 3の倍数です。
たしか 4の倍数についても同じような判定規則があ
たしか 5の倍数についてもどこかの桁を見るだけで(略
4は 100を作るから下2桁だけ。5は 10を作るから下1桁だけを見ればいい。
一番時間を食
とりあえず、今の素数判定より賢い素数判定があるのはわか
最終更新: 2011-02-13T04:35+0900
7500の正の約数は何個あるか。
Fラン大学の実態:ハムスター速報
素因数の数を数えてしま
復習～。
コメントに↑そのまんま書いてあ
最終更新: 2012-12-12T02:17+0900
適当にカスタマイズして設置した。
XHTML化キ
閲覧不可能にな
<script>タグの中であif(a && b) {} とか置換してしま
scriptタグが解釈できないブラウザなんて PCを手に入れた当時から持
<script><!-- --></script>
なんて最初から書かなか
<script>/*<![CDATA[*/ /*]]>*/</script>
コメントで囲うのは JavaScriptとして正しくあるため。より字数の少ない行コメントにしないのは、なにかでエラ
但し書きを付けても無駄。HTMLと日本語は混ぜるな危険。中途半端な HTMLの隠蔽は悪。tDiaryスタイルと etDiaryスタイルより Wikiスタイル。
自業自得。さすがに、タグに挟まれた部分に & や <, > を放置してたわけではない。
<a href="ttp://hoge/script.cgi?a=b&c=d"> <img src="ttp://hoge/script.cgi?a=b&c=d">
すべてこの形の & がエラ
それにしても、ちらちら目に入る古い日記が恥ずかしくて死ねる。読む人間も、そもそも読める内容もないのであえて気づかぬふりで放置するけども。
最終更新: 2011-02-12T22:42+0900
Bignumはできれば使いたくない。aが 100未満なので 8桁ずつ。
answer = [0, 0, 0] # sum, a, b 1.upto(99){|a| digits = "1" 1.upto(99){|b| sum = 0 carry = 0 0.step(digits.size-1, 8) {|i| l, r = [0, digits.size-i-8].max, digits.size-i carry, digits8 = (digits[l...r].to_i * a + carry).divmod(100000000) digits8 = "00000000#{digits8}"[-8,8] digits[l...r] = digits8 digits8.each_byte{|byte| sum += byte - ?0 } } if carry != 0 digits8 = carry.to_s digits = digits8 + digits digits8.each_byte{|byte| sum += byte - ?0 } end if answer[0] < sum *answer = sum, a, b end } } p answer
とかいいながら Bignum。
count = 0 numer, denom = 1, 1 1000.times{ numer, denom = numer + denom + denom, numer + denom count += 1 if numer.to_s.length != denom.to_s.length } p count
最終更新: 2011-02-10T23:58+0900
| 経過 | 荷物受付 | 02/10 | 12:36 | 金沢物流システム支店 |
| 経過 | 発送 | 02/10 | 12:36 | 金沢物流システム支店 |
| 最新 | 配達完了 | 02/10 | 12:06 | ○○センタ |
受付は昨日のはずだ。このせいで一切のトラ
最終更新: 2011-02-11T00:59+0900
Fix: 検索(ツ
ールバ ー)を使うとプラグインコマンドが実行される(2)
検索ボ
最終更新: 2011-02-10T04:56+0900
ただただ、手と CPUを動かすだけで精一杯。(頭は役に立
primes = [2] is_prime = lambda{|x| result = true primes.each{|prime| quo, rem = x.divmod(prime) if rem == 0 result = false break end break if quo < prime } return result } # replace 2 digits or 3 digits. キ・メ・ウ・チ def find_8_prime_family(a) return [] if a.size < 8 a.map!{|x| x.to_s } h = Hash.new{|h,k| h[k] = [] } # 2 digits 0.upto(a.first.size-3){|i| (i+1).upto(a.first.size-2){|j| h.clear a.each do |prime| if prime[i] == prime[j] h[prime[0...i]+prime[(i+1)...j]+prime[(j+1)...(prime.size)]].push prime end end h.each do |_,v| return v if v.size == 8 end } } # 3 digits 0.upto(a.first.size-4){|i| (i+1).upto(a.first.size-3){|j| (j+1).upto(a.first.size-2){|k| h.clear a.each do |prime| if prime[i] == prime[j] and prime[j] == prime[k] h[prime[0...i]+prime[(i+1)...j]+prime[(j+1)...k]+prime[(k+1)...(prime.size)]].push prime end end h.each do |_,v| return v if v.size == 8 end } } } return [] end x = 1 start = 0 # start of primes of a width. loop { x += 2 next unless is_prime.call x print "#{x}\r" if primes[start].to_s.length != x.to_s.length a = find_8_prime_family primes.last(primes.size-start) if ! a.empty? puts a.sort.join(" ") exit end start = primes.size end primes.push x }
桁数ごとに探索範囲を決めて、総当たり。
問題が xについても同じ数の組み合わせであることを求めてると思わなくてチ
digits = 10 loop { digits *= 10 (digits/2).upto((digits*10-1)/6){|x| print "#{x}\r" x2 = (x*2).to_s.split(//).sort if [3,4,5,6].all?{|n| x2 == (x*n).to_s.split(//).sort } then puts [1,2,3,4,5,6].map{|n| x*n }.join(" ") exit end } }
浮動小数点数なんてフ
count = 0 23.upto(100){|n| cmb = 1.0 1.upto(n/2){|r| cmb /= r cmb *= (n-r+1) count += (n-r == r) ? 1 : 2 if 1_000_000 < cmb } } p count
問題文が難しか
あto_s.reverse.to_i みたいなのをなくすべく、Integer#reverse を自作してみたら、かえ
class Integer # 負数については考えてない。 def reverse x = 0 this = self begin this, rem = this.divmod(10) x = 10*x + rem end while 0 < this x end end count = 0 10.upto(10_000-1){|x| is_lychrel = true 50.times{ x = x + x.reverse if x == x.reverse is_lychrel = false break end } count += 1 if is_lychrel } p count
最終更新: 2011-02-09T20:16+0900
時間がかかるので逐一進捗を表示してる。この問題に魔法の一手なんてあるのかね。
primes = [] is_prime = lambda{|x| result = true primes.each{|prime| quotient, remainder = x.divmod(prime) if remainder == 0 result = false break end break if quotient < prime } return result } 2.upto(999_999){|x| primes.push x if is_prime.call x } puts "#{primes.size} primes under 1 million." work = primes.dup step = 0 primes_found = [] live_elements = work.size while 0 < live_elements step += 1 primes_found.clear live_elements = 0 print "step #{step}\r" 0.upto(work.size-1-step){|i| work[i] += primes[i+step] if work[i] < 1_000_000 live_elements += 1 primes_found.push work[i] if is_prime.call work[i] end } if primes_found.empty? elsif primes_found.size < 10 puts "step #{step}: #{primes_found.join ' '}" else puts "step #{step}: #{primes_found.size} primes" end end
魔法の一手はなくても……
答えを出した後でググるのが楽しい。フ
最終更新: 2011-02-09T01:05+0900
昨日よりち
primes = [2] have4primefactors = [] num_of_factors = lambda{|x| prime_factors = 0 primes.each{|prime| quotient, remainder = x.divmod(prime) if quotient < prime prime_factors += 1 break end if remainder == 0 prime_factors += 1 break if 4 < prime_factors x /= prime while x % prime == 0 break if x == 1 end } return prime_factors } x = 2 loop { x += 1 print "#{x}\r" case num_of_factors.call(x) when 1 primes.push x have4primefactors.clear when 4 have4primefactors.push x p have4primefactors.first if have4primefactors.length == 4 else have4primefactors.clear end }
恥ずかしいほどま
p (1..1000).inject(0){|sum,x| sum + x**x }
10秒くらいかかります。
primes = [] is_prime = lambda{|x| result = true primes.each{|prime| quotient, remainder = x.divmod(prime) if remainder == 0 result = false break end break if quotient < prime } return result } 2.upto(9999){|x| primes.push x if is_prime.call x } primes_4digit = primes.last(primes.length - primes.rindex{|x| x < 1000 } - 1) 0.upto(primes_4digit.size-1){|i| p = primes_4digit[i] # next if p == 1487 (i+1).upto(primes_4digit.size-1){|j| q = primes_4digit[j] r = q + q - p next if p.to_s.split(//).sort != q.to_s.split(//).sort or q.to_s.split(//).sort != r.to_s.split(//).sort k = nil (j+1).upto(primes_4digit.size-1){|_k| if r == primes_4digit[_k] k = _k break elsif r < primes_4digit[_k] break end } if k puts "#{p} #{q} #{r}" # exit end } }
最終更新: 2011-02-07T05:28+0900
squares[]はソ
primes = [] # Omit 2. Even prime is not needed. squares = [1] def prime?(n) return false if 0 == n%2 3.step(n/2, 2) {|x| return false if 0 == n%x } return true end x = 1 loop { x += 2 squares.push((squares.size+1)**2) if squares.last < x if prime?(x) primes.push x next end print "#{x}\r" next if primes.any?{|prime| prime < x and squares.include?((x-prime)/2) } p x # answer break }
何の工夫もないのですんごく時間がかかる。
def prime_gt2?(n) return false if 0 == n%2 x, upper_bound = 3, n/2 while x <= upper_bound upper_bound, remainder = n.divmod(x) return false if 0 == remainder x += 1 end return true end primes = [2] have4primefactors = [] have4primefactor = lambda{|x| num_of_factors = 0 primes.each{|prime| if x % prime == 0 num_of_factors += 1 break if 4 < num_of_factors x /= prime while x % prime == 0 end } return num_of_factors == 4 } x = 2 loop { x += 1 print "#{x}\r" if prime_gt2? x primes.push x have4primefactors.clear elsif have4primefactor.call(x) have4primefactors.push x p have4primefactors.first if have4primefactors.length == 4 else have4primefactors.clear end }
最終更新: 2011-02-05T10:26+0900
ち
Q14
この漸化式は『珠玉のプログラミング』で見た。どうして収束するのかわからなか
脳log[2011-01-24] Q11, Q14, Q15, Q16, Q18, Q67, Q20, Q22, Q24, Q25, Q26った。
見た
4.6問題
5.入力xが正の整数であるとき、以下のル
ープが終了することを示してください。 while x != 1 do if xが偶数なら x = x/2 else x = 3*x+1
これがまんま「コラ
もし、この問題が解けたら、近くの大学の数学科に急いで行
って、博士号を申請しまし ょう。
ひどい(笑)。わからなくて当然だ。遅刻学生が黒板の問題を宿題だと思
最終更新: 2011-02-05T05:33+0900
無駄にこ
generators = [ lambda { n, tn = 1, 1 lambda { n+=1; tn+=n; tn } # triangle numbers generator }.call, lambda { n, pn = 1, 1 lambda { pn+=3*n+1; n+=1; pn } # pentagonal numbers generator }.call, lambda { n, hn = 1, 1 lambda { hn+=4*n+1; n+=1; hn } # hexagonal numbers generator }.call ] numbers = [1, 1, 1] # Ti, Pj, Hk relations = "===" # Ti?Pj, Pj?Hk, Hk?Ti actions = lambda { relation = lambda {|a,b| a==b ? '=' : a>b ? '>' : '<' } when_Nth_is_the_smallest = lambda {|i| lambda { numbers[i] = generators[i].call relations[i] = relation.call(numbers[i], numbers[(i+1)%numbers.size]) j = (i-1) % relations.size relations[j] = relation.call(numbers[j], numbers[(j+1)%numbers.size]) print "#{numbers[i]}\r" } } (0..2).map{|i| when_Nth_is_the_smallest.call(i) } }.call action_table = Hash.new {|h,rel| raise "missing action for '#{rel}'" } [ ["<<>", "<>>", "<=>", "=<>", "<>="], # when Ti is the smallest ["><<", "><>", ">=<", "><="], # when Pj is the smallest (and Ti not) [">><", "<><", "=><"], # when Hk is the smallest (and the other not) ].each_with_index {|rels, i| rels.each {|rel| action_table[rel] = actions[i] } } action_table["==="] = lambda { puts numbers[0] # answer actions[0].call } loop { action_table[relations].call }
相当な時間をかけて(求められていない)三番目の数字が出た。>57722156241751
六角数は三角数なので、三角数は無視できる。五角数と六角数を並べて比較していくだけ。
Project Euler 45,46 - 桃の天然水
それがわからない。
チ
Hn = n(2n-1) = (2n-1)(2n)/2 = m(m+1)/2 = Tm (m = 2n-1)
nは自然数だから、mは正の奇数になる。Triangle Numbersの奇数番目が Hexagonal Numbers.(逆も真) 言われたらそうかもね。それぞれの数列を眺めてたら気付くかもね。(それが無理なのはわか