整数表記で，数字の 1 桁ごとに、0～9 の値は「00, 01, 02, 03, 04, 10, 11, 12, 13, 14」の 2 桁の値に変換する。
「特定の言語で，特定の機能を使わないでプログラムする」ということだが，そんな条件にどんな意味があるというのかわからん。
func = function(n) {
func2 = function(m) {
sprintf("%i%i", m %/% 5, m %% 5)
}
ans = character(1)
count = 0
repeat {
if (n == 0) return(paste(rev(ans), collapse=""))
count = count+1
ans[count] = func2(n %% 10)
n = n %/% 10
}
}
for (i in c(1:15, 99, 100)) {
print(func(i))
}
1, 2, 3, …, n の中から異なる 2 数を取り出してその積をつくる。これらの積の総和を求めよ。
n = 5 のときは，1*2 + 1*3 + 1*4 + 1*5 + 2*3 + 2*4 + 2*5 + 3*4 + 3*5 + 4*5 = 85
n = 1e3, n = 1e8 のときの総和を求めよ。
解答は，この記事のコメントを参照。
整数 220×330×550×770×11110×13130 において，
(1) 末尾の 0 は何個あるか（初級）
(2) 先頭 1 桁目の数字は何か（初級）
(3) 全ての約数の総数はいくつか（中級）
(4) 全ての約数の総和はいくつか（上級）
解答は，この記事のコメントを参照
暗号解読には，若干のヒントが必須。それが，明示されていようが，暗示されたものであろうが
2qlglkl9b4f8.xy 0qdmeh
う～～む。とっかかりがない。老婆心ながら l は，小文字のエル，0 はゼロ。
暗号送出者（挑戦者）は日本的（？），受信者（被挑戦者）はそうではない（？）。
受信者は送信者の娘を旅行に誘ったが，その返事が件の暗号。受信者は，前半には「了解」，後半に
「非同意」と答えたいとのことだが。
換字式暗号ではないだろう。暗号文が短すぎるから。
ちなみに，以下は，解けるかな？
a03a1a9e4aba4abe4aea4a9b4abb3cca4a8bac6e9b5c0b3a1a6a4ade
4a0c4a4a4aac4afc4a7c4a6e9b5c0b0bcbafbb9b4ba03a1aca4a0c4a
8c4a3b4aec4a8c4a4a4afb4a8a4aaf5c8c4a7d1a5d0b1b6c3f8c6d1a
a0bc4aeb8c5e8b4a1a7d1a2f2bbbec6d1afc4abc4aeb8c0b1c4a1afc
4a4dcbeafb5fcb3a1a6e9b5c0bec4afe7bca4a6fbb6dacec4adb4a4a
1aca4afb4a3c4a6bdcbc4a4d9b9bec2f4acbccec4a4dcbeafb7f1cfc
4a4dcbeafb5fcba03a1abc1a9a1aac1a4a4aac4afc4a7c4a6a4adb4a
fc4abc1a4dcbfe0c9a4cfe8cac1a4dcbeafb5fcb4a1abc1a9a1aac1a
aa5ccdbccf6cfc4abc1a4dcbfe0c9a4cac1a4dcb0ddb7f1c6e9b5c0b
a03a1ade5acb5afc4a02034a1abe5a8a5aec4aafbb8baceaeb4a1afc
4a02c6029e4aca4aac4a4bfbcc7c7bfc3a1a4a4aac4aca4aae4aba4a
ba4a3c4a8c4a3a1a0e4a1c1a1c1a6a4aa08656d6461703029787e283
66432693c6b6c676c61723a0ca4a6a4ade4a2a4a7c4aec4a2e4afb4a
ce4a5b4a8acb5c0b4a1aca4a6a4a8e4a4a4a6c4ace4a5b4a8acb0ccc
4a1aca4ace4adb4a3a1acdfbca9cca4a8c5a3f5a2d5aec4a3b4b3ecb
4a1afc4abc4a9c6c2f2b6e9b5c0b
適当に改行されているが，一続きの文字列。
こちらは，参加自由，回答しても何のメリットもない。
回答があれば，コメント欄へというか，解けたら正解であることは自明。
要素が素数であるような数列がある。数列の要素どうしを掛け合わせることで得られる数字の個数を求めよ（全ての要素を使う必要はない）。
前にもあったが，約数の個数を求めよというのと同じ。ただし，1 を除くということ。
R で書くならば，数列のベクトルを x とすれば，prod(table(x)+1)-1 だけ。
x = c(2,3,5)
prod(table(x)+1)-1 # 7
x = c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73)
prod(table(x)+1)-1 # 2097151
x = c(2, 2, 2, 2, 11, 11, 11, 11, 23, 23)
prod(table(x)+1)-1 # 74
x = c(2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3)
prod(table(x)+1)-1 # 467
x = c(2, 2, 2, 2, 11, 11, 11, 11, 23, 23, 31, 37, 41, 43, 43, 53, 59, 61, 67, 67, 73, 199, 211, 211, 211, 211, 211, 211, 211, 211, 211, 263, 263, 263, 263, 263, 283, 283, 283, 311, 311, 311, 311, 337, 337, 349, 353, 359, 367, 373)
prod(table(x)+1)-1 # 19906559999
コイン投げに一度勝つと所持金が 2 倍になる。
コイン投げに一度負けると所持金が 1/16 になる。
ギャンブルの終了条件は、以下の通り。
・コイン投げに勝った回数が整数の 2 乗になっている
・コイン投げに負けた回数が整数の 2 乗になっている
・所持金が 0.5 円のような小数混じりの額ではなく、きちんと整数の額になっている
1円を元手として挑戦したハフィスは，儲けた金が 1000 万円以上であるが 1000 億円以下であることしか分からない。
【問】
このとき，ハフィスがコイン投げに勝った回数と負けた回数の考え得る組み合わせのパターン数を答えよ。
R コンソールを電卓代わりに手計算で解く
# 勝ち数と負け数を，Win と Lose で表す
# 1e7 < 2^(Win-4*Lose) < 1e11
# log10(1e7) < log10(2^(Win-4*Lose)) < log10(1e11)
# 7 < (Win-4*Lose)*log10(2) < 11
# 7/log10(2) < Win - 4*Lose < 11/log10(2)
# 23.2535 < Win - 4*Lose < 36.54121
# Win - 4*Lose = 24:36
# Win = 24:36+4*Lose かつ Win, Lose が平方数
# Lose = 1 なら Win = 24:36+4*1 = 28:40 平方数は 36
# 1e7 < 2^(36-4*1) < 1e11
# Lose = 4 なら Win = 24:36+4*4 = 40:52 平方数は 49
# 1e7 < 2^(49-4*4) < 1e11
# Lose = 9 なら Win = 24:36+4*9 = 60:72 平方数は 64
# 1e7 < 2^(64-4*9) < 1e11
# Lose = 16 なら Win = 24:36+4*16 = 88:100 平方数は 100
# 1e7 < 2^(100-4*16) < 1e11
# Lose = 25 なら Win = 24:36+4*25 = 124:136 平方数は ない！
# Lose = 36 なら Win = 24:36+4*36 = 168:180 平方数は 169
# 1e7 < 2^(169-4*36) < 1e11
# Lose = 49 なら Win = 24:36+4*49 = 220:232 平方数は 225
# 1e7 < 2^(225-4*49) < 1e11
# Lose = 64 なら Win = 24:36+4*64 = 280:292 平方数は 289
# 1e7 < 2^(289-4*64) < 1e11
# Lose = 81 なら Win = 24:36+4*81 = 280:292 平方数は ない！
# Lose = 100 なら Win = 24:36+4*100 = 424:436 平方数は ない！
# Lose = 121 なら Win = 24:36+4*121 = 508:520 平方数は ない！
# 以下のプログラムで，上記以外で条件を満たす Lose, Win はない
#for (i in 1:120) {
# Win = sqrt(24:36+4*i^2)
# j = which(Win == floor(Win))
# print(Win[j]^2)
#}
# まとめると，以下の 7 パターン
# 勝ち数, 負け数
# 36, 1
# 49, 4
# 64, 9
# 100, 16
# 169, 36
# 225, 49
# 289, 64
文字を convert すると，数値になる。
ヒントは「み・こ」。
“123” |＞ convert |＞ 1298
“abc” |＞ convert |＞ 12647
“ff7” |＞ convert |＞ 18907
“dq2” |＞ convert |＞ 16837
“y2k” |＞ convert |＞ 41740
10 以降を a, b, c, ... で表す n 進法で，最も大きい数値が "y" である。つまり 35 進法（なんというヒント！）と当たりをつけて，一つやってみるとビンゴ。
func = function(s) {
dig = c(0:9, letters[1:25])
s = unlist(strsplit(s, ""))
d = sapply(s, function(c) which(dig == c))-1
sum(d*(35^((length(s)-1): 0)))
}
func("123") # 1298
func("abc") # 12647
func("ff7") # 18907
func("dq2") # 16837
func("y2k") # 41740
func("codeiq") # 666852681
「大きな数の先頭と末尾（2）」を awk で書いてみると，「大きな数の先頭と末尾（2）」が R の特殊な機能を使っているのではないことが理解できるだろう。
# file name : func.awk
BEGIN {
print fun(3863080011, 2613515386) # 254361
print fun(21321331, 1234653876) # 81
print fun(521340345, 1396720193) # 84765625
print fun(1843165372, 2835135645) # 79967232
print fun(417934669, 3961963772) # 11298161
print fun(7564929, 1434531250) # 1
print fun(3713420107, 616334320) # 57768001
print fun(57564748, 243756997) # 3328
print fun(2249407224, 3483719867) # 32397824
print fun(444893257, 3572472608) # 25452801
}
function mul(m, n, km, kn, am, an, i, j, carry, num, ans) { # 8 桁以下の，m, n の掛け算を行い，下 8 桁を返す
km = m
kn = n
for (i = 1; i <= 8; i++) {
am[i] = km % 10
km = int(km / 10)
an[i] = kn % 10
kn = int(kn / 10)
}
for (i = 1; i <= 8; i++) {
for (j = 1; j <= 8; j++) {
ans[i+j-1] += am[i]*an[j]
}
}
carry = 0 # 繰り上がり
num = 0
for (i = 1; i <= 8; i++) { # 繰り上がり処理
ans[i] += carry
carry = int(ans[i] / 10)
num += (ans[i] % 10) * 10^(i-1)
}
return num # 答の下 8 桁を返す
}
function fun(m, n, ans) {
m = m % 1e8
ans = 1
for (;;) {
if (n % 2 == 1) {
ans = mul(ans, m) # もとの n の ビットが立っているところを掛け算
}
n = int(n / 2) # もとの n のビットが立っているところを探すため半分ずつにしていく
if (n == 0) return ans
m = mul(m, m) # 被巾数は倍々にしていく
}
return ans
}
$ gawk -f func.awk
254361
81
84765625
79967232
11298161
1
57768001
3328
32397824
25452801
偶然，「大きな数の先頭と末尾」の後に類似問題が出たようだ。
「大きな数の先頭と末尾」では本当は先頭1桁だけが必要なのだが，4 桁求めるようにしていた。
更に，べき乗される数もそんなに大きいものは考えていなかった。
なので，仕様を満たすために，以下のプログラムを書くことになった。
問題：a, x を符号なし 32 bit 整数として，べき乗計算 a^x の下 8 桁のみを高速に計算するプログラム
mul = function(m, n) { # 8 桁以下の，m, n の掛け算を行い，下 8 桁を返す
dec = function(k) { # 8 桁の整数を一桁ずつ配列に落とす
a = numeric(8)
for (i in 1:8) {
a[i] = k %% 10
k = k %/% 10
}
return(a)
}
am = dec(m)
an = dec(n)
ans = numeric(17) # 掛け算の答が入る
for (i in seq_along(am)) {
for (j in seq_along(an)) {
ans[i+j-1] = ans[i+j-1]+am[i]*an[j]
}
}
carry = 0 # 繰り上がり
for (i in 1:8) { # 繰り上がり処理
ans[i] = ans[i]+carry
carry = ans[i] %/% 10
ans[i] = ans[i] %% 10
}
return(sum(ans[1:8] * 10^(0:7))) # 答の下 8 桁を返す
}
func = function(m, n) {
m = m %% 1e8
ans = 1
repeat {
if (n %% 2 == 1) {
ans = mul(ans, m) # もとの n の ビットが立っているところを掛け算
}
n = n %/% 2 # もとの n のビットが立っているところを探すため半分ずつにしていく
if (n == 0) return(ans)
m = mul(m, m) # 被巾数は倍々にしていく
}
ans
}
func(3863080011, 2613515386) # 254361
func(21321331, 1234653876) # 81
func(521340345, 1396720193) # 84765625
func(1843165372, 2835135645) # 79967232
func(417934669, 3961963772) # 11298161
func(7564929, 1434531250) # 1
func(3713420107, 616334320) # 57768001
func(57564748, 243756997) # 3328
func(2249407224, 3483719867) # 32397824
func(444893257, 3572472608) # 25452801
以上全てを計算するのに，小生のポンコツ・マシンは 0.126 秒を要した。
一休さんのとんち話にもあったが，「一日目は1粒，二日目は倍の2粒，三日目は更にその倍の4粒というように増やして行くとき，一日に 8000万粒以上になるのは何日目か」というもの。
プログラムしてはいけない。ただ，そのためには log10(2)≒0.3010 を記憶していなければならないが（大学受験生なら知っているだろう）。
80000000 ≦ 2^(n-1)
3+7/log10(2) ≦ n-1
27.3 ≦ n
よって，28日目
なお，27日目までの累計も 80000000 を超える。
sum(2^0 + 2^1 + 2^2 + … + 2^(n-1)) = 2^n - 1
