Задача поиска степени двойки. Как только получается 2^N, то кол-во оставшихся итераций равно N.
Теперь как находим степень двойки:
Может быть можно воспользоваться тем, что:
N*N - (N-1)*(N-1)=2N-1 -разность квадратов соседних чисел всегда нечетна
и тем, что (3N+1)-N =2N+1 -разность чисел найденных с помощью 3N+1 - всегда нечетна, т.е. результат всегда четный:
K=K/2, если K=2N
K=K*3+1, если К=2N+1, причем после этой итерации K всегда будет четным и за этой итерацией всегда будет K/2, значит:
K=(K*3+1)/2, если K=2N+1
А вот дальше...

СУВ.

Цитата(bagira @ 5.3.2004, 23:27)

Зачем спрашивать, если знаете, что задача заведомо нерешаемая? Мы ведь не подозревали подвоха, старались все, как могли...

Багира, я, конечно, злой, но не на столько.
О том, что задача не решается я узнал только после того как в этом топике про это рассказали. После чего покапался по нэту и только убедился в этом.

Я сам 2 дня пытался это решить, но сами понимаете, что тщетно.

Вариант, предложенный Багирой.



Присоединённый файл ( Кол-во скачиваний: 43 )
 solution.zip

ДОКАЗАННО!!! Эта задача решается за 100 в среднем шагов и на С++.

Код

int main(int argc, char* argv[]) { srand(time(0)*125); char s[256]; long i=0; long x=(long)rand()*254; while(x!=1){  i++; //  printf("x = %li n = %li\n",x,i); //  scanf(s);  if(x%2!=1)    x/=2;  else {    x*=3;x++;  } } printf("x = %li n = %li",x,i); scanf(s); return 0; }

Поправьте меня если я неправ!

Нужна не программа, а строгое доказательство в общем виде.

Цитата

Erdos commented that "mathematics is not yet ready for such problems" (Lagarias 1985).

Я конечно не претендую на решение данной проблемы. Мы пытались
составить программу, находящую самые вредные такие числа на
http://algolist.manual.ru. Вот к чему пришли

1) Можно не разбирать четные числа (они максимум на 1 сложнее
в два раза меньших)
2) Числа вида 3N+2 можно не рассматривать, так как всегда есть
более вредное число 2N+1:

2N+1 ---> 6N+4 --> 3N+2

3) Самое сложное: Если число нечетное, то

1) Прибавляем к нему 1
2) Раскладываем полученное число на множители
3) Заменяем все двойки на тройки
4) Вычитаем из полученного числа 1
5) Делим на 2
6) Это число получится из исходного после 2N+1 итераций,
где N - число двоек в разложении.

Например - число 7. Прибавляем 1 - 8
Раскладываем - 8=2*2*2
Заменяем - 3*3*3=27
Вычитаем - 27-1=26
Делим - 26/2 = 13
Это число получится из 7 после 2*3+1=7 итераций

Проверка 7-22-11-34-17-52-26-13 :-)

Если интересно, будем копать дальше

Мое почтение!
Вот размышление на тему решения данной задачи
Введем последовательность нечетных чисел след.образом
Chislo[k] = (Chislo[k-1]*3+1)>>j, k>1, j>0(j степень двойки на кот. делится число на к-1 шаге). Или что то же самое
Chislo[k] = (Chislo[k-1]<<1 +(Chislo[k-1]+1))>>j
Причем в силу нечетности Chislo[k] имеет вид 1...0111(1 повторяются к раз).
0 -- 1-ый 0
Chislo[k-1]<<1 =1..01110
Chislo[k-1]+1 =01.s1000(s - нас не интересует что).
Таким образом при сложении 0 точно "перепрыгивает" по крайней мере на 1 позицию вправо(cлева от него единица в каждом слагаемом ),где в последствии и "съедается" сдвигом. Таким образом Chislo[k] <= Chislo[k-1]*2 и последовательность заведомо сходится;
Если нет 0 в числе т.е. Сhislo[k-1] = 1......1...1..1...1, то
п.1 Сhislo[k] = 10...1..1..1..1 (т.е хотябы 1 ноль точно появится -- проверяется непосредственной проверкой, мат. индукцией или как угодно), далее повторяем до тех пор пока не останется 1.
Вот самая банальная часть докозательства --
Осталось
1) Строго показать, что последовательность сходится
2) Проверить п.1
У меня ни сил ни времени (ехал в метро когда решал) не хватило.

Это сообщение отредактировал(а) Sined - 31.8.2004, 18:23

Хочется сказать пару слов о решении Багиры : условие взятое в док-ве слишком жесткое, достаточно чтоб для любого начального значения, исключая 1, существовал элемент последовательности меньший начального, совершенно не обязательно доказывать строгое убывание.

3,14
Возможно, ты прав...
Но, узнав, что задача не решается в принципе, я больше и не бралась за нее
Но вдруг у тебя получится?

Пробовал, ещё до того как эта задача попала на форум, один злобный студент с механико-математического факультета подсунул, не получилось док-во с числами вида 2*j+1, где j-нечётное

Цитата(3)

не получилось док-во с числами вида 2*j+1, где j-нечётное

Вот этот момент можно пояснить?
Очевидно, что 2*j+1 и так нечетно, если j - целое.

Если j - нечётное, а не 2*j + 1

Прочитал решение bagira. Даже упрощенное - оно с ошибками. Комментарии нужны?

Цитата(Peter @ 3.9.2004, 12:41)

Прочитал решение bagira. Даже упрощенное - оно с ошибками. Комментарии нужны?

В чем мои ошибки?