Help us understand the problem. What is going on with this article?

60年解けなかった数学の難題 世界中のPCつなぎ解決

https://digital.asahi.com/articles/ASMBL5481MBLULBJ00N.html?iref=comtop_favorite_02

この問題は1950年代、英国の数学者ルイス・モーデルが考え出した
そして今春、英ブリストル大のアンドリュー・ブッカー教授(整数論)が、大学のスーパーコンピューターで3週間計算して33の答えを出した。
 米MITのアンドリュー・サザーランド教授(計算数論)と協力し、数カ月かけて専用のプログラムを書いた。そして今年9月、50万台のパソコンに2日間計算させ、最後まで残っていた42の答えについに行き着いた。その答えは、次の17桁の三つだった。
-8京0538兆7388億1207万5974
 8京0435兆7581億4581万7515
 1京2602兆1232億9733万5631

note:この3つの数字をそれぞれ3乗して足すと42になる。
(-80,538,738,812,075,974)^3
+80,435,758,145,817,515^3
+12,602,123,297,335,631^3
-522413599036979150280966144853653247149764362110424+
 520412211582497361738652718463552780369306583065875+
   2001387454481788542313426390100466780457779044591
  =0000000000000000000000000000000000000000000000042

3乗は借り物ですが、筆算は力技です。。。

Function zentonumberstring(str As String) As String
Dim re As New RegExp
Dim MC As MatchCollection, M As Match
Dim i As Long, buf As String
With re
.Global = True
.IgnoreCase = False
.MultiLine = True
.Pattern = "([0-9]|\-)"
Set MC = .Execute(StrConv(str, vbNarrow))
For i = 0 To MC.Count - 1
buf = buf & MC.Item(i).Value
Next i

zentonumberstring = buf
End With
End Function

image.png
4桁ずつ区切って計算すると不思議な連続が現れる。
image.png
ここから上の筆算に飛んだ。
一定のパターンでマイナスになるなら、途中とはじめが0になるなら、概ね繰り上がりを前提にしても0になる
100から上は、すべての桁が n-n = 0、繰り上がって1を足してと+10+n-n or という結果になり、たぶん0になる。
以上から42が求められそうである。
一応20桁近く計算して死にました。だって51桁ある。上の52はすぐ消えるから49桁。数が悪い。。。

このニュースの前段

Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33
https://www.quantamagazine.org/sum-of-three-cubes-problem-solved-for-stubborn-number-33-20190326/
33は3つの立方数の和で表せるのか——64年来の数学上の難題が解かれる fabcross 2019/5/7
日本語版が下のリンクだが、動画がない。

この動画にアルゴリズムのヒントがある

IMAGE ALT TEXT HERE
33を発見したときはスパコンを3週間走らせた。
しかし、33より42のほうが計算量が多い。つまりスパコンを3週間走らせた数の中に42がなかったことを同時に見つけている

推定

ここでスパコンから切り替えたのは、42がなく、これ以上数を大きくすれば、組み合わせ爆発が起きることがわかったためであろう。
IMAGE ALT TEXT HERE
8*8のとき
3266598486981642通り
計算時間4時間半
9*9のとき
41044208702632496804通り
計算時間 6年半
ここで組み合わせ爆発が起きている
10*10
1568758030464750013214100通り
計算時間 25万年
11*11
290億年
ところが最新のアルゴリズムを使うと
16*16
数十分

3乗して42になる組み合わせも、スパコンで3万年かかるということだったのかもしれない。
そして33になる組み合わせの発見から5か月、今まで計算した結果を除き、アルゴリズムをさらに改良し、分散型システムで50万台のPCを走らせる方法に変更し42になる組み合わせが見つかったということになる。したがって、組み合わせ爆発を回避し、あたりをつけた組み合わせを50万台のPCで計算させるプログラムだったということになるだろう。
おそらくアルゴリズム自体はそこまで進化はしていない。 33を発見してから5か月しかたっていないからだ。x2+xy+y2...という式から計算量を推定できたことから、50万台のPCにそれぞれある3乗の組み合わせを計算させていると考えられる。
仮に計算した数の組み合せを計算するのに1時間かかるとする(実際はもっと短いため、もっと多い、しかし1秒では計算できないとする)
すると2日で48通りの組み合わせを計算するので
48×50万=2400万通り
しかし、答えの数字が8京なので、この2倍(正負)の3つ16^3京の組み合わせからすればきわめて少ない組み合わせを抜き出しているということがわかる。かりにPCの1つが100分の1秒で計算できたとしても6000倍程度にしかならない。10の16乗の3乗ということは48桁になっているので、この程度の差はないに等しい(嘘)。

