Сиракузская последовательность

М. Л. Гервер

По любому натуральному n строится последовательность s(n) = {s1, ..., sk, ...}:

s1=n,   sk+1=sk/2, если sk четно,   sk+1=(3sk+1)/2, если sk нечетно.

В математическом фольклоре s(n) известна много лет под названием сиракузская последовательность. Значения s(n), вычисленные на компьютере для всех n<240, после хаотического блуждания с завораживающим постоянством приходят к 1.

Пример s(31) приходит к 1 за 68 шагов: 31, 47, 71, 107, 161, 242, 121, 182, 91, 137, 206, 103, 155, 233, 350, 175, 263, 395, 593, 890, 445, 668, 334, 167, 251, 377, 566, 283, 425, 638, 319, 479, 719, 1079, 1619, 2429, 3644, 1822, 911, 1367, 2051, 3077, 4616, 2308, 1154, 577, 866, 433, 650, 325, 488, 244, 122, 61, 92, 46, 23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1.

Верно ли, что s(n) при всех n приходит к 1, а точнее - к циклу 1<->2 ?

Эта нерешенная (3n+1)-проблема известна с 1930 года.

Аналогично формулируется (3n-1)-проблема:

По любому натуральному n строится последовательность s(n) = {s1,... sk, ...},

s1=n,   sk+1=sk/2, если sk четно,   sk+1=(3sk-1)/2, если sk нечетно.

Верно ли, что s(n) при всех n приходит либо к 1, либо к одному из двух циклов ? Вскоре вы узнаете, что это за циклы.

Ниже предлагается новый подход к (3n+1)-проблеме и к (3n-1)-проблеме.

Возможно, его развитие поможет в дальнейшем решить эти проблемы.

Упражнения (цепочки и {c,d}-пары)

1. Проверьте, что 1<->2 - цикл в (3n+1)-проблеме. Проверьте, что 1 - неподвижная точка в (3n-1)-проблеме. Найдите 2 цикла в (3n-1)-проблеме.

Предположим на минуту, что верна следующая теорема: ни в (3n+1)-проблеме, ни в (3n-1)-проблеме нет других циклов. Следует ли из нее положительное решение (3n+1)-проблемы и (3n-1)-проблемы?

2. Сравните первые серии нечетных чисел в сиракузской последовательности s(15) в (3n+1)-проблеме и в последовательности s(17) в (3n-1)-проблеме:
15, 23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1.
17, 25, 37, 55, 82, 41, ...

С точностью до 1 числа в обеих сериях - это подчиняющиеся красивому закону (какому?) числа 16, 24, 36, 54, 81. Чтобы отметить, что 1 вычитается из всех этих чисел (или прибавляется ко всем этим числам), заключим их в скобки:

15, 23, 35, 53, 80 = -1 + [16, 24, 36, 54, 81],

17, 25, 37, 55, 82 = 1 + [16, 24, 36, 54, 81].

Рассмотрите другие примеры, например, следующие 3 серии в (3n+1)-проблеме:

31, 47, 71, 107, 161, 242;   7, 11, 17, 26;   87, 131, 197, 296.

Попробуйте найти общее правило и описать каждую серию нечетных чисел (с четным числом в конце серии) с помощью всего двух чисел: "коэффициента c и степени d".

3. Вот s(27) в (3n+1)-проблеме: 27, 41, 62, 31, 47, 71, 107, 161, 242, 121, 182, 91, 137, 206, 103, 155, 233, 350, 175, 263, 395, 593, 890, 445, 668, 334, 167, 251, 377, 566, 283, 425, 638, 319, 479, 719, 1079, 1619, 2429, 3644, 1822, 911, 1367, 2051, 3077, 4616, 2308, 1154, 577, 866, 433, 650, 325, 488, 244, 122, 61, 92, 46, 23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1. Рассмотрим серии нечетных чисел (с четным числом в конце каждой серии):


27, 41, 62 = -1 + [28, 42, 63]
31, 47, 71, 107, 161, 242 = -1 + [32, 48, 72, 108, 162, 243]
121, 182 = -1 + [122, 183]
91, 137, 206 = -1 + [92, 138, 207]
103, 155, 233, 350 = -1 + [104, 156, 234, 351]
175, 263, 395, 593, 890 = -1 + [176, 264, 396, 594, 891]
445, 668, 334 = -1 + [446, 669], 334

