プログラミング力を鍛えるために最近AtCoderを始めました。始めたばかりで時間内に終わらないことが多いですが、コツコツ頑張っていきたいです。
さて、今回は「任意の自然数を1から連続する有限個の自然数のプラマイで表せるか」について考えます。例えば以下の通りです。
\begin{alignat*}{2}
1&= &1&\\
2&=&1&-2+3\\
3&=&1&+2\\
4&=&-1&+2+3\\
5&=&-1&+2+3-4+5\\
6&=&1&+2+3\\
7&=&1&+2+3-4+5\\
8&=&-1&+2+3+4\\
9&=&1&+2-3+4+5\\
10&=&1&+2+3+4\\
11&=&1&-2+3+4+5\\
12&=&1&-2+3+4+5-6+7\\
13&=&-1&+2+3+4+5\\
14&=&-1&+2+3+4+5-6+7\\
15&=&1&+2+3+4+5
\end{alignat*}
任意の自然数を1から連続する有限個の自然数の足し引きで表示可能であることの証明は割と簡単です。というのも、自然数$n$に対して
\begin{align*}
\sum_{k=1}^{2n}(-1)^k k &=\underbrace{-1+2}_{+1}\underbrace{-3+4}_{+1}-\cdots\underbrace{-(2n-1)+2n}_{+1}\\
&=n
\end{align*}
と表せることが分かるからです。
ただ、上記の方法だと自然数を無駄に多く使っている可能性があります。例えば、
$6=-1+2-3+4-5+6-7+8-9+10-11+12$ですが、$6=1+2+3$のほうがエコです。
そこで、$n = \pm1\pm2\pm...\pm k$ と表せる最小の$k$を求め、pythonで関数を作ろうと思います。ただし、汎用性を高めるために、任意の数列を設定できるようにしました。
import numpy as np
def a(n, f):
def S(k):
return sum([f(j) for j in range(1,k+1)]) #S(0)=0と出力される仕様に依存
k=-1
while S(k)<n:
k+=1
max_iter = int(S(k)-S(k-1)+5) #上限の設定
for i in range(1,max_iter+1):
#f(1),f(2)...,f(i)
list_f = [f(j) for j in range(1,i+1)]
for e in range(2**i):
#i個の1と-1の列(eをi桁にゼロ埋めした2進数に変換し、listでバラバラにする)
list_sgn = [(-1)**j for j in [int(m) for m in list(format(e,'b').zfill(i))]]
#内積を計算
N = np.dot(list_f,list_sgn)
if n == N:
list_num = f"{n} ="
for l in range(i):
if list_sgn[l]==1:
list_num += f" + {list_f[l]}"
else:
list_num += f" - {list_f[l]}"
return list_num
#見つからなかった場合
return f"No solution for k≦{max_iter}"
#ここで好きな数列を設定する
def f(n):
return n
a(100, f)
出力結果：
'100 = + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 - 10 + 11 + 12 + 13 + 14 + 15'
0から任意に指定した$n$までの自然数を、指定の数列の1番目から$k$番目までの足し引きで表示するものも作ってみました（標準入力）。
入力1: $n$に関する数式
入力2: $n$の最大値
出力: $0$から$n$までの自然数を、入力1で記述した数列の1番目から$k$番目までの足し引きで表示（若干の装飾あり）
def pm_fx():
func = input("nに関する式を入力: ")
max_number = int(input("nの最大値を入力: "))
def f(n):
return eval(func)
def S(f,k):
return sum([f(j) for j in range(1,k+1)])
print("～～～計算開始～～～")
for i in range(max_number+1):
print(a(i, f))
k=-1
while S(f,k)<i:
k+=1
if i==S(f,k):
print("----------")
print("～～～計算終了～～～")
(中略)
ちなみに、自然数$n$が1番目から$k$番目までの和で表せた場合、"----------"で区切りを入れています。その理由は、$n+1$以降の自然数は$k+1$番目まで必ず必要になるからです。例えば、↑の結果では
\begin{align}
81 &= + 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17\\
&\text{----------}\\
82 &= + 1 + 3 + 5 + 7 - 9 + 11 + 13 + 15 + 17 + 19
\end{align}
となっていますが、17までの奇数のプラマイでは最大でも81にしかならないため、82以降の自然数は19が必要になることがわかります。この事実はmax_iter = int(S(k)-S(k-1)+5)にも反映されています（5は適当）。
f(k)=S(k)-S(k-1)なのでf(k)の方が簡潔なのですが、
prime(0)ではエラーを起こしてしまいます。ですが、S(-1)=S(0)=0と出力される仕様を利用して、S(k)-S(k-1)を採用しています。仕様変更等でエラーが起きるかもしれない箇所なので注意が必要です。
もちろん、入力する数列によっては解がないこともあります。例えば、偶数の列を考えると、$\pm2\pm4\pm6\cdots\pm 2k$は偶数になるため、奇数をこれで表示できないことがわかります。
sympyにある$n$番目の素数を返す関数sympy.primeを使えば、2から始まる連続する素数のプラマイで表示することもできます。
from sympy import prime
pm_fx()
ちなみに、「任意の自然数は2から始まる連続する素数のプラマイで表示することができるか」という問題は未解決問題の「ゴールドバッハ予想」が関係していると思われます。この予想が正しければ、マイナスにする部分は最大3つでいけそう（要検証）なので、探索を若干早められるかもしれないです。