この記事の意味

総当たりではなくあたりをつけろ

今はビッグデータで何でもかんでも個人情報を抜いてプライバシーを丸裸にして監視社会にすれば便利な世の中になると考えられているが、残念ながらこのような革新的な結果はあまり得られていない。それもそのはずで、そういうことをしなくても標本調査という技術があり、だいたいそれで結論が出るためである。ビッグデータが言われるほど目覚ましい成果がなく、ことごとく凡庸な結論(標本調査で分かるレベル)に至るのは標本調査が正しいことを証明している。
しかも総当たりでは解決ができず、むしろあたりをつけたほうが解決に至るということを証明している。つまりビッグデータはあまり役立たないし非常に効率が悪い、ということをこの結果から判断することができる。

Gizmode

人生、宇宙、すべての答えの「42」を3つの立法数の和で表す難問がついに解ける

ほんで、そこからアルゴリズムを考えて、大学のスパコン(動画の7分ぐらいから出てくる)をガンガン回し続けて3週間。1に16個0がつく桁(1京)まで総当たりして、ようやく2月の朝、子どもを学校に送って大学に向かう途中でビンゴ!と解けたんだそうですよ? 「思わず飛び上がって喜んだ」と動画では仰ってます。力なく笑う顔(たぶん一番うれしいときの顔がこれなんでしょね)がどことなくリッキー・ジャヴェイスみたいでかわゆす。

42に続き3の難問もあっさり解決!地球スパコン連続快挙

今月上旬に42の解を求めたときと同じように、今回も計算で使ったのは、全世界の研究員の自宅パソコンの余った処理パワーを結集したクラウドスパコン「Charity Engine」です。大学側の発表によると、かかった処理時間は全世界で約400万時間。本当ならもっと時間がかかるのですが、過去の理論で9の倍数との間隔に一定のパターンが確認されていることから、それでターゲットを絞って処理を早めたそうですよ。

想定の通りのようだ。

むおおおおーーー!!!ぬあんじゃこれは。これだけのプラスマイナスを旅して3に戻るなんて、憧れます。目がちらちらして数字拾えない人は下記でどうぞどうぞ。

569936821221962380720^3 + (-569936821113563493509)^3 + (-472715493453327032)^3 = 3

計算を放棄しないほうが美しい状況が見える。

185131426470358721030003064550489120286063150089838997749248000-
185131426364725746289073278168542399539619802127338908944671229-
         105632974740929786381946720746443347962500088804576768

この3乗は最大68桁に及んでおり、42の51桁より17桁多い。そして上位9桁は第1、第2の数で消える。

アルゴリズムである程度効率化

アルゴリズムはPCで計算可能か、あるいは下記のビッグデータが使える場合でも該当するが、現在の計算困難な問題は計算量が非常に多いものしか残っていない。このため、PCはこれまで一貫していかに早く計算できるかということが課題だったが、これからは効率よく計算できるかが課題となると考えられる。 http://sevendays-study.com/algorithm/ex-day2.html Brute-force algorism https://www.slideshare.net/kazumamikami1/ss-16964389 からKMP法への流れはその例といえるだろう。

名言ナビによるとルイス・モーデルは次のように言ったという

https://meigennavi.net/word/234/234510.htm
(数学において)計算よりもむしろ考え方を主な拠り所とした解答は、知性に糧を与えるものである。
考え方はこんなにも簡単で、それからこんなにも重要な結果が導かれるのかと、ただただ驚くようなこともよくある。
これほどわずかなものから、これほど多くのものが得られるとは、とても信じられないくらいである。
https://meigennavi.net/word/255/255582.htm
数学者がコンピューターを扱う上であてにできるのは、せいぜい速さである。
すなわち、彼が機械にかけようとする問題に対する計算の速さである。

Andrew Bookerさんのプロフィール






https://www.sciencealert.com/the-sum-of-three-cubes-problem-has-been-solved-for-42

