Комментарии 24
Хороший вопрос для собеседования по программированию!

Видимо, 3 вопроса-упражнения. А действительно: решаются элементарно, но требуют некоторого "проблеска" рассудка.


А гипотеза, конечно, интересная. Интересно, можно ли её как-то заюзать практически? Например, если для некоторого числа заранее неизвестно число шагов, то можно ли это задействовать, скажем, в ГСЧ?

Спасибо, да, я имел в виду упражнения в конце статьи. Но для особо умных можно попросить найти первое число, которое не приведёт к бесконечному циклу.
«Генерация случайных чисел слишком важна, чтобы оставлять её на волю случая» Р. Кавью
Идея ГПСЧ интересная, такое использование в литературе не встречается. По результатам небольшого гугления.
Осталось исследовать распределение числа шагов, оценить эффективность вычислений и периоды циклов самой генерации.
НЛО прилетело и опубликовало эту надпись здесь

Я работаю в такой компании, где иногда надо решать теоретически нерешаемые задачи. Если задать вопрос о гипотезе Коллатца, и кандидат её знает, это говорит о том, что либо он интересуется математикой или читает Хабр. В любом случае, стоит его послушать. А если не знает, то интересен подход кандидата — может быть, напишет код для проверки орбиты любого числа.

НЛО прилетело и опубликовало эту надпись здесь
Нифига не понимаю в математике, но накидал простой скрипт перебора по условию. Скрипт берет числа от одного в гору и согласно описанных условий производит мат. вычисления, до тех пор, пока не упрется в одно из чисел 8,4,2,1. Как только это условие выполняется, все промежуточные значения вычисления записываются в файл. Следующее число равно предыдущему +1 и перед вычислением проверяется на наличие в этом файле, если такое значение уже есть, добавляется еще единица и так, до тех пор пока мы не найдем отсутствующее число. Его прогоняем по условиям и т.д.
И вот (для меня дилетанта) на вид кажется, что необходимость вычисления того или иного значения поддается какой-то закономерности.
Вообще не сварщик, просто поделился наблюдением.
В конце есть примеры других петель (помимо 8,4,2,1), и не факт, что это все возможные петли, поэтому алгоритм не так уж и прост

Прочитал еще раз статью и понял, что аналитически нащупал то, что уже изложено математически. Ну и ладно, зато мозг размял.

логично проверять пока не упрется в число меньшее или равное проверяемому
Хорошо, а какой другой вариант решения рассматривается? Что прогрессия пойдет вверх? Что будут получаться только нечетные числа после (n*3+1)/2?
Или какое решение кроме этой петли рассматривается?
или как вариант цикл между двумя волшебными числами, не равными 1.
Только при n*3+1 нечетное число не может получится впринципе

Результата меньше 1 тоже быть не может — для этого нужно делить предыдущее число на ноль или на отрицательное число.
Только при n*3+1 нечетное число не может получится впринципе

Это как так?
а, нет. Все правильно. Когда нужно сделать операцию n*3+1, в качестве n всегда выступает нечетное число, по условию.

Оригинал:
"In fact, some simple number theory can show us that as long as n > 1, then it’s always true that"
Перевод:
"И в самом деле, мы знаем для простых чисел покуда п> 1, то всегда верно что"
К математическим статьям надо бы подходить более тщательно.

Именно так. Автор оригинала, конечно же, не имел в виду "prime": неравенство n/2+1/2 < n выполняется для всех действительных, больших единицы. А "simple" относится, видимо, к "theory".

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Информация

Дата основания
Местоположение
Россия
Сайт
otus.ru
Численность
51–100 человек
Дата регистрации

Блог на Хабре