エルデス・シュトラウス予想とは

2以上の任意の正整数Nに対し、 X,Y,Z:正整数として、4/N=1/X+1/Y+1/Zをみたす(X,Y,Z)の組が存在する。

という予想。これを肯定的に証明してみたいと思い、かつていろいろやってみました。現在、Nが24n+1型素数以外の場合なら必ず存在することが判明しており、示すべき残りはNが24n+1型素数の場合のみです。

（参考：http://www004.upp.so-net.ne.jp/s_honma/number/erdos.htm）

24n+1型以外の有名な公式は導出できましたが、24n+1型だけは同じ方法ではまだ作れていません。

これまでの議論のまとめが以下のTogetterになります。興味がありましたら見てみてください。

エルデス・シュトラウス予想を解こうの会 - Togetterまとめ

2017/01/12追記

この予想、24N+1型の恒等式を作る方針では、120N+1型が残り、…と無限降下になり、全てを示し尽くすことはできないようで、分母の多項式を探索するという方針でずっとやっていたのは失敗でした。

参考：１章 4-n=1-a+1-b+1-c

プリクラ問題はさておき、エルデス・シュトラウス予想に関しては分母の整式の積の形になっているのを、小さい整式から入れて探索していければ24n+1型素数でも何かしらの一般的な分解方法が見つかると期待してるんだけど、変数を無限に生成できるコードの書き方がわからず頓挫。

— まる (@ps_maru) 2017年1月7日

@ps_maru https://t.co/KNlgbIDzKS この問題、恒等式は無限に作れるけどan+1の形の恒等式を作ることは原理的に不可能なんですね。24n+1型は120n+73、120n+97の恒等式は存在するけど、結局120n+1の恒等式は存在しないから堂々巡りに。

— TokusiN (@toku51n) 2017年1月7日

@ps_maru エルデシュ・シュトラウス予想って24に限らず任意のaに対して4/(an+1)の形の数が3つの自然数の逆数和で表せる事を証明出来ればほぼ解決なんですね。an+b(b≠1)の形なら漸化式が作れるから、後から間を埋めればいい。

— TokusiN (@toku51n) 2017年1月7日

@ps_maru n=0の時に矛盾するからan+1型の恒等式は存在しない、と思っていたのですが、どうやら間違っていたみたいです。1/n + 1/(n*(4n-1))は、n→0の時に-4に収束するけど1/(4n-1)の恒等式の存在は否定されない。

— TokusiN (@toku51n) 2017年1月7日

@ps_maru 別の理由でan+1型の恒等式は存在しないようなのですが、それほど単純な理由ではないようですね。

— TokusiN (@toku51n) 2017年1月7日

@ps_maru 120+73と120+97の漸化式は見つかっていて、多分25と49もあるでしょう。そして120n+1が残ります…

— TokusiN (@toku51n) 2017年1月8日

@ps_maru その後で840n+…と進んでも不毛以外の何物でもないのでどこかでアプローチを切り替えないとダメそうですね。

— TokusiN (@toku51n) 2017年1月8日

これで挫折して私は匙を投げましたが、いつか解かれる日が来るのを楽しみにしています。

素因数分解を多項式時間で解く方法については様々議論されています。Shorのアルゴリズムから隆盛して近年量子コンピュータの研究が盛んですが、古典的コンピュータではもはやP≠NP予想であり、成否どちらも証明できるかは怪しいものとなっています。

さて、それについて、2012年11月15日(木)に、あるツイートがTwitterの一部界隈をにぎわせました。不思議な人物が彼にそれについての研究成果らしき紙束を渡したのです。しかし、中身は意味不明な表ばかり。筆者も当時読んでみましたが、方法が書かれているのか補題までなのかすらわかりませんでした。

yamu_chaさんが垢消しをしてしまったので、リンクだけ貼っておきます。（まさか真理に触れてしまったのだろうか……？と思ったけど、普通に卒業？とともに垢消ししただけっぽい？行方をご存知の方はぜひ知らせていただけると嬉しいかも。）

元ツイートURL：https://twitter.com/yamu_cha/status/268878201890144256

該当ツイートのぱくったー：http://lovelove.rabi-en-rose.net/pakutter.php?tweetid=268878201890144256

流れ：http://twilog.org/ps_maru/search?word=%40yamu_cha&ao=a

画像：http://www.mobypicture.com/user/yamu_cha

画像は荒いです。yamu_chaさん自身がスキャンしたpdfのリンクをツイートしていたのでそこからダウンロードしたのですが、元リンクが不明となっており、とりあえずこれだけ。

ぱくったーによると、約870Fav・約180RTいっていたようです。

もし正しい方法が書かれているのであれば数学史上最大のイベントの1つとなり世界中の暗号が揺るがされてしまいますが、個人的にはこの資料だけでP≠NP予想の解決までいくものではない気がします。もし解読できる方がいましたらぜひ挑戦してみてください。

