Функция линейки

Две тесно связанные серии в теории чисел

В теории чисел функция-линейка целого числа может быть одной из двух тесно связанных функций. Одна из этих функций подсчитывает количество раз, которое может быть разделено на два без остатка, что для чисел 1, 2, 3, ... равно $n$ $n$

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ... (последовательность A007814 в OEIS ).

Альтернативно, функцию линейки можно определить как те же числа плюс один, что для чисел 1, 2, 3, ... дает последовательность

1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, ... (последовательность A001511 в OEIS ).

Помимо того, что они связаны добавлением единицы, эти две последовательности связаны и другим образом: вторая может быть образована из первой путем удаления всех нулей, а первая может быть образована из второй путем добавления нулей в начале и между каждой парой чисел. Для любого определения функции линейки закономерности роста и падения значений этой функции напоминают длины отметок на линейках с традиционными единицами измерения, такими как дюймы . Эти функции следует отличать от функции Томаэ , функции на действительных числах , которая ведет себя аналогично функции линейки, когда ограничена двоичными рациональными числами .

В высшей математике функция линейки, основанная на 0, является 2-адической оценкой числа, ^[1] и лексикографически самым ранним бесконечным бесквадратным словом над натуральными числами. ^[2] Она также дает положение бита, который изменяется на каждом шаге кода Грея . ^[3]

В головоломке «Ханойская башня» , где диски головоломки пронумерованы в порядке их размера, функция линейки, основанная на 1, дает номер диска, который нужно переместить на каждом шаге в оптимальном решении головоломки. ^[4] Моделирование головоломки в сочетании с другими методами генерации ее оптимальной последовательности ходов может быть использовано в алгоритме для генерации последовательности значений функции линейки за постоянное время на значение. ^[3]

Ссылки

^ Эриксон, Алехандро; Исгур, Абрахам; Джексон, Брэдли В.; Раски, Фрэнк; Танни, Стивен М. (январь 2012 г.). «Вложенные рекуррентные соотношения с решениями, подобными решениям Конолли». Журнал SIAM по дискретной математике . 26 (1): 206–238 . arXiv : 1509.02613 . Bibcode : 2015arXiv150902613E. doi : 10.1137/100795425. ISSN 0895-4801. S2CID 8116882.
^ Guay-Paquet, Mathieu; Shallit, Jeffrey (ноябрь 2009 г.). «Избегание квадратов и наложений на натуральные числа». Дискретная математика . 309 (21): 6245– 6254. arXiv : 0901.1397 . doi : 10.1016/j.disc.2009.06.004 . S2CID 8646044.
^ ab Herter, Felix; Rote, Günter (ноябрь 2018 г.). «Бесциклическое перечисление кода Грея и башня Бухареста». Теоретическая информатика . 748 : 40–54 . arXiv : 1604.06707 . Bibcode : 2016arXiv160406707H. doi : 10.1016/j.tcs.2017.11.017. S2CID 4014870.
^ Хинц, Андреас М.; Клавжар, Санди; Милутинович, Урош; Петр, Кирилл (2013). Ханойская башня – мифы и математика. Базель: Springer Basel. стр. 60–61 . doi : 10.1007/978-3-0348-0237-6. ISBN 978-3-0348-0236-9.

Внешние ссылки

Вайсштейн, Эрик В. "Функция линейки". MathWorld .

Эта статья по теории чисел — заглушка . Вы можете помочь Википедии, расширив ее.

[1] Эриксон, Алехандро; Исгур, Абрахам; Джексон, Брэдли В.; Раски, Фрэнк; Танни, Стивен М. (январь 2012 г.). «Вложенные рекуррентные соотношения с решениями, подобными решениям Конолли». Журнал SIAM по дискретной математике . 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 г.). «Избегание квадратов и наложений на натуральные числа». Дискретная математика . 309 (21): 6245– 6254. arXiv : 0901.1397 . doi : 10.1016/j.disc.2009.06.004 . S2CID 8646044.

[herter-rote-3] Herter, Felix; Rote, Günter (ноябрь 2018 г.). «Бесциклическое перечисление кода Грея и башня Бухареста». Теоретическая информатика . 748 : 40–54 . arXiv : 1604.06707 . Bibcode : 2016arXiv160406707H. doi : 10.1016/j.tcs.2017.11.017. S2CID 4014870.

[4] Хинц, Андреас М.; Клавжар, Санди; Милутинович, Урош; Петр, Кирилл (2013). Ханойская башня – мифы и математика. Базель: Springer Basel. стр. 60–61 . doi : 10.1007/978-3-0348-0237-6. ISBN 978-3-0348-0236-9.