Стоп! Мы встретили 2 четных числа подряд (668, 334), это (по ОПРЕДЕЛЕНИЮ) КОНЕЦ ЦЕПОЧКИ.

Представим эту ЦЕПОЧКУ в виде последовательности {c,d}-пар (с четным числом 334 в конце): {7,2} {1,5} {61,1} {23,2} {13,3} {11,4} {223,1}, 334.

Пояснение. [28, 42, 63] = 7*[22, 2*3, 32] <-> {7,2} . Сравните с предыдущей задачей 2, где [16=24, 24=23*3, 36=22*32, 54=2*33, 81=34] <-> {1,4} .

Итак, я предлагаю

1) выписывать {c,d}-ПАРЫ вместо ЧИСЕЛ,

2) рассматривать ЦЕПОЧКИ {c,d}-пар (с четным числом в конце каждой цепочки).

3) ассоциировать s(n) с множеством цепочек.

4. Будьте внимательны со следующими сериями нечетных чисел:


167, 251, 377, 566 = -1 + [ ]
283, 425, 638 = -1 + [ ]
319, 479, 719, 1079, 1619, 2429, 3644, 1822 = -1 + [ ], 1822,

первая строчка 167, 251, 377, 566 начинается РАНЬШЕ (я предлагаю всегда начинать цепочки с нечетных чисел, кратных трем):

111, 167, 251, 377, 566 = -1 + [112, 168, 252, 378, 567] = -1 + 7*[16, 24, 36, 54, 81] <-> {7,4},

так что первая {c,d}-пара в этой цепочке - {7,4}. Каковы остальные {c,d}-пары в этой цепочке? Постарайтесь дать точное определение ЦЕПОЧЕК в (3n+1)-проблеме.

5. Продолжите (рассмотрите соответствующие {c,d}-пары и цепочки): 911, 1367, 2051, 3077, 4616, 2308, 1154, 577, 866, 433, 650, 325, 488, 244, 122, 61, 92, 46, 23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1.

Перспективы

Чтобы можно было представить себе направление дальнейших исследований, ниже сформулировано несколько сложных задач (в том числе, пока нерешенных).

Некоторые из них мы обсудим подробнее в разделе "Основные задачи".

Верны ли в (3n+1)-проблеме следующие утверждения I и II?

I. Для любого n>2, n не равно 0 (mod 6), существует ровно одна пара (a,b), такая что s(6a+3) содержит n, s(n) содержит 6b+4 и отрезок [s(6a+3),s(6b+4)] не содержит других чисел = 4 (mod 6).

II. В любой цепочке {c1,d1},...,{cn,dn} все ck различны.

III. Сколь длинными бывают цепочки? (Сколько {c,d}-пар могут они содержать?)

Подготовительные задачи

6. В (3n-1)-проблеме аналогом утверждения I является утверждение

I'. Для любого n>2, n не равно 0 (mod 6), существует ровно одна пара (a,b), такая что s(6a+3) содержит n, s(n) содержит 6b+2 и отрезок [s(6a+3),s(6b+2)] не содержит других чисел = 2 (mod 6).

Формально в (3n-1)-проблеме утверждения I' и II неверны, но вероятно, имеется лишь 4 контрпримера к ним: 3 числа, не удовлетворяющих I' и 1 цепочка, не удовлетворяющая II. Найдите их.

7. a. Если гипотеза о сиракузской последовательности верна, то все натуральные n>2, n не равно 0 (mod 6), являются вершинами дерева T. В (3n+1)-проблеме некоторые нечетные числа в s(n) равны 1 (mod 3), некоторые равны 2 (mod 3), а некоторые равны 0 (mod 3). Как это связано со степенями вершин T? Сформулируйте правило.

b. Сформулируйте аналогичное правило для (3n-1)-проблемы.

