連続する正の整数の和
締め切りが 2018/01/23 10:00 AM なので，その 1 分後に投稿されるように予約
ある数を「連続する正の整数の和」で表現することを考えます。
例えば、15は「1+2+3+4+5」「4+5+6」「7+8」のように表現できます。
このように複数の表現が可能で、しかもその表現で使われる数が連続するものを探します。
例えば、15の場合は「4+5+6」「7+8」が「4, 5, 6, 7, 8」のように連続します。
このように連続する表現が可能な数を小さい方から順に調べると、3, 15, 27, …となります。
・ 3 … 1 + 2, 3
・ 15 … 4 + 5 + 6, 7 + 8
・ 27 … 2 + 3 + 4 + 5 + 6 + 7, 8 + 9 + 10
標準入力から整数 n が与えられたとき、小さい方から n 番目の数を標準出力に出力してください。
なお、n は80以下の整数とします。
【入出力サンプル】
標準入力
2
標準出力
15
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
これは，オンライン整数列大辞典の A110703 であるが，漸化式のようなものは知られていないようだ。
ただし，これを満たす n は 3 の倍数であること，数列を (a, a+1, ..., b) と (b+1, b+2, ..., c) としたとき，
a * (1 - a) + b * (1 + b) = 2n
-b * (1 + b) + c * (1 + c) = 2n
a * (1 - a) + c * (1 + c) == 4n
という関係式があるの（2つで十分，他の1つは従属）で，探索範囲を狭めることができる。
解答先のシステムの R が極端に遅く，Python3 は速い。
当方では R が速く，Python3 が遅いという。
なんとも，間抜けな事態である。
R プログラム
当方では f(80) が 0.1 秒ほどだが，投稿先ではなんと 1 秒を超える？？
f = function(n) {
ans = NULL
for (a in 1:255) {
for (b in a:255) {
b2 = b*(1+b)
x = a*(1-a)+b2
for (c in b:255) {
y = c*(1+c)-b2
if (y > x) {
break
} else if (y == x) {
ans = c(ans, x)
}
}
}
}
cat(sort(unique(ans/2))[n])
}
#cat(f(scan(file("stdin", "r"))))
system.time({
f(80)
}) # 0.109 seq.
f(2) # 15
f(10) # 147
f(35) # 945
f(70) # 3267
f(80) # 3978
Python プログラム
import numpy as np
def f(n):
mx = 4000
ans = np.zeros(mx)
count = 0
for a in range(1, 256):
for b in range(a, 256):
b2 = b*(1+b)
x = a*(1-a)+b2
for c in range(b, 256):
y = c*(1+c)-b2
if y > x:
break
elif x == y:
ans[count] = x
count += 1
ans = np.sort(ans/2)
g = ans
count = 0
for i in range(1, mx):
if ans[i] != ans[i-1]:
g[count] = ans[i]
count += 1
print(int(g[n-1]))
f(int(input()))
f(80) が 0.268 seq.
