〜2016年2月上旬〜
Non-abundant sums. 非過剰数の総和。
真の約数の和が出てくるのでProblem 21の方法が使える。
% time seq 28123 | gawk 'i=$0{n[i]=i;for(j=i*2;j<=28123; j+=i)a[j]+=i;if(i<a[i])b[++k]=i}END{for(i in b)for(j=i;(sum=b[i]+b[j])<=28123;j++)n[sum]=0;for(i in n)s+=n[i];print s}'
4179871
seq 28123 0.00s user 0.00s system 0% cpu 0.066 total
gawk 4.41s user 0.00s system 99% cpu 4.416 total
aに真の約数の和、bに過剰数をいれて、それを使って過剰数の和を削除している。
n[sum]=0はdelete n[sum]でいいんだけど遅い。
それとjはfor(j in b)とできるんだけどやはり遅い。
mawkはgawkよりやはり速い。
% time seq 28123 | mawk 'i=$0{n[i]=i;for(j=i*2;j<=28123; j+=i)a[j]+=i;if(i<a[i])b[++k]=i}END{for(i in b)for(j=i;(sum=b[i]+b[j])<=28123;j++)n[sum]=0;for(i in n)s+=n[i];print s}'
4179871
seq 28123 0.00s user 0.00s system 0% cpu 0.077 total
mawk 3.30s user 0.00s system 99% cpu 3.300 total
Lexicographic permutations. 辞書式順列。
0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目。
順列ということは10!通りの数がある。
1桁目は10通り。ということはそれぞれ9!(362880)のブロックになる。
1000000/362880が2.7ぐらいなので、1桁目は0,1,2の2になる。
1000000%362880=274240ということで、今度は8!(40320)で同じように進めると、
274240/40320が6.8ぐらいなので、2桁目は0,1,3,4,5,6,7の7になる。
これをシェル芸で表現する。
% echo 0123456789 | sed -r "$(echo 'n=999999;f=3628800;for(i=10;i>0;--i){f/=i;n/f;n%=f}'|bc|sed 's/./s,(.{&})(.)(.*),\\1\\3\\2,/')"
2783915460
まず、3628800は10!。階乗の値は9!,8!と必要になるのでつぎつぎと割ってあげればいい。
% echo 'n=999999;f=3628800;for(i=10;i>0;--i){f/=i;n/f;n%=f}'|bc
2
6
6
2
5
1
2
1
1
0
これを使って0123456789から抜き出すわけだけど、抜き出す代わりに並び換える。
次々と最後へ10回繰り返して移動させれば抜き出すのと同じことになる。
% echo 2662512110|sed 's/./s,(.{&})(.)(.*),\\1\\3\\2,\n/g'
s,(.{2})(.)(.*),\1\3\2,
s,(.{6})(.)(.*),\1\3\2,
s,(.{6})(.)(.*),\1\3\2,
s,(.{2})(.)(.*),\1\3\2,
s,(.{5})(.)(.*),\1\3\2,
s,(.{1})(.)(.*),\1\3\2,
s,(.{2})(.)(.*),\1\3\2,
s,(.{1})(.)(.*),\1\3\2,
s,(.{1})(.)(.*),\1\3\2,
s,(.{0})(.)(.*),\1\3\2,
このsed scriptを通してあげれば並び換え完成。
backslashがうっとうしいので-rオプションを使っている。
cf: Project Eulerをシェル芸で解いてみる(Problem 24) #シェル芸 - Qiita
やってることは基本同じ。
1000-digit Fibonacci number. 1000桁のフィボナッチ数。
ひねりなし。
% echo 'b=1;l=10^999;for(;a<l;i++){a=b-a;b+=a}; i' | bc
4782
最初の1000桁は10^999なので豪快にこれと比較する。
Reciprocal cycles. 逆数の循環節。
d < 1000 なる 1/d の中で小数部の循環節が最も長くなるような d を求めよ。
bcでscaleを適当に大きく設定すれば力ずくで解ける。
肝は繰り返しの正規表現でこればかりはRubyやPerlじゃないと面倒。
% time (seq -f 'scale=2000;1/%g' 999|BC_LINE_LENGTH=0 bc|ruby -pe 'sub(/.*(.+)\1+$/){"#$. #{$1.size}"}'|sort -k2n|tail -n1)
983 982
( seq -f 'scale=2000;1/%g' 999 | BC_LINE_LENGTH=0 bc | ruby -pe | sort -k2n ) 3.13s user 0.01s system 104% cpu 3.011 total
3秒かかる。
というわけでちゃんと計算してみる。
たとえば1/17を小数点以下40桁分計算するとこんな感じになる。
% echo 'r=1;for(i=0;i<40;i++){r*=10;print r/17;r%=17}'|bc;echo
0588235294117647058823529411764705882352
循環は商で考えてしまうと難しい。ここで重要なのは余りのほう。
同じ余りに戻ってきたときに1周したと考えればいい。
この方針だと瞬時に求まる。しかも短い。
% time (seq 999 | awk '{for(r=1;!a[r];r=10*r%$0)a[r]=1;print $0,length(a);delete a}'|sort -k2n|tail -n1)
983 982
( seq 999 | awk '{for(r=1;!a[r];r=10*r%$0)a[r]=1;print $0,length(a);delete a}) 0.05s user 0.00s system 90% cpu 0.053 total
余りで考えると循環の長さは最大でも除数-1にしかならないことがわかる。
これを利用するとさらに高速化が可能となる。
料金そのままで下りは倍速になったらしい。
全然変わってない気もするが。
上りはそのままだしな。
AWS ECRに毎回同じタグをつけてpushしても上書きされるのではなく、
古いのはタグが外されてただ残るのでたまに掃除してあげないといけない。
というわけでシェル芸。
% aws --region us-east-1 ecr list-images --repository-name repository | \ jq -r '.imageIds[]|select(.imageTag|not).imageDigest' | sed 's/^/imageDigest=/' | \ xargs -tr aws --region us-east-1 ecr batch-delete-image --repository-name repository --image-ids
imageDigestの部分がjqとsedで冗長だけど、どうしたもんか。jqだけならこんな感じか。
jq -r '.imageIds[]|select(.imageTag|not)|to_entries[]|[.key,.value]|join("=")'
いやこれでいいや。
jq -r '.imageIds[]|select(.imageTag|not)[]|"imageDigest=\(.)"'
これって力技だと三重ループになって時間がかかりすぎるので、
なんとかして数を減らさないといけない。
bが素数になるのはすぐわかるが、素数を発生させるというのも結構面倒だ。
accesskey+region.dbという形式になるので、
~/.aws/configureのアクセスキーがファイル名に含まれるのがいやなら、
環境変数を設定するといい。
% AWS_ACCESS_KEY_ID=test AWS_SECRET_ACCESS_KEY= aws dynamodb create-table \
--endpoint-url http://localhost:8000 \
--region us-east-1 \
--table-name test \
--attribute-definitions AttributeName=foo,AttributeType=S \
--key-schema AttributeName=foo,KeyType=HASH \
--provisioned-throughput ReadCapacityUnits=1,WriteCapacityUnits=1
{
"TableDescription": {
"AttributeDefinitions": [
{
"AttributeName": "foo",
"AttributeType": "S"
}
],
"TableStatus": "ACTIVE",
"ProvisionedThroughput": {
"LastIncreaseDateTime": 0.0,
"LastDecreaseDateTime": 0.0,
"WriteCapacityUnits": 1,
"NumberOfDecreasesToday": 0,
"ReadCapacityUnits": 1
},
"KeySchema": [
{
"AttributeName": "foo",
"KeyType": "HASH"
}
],
"ItemCount": 0,
"TableName": "test",
"TableSizeBytes": 0,
"CreationDateTime": 1454935278.852
}
}
% ls test*
test_us-east-1.db
適当な名前にできるので、わかりやすい名前をつけられる。
Quadratic primes. 二次式素数。
なんだかんだでawk芸。
n**2+a*n+bが素数になるにはいろいろ制限がある。
それを使うとチェックする数を減らせる。
n=0のときを考えるとbは素数だとわかる。
n=2のときは4+a*2+bなのでbは奇数。よってbは奇素数になる。
n=1のときは1+a+bとなるが、bは奇数なのでaも奇数になる。
さらに1+a+bが素数なので1+a+b>1と言える。つまりa>-bとなる。
以上を踏まえてawkで実装。
BEGIN {
for (b=3; b<=999; b+=2) {
if(!prime(b))
continue
for (a=-b; a<=999; a+=2) {
for (n=0; prime((n+a)*n+b); n++);
if (maxn < n) {
maxn = n-1;
f = a*b
}
}
}
print f
}
function prime(n) {
if (n in h)
return h[n]
if (n<2)
return h[n]=0
for (i=3; i*i<n; i++)
if (n%i==0)
return h[n]=0
return h[n]=1
}
素数の判断は素朴な方法で、試し割り。
何度も同じ数が出てきたのでcacheするようにした。
効果は絶大で4倍ほど速くなる。