Простые числа: модель покрытия простых осей

Контекст

Направление: ИИ

Клиент: Клиент обезличен

Проблема

Нужно сформулировать и проверить модель поиска простых через пространство произведений степеней уже найденных простых.

Решение

Построено покрытие M({p₁,…,pₖ}) до конечной границы. Каждая новая минимальная пустота становится осью, после чего добавляется её слой произведений с прежним пространством.

Технические детали

Определение модели

Для уже открытых простых осей p₁,…,pₖ задаётся пространство M({p₁,…,pₖ}) = {p₁^a¹ · … · pₖ^aᵏ : aᵢ ≥ 0}. Его счётчик Cₖ(X) — число точек M ∩ [1,X].

Алгоритм хранит покрытие этого пространства до границы N. Минимальная незакрытая позиция p объявляется новой осью. После этого помечаются p·m для всех m из прежнего пространства и p·m ≤ N. Поэтому составное создаётся в слое своего наибольшего простого множителя, а не проверяется делением кандидата.

Проверяемая часть

Индуктивно: после k шагов покрытие равно M({p₁,…,pₖ}) ∩ [1,N]; следовательно минимальная пустота — простое. Код проверен до 10 000: получено 1 229 простых, последнее 9 973. Список сравнен с независимым медленным тестом делимости, использованным только для validation. Это не сравнение быстродействия с решетом и не доказательство новой теоремы о распределении простых.

Интерпретация «мерностей» и теней — гипотеза/визуальный язык

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

Python-код

```python """Воспроизводимая модель покрытия пространства простых осей.

Это не решето: составные числа появляются только как произведения новой простой оси p и уже построенного пространства M({p1, ..., p(k-1)}). Проверка простоты делением используется лишь в validate(), как независимый эталон результата. """

from __future__ import annotations

from dataclasses import dataclass from typing import Iterable

@dataclass(frozen=True) class Step: """Один шаг: первая пустота стала новой осью пространства."""

prime: int previous_count: int added: int count: int

def products_of_axes(axes: Iterable[int], limit: int) -> set[int]: """M(axes) ∩ [1, limit]: все произведения неотрицательных степеней осей.""" points = {1} for p in axes: expanded: set[int] = set() power = 1 while power <= limit: expanded.update(value * power for value in points if value * power <= limit) power *= p points = expanded return points

def C(axes: Iterable[int], x: int) -> int: """Счётчик C_k(X) = |M({p1,...,pk}) ∩ [1,X]|.""" return len(products_of_axes(axes, x))

def recursive_shadow_depth(axes: list[int], index: int, limit: int) -> int: """Глубина ветви теней: p_i p_(i-1) ... p_(i-d) <= limit.

На каждом переходе уменьшается масштаб, то есть новая граница делится на следующую предыдущую ось. Это вычислительная форма наблюдаемой рекурсии. """ product = 1 depth = -1 for j in range(index, -1, -1): product *= axes[j] if product > limit: break depth += 1 return max(depth, 0)

def generate_primes(limit: int, keep_steps: bool = False) -> tuple[list[int], list[Step]]: """Находит простые <= limit через покрытие M, без решета и prime-библиотек.

covered[n] означает n принадлежит пространству уже открытых осей. Поэтому минимальная пустая позиция является следующей простой осью. После открытия p помечаются ровно p*m, где m лежит в прежнем пространстве; так каждое составное получает слой своего наибольшего простого множителя. """ if limit < 2: return [], []

covered = bytearray(limit + 1) covered[1] = 1 space_count = 1 primes: list[int] = [] steps: list[Step] = []

for candidate in range(2, limit + 1): if covered[candidate]: continue

# candidate is the minimum void and opens one new prime axis. p = candidate previous_count = space_count upper = limit // p added = 0 for m in range(1, upper + 1): if covered[m]: n = p * m if not covered[n]: covered[n] = 1 added += 1 primes.append(p) space_count += added if keep_steps: steps.append(Step(p, previous_count, added, space_count))

return primes, steps

def trial_primes(limit: int) -> list[int]: """Независимый медленный эталон только для проверки модели.""" result: list[int] = [] for n in range(2, limit + 1): divisor = 2 while divisor * divisor <= n and n % divisor: divisor += 1 if divisor == 2 else 2 if divisor * divisor > n: result.append(n) return result

def validate(limit: int = 10_000) -> None: generated, steps = generate_primes(limit, keep_steps=True) reference = trial_primes(limit) assert generated == reference, "покрытие и независимый эталон разошлись" assert generated[-1] == 9_973 and len(generated) == 1_229

# C_k(X) из явного определения совпадает с накопленным покрытием на малом X. for k in range(1, min(8, len(generated)) + 1): assert C(generated[:k], limit) == steps[k - 1].count

print(f"OK: {len(generated)} простых до {limit}; последнее = {generated[-1]}")

if __name__ == "__main__": validate() ```

Результат

Python-проверка до 10 000 получила 1 229 простых; результат совпал с независимым проверочным алгоритмом деления. Экспериментальная геометрическая интерпретация явно отделена от этой проверки.

Технологии

• —Python
• —Конечное пространство произведений
• —Независимая validation-проверка

Связанные услуги

• Исследование