「くどー」さんが、
そろそろ誰かに解いてほしい自作問題(未解決)
という記事を書かれています。
私には数学的な解決はできないですが、数値計算ならできると思い、やってみました。
問題の定義等は上記記事を御覧ください。
現状は
というかんじです。
つまり
以下少し詳しく説明します。
なお、整数論の問題ながら、整数論的な考察は一切ありません。ご容赦ください。
このあと出てくる用語・記号に関し定義をします。
(先にくどーさんの記事をみておいたほうがよいと思います。また、当方数学に不慣れなので、以下の定義に不備があったらすみません。その場合フィーリングで理解してください)
「くどー条件」の定義:
自然数の集合
を満たすとき、「
の順に数字を取り除く。どの削除の段階でも、その集合がくどー条件を満たすとき
ある
以上の準備のもと、くどーさんの作成した問題は
削除可能な
と言えます。
冒頭の繰り返しになりますが、数値計算でわかっていることを書いておきます。
ちなみに、
Appendix (a)に、数値計算のコードおよびアルゴリズムの概要を簡単に示しておきましたので、よろしければ御参照ください。
可能な削除列を具体的に見てみると、特長があることがわかります。
Appendix (b)に可能な削除列の例が載っていますのでご参照ください。
例えば
です。3,4,5と連続した自然数が見られます。
このような「連続する自然数」は、多くの
Appendix (b)を見ると
という特長があることがわかります。
理由はよくわかりません。
m^{(n)}{\rm max}をnに対してプロットした図。青い線はm^{(n)}{\rm max}=n-2の線。緑のバツが存在するnでは、探索が終わっていないため、データは存在しない。
青い線は
多くの場合、
n=19, 54, 55, 59, 63, 74におけるL(n;m)。縦軸のスケールがnにより違うことに注意
縦軸のスケールが図によって大きく異なることに注意してください。特に
更に図2を対数プロットにしたのが図3です:
図2を対数プロットしたもの。青い点線は、線形領域をy=aexp(bm)で近似した線。
これを見ると、
となります。
これが意味するのは、
ということです。そして
ある
ということです。付け加えられる数字は「少ない」と言えるかと思います。
計算量が多くなり計算が終わらない
とりあえずわかっていることは以上です。
改めてまとめておくと
という感じです。
おしまい
数値計算は以下のようなアルゴリズムで行っています:
以下に使用したPythonコードを載せておきます。実行環境は"Google Colaboratory"と"Amazon SageMaker Studio Lab"です。
C的な言語とかFortranとか、またはGPUで計算したらもっと速いと思います。
コード中の変数と、本記事のnotationとの対応は以下です:
インプットはNuplim(
from concurrent import futures
import numpy as np
import pickle
import sys
#---------
def Kudo_prob_01(Nuplim):
Nlist = [i+1 for i in range(Nuplim)]
temp_list = []
temp_pos_list = []
temp_rem_list = []
for i in range(1,Nuplim-1):
temp_list[:] = Nlist[:]
temp_list.pop(i)
if np.array([j**3 for j in temp_list]).sum() % np.array([j for j in temp_list]).sum() == 0:
temp_pos_list.append(temp_list[:])
temp_rem_list.append([Nlist[i]])
return temp_pos_list,temp_rem_list
def Kudo_prob_gt01(Nuplim,Nm,pos_list,rem_list):
if pos_list == []:
Nlen_pos_list = 2
else:
Nlen_pos_list = len(pos_list[0])
temp_list=[]
temp_pos_list=[]
temp_rem_list=[]
for k,i_list in enumerate(pos_list):
for i in range(1,Nlen_pos_list-1):
temp_list[:] = i_list[:]
temp_list.pop(i)
if np.array([j**3 for j in temp_list]).sum() % np.array([j for j in temp_list]).sum() == 0:
temp_pos_list.append(temp_list[:])
temp_rem_list.append(rem_list[k]+[i_list[i]])
return temp_pos_list,temp_rem_list
#---------
# Main:
## inputs ###
Nuplim = 10
Nthread = 10
#############
print ("#############")
print ("n =",Nuplim)
print ("### start ###")
# calculation 01:
pos_list, rem_list = Kudo_prob_01(Nuplim)
print ("- m =",1)
print ("L(n;m) =",len(rem_list))
for Nm in range(1,Nuplim-2):
print ("- m =",Nm+1)
length_datafile = len(pos_list)
Nconf = int(length_datafile/Nthread)
Nres = length_datafile-Nconf*Nthread
# print ("length_datafile,Nconf,Nres,tot:",length_datafile,Nconf,Nres,Nconf*Nthread+Nres)
pos_list_div = []
rem_list_div = []
for i in range(Nthread-1):
pos_list_div.append(pos_list[Nconf*i:Nconf*(i+1)])
rem_list_div.append(rem_list[Nconf*i:Nconf*(i+1)])
ilast = Nthread-1
pos_list_div.append(pos_list[Nconf*ilast:])
rem_list_div.append(rem_list[Nconf*ilast:])
# calculation greater than 01:
future_list = []
with futures.ThreadPoolExecutor(max_workers=Nthread) as executor:
for i in range(Nthread):
future = executor.submit(Kudo_prob_gt01,Nuplim,Nm,pos_list_div[i],rem_list_div[i])
future_list.append(future)
pos_list = []
rem_list = []
for x in future_list:
if x.result()[0] != []:
#print ("x.result():",x.result())
pos_list = pos_list + x.result()[0]
rem_list = rem_list + x.result()[1]
print ("L(n;m) =",len(rem_list))
print ("### finished ###")
if len(rem_list) > 0:
print ("n =",Nuplim, " is deletable !!!!!!!!!!")
else:
print ("n =",Nuplim, " is undeletable")
print ("")
- n=6
m=4
L(m;n)=1
[3,4,5,2]
- n=19
m=15
L(m;n)=14
[15, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 2, 18]
[15, 4, 5, 6, 7, 8, 9, 16, 18, 12, 3, 17, 10, 11, 13]
[15, 4, 5, 6, 7, 8, 9, 16, 18, 12, 3, 17, 10, 11, 14]
[15, 4, 5, 6, 7, 8, 9, 16, 18, 12, 3, 17, 10, 14, 11]
[15, 4, 5, 6, 7, 8, 9, 16, 18, 12, 10, 17, 3, 11, 13]
[15, 4, 5, 6, 7, 8, 9, 16, 18, 12, 10, 17, 3, 11, 14]
[15, 4, 5, 6, 7, 8, 9, 16, 18, 12, 10, 17, 3, 14, 11]
[15, 4, 5, 6, 7, 9, 8, 10, 11, 12, 13, 14, 16, 2, 18]
[15, 4, 5, 6, 7, 9, 8, 16, 18, 12, 3, 17, 10, 11, 13]
[15, 4, 5, 6, 7, 9, 8, 16, 18, 12, 3, 17, 10, 11, 14]
[15, 4, 5, 6, 7, 9, 8, 16, 18, 12, 3, 17, 10, 14, 11]
[15, 4, 5, 6, 7, 9, 8, 16, 18, 12, 10, 17, 3, 11, 13]
[15, 4, 5, 6, 7, 9, 8, 16, 18, 12, 10, 17, 3, 11, 14]
[15, 4, 5, 6, 7, 9, 8, 16, 18, 12, 10, 17, 3, 14, 11]
- n=54
m=28
L(m;n)=4573
[33, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 38, 25, 26, 27, 28, 29, 30, 31, 32, 49]
[33, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 42, 20, 40, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 53]
[33, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 42, 20, 40, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 53, 32]
[33, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 42, 20, 40, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 53, 49]
[33, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 42, 20, 40, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 53, 52]
[33, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 42, 20, 40, 22, 23, 24, 25, 26, 27, 28, 29, 30, 53, 31, 32]
[33, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 42, 20, 40, 22, 23, 24, 25, 26, 27, 28, 29, 30, 53, 31, 49]
[33, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 42, 20, 40, 22, 23, 24, 25, 26, 27, 28, 29, 30, 53, 31, 52]
[33, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 42, 20, 40, 22, 23, 24, 25, 26, 27, 28, 29, 30, 53, 52, 31]
[33, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 42, 20, 40, 22, 23, 24, 25, 26, 27, 28, 29, 30, 53, 52, 51]
...
- n=55
m=22
L(m;n)=451
[28, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27]
[28, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 40, 24, 25, 26, 27]
[28, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 40, 24, 38, 26, 27]
[28, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 40, 24, 38, 26, 36]
[28, 7, 8, 9, 10, 11, 12, 13, 14, 15, 27, 36, 41, 34, 21, 22, 23, 24, 25, 26, 54, 40]
[28, 7, 8, 9, 10, 11, 12, 13, 14, 15, 27, 36, 41, 34, 21, 22, 23, 24, 25, 26, 54, 53]
[28, 7, 8, 9, 10, 11, 12, 13, 14, 15, 27, 36, 41, 34, 21, 22, 23, 24, 25, 54, 26, 40]
[28, 7, 8, 9, 10, 11, 12, 13, 14, 15, 27, 36, 41, 34, 21, 22, 23, 24, 25, 54, 26, 53]
[28, 7, 8, 9, 10, 11, 12, 13, 14, 15, 27, 36, 41, 34, 21, 22, 23, 24, 25, 54, 53, 26]
[28, 7, 8, 9, 10, 11, 12, 13, 14, 15, 27, 36, 41, 34, 21, 22, 23, 24, 25, 54, 53, 39]
[28, 7, 8, 9, 10, 11, 12, 13, 14, 15, 27, 36, 41, 34, 21, 22, 23, 24, 25, 54, 53, 52]
...
- n=59
m: 21
L(m;n)=326
[30, 29, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]
[30, 29, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 53]
[30, 29, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 27, 26, 28]
[30, 29, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 27, 26, 53]
[30, 29, 10, 11, 52, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]
[30, 29, 10, 11, 52, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 38]
[30, 29, 10, 11, 52, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 32, 58, 57, 56, 55]
[30, 29, 10, 11, 52, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 54, 42, 57, 55, 44]
[30, 29, 10, 11, 52, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 54, 42, 57, 55, 56]
[30, 29, 10, 11, 52, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 54, 42, 57, 56, 43]
...
- n=63
m=33
L(m;n)=18
[56, 40, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39]
[56, 40, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 46, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39]
[56, 40, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 46, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 44, 54]
[56, 40, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 46, 26, 44, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 27, 54]
[56, 40, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 46, 26, 44, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39]
[56, 40, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 46, 26, 44, 28, 42, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39]
[56, 40, 9, 10, 11, 12, 13, 14, 15, 16, 52, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 4]
[56, 40, 9, 10, 11, 12, 13, 14, 15, 16, 52, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39]
[56, 40, 9, 10, 11, 12, 13, 14, 15, 16, 52, 18, 50, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 2, 4, 6, 8]
[56, 40, 9, 10, 11, 12, 13, 14, 15, 16, 52, 18, 50, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 2, 4, 6, 39]
...
- n=74
m: 30
L(m;n)=2
[37, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36]
[37, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 56]
- n=119
m=51
L(m;n)=161747
[60, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59]
[60, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 94]
[60, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 94, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 40]
[60, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 94, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59]
[60, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 94, 41, 92, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59]
[60, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 94, 41, 92, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 118]
[60, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 94, 41, 92, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 118, 58]
[60, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 94, 41, 92, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 118, 117]
[60, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 94, 41, 92, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 118, 57, 58]
[60, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 94, 41, 92, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 118, 57, 117]
...