ウラム数

数学において、ウラム数は1964年に発表したスタニスワフ・ウラムによって考案され、その名が付けられた整数列である。 ^[1] 標準的なウラム数列（(1, 2)-ウラム数列）は、U ₁  = 1およびU ₂  = 2で始まる。次に、 n  > 2の場合、U _nは、2つの異なる前の項を正確に一方向に加算した最小の整数であり、前のすべての項よりも大きいと定義される。

定義の結果として、3はウラム数（1 + 2）であり、4はウラム数（1 + 3）です。（ここで、2 + 2は4の2番目の表現ではありません。前の項は異なる必要があるためです。）整数5はウラム数ではありません。5 = 1 + 4 = 2 + 3だからです。最初のいくつかの項は

1、2、3、4、6、8、11、13、16、18、26、28、36、38、47、48、53、57、62、69、72、77、82、87、97、99、102、106、114、126、131、138、145、148、155、175、177、180、182、189、197、206、209、219、221、236、238、241、243、253、258、260、273、282、...（シーケンスOEISのA002858 を参照。

ウラム数は無限に存在する。なぜなら、数列の最初のn個の数がすでに決定された後_{、数列をさらに1つの要素で拡張することが常に可能であるからである。U n} −1 + _U nは_最初のn個の数のうち2つの和として一意に表され、同様に一意に表される他のより小さな数が存在する可能性があるので、次の要素はこれらの一意に表せる数の中で最小のものとして選択することができる。^[2]

ウラムはこれらの数の密度はゼロであると推測したと言われているが^[3]、これらの数の密度は約0.07398であると思われる。^[4]

1 + 2 = 3 を除き、後続のウラム数は、その前の 2 つの連続するウラム数の合計になることはできません。

証明: n > 2 の場合、U _{n −1} + U _n = U _{n +1}が唯一の方法で必要な和であると仮定します。すると、U _{n −2} + U _{n も}唯一の方法で和を生成し、それはU _nとU _{n +1の間にあります。これは、} U _{n +1 が}次に小さいウラム数であるという条件と矛盾します。 ^[5]

n > 2の場合、連続する3つのウラム数（U _{n −1}、U _n、U _{n +1}）を整数辺としてとると三角形を形成します。^[6]

証明: 前の性質は、 n > 2 の場合、U _{n −2} + U _n ≥ U _{n + 1}であると述べています。したがって、U _{n −1} + U _n > U _{n +1であり、} U _{n −1} < U _n < U _{n +1 で}あるため、三角不等式が満たされます。

ウラム数の列は完全な列を形成します。

証明: 定義により、U _n = U _j + U _kとなり、 j < k < nであり、2つの異なるより小さなウラム数の和が正確に1つの方法で得られる最小の整数です。これは、n > 3 のすべてのU _nについて、 U _{j が}取り得る最大値はU _{n −3であり、} U _{k が}取り得る最大値はU _{n −1}であることを意味します。^{[5] [7]}

したがって、U _n ≤ U _{n −1} + U _{n −3} < 2 U _{n −1} かつU ₁ = 1、U ₂ = 2、U ₃ = 3 です。これは、ウラム数が完全な数列となるための十分な条件です。

n > 1 の整数ごとに、n ≤ U _j < 2 nを満たすウラム数U _{j が}少なくとも 1 つ存在します。

証明: ウラム数は無限にあり、1 から始まることが証明されています。したがって、n > 1 のすべての整数に対して、 U _{j −1} ≤ n ≤ U _jとなるj を見つけることができます。上記の証明から、 n > 3 の場合、U _j  ≤  U _{j −1}  +  U _{j −3}  < 2 U _{j −1}です。したがって、n  ≤  U _j  <  2U _{j −1}  ≤ 2 nです。また、 n = 2 および 3の場合も、計算によりこの特性が真となります。

連続する5つの正の整数{ i , i + 1,..., i + 4}（i >4）の列には、最大2つのウラム数が存在する。^[7]

証明: 数列 { i , i + 1,..., i + 4} の最初の値がi = U _jでウラム数であるとすると、 i + 1 が次のウラム数U _{j +1}である可能性があります。次にi + 2を考えます。これは、前の 2 つの項の一意の和ではないため、次のウラム数U _{j +2}にはなりません。 i + 2 = U _{j +1} + U ₁ = U _j + U ₂です。同様の議論がi + 3 とi + 4 にも当てはまります。