最近Twitterで話題になった数学の未解決問題で筆者が取り組んでいる問題に、プリクラ問題というのがあります。

あのね。前々からずーーっと答えが知りたい数学の問題があって。

①n人のグループがいる
②プリクラ機械には一度にm人しか入れない

この場合、全員が必ず他の全員と最低一回は同時に撮影される為には、何回撮影する必要があるか？

実際の事例から考えた問題だけど、自力では解けない。

— あしやまひろこ (@hiroko_TB) 2015年1月1日

という問題提起から始まったものです。Togetterまとめは以下。

プリクラ問題 - Togetterまとめ

プリクラ問題２

プリクラ問題まとめのまとめ - Togetterまとめ

---以上、2016年5月31日追記。---

プリクラ問題の総探索プログラムのRubyコードをおいておきます。

def solve(n,m) #プリクラ問題。n人がm人まで入れるプリクラで全員自分以外の人と1回以上撮るためのプリクラ撮影回数の最小値を求める。
  mincount = C(n,m)
  card = card(n,m)
  order = order(C(n,m))
  order.each{|elem| mincount=min(mincount,count(card,elem))}
  return mincount
end
def count(card,order) #cardをorder順にparseしてcard使用回数を数えて返す関数
  flag = make2d(order.length(),order.length())
  counter = 0
  for i in 0..(order.length()-1)
    counter = counter + 1
    parse(card[order[i]-1]).each{|elem| flag[elem[0]-1][elem[1]-1]=1}
    if (sumElem(sumElem(flag)) == C(order.length(),2))
      break
    end
  end
  return counter
end
def parse(a) #[3,1,2]を代入すると[[3,1],[3,2],[1,2]]を返すような関数
  deck = make1d(C(a.length(),2))
  count = 0
  for i in 0..(a.length()-1)
    for j in (i+1)..(a.length()-1)
      deck[count] = [a[i]] + [a[j]]
      count = count + 1
    end
  end
  return deck
end
def order(n) #[[1,2,3],..,[3,2,1]]を返すような関数
  deck = make1d(P(n,n))
  line = make1d(n)
  for i in 0..(n-1)
    line[i] = i + 1
  end
  counter = [0]
  def shuffle(orig,count,a,b=[]) #配列の要素を順番に抜き出す再帰的関数
    if a.length() == 0
      orig[count[0]] = b
      count[0] = count[0] + 1
    else
      a.each{|i| shuffle(orig,count,a-[i],b+[i])}
    end
  end
  shuffle(deck,counter,line)
  return deck
end
def card(n,m) #[[1,2,3],..,[3,4,5]]を返すような関数
  deck = make1d(C(n,m))
  temp = deck.clone
  temp[0] = make1d(m)
  for i in 0..(m-1)
    temp[0][i] = i+1
  end
  deck[0] = temp[0].clone
  def pointer(n,m,narray,num) #[1,4,5]を代入すると[2,3,4]を返すような関数
    if num > -1
      if narray[num] < n+num+1-m
        narray[num] = narray[num]+1
        if num < m-1
          for i in 1..(m-1-num)
            narray[num+i] = narray[num]+i
          end
        end
        return narray
      else
        pointer(n,m,narray,num-1)
      end
    else
      return 'error: the last elem [n-m+1,..,n] was put in pointer().'
    end
  end
  for i in 1..C(n,m)-1
    temp[i] = pointer(n,m,temp[i-1],m-1)
    deck[i] = temp[i].clone
  end
  return deck
end
def max(x,y) #x,yのうち大きい方を返す
  if x >= y
    x
  else
    y
  end
end
def min(x,y) #x,yのうち小さい方を返す
  if x <= y
    x
  else
    y
  end
end
def maxElem(a,i=a.length()-1) #0..iの配列aのうち最大の要素を返す
  if i==0
    a[0]
  else
    if maxElem(a,i-1) > a[i]
      maxElem(a,i-1)
    else
      a[i]
    end
  end
end
def minElem(a,i=a.length()-1) #0..iの配列aのうち最小の要素を返す
  if i==0
    a[0]
  else
    if minElem(a,i-1) > a[i]
      a[i]
    else
      minElem(a,i-1)
    end
  end
end
def sumElem(a,i=a.length()-1) #配列の要素の合計を返す
  if i==0
    a[0]
  else
    a[i] + sumElem(a,i-1)
  end
end
def make1d(n) #長さnの零列ベクトルを返す
  a = Array.new(n)
  for i in 0..(n-1)
    a[i] = 0
  end
  a
end
def make2d(height,width) #height行witdth列の行列を返す
  a = Array.new(height)
  for i in 0..(height-1)
    a[i] = make1d(width)
  end
  a
end
def C(n,k) #nCkを返す
  if k > n
    0
  else
    if k == 0
      1
    else
      C(n-1,k-1)+C(n-1,k)
    end
  end
end