Длина и структура цепочки В соответствии с утверждением I и с 7a, возьмем любую цепочку (a,b), т.е. отрезок [6a+3, 6b+4] последовательности s(6a+3) до первой пары 12b+8, 6b+4 четных чисел подряд. Пока это лишь экспериментальный результат, что для любого числа n>2, n не равно 0 (mod 6), последовательность s(n) содержит такую пару. Этот факт не доказан ни для всех n>2, ни для n=6a+3. Но имеется миллион примеров цепочек. Так что пусть (a,b) - одна из них. Разобьем отрезок [6a+3, 12b+8] цепочки (a,b) на куски, каждый из которых содержит одно или несколько нечетных чисел и ровно одно четное число (в конце каждого куска).

По определению число L этих кусков есть ДЛИНА цепочки, а конечная последовательность d1, ..., dL (где dk - число нечетных чисел в k-ом куске) - СТРУКТУРА цепочки. Последнее число последнего (L-го) куска - это первое в цепочке число, кратное четырем, т. е. число вида 12b+8, выпишем вслед за ним и число 6b+4. Пример:

d1=2   27 41 62
d2=5   31 47 71 107 161 242
d3=1   121 182
d4=2   91 137 206
d5=3   103 155 233 350
d6=4   175 263 395 593 890
d7=1   445 668 334

8. Попробуйте найти другую цепочку той же длины L=7 с той же структурой.

Основные задачи

9. a) Возьмем любую конечную последовательность из нулей и единиц, например:

1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0.

Докажите, что найдется такое n, что в начальном отрезке s(n) на местах единиц будут стоять нечетные числа, а на местах нулей - четные числа.

b) Обратно, каждой s(n) можно сопоставить бесконечную последовательность из нулей и единиц (единицы соответствуют нечетным числам, а нули - четным числам). Покажите, что эти последоватедьности различны, если они сопоставлены различным s(n) и s(m).

10. Докажите, что для любого натурального L и любых натуральных d1, ..., dL существует цепочка со структурой d1, ..., dL.

11. Докажите следующую теорему:

Теорема 1. Пусть (a,b) - цепочка длины L со структурой d1, ..., dL.

Положим j=d1+...+dL, i=j+L, A=2i, B=3j, a'=a+A, b'=b+B. Тогда
1) (a',b') - цепочка,
2) ее длина равна L, как и у цепочки (a,b),
3) ее структура: d1, ..., dL, тоже как и у цепочки (a,b).

Итак, вместо миллиона примеров цепочек, теперь у нас есть бесконечное множество цепочек: вместе с любой цепочкой (a0,b0) у нас имеется бесконечная последовательность цепочек (ak,bk)=(a0,b0)+k*(A,B), k=1,2,3, ...

12. Докажите следующую теорему:

Теорема 2. Пусть (a,b) и (a',b') - 2 цепочки с одной и той же структурой d1, ..., dL, a'>a. Положим j=d1+...+dL, i=j+L, A=2i, B=3j. Тогда существует такое k, что a'=a+kA, b'=b+kB.

13. Докажите, что в (3n+1)-проблеме имеются цепочки со структурами

<1>, <1,1>, <1,1,1>, <1,1,1,1>, <1,1,1,1,1>, ...


с коэффициентами c1 и с числами a0,b0 следующего вида:


<1>: c1 = 11 = 5*2+1, a0 = 3, b0 = 2,
<1,1>: c1 = 41 = 5*23+1, a0 = 13, b0 = 7,
<1,1,1>: c1 = 161 = 5*25+1, a0 = 53, b0 = 22,
<1,1,1,1>: c1 = 641 = 5*27+1, a0 = 213, b0 = 67,
<1,1,1,1,1>: c1 = 2561 = 5*29+1, a0 = 853, b0 = 202,
............................................................

a) Найдите остальные cj для этих цепочек,

b) Найдите рекуррентные формулы для a0 и b0,

c) Найдите cj, 1<j<6, и a0 и b0 для цепочки со структурой <1,1,1,1,1,1>.

14. Сформулируйте и решите задачу, аналогичную 13, для (3n-1)-проблемы.

15. a) Докажите для любого n=6a+3, что сиракузская последоватедьность s(n) не может зациклиться прежде, чем цепочка с началом n=6a+3 закончится, т. е. прежде, чем появятся числа 12b+8 и 6b+4. b) Можете ли вы получить тот же результат для любого n (n>2, n не равно 6a+3) ?

M.L@gerver.mccme.ru