裏 RjpWiki

Julia ときどき R, Python によるコンピュータプログラム,コンピュータ・サイエンス,統計学

特定の性質を持つ整数

2015年03月09日 | ブログラミング

数字の 0 から 9 までを一度ずつ使ってできる数で,
0 を除く全ての一桁の数で割り切れ,
この数に含まれる任意の隣り合う二桁でも割り切れる,
そんな数を探せ。

 library(e1071)
 d = cbind(permutations(9), 0) # 2 と 5 を因数に含むので,末尾が 0 の数だ
 w = 10^(9:0) # 10 進数の重み
 x = rowSums(t(t(d)*w)) # 10 進数として扱う
 f1 = x %% (7*8*9) == 0 # 2 ~ 9 のすべてを因数として持つか?
 d = d[f1,]
 x = x[f1]
 f12 = x %% (d[,1] * 10 + d[,2]) # 隣り合う 2 桁の数値を因数として持つか
 f23 = x %% (d[,2] * 10 + d[,3])
 f34 = x %% (d[,3] * 10 + d[,4])
 f45 = x %% (d[,4] * 10 + d[,5])
 f56 = x %% (d[,5] * 10 + d[,6])
 f67 = x %% (d[,6] * 10 + d[,7])
 f78 = x %% (d[,7] * 10 + d[,8])
 f89 = x %% (d[,8] * 10 + d[,9])
 f9x = x %% (d[,9] * 10)
 f2 = f12+f23+f34+f45+f56+f67+f78+f89+f9x == 0
 x[f2]

0.2 秒(!!)ほどで見つかる。3912657840

上のプログラムは冗長ともいえるが,下のように書き直したプログラムは,短いけどお行儀は悪い(良いのか?)

 library(e1071)
 d = permutations(9) # 2 と 5 を因数に含むので,末尾が 0 の数だ
 w = 10^(9:1) # 10 進数の重み
 x = colSums(t(d)*w) # 10 進数として扱う
 f1 = x %% (7*8*9) == 0 # 2 ~ 9 のすべてを因数として持つか?
 d = d[f1,]
 x = x[f1]
 x[rowSums(x %% (d*10 + cbind(d[,-1], 0))) == 0]


コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

PVアクセスランキング にほんブログ村

PVアクセスランキング にほんブログ村