もうカツ丼でいいよな

■[Emacs] EmacsのフォントをRictyにした 22:55

Rictyというフォントが話題になっていたのでEmacsのフォントに設定してみた。

Mac OS X 10.6.7、Emacs 23.2.1(ただEmacsどうやって入れたんだったか今ひとつ思い出せない…)。

フォントはプログラミング用フォント Rictyからダウンロードしてきてインストール。

.emacsには

;; Ricty {{{2 (http://save.sys.t.u-tokyo.ac.jp/~yusa/fonts/ricty.html)
(set-face-attribute 'default nil
                   :family "Ricty"
                   :height 160)
(set-fontset-font
 nil 'japanese-jisx0208
 (font-spec :family "Ricty"))

と書いておいた。前使ってたInconsolataとTakaoゴシックの設定ほぼそのままなので中身の意味はよく分からない。

日本語読みやすくなったけど三点リーダ(…)の幅が半角なのがちょっと気になる。

(2011/5/4 追記) 本日公開されたVersion 2.0.2でInconsolata由来のAmbiguous文字の全角化がされて、三点リーダも全角で表示されるようになった。古いのを一旦消してインストールしなおしたら無事表示された。マメにアップデートされてるしRSSで配信されるしありがたい限りです。

ツイートする

■[R][Project Euler] Problem 132 20:54

Problem 132 - Project Euler

1のみからなる数(1, 11, 111, ...)をrepunitと呼ぶ。k桁のrepunitをR(k)で表すことにしよう。

さて、R(10) = 1111111111を素因数分解すると素因数は11, 41, 271, 9091であるから、素因数の総和は9414である。

R()の素因数のうち小さいものから40個の総和を求めよ。

R(A(n))はnで割り切れるが、剰余が循環するという性質から、mを1以上の整数としてR(m * A(n))もnで割り切れる(c.f. Problem 129 - もうカツ丼でいいよな)。

つまり、10^9がA(n)で割り切れるかどうかを調べればR(10^9)がnで割り切れるかどうかを調べることができる。ただ、このやりかたで素因数を網羅的に調べようとすると時間がかかりすぎるので別のアプローチをする。

R(k)を9倍して1を足すと10^kになる。よって

であるならば、nはR(k)の9倍を割り切れる。

冪剰余は高速に求められる(c.f.冪剰余 - Wikipedia)ので、

を満たしかつ素数であるようなnを小さいものから40個探せばよい。

ただ、R(k)の9倍はkの値に関わらず3で割りきれてしまうので、3は最初のやり方で別にチェックする。9も割り切れるが、9は素数でないのでそもそも対象外。

library(gmp)

lim <- 1e6
sieve <- logical(lim)
sieve[c(1, seq(4, lim, by=2))] <- TRUE
for(i in 3:(sqrt(lim))){
  if(!sieve[i]) sieve[seq(i*2, lim, by=i)] <- TRUE
}

prm.list <- (1:lim)[!sieve]

A <- function(n){
  if(n %% 2 == 0 || n %% 5 == 0) return(0)
  k <- 1
  m <- 1
  while(m != 0){
    k <- k + 1
    m <- (m * 10 + 1) %% n
  }
  k
}
lim <- 1e9
f <- lim %% A(3)

cnt <- 0
ans <- 0
if(f){
  i <- 3
}else{
  i <- 2
}
while(cnt < 40){
  if(powm(10, lim, prm.list[i]) == 1){
    ans <- ans + prm.list[i]
    cnt <- cnt + 1
  }
  i <- i + 1
}
ans

610ms。

ツイートする