Проверка гипотезы Коллатца

Проверка гипотезы Коллатца

Описание

Гипотеза Коллатца (также известна как проблема 3n+1) — это одна из самых известных нерешённых проблем в математике. Гипотеза утверждает, что для любого натурального числа последовательность, полученная по правилам, всегда достигает 1.

Решение 1: Базовое решение для одного числа

def collatz_sequence(n):
    """Возвращает последовательность Коллатца для числа n."""
    sequence = []
    
    while n != 1:
        sequence.append(n)
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
    
    sequence.append(1)  # Добавляем последнее значение
    return sequence

print(collatz_sequence(6))   # [6, 3, 10, 5, 16, 8, 4, 2, 1]
print(collatz_sequence(10))  # [10, 5, 16, 8, 4, 2, 1]
print(collatz_sequence(1))   # [1]

Решение 2: Проверка для первых n чисел (базовое)

def collatz_check(n):
    """Проверяет гипотезу Коллатца для чисел от 1 до n."""
    def reaches_one(num):
        while num != 1:
            if num % 2 == 0:
                num = num // 2
            else:
                num = 3 * num + 1
        return True
    
    for i in range(1, n + 1):
        if not reaches_one(i):
            return False
    
    return True

print(collatz_check(100))  # True

Решение 3: С подсчётом количества шагов

def collatz_steps(n):
    """Возвращает количество шагов для достижения 1."""
    steps = 0
    
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        steps += 1
    
    return steps

print(collatz_steps(6))    # 8
print(collatz_steps(27))   # 111
print(collatz_steps(1))    # 0

Решение 4: С предохранением от бесконечных циклов

def collatz_check_safe(n, max_iterations=10000):
    """Проверка с защитой от бесконечных циклов."""
    def reaches_one(num, max_iter):
        iterations = 0
        while num != 1 and iterations < max_iter:
            if num % 2 == 0:
                num = num // 2
            else:
                num = 3 * num + 1
            iterations += 1
        
        return num == 1, iterations
    
    for i in range(1, n + 1):
        reached, steps = reaches_one(i, max_iterations)
        if not reached:
            return False, i, steps
    
    return True, None, None

result, failed_num, steps = collatz_check_safe(100)
if result:
    print("Гипотеза верна для первых 100 чисел")
else:
    print(f"Гипотеза неверна для числа {failed_num} (шагов: {steps})")

Решение 5: С использованием мемоизации для оптимизации

def collatz_check_optimized(n):
    """Проверка с мемоизацией для ускорения."""
    memo = {1: True}
    
    def reaches_one(num):
        if num in memo:
            return memo[num]
        
        original = num
        path = []
        
        while num not in memo:
            path.append(num)
            if num % 2 == 0:
                num = num // 2
            else:
                num = 3 * num + 1
        
        result = memo[num]
        
        # Запоминаем результат для всех чисел в пути
        for p in path:
            memo[p] = result
        
        return result
    
    for i in range(1, n + 1):
        if not reaches_one(i):
            return False
    
    return True

print(collatz_check_optimized(1000))  # True

Решение 6: Рекурсивный подход

def collatz_sequence_recursive(n):
    """Рекурсивное вычисление последовательности Коллатца."""
    if n == 1:
        return [1]
    
    if n % 2 == 0:
        return [n] + collatz_sequence_recursive(n // 2)
    else:
        return [n] + collatz_sequence_recursive(3 * n + 1)

print(collatz_sequence_recursive(6))  # [6, 3, 10, 5, 16, 8, 4, 2, 1]

⚠️ Примечание: рекурсивный подход может привести к переполнению стека для больших чисел.

Решение 7: Анализ всех чисел до n с информацией

def collatz_analysis(n):
    """Анализирует свойства последовательностей Коллатца."""
    results = {}
    
    for num in range(1, n + 1):
        current = num
        steps = 0
        max_value = num
        
        while current != 1:
            if current % 2 == 0:
                current = current // 2
            else:
                current = 3 * current + 1
            
            max_value = max(max_value, current)
            steps += 1
        
        results[num] = {
            'steps': steps,
            'max_value': max_value
        }
    
    return results

analysis = collatz_analysis(10)
for num, info in analysis.items():
    print(f"{num}: {info['steps']} шагов, макс значение {info['max_value']}")

Рекомендуемое решение для интервью

def collatz_check(n: int) -> bool:
    """Проверяет гипотезу Коллатца для первых n чисел.
    
    Args:
        n: верхний предел проверки
    
    Returns:
        True если все числа от 1 до n сходятся к 1
    
    Временная сложность: O(n * m), где m — среднее количество шагов
    Пространственная сложность: O(1) для базового, O(n) для мемоизации
    """
    def reaches_one(num):
        while num != 1:
            if num % 2 == 0:
                num = num // 2
            else:
                num = 3 * num + 1
        return True
    
    for i in range(1, n + 1):
        if not reaches_one(i):
            return False
    
    return True

Интересные факты о Коллатце

• Гипотеза проверена компьютерами для чисел до 2^68 — все сходятся к 1
• Средняя длина последовательности растёт логарифмически
• Для числа 27 требуется 111 шагов, что необычно много
• Проблема 3n+1 остаётся нерешённой уже более 90 лет
• Похожие проблемы существуют для других формул (5n+1, 7n+1 и т.д.)

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