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

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

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 Journal по дискретной математике . 26 (1): 206–238. arXiv : 1509.02613 . Бибкод : 2015arXiv150902613E . дои : 10.1137/100795425 . ISSN 0895-4801 . S2CID 8116882 .
^ Гуай-Паке, Матье; Шалит, Джеффри (ноябрь 2009 г.). «Избегание квадратов и совпадений натуральных чисел» . Дискретная математика . 309 (21): 6245–6254. arXiv : 0901.1397 . дои : 10.1016/j.disc.2009.06.004 . S2CID 8646044 .
^ Jump up to: ^а ^б Гертер, Феликс; Роте, Гюнтер (ноябрь 2018 г.). «Безцикловое перечисление кода Грея и Бухарестская башня» . Теоретическая информатика . 748 : 40–54. arXiv : 1604.06707 . Бибкод : 2016arXiv160406707H . дои : 10.1016/j.tcs.2017.11.017 . S2CID 4014870 .
^ Хинц, Андреас М.; Клавжар, Санди; Милутинович, Урош; Петр, Кирилл (2013). Ханойская башня – мифы и математика . Базель: Springer Basel. стр. 60–61. дои : 10.1007/978-3-0348-0237-6 . ISBN 978-3-0348-0236-9 .

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

Вайсштейн, Эрик В. «Функция линейки» . Математический мир .

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

[1] Эриксон, Алехандро; Исгур, Авраам; Джексон, Брэдли В.; Раски, Фрэнк; Тэнни, Стивен М. (январь 2012 г.). «Вложенные рекуррентные отношения с решениями, подобными Конолли» . SIAM Journal по дискретной математике . 26 (1): 206–238. arXiv : 1509.02613 . Бибкод : 2015arXiv150902613E . дои : 10.1137/100795425 . ISSN 0895-4801 . S2CID 8116882 .

[2] Гуай-Паке, Матье; Шалит, Джеффри (ноябрь 2009 г.). «Избегание квадратов и совпадений натуральных чисел» . Дискретная математика . 309 (21): 6245–6254. arXiv : 0901.1397 . дои : 10.1016/j.disc.2009.06.004 . S2CID 8646044 .

[herter-rote-3] Jump up to: ^а ^б Гертер, Феликс; Роте, Гюнтер (ноябрь 2018 г.). «Безцикловое перечисление кода Грея и Бухарестская башня» . Теоретическая информатика . 748 : 40–54. arXiv : 1604.06707 . Бибкод : 2016arXiv160406707H . дои : 10.1016/j.tcs.2017.11.017 . S2CID 4014870 .

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

[1]

[2]

[3]

[4]