Обратная задача к функции τ(n): для заданного k найти наименьшее число, имеющее ровно k делителей
Последовательность OEIS A005179 — ключевые свойства, алгоритмы и задания
Концепция последовательности
Определение: Пусть a(n) — наименьшее натуральное число, имеющее ровно n положительных делителей.
Математически: a(n) = min{m ∈ ℕ : τ(m) = n}
Последовательность не монотонна. Например:
a(6) = 12 < a(5) = 16
Потому что мы ищем не следующее число с большим τ, а наименьшее с заданным τ.
Значения растут очень неравномерно:
• Для простых n: a(n) = 2n-1 (быстрый рост)
• Для составных n с хорошим разложением: относительно малые значения
Таблица первых значений (до n=60)
Автор в OEIS: David W. Wilson
Год включения: 1994
Исследователи: Задача известна с XIX века, систематически изучалась с развитием теории чисел.
Как читать таблицу: Для каждого n (количество делителей) указано наименьшее число с таким количеством делителей. Жёлтым выделены важные случаи.
| n (делителей) |
a(n) (наименьшее число) |
Разложение на простые |
Проверка τ(a(n)) = n |
Особенности |
|---|---|---|---|---|
| 1 | 1 | 1 | τ(1)=1 | Единственное число с τ=1 |
| 2 | 2 | 2 | τ(2)=2 | Наименьшее простое |
| 3 | 4 | 2² | τ(4)=(2+1)=3 | Квадрат простого |
| 4 | 6 | 2×3 | τ(6)=(1+1)×(1+1)=4 | Произведение двух простых |
| 5 | 16 | 2⁴ | τ(16)=(4+1)=5 | 2n-1 для простого n>2 |
| 6 | 12 | 2²×3 | τ(12)=(2+1)×(1+1)=6 | 12 < 16! Не монотонность |
| 7 | 64 | 2⁶ | τ(64)=(6+1)=7 | Простое n: 2n-1 |
| 8 | 24 | 2³×3 | τ(24)=(3+1)×(1+1)=8 | 24 < 64 |
| 9 | 36 | 2²×3² | τ(36)=(2+1)×(2+1)=9 | Квадрат составного |
| 10 | 48 | 2⁴×3 | τ(48)=(4+1)×(1+1)=10 | |
| 11 | 1024 | 2¹⁰ | τ(1024)=(10+1)=11 | Простое n |
| 12 | 60 | 2²×3×5 | τ(60)=(2+1)×(1+1)×(1+1)=12 | Highly composite |
| 13 | 4096 | 2¹² | τ(4096)=(12+1)=13 | Простое n |
| 14 | 192 | 2⁶×3 | τ(192)=(6+1)×(1+1)=14 | |
| 15 | 144 | 2⁴×3² | τ(144)=(4+1)×(2+1)=15 | |
| 16 | 120 | 2³×3×5 | τ(120)=(3+1)×(1+1)×(1+1)=16 | Highly composite |
| 17 | 65536 | 2¹⁶ | τ(65536)=(16+1)=17 | Простое n |
| 18 | 180 | 2²×3²×5 | τ(180)=(2+1)×(2+1)×(1+1)=18 | |
| 19 | 262144 | 2¹⁸ | τ(262144)=(18+1)=19 | Простое n |
| 20 | 240 | 2⁴×3×5 | τ(240)=(4+1)×(1+1)×(1+1)=20 | |
| 24 | 360 | 2³×3²×5 | τ(360)=(3+1)×(2+1)×(1+1)=24 | Highly composite |
| 30 | 720 | 2⁴×3²×5 | τ(720)=(4+1)×(2+1)×(1+1)=30 | Highly composite |
| 32 | 840 | 2³×3×5×7 | τ(840)=(3+1)×(1+1)×(1+1)×(1+1)=32 | Первое число с 4+ простыми множителями |
| 36 | 1260 | 2²×3²×5×7 | τ(1260)=(2+1)×(2+1)×(1+1)×(1+1)=36 | |
| 48 | 2520 | 2³×3²×5×7 | τ(2520)=(3+1)×(2+1)×(1+1)×(1+1)=48 | Highly composite |
| 60 | 5040 | 2⁴×3²×5×7 | τ(5040)=(4+1)×(2+1)×(1+1)×(1+1)=60 | Highly composite |
Алгоритм поиска a(n)
Для заданного n нужно:
1. Разложить n на множители: n = d₁ × d₂ × … × dₖ
2. Каждому разложению сопоставить кандидата: 2d₁-1 × 3d₂-1 × … × pₖdₖ-1
3. Выбрать минимальный среди кандидатов
Шаг 1: Разложение n
Найти все разложения n в произведение натуральных чисел > 1.
Пример для n=12: 12, 6×2, 4×3, 3×2×2
Шаг 2: Сортировка разложений
Упорядочить множители в каждом разложении по убыванию.
3×2×2 → (3,2,2)
Шаг 3: Сопоставление простых чисел
Каждому множителю сопоставить простое число:
(a,b,c,…) → (2a-1, 3b-1, 5c-1, …)
Шаг 4: Вычисление кандидатов
Вычислить произведение для каждого разложения.
Для (3,2,2): 2² × 3¹ × 5¹ = 60
Шаг 5: Выбор минимального
Среди всех кандидатов выбрать наименьший.
Для n=12: 2¹¹=2048, 2⁵×3=96, 2³×3²=72, 2²×3×5=60 → min=60
Закономерности и свойства
Если n > 2 — простое число, то:
a(n) = 2n-1
Примеры: a(5)=16=2⁴, a(7)=64=2⁶, a(11)=1024=2¹⁰
Если n = m², часто a(n) относительно мало:
a(9)=36=6², a(16)=120 (не квадрат!), a(25)=1296=2⁴·3⁴
Не всегда совпадает с квадратом наименьшего числа!
Интересные случаи:
Скачок на простых числах: a(13)=4096, но a(12)=60
Первое составное значение: a(4)=6 — первое нестепенное
Первое с 4 простыми: a(32)=840=2³×3×5×7
Задания и упражнения
Задание 1.1: Найдите a(8) — наименьшее число с 8 делителями.
Решение:
8 = 8 = 4×2 = 2×2×2
Разложения: (8), (4,2), (2,2,2)
Кандидаты:
- 2⁷ = 128
- 2³×3¹ = 8×3 = 24
- 2¹×3¹×5¹ = 2×3×5 = 30
Минимум: 24
Ответ: a(8) = 24
Задание 2.1: Почему a(6)=12 меньше a(5)=16? Объясните, почему последовательность не монотонна.
Объяснение:
1. a(5)=16 потому что 5 — простое, и наименьшее число с 5 делителями — 2⁴=16
2. a(6)=12 потому что:
- 6 = 6 = 3×2 = 2×3 (одно разложение)
- Кандидаты: 2⁵=32, 2²×3=12
- Минимум: 12
3. 12 < 16 потому что 6 — составное число, допускает эффективное разложение на множители
Вывод: Последовательность не монотонна, потому что для составных n можно найти числа меньшие, чем степени двойки для простых n.
Задание 3.1: Докажите, что если n > 2 — простое, то a(n) = 2n-1.
Доказательство:
1. Пусть n > 2 — простое число
2. Нам нужно число m с τ(m) = n
3. Из формулы τ(p^α) = α+1 следует, что если m = p^(n-1), то τ(m) = (n-1)+1 = n
4. Чтобы m было минимальным, нужно выбрать наименьшее простое p
5. Наименьшее простое = 2
6. Следовательно, m = 2n-1 — наименьшее число с n делителями
7. Проверим, нет ли меньших чисел: любое число с n делителями должно иметь вид p^(n-1), так как n простое
Доказано: a(n) = 2n-1 для простых n > 2
Памятка для педагога: Методика преподавания
- Начать с простых примеров: a(2)=2, a(3)=4, a(4)=6
- Объяснить не монотонность: Важнейший момент! a(6)=12 < a(5)=16
- Ввести алгоритм: Поэтапно, с примерами для n=8, n=12
- Показать закономерности: Простые n → степени двойки
- Связать с τ(n): A005179 обратна к A000005, но не полностью
- Дать практические задачи: От вычислений к доказательствам
Связи с другими последовательностями
• A000005 — функция количества делителей τ(n)
• A005179 — обратная задача: по τ найти наименьшее n
• A002182 — highly composite numbers (часто совпадают с a(n) при составных n)