定規機能

数論において、整数の定規関数 $n$ 密接に関連する2つの関数のいずれかになります。これらの関数の1つは、 $n$ は 2 で割り切れる。1、2、3、… の場合、

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ... ( OEISのシーケンスA007814 )。

あるいは、ルーラー関数は同じ数に1を加えたものとして定義でき、1、2、3、...の数に対しては次の数列を生成します。

1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, ... ( OEISのシーケンスA001511 )。

これら 2 つの数列は、1 を加えることで関連付けられるだけでなく、別の方法でも関連付けられています。2 番目の数列は、1 番目の数列からすべてのゼロを取り除くことで形成でき、1 番目の数列は、2 番目の数列の先頭とすべての数値のペアの間にゼロを追加することで形成できます。定規関数のどちらの定義でも、この関数の値の上昇と下降のパターンは、インチなどの従来の単位を持つ定規の目盛りの長さに似ています。これらの関数は、二進有理数に限定すると定規関数と同様の挙動を示す実数上の関数であるトマエ関数とは区別する必要があります。

高度な数学では、0 ベースの定規関数は、数の2 進評価であり、 ^{[ 1 ]}自然数上の辞書式順序で最も早い無限平方フリー語です。[ 2 ]また^{、グレイコード}の各ステップで変化するビットの位置も示します。^{[ 3 ]}

ハノイの塔パズルでは、パズルの円盤がサイズ順に番号付けされており、1 から始まる定規関数は、パズルの最適な解法において各ステップで移動させる円盤の番号を示します。^{[ 4 ]}パズルのシミュレーションは、最適な移動シーケンスを生成する他の方法と組み合わせて、定規関数の値のシーケンスを値ごとに定数時間で生成するアルゴリズムに使用できます。^{[ 3 ]}

参考文献

↑ Erickson, Alejandro; Isgur, Abraham; Jackson, Bradley W.; Ruskey, Frank; Tanny, Stephen M. (2012 年 1 月). "Conolly 型解を持つ入れ子になった漸化式" . SIAM Journal on Discrete Mathematics . 26 (1): 206– 238. arXiv : 1509.02613 . Bibcode : 2015arXiv150902613E . doi : 10.1137/100795425 . ISSN 0895-4801 . S2CID 8116882 .
↑ Guay-Paquet, Mathieu; Shallit, Jeffrey (2009年11月) 「自然数における平方数と重複の回避」 . Discrete Mathematics . 309 (21): 6245–6254 . arXiv : 0901.1397 . doi : 10.1016/j.disc.2009.06.004 . S2CID 8646044 .
1 2 Herter, Felix; Rote, Günter (2018 年 11 月). "ループなしグレイコード列挙とブカレストの塔" . Theoretical Computer Science . 748 : 40– 54. arXiv : 1604.06707 . Bibcode : 2016arXiv160406707H . doi : 10.1016/j.tcs.2017.11.017 . S2CID 4014870 .
↑ヒンツ、アンドレアス M.クラヴジャール、サンディ。ミルティノヴィッチ、ウロシュ。ペトル、シリル (2013)。ハノイの塔 – 神話と数学。バーゼル：シュプリンガー・バーゼル。 pp. 60–61 .土井: 10.1007/978-3-0348-0237-6。ISBN 978-3-0348-0236-9。

外部リンク

ワイススタイン、エリック W. 「定規関数」 . MathWorld .

[1] Erickson, Alejandro; Isgur, Abraham; Jackson, Bradley W.; Ruskey, Frank; Tanny, Stephen M. (2012 年 1 月). "Conolly 型解を持つ入れ子になった漸化式" . SIAM Journal on Discrete Mathematics . 26 (1): 206– 238. arXiv : 1509.02613 . Bibcode : 2015arXiv150902613E . doi : 10.1137/100795425 . ISSN 0895-4801 . S2CID 8116882 .

[2] Guay-Paquet, Mathieu; Shallit, Jeffrey (2009年11月) 「自然数における平方数と重複の回避」 . Discrete Mathematics . 309 (21): 6245–6254 . arXiv : 0901.1397 . doi : 10.1016/j.disc.2009.06.004 . S2CID 8646044 .

[herter-rote-3] 1 2 Herter, Felix; Rote, Günter (2018 年 11 月). "ループなしグレイコード列挙とブカレストの塔" . Theoretical Computer Science . 748 : 40– 54. arXiv : 1604.06707 . Bibcode : 2016arXiv160406707H . doi : 10.1016/j.tcs.2017.11.017 . S2CID 4014870 .

[4] ヒンツ、アンドレアス M.クラヴジャール、サンディ。ミルティノヴィッチ、ウロシュ。ペトル、シリル (2013)。ハノイの塔 – 神話と数学。バーゼル：シュプリンガー・バーゼル。 pp. 60–61 .土井: 10.1007/978-3-0348-0237-6。ISBN 978-3-0348-0236-9。

[ 1 ]

、グレイコード

[ 3 ]

[ 4 ]