ウラム数は擬似ランダムであり、厳密な境界を持つには不規則すぎる。しかし、上記の性質、すなわち、最悪でも次のウラム数はU _{n +1} ≤ U _n + U _{n −2}であり、連続する5つの正の整数のうち最大2つがウラム数となり得ることから、次のように言える。

⁠5/2⁠ n −7 ≤ U _n ≤ N _{n +1 （} n > 0の場合）、 ^[7]

ここで、N _{n は}ナラヤナの牛の列の数字です: 1、1、1、2、3、4、6、9、13、19、...。 N ₀から始まる再帰関係N _n = N _{n −1} + N _{n −3}です。

最初の1000万個のウラム数は4つの要素を除いてを満たすことが観察されている^[8]（これは最初のウラム数で検証されている）。このタイプの不等式は通常、何らかの周期性を示す数列に当てはまるが、ウラム数列は周期的ではないようで、この現象は理解されていない。これを利用してウラム数列を高速に計算することができる（外部リンクを参照）。 ${\displaystyle \cos {(2.5714474995\,U_{n})}}0}$${\displaystyle \left\{2,3,47,69\right\}}$${\displaystyle 10^{9}}$

この考え方は、異なる開始値 ( u 、 v ) を選択することで、( u 、 v )-ウラム数として一般化できます。( u、  v ) - ウラム数列は 、連続する数列間の差の列が最終的に周期的である場合に正則です。vが3 より大きい奇数の場合、(2、  v ) -ウラム数は正則です。v が 1 (mod 4) かつ 5 以上と合同である場合、 (4、  v ) -ウラム数は再び正則です。ただし、ウラム数自体は正則ではないようです。^[9]

数列がs加法であるとは、数列の最初の2s項の後に、数列の各数が前の2つの数の和として正確にs個の表現を持つ場合である。したがって、ウラム数と( u ,  v )-ウラム数は1加法数列である。^[10]

一意に表現できる最小の数を付加するのではなく、最大の数に前の2つの数の和として一意に表現したものを付加して数列を形成すると、その結果得られる数列はフィボナッチ数列となる。^[11]

• Cassaigne, Julien; Finch, Steven R. (1995)、「1 加法シーケンスと二次回帰のクラス」(PDF)、Experimental Mathematics、4 (1): 49–60、doi :10.1080/10586458.1995.10504307、MR  1359417、S2CID  9985793
• フィンチ、スティーブン R. (1992)、「特定の 1 加法シーケンスの規則性について」、組み合わせ理論ジャーナル、シリーズ A、60 (1): 123–130、doi :10.1016/0097-3165(92)90042-S、MR  1156652
• ガイ、リチャード（2004）、数論における未解決問題（第3版）、シュプリンガー・フェアラーク、pp. 166-167、ISBN 0-387-20860-7
• Queneau, Raymond (1972)、「Sur les suites s -additives」、Journal of Combinatorial Theory、シリーズ A (フランス語)、12 (1): 31–71、doi : 10.1016/0097-3165(72)90083-0、MR  0302597
• レカマン、ベルナルド (1973)、「ウラムのシーケンスに関する質問」、アメリカ数学月刊誌、80 (8): 919–920、doi :10.2307/2319404、JSTOR  2319404、MR  1537172
• シュメル、ジェームズ; シュピーゲル、ユージン (1994)、「いくつかの 1 加法シーケンスの規則性」、組み合わせ理論ジャーナル、シリーズ A、66 (1): 172–175、doi :10.1016/0097-3165(94)90058-2、MR  1273299
• ウラム、スタニスワフ(1964a)、「無限集合における組合せ解析といくつかの物理理論」、SIAM Review、6 (4): 343–355、Bibcode :1964SIAMR...6..343U、doi :10.1137/1006090、JSTOR  2027963、MR  0170832
• ウラム、スタニスワフ（1964b）、現代数学の問題、ニューヨーク：ジョン・ワイリー＆サンズ社、p. xi、MR  0280310
• シュタイナーバーガー、ステファン (2015)、ウラム系列に隠されたシグナル、実験数学、arXiv : 1507.00267、Bibcode :2015arXiv150700267S

• MathWorld の Ulam シーケンス
• フィリップ・ギブスによるウラム数列の高速計算
• ドナルド・クヌースによるアルゴリズムの説明
• ダニエル・ロスのgithubページ