その後の数十年にわたって、より簡単な数のソリューションが見つかりました。 2000年、ハーバード大学の数学者Noam Elkiesは、より難しいアルゴリズムを見つけるのに役立つアルゴリズムを開発しました 。
今年、最も困難なのは33と42だけでした。
次に、人気の数学チャンネルNumberphileの33の問題に関するYouTubeビデオを視聴した後、英国のブリストル大学の数学者Andrew Bookerは、 新しいアルゴリズムを書くことに触発されました 。 彼はこれを大学のAdvanced Computing Research Centreの強力なスーパーコンピューターで実行し、 わずか3週間後に33のソリューションを得ました 。

Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33
これは33のとき(2019/03)かかれたものだが、アルゴリズムの研究自体は2000年くらいから続いている。
42 is the answer to the question “what is (-80538738812075974)³ + 80435758145817515³ + 12602123297335631³?”
Tweeを紹介したRobin氏の記事によると、どさくさに紛れて165,795,965も発見しているようだ

次のKは114

1000より小さい数で3乗の数で表現できる組み合わせが見つかっていないもののうち最小のものは114。
これが次のターゲットだ。
また、3のアナザーも重要。
3つあったら4つめがある。
IMAGE ALT TEXT HERE
ヒルベルト第10問題と関連。

NumberPhileは今日も絶好調

IMAGE ALT TEXT HERE
今回副次的にわかったことは、一連の中でこのYoutubeのNumberphileが貢献しているということ(混乱させたこともあるが)。一昨日のビデオ、やめろ、Tree(g64)とかやめろ、死ぬぞまじで。

ではビッグデータが役立つときとは

本題に戻ろう。ビッグデータは詐欺商法だと真実を暴いていても意味がないので、反対にビッグデータが役だったときなどを参考に、どういう場合なら役立つ時を考えてみよう

その性質が整数で表現され、除算がないもの

今回の技術でも明らかになったように、また演算誤差という特性からPCが整数の計算で除算がない場合は誤差が生じないプログラミングが可能である。Windowsはデフォルトでは最大32桁程度しかないので、こうした16桁以上の3乗の計算はプログラムを組まなければならないが、演算誤差も起きにくい。このような整数の計算に問題を落とし込めれば、解決が見込める。

アルゴリズムである程度効率化できるもの

ビッグデータは総当たりは組み合わせ爆発が容易に起きるので全く意味がない金の無駄としか言いようがないが、反対にアルゴリズムによって高速に計算できれば意味があるといえる。

標本調査でもみつからないもの

標本調査の正しさを超える例はないといっていいので、そうした推計が効かない、あるいはできないものにも有効だろう。
この例として、成人T細胞白血病リンパ腫における遺伝子異常の解明を上げたい。約400例のATL症例について網羅的に遺伝子解析を行っている。ということは発症していない、あるいは発症しにくい遺伝子異常が除かれている、というバイアスの存在があるかもしれない(実際キャリア3000人に対して1人しか発症しない)。しかしこのように要素が多数に及ぶときは標本調査が困難で、ビッグデータの分析が有効な場合があるということが言える。とくに疫学の分野は有効な場合があるだろう。
なお余談だが、このHTLV-1というのはレトロウィルスの1種であり、このレトロウィルスとの闘いこそスパコンの活躍が期待されるところだといえる。というのも、このレトロウィルス科のウィルスは1部を除いて進行が極めて遅く、必ずしも発症しない。しかもその症例が少ないことが多い。新薬を開発しようとしても回収できないし、試験もできないため、製薬会社も薬が作れないからだ。
詳細はあとの文章を見てもらうとして一つ肺がん治療薬の有効性予測という問題で、グループはこう述べている。
スパコン・京の予測システムで肺がん治療薬の有効性を予測 慶應大や京大

グループは、「がんゲノム医療の現場で見つかる、治療が明らかではない遺伝子変異に対して、有効な治療薬を選択し、より早く多くのがん患者に最適な薬剤を届けることにつながる成果だ」とコメントしている。実用化を目指し、他の遺伝子にも適応を拡大したい考えだ。

これも標本調査が困難な例といえるだろう。しかしこの国は平気で疫学のデータを改ざんするので、ビッグデータも疫学もあまり意味もない。
以上からビッグデータの役立つ場合は3乗して合計すると3になる数の組合せより少ない。

<以下参考記事>

https://www.ncc.go.jp/jp/information/pr_release/2015/1006/index.html
成人T細胞白血病リンパ腫における遺伝子異常の解明
2015年10月6日

概要

成人T細胞白血病・リンパ腫(adult T-cell leukemia lymphoma: ATL)は、日本を主要な流行地域の一つとするヒトT細胞白血病ウイルス1型(human T-cell leukemia virus type-1: HTLV-1)感染によって生じる極めて悪性度の高い血液がんの一つです。乳児期にHTLV-1ウイルスに感染したT細胞に、数十年間にわたってさまざまな遺伝子の変化が生ずることによってATLの発症に至ると考えられていますが、従来こうした遺伝子の変異については多くが不明のままでした。
今回の研究の主な成果は以下の点です。

  1. 最先端の遺伝子解析手法とスーパーコンピューティングを用いた統合的な解析によって、これまで同定されていなかった多数の新規の異常を含むATLの遺伝子異常の全体像の解明に成功しました。
  2. 今回同定された異常は、PLCG1、PRKCB、CARD11、VAV1、IRF4、FYN、CCR4、CCR7などの機能獲得型変異、CTLA4-CD28、ICOS-CD28などの融合遺伝子、CARD11、IKZF2、TP73などの遺伝子内欠失などからなります。これらの異常は、T細胞受容体シグナルの伝達をはじめとする、T細胞の分化・増殖などのT細胞の機能に深く関わる経路や、がん免疫からの回避に関わる経路に生じており、こうした異常によって正常なT細胞の機能が障害される結果、T細胞のがん化が生じてATLの発症に至ると考えられました。
  3. 特に、ホスホリパーゼCやプロテインキナーゼC、FYNキナーゼ、ケモカイン受容体など、同定された変異分子の多くが新規治療薬剤の開発に向けた有望な標的と考えられました。

本研究は、ATLについて行われた過去最大規模の遺伝子解析研究です。さまざまな手法を組み合わせることにより包括的にATLの遺伝子異常を明らかにすることに成功しました。本研究の結果は、ATLの病気の仕組みの解明に大きな進展をもたらすのみならず、今後、本疾患を克服するための診断や治療への応用が期待されます。

本研究は、厚生労働省ならびに2015年度からは日本医療研究開発機構(AMED)の「革新的がん医療実用化研究事業」、科学研究費助成事業新学術領域研究(22134006)、HPCI戦略プログラム利用研究(hp140230)、国立がん研究センター研究開発費(26-A-6)の支援を受けて行われたもので、その成果は、2015年10月6日付で国際科学誌「Nature Genetics」電子版にて公開されます。
背景

成人T細胞白血病リンパ腫(adult T-cell leukemia lymphoma: ATL、図1)はヒトT細胞白血病ウイルス1型(human T-cell leukemia virus type-1: HTLV-1)の感染によって生じる血液がんの一つです。現在日本だけでも約120万人(全世界で2,000万人)が同ウイルスに感染しており(HTLV-1キャリア)、このうち年間1,000人程度(生涯で5%)の方がATLを発症すると推定されています。本疾患は極めて悪性度の高いがんで、ひとたび発症すれば既存の抗がん剤では十分な治療効果を得ることが難しく、同種造血幹細胞移植を除いて根治的な治療手段は知られていません。ATLは、乳児期に主として母乳を通じてHTLV-1ウイルスがT細胞に感染したのち、数十年の年月を経て発症に至ります。この間に感染したT細胞に蓄積する「遺伝子の変異」がその本質的な原因になっていると考えられています。従って、本症の克服のためには、その発症に関わるこれらの遺伝子の異常を同定することによってその分子メカニズムを解明し、これに基づいて新たな発症予測の方法や有効な治療薬剤の開発を行うことが重要となります。しかし、従来こうしたATLの発症に関わる遺伝子の異常については多くが不明のままでした。
研究方法と結果
次世代シーケンサーとスーパーコンピュータによる塩基配列の解読

今回、主に国内7施設・グループ(宮崎大学、国立がん研究センター、HTLV-1感染者コホート共同研究班、熊本大学、京都大学、長崎大学、佐世保市立総合病院)から合計426例のATLの検体を採取し、京都大学にて包括的な遺伝子解析を行いました。今回の研究では、全エクソン解析・全ゲノム解析・トランスクリプトーム解析などの次世代シーケンサーを用いた解析およびマイクロアレイを用いたコピー数異常やDNAメチル化の解析を組み合わせて、さまざまな遺伝子の異常を網羅的に明らかにしました。この大規模なデータ解析は、東京大学医科学研究所附属ヒトゲノム解析センターと共同でスーパーコンピュータ「京」を利用することにより可能となりました。

T細胞受容体シグナリング/NF-κB経路への遺伝子異常の集積

本研究の解析の結果、ATLにおける遺伝子異常の最も顕著な特徴は、T細胞受容体シグナリング/NF-κB経路に遺伝子異常が高度に集積することであることが明らかになりました(図3)。全体の90%以上を超える症例にこの経路の少なくとも一つの遺伝子異常を認め、この経路の異常がATLの病態において中心的な役割を果たすことが示唆されました。中でも、PLCG1(36%)、PRKCB(33%)、CARD11(24%)、VAV1(18%)、IRF4(14%)、FYN(4%)変異などの機能獲得型変異(遺伝子の機能が亢進する、あるいは新たな機能を獲得するタイプの変異)が多数認められることが特徴と考えられました(図4)。この中でもPRKCB変異はプロテインキナーゼCファミリーというがんにおいて大変重要な機能を持つタンパク群で初めて同定された機能獲得型変異でありました。最も頻度が多かったPRKCB D427N変異を用いた、機能を検証する実験においても、この変異によりNF-κB経路が活性化することが明らかにされました。さらに、このPRKCB変異はCARD11変異と共存することが多いこと、両者は機能的にも協調してNF-κB経路を活性化することが明らかになりました。

https://www.ncc.go.jp/jp/information/pr_release/2019/0430/index.html

慶應義塾大学医学部内科学(呼吸器)教室の安田浩之専任講師、肺がん病態制御寄附講座浜本純子特任助教、腫瘍センターの池村辰之介助教、臨床研究推進センターの副島研造教授と、京都大学大学院医学研究科人間健康科学系専攻の鎌田真由美准教授、荒木望嗣特定准教授、奥野恭史教授、国立がん研究センター先端医療開発センターの土原一哉トランスレーショナルインフォマティクス分野長、小林進ゲノムトランスレーショナルリサーチ分野長、同東病院の後藤功一呼吸器内科長、松本慎吾医長、同研究所の河野隆志ゲノム生物学研究分野長らのグループは、LC-SCRUM-Japanで構築した日本最大の臨床ゲノムデータを活用し、スーパーコンピュータ「京」を用いた予測システムにより、肺がんの遺伝子変異に対する薬剤有効性が高精度に予測可能なことを確認しました。

がんゲノム医療(注1)の普及により、さまざまな遺伝子の変異が同定され、治療薬(分子標的薬)の効果が予測されていますが、稀な遺伝子変異に対しては投薬効果の予測が難しく、薬剤を選ぶ上で大きな障害となっていました。

今回、研究グループでは、日本人の肺がんで最も多く変異の見られるEGFR遺伝子(注2)に注目し、約2,000例の肺がんの遺伝子変異を分析しました。その結果、稀なEGFR遺伝子変異をもつ肺がんに対して治療効果の高い抗がん剤をスーパーコンピュータ「京」を用いて高精度に予測することができました。超高速・高性能な計算機を用いたこのシステムを実用化することで、より多くの肺がん患者に迅速に、有効性が高い治療薬を選ぶことが可能になると期待されています。また、他の多くの遺伝子にも適応を拡大することで、がんゲノム医療の進歩に大きく貢献することが予想されます。

抗がん剤と抗菌剤の種類が1万あったとして、このうちから2つ選んで組み合わせて最適なものを、あるいは避けるべきものを導き出す。
チェックする要素が1000あるとする。
https://www.ganchiryo.com/prevention/anticancer_drug.php

するとこの組み合わせの近似値は、1億×1000×1億×1000程度でこれは当期時の話題からスパコンで短時間で計算できそうだ。
(もっとも薬品の種類はこんなに多くなく、禁忌、副作用等で決めるため決定要素もここまで多くないが、全くわからないものはスケールは大きくとるしかない)

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした