Хаотическая последовательность Хофштадтера

[fregimus]

Последовательность Хофштадтера (D.Hofstadter 1979,1999; GEB) задается рекуррентной формулой

Идея подобна последовательности Фибоначчи, только немного запутаннее. В последовательности Фибоначчи мы берем два предыдущих члена и складываем, чтобы получить следующий. В последовательности Хофштадтера мы берем два предыдущих члена, для каждого из них отсчитываем столько шагов назад, чему равен этот член, и теперь уже эти найденные элементы складываем.

Первые 500 элементов последовательности (20 в ряд):

1	1	2	3	3	4	5	5	6	6	6	8	8	8	10	9	10	11	11	12
12	12	12	16	14	14	16	16	16	16	20	17	17	20	21	19	20	22	21	22
23	23	24	24	24	24	24	32	24	25	30	28	26	30	30	28	32	30	32	32
32	32	40	33	31	38	35	33	39	40	37	38	40	39	40	39	42	40	41	43
44	43	43	46	44	45	47	47	46	48	48	48	48	48	48	64	41	52	54	56
48	54	54	50	60	52	54	58	60	53	60	60	52	62	66	55	62	68	62	58
72	58	61	78	57	71	68	64	63	73	63	71	72	72	80	61	71	77	65	80
71	69	77	75	73	77	79	76	80	79	75	82	77	80	80	78	83	83	78	85
82	85	84	84	88	83	87	88	87	86	90	88	87	92	90	91	92	92	94	92
93	94	94	96	94	96	96	96	96	96	96	128	72	96	115	100	84	114	110	93
106	124	82	101	111	108	118	104	108	106	114	104	114	109	100	109	120	112	108	118
106	105	130	110	114	115	112	107	120	114	122	121	120	114	138	110	122	119	120	130
132	113	133	123	118	125	121	129	122	136	129	116	149	137	120	123	143	146	107	139
138	139	135	120	146	135	143	129	151	133	135	136	148	148	136	144	143	152	129	139
151	140	148	136	151	159	125	147	153	148	154	152	136	152	155	146	144	162	151	157
154	149	160	155	152	155	162	154	159	153	165	157	154	168	161	156	160	168	153	169
170	159	161	172	161	168	161	172	171	161	171	172	167	172	172	168	175	170	171	173
174	175	175	174	176	174	177	182	175	178	178	184	177	178	184	180	179	186	179	185
185	184	186	184	187	188	186	186	188	190	187	188	190	192	188	192	190	192	192	192
192	192	192	256	135	202	210	188	200	220	186	196	202	242	149	201	229	171	193	238
188	193	206	228	202	193	220	196	210	202	214	220	182	217	234	204	208	215	215	222
218	194	231	186	216	236	210	240	204	211	230	230	164	234	241	239	214	220	222	230
222	222	212	226	228	230	228	230	214	228	252	203	242	233	219	252	230	215	243	238
242	228	244	228	228	238	240	221	249	228	238	237	248	237	231	238	245	250	234	239
234	262	228	228	286	239	235	271	249	240	242	252	261	233	253	268	243	234	269	257

Никакой системы не видно, но заметно, что значения близки к n/2. Поэтому интересно будет посмотреть на разность каждого члена с половиной его номера в последовательности. Эта разность тоже будет слегка расти с ростом n, поэтому имеет смысл, изображая ее графически, поделить на небольшую степень n. Мы рассмотрим точечные графики последовательности, заданной формулой . Конечное n с каждым графиком удваивается.

 

Фрактальненько?

Comments

[ai-enable.livejournal.com]

похоже на диаграмму-бабочку. А так - фрактальненько... ((:

[fregimus.livejournal.com]

Похоже? Ну, может быть.

[alverena.livejournal.com]

Похоже на ёлку, повёрнутую на 90 градусов. =)

[fregimus.livejournal.com]

Точно!

[dmitry-thinker.livejournal.com]

Последовательность взята непосредственно из ГЭБ? Или Хофштадтер где-то ещё об этом писал? Интересно!

[fregimus.livejournal.com]

Стр. 137 во втором издании. Больше не встречал нигде.

[zwh.livejournal.com]

можно попытаться сделать wav файл и прослушать

[fregimus.livejournal.com]

Ничего неожиданного.

[zwh.livejournal.com]

и правда :)

[janatem.livejournal.com]

А что особенного в точках (примерно): ..., 375, 750, 1500, 3000, 6к, 12к ?
Перед этими точками "дисперсия" уменьшается, а потом резко возрастает. Из формулы как-то неочевидно наличие таких особенностей.

[fregimus.livejournal.com]

Видно, что-то есть. В хаосе непременно должен быть порядок, иначе это какой-то неправильный хаос.

странные последовательности

[falcao.livejournal.com]

"Хаотичненько", я бы сказал! :)

В таблицах у Вас числа слились -- видимо, из-за трёхзначности.

Из моих любимых примеров последовательностей с "непонятным" поведением я могу назвать такую: первый член равен 8, а каждый следующий получается из предыдущего по такому правилу: если x делится на 3, то далее идёт 2x/3; если не делится, то округляем 4x/3 до ближайшего целого. То есть получается 8, 11, 15, 10, 13, 17, 23, 31, 41, ... .

Неизвестно, что происходит далее. Например, "зацикливается" ли это дело. Эту последовательность также легко развернуть в обратную сторону -- перед 8 идёт 12, потом 18, 27, 20 и так далее.

Re: странные последовательности

[fregimus.livejournal.com]

Числа слились — Вы, наверное, смотрите в Вашем стиле? У меня не сливаются ни в FF3, ни в IE7. Попробуйте вот так посмотреть: http://fregimus.livejournal.com/39568.html?format=light

Да, интересная последовательность. Надо будет подумать.

форматы

[falcao.livejournal.com]

В таком изображении всё видно как надо (у меня MSIE6). А что это за формат "лайт"? И какие бывают "исчо"?

Re: форматы

[fregimus.livejournal.com]

Вот тут есть кое-что:
lj://faq/259/
lj://faq/177/ (s2id=, styleid=)
lj://faq/175/ (style=mine, mode=reply)

[denv23.livejournal.com]

Здравствуйте!
попал на в ваш журнал по ссылке на переведенное вами эссе "Плач математика".
(спасибо большое за перевод!!!)
там вы сказали, что выкладываете "сырой" вариант перевода и анонсированли , что "будет и полный текст в виде одного файла, уже откорректированный, но на это потребуется некоторое время."

вот хотелось бы узнать - вы его здесь в окончательном виде еще не выкладывали? вдруг, я что-то пропустил... ;-)

извините за такой _потребительсткий_ вопрос, но уж оочень понравилась статья и хотел сохранить её для себя.

спасибо. :)

[fregimus.livejournal.com]

Нет-нет, Вы правы совершенно, что спрашиваете — в же обещал, но вот запустил. Постараюсь в ближайший день-два выложить.

Где такое дают?

[termometr.livejournal.com]

и мне мистер Шухарт, и мне!..

Re: Где такое дают?

[fregimus.livejournal.com]

Пока здесь: http://fregimus.livejournal.com/27820.html

Re: Где такое дают?

[termometr.livejournal.com]

спасибо.

[termometr.livejournal.com]

Это отображение - дискретный аналог уравнения Хатчинсона для процессов с памятью. Одно из сложнейших уравнений для интегрирования.

Где Вы их только находите? :)

[fregimus.livejournal.com]

Аналог — не аналог, но идея похожая, да, — функция задает еще «сдвиг во времени», если бы аргумент был временем.

[termometr.livejournal.com]

отображения - дискретный аналог дифуров. В них время как бы есть...

Так где откопали-то?
и когда музыку фликкер-шума будем уже слушать?

[fregimus.livejournal.com]

Ну в первой же строчке написано: у Хофштадтера, в GEB. Во втором издании — на с. 137.

Музыку? Не-а, танцев сегодня не будет.

[termometr.livejournal.com]

жаль. у меня еще столько идей! :)

[dorinem.livejournal.com]

Ужжжжжасно интересно, спасибо!

[fregimus.livejournal.com]

Пожалуйста, рад, что понравилось.

[knop.livejournal.com]

http://www.research.att.com/~njas/sequences/A005185

[fregimus.livejournal.com]

Спасибо. Надо будет посмотреть библиографию. Интересная последовательность.