東方の海

サブカル考察など。

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

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

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

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

スポンサーサイト
2016.05.31 03:14 | 数学 | トラックバック(-) | コメント(0) |

素因数分解を多項式時間で解く方法の資料らしきものについて

素因数分解を多項式時間で解く方法については様々議論されています。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予想の解決までいくものではない気がします。もし解読できる方がいましたらぜひ挑戦してみてください。

2016.05.31 02:59 | 数学 | トラックバック(-) | コメント(0) |

プリクラ問題まとめと総探索Rubyコード

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

という問題提起から始まったものです。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
2016.03.08 01:40 | 数学 | トラックバック(-) | コメント(0) |
| ホーム |