Прогрессии из арифметических функций

[Ktina]

а) Найти все натуральные $n$, для которых

$$n,\quad \tau(n)\quad\text{и}\quad\tau_2(n)$$

образуют арифметическую прогрессию.

б) Конечно или бесконечно множество всех натуральных $n$, для которых

$$n,\quad \tau(n)\quad\text{и}\quad\tau_2(n)$$

образуют геометрическую прогрессию?

($\tau$ это число делителей, $\tau_2$ это число делителей, являющихся квадратами)

[Руст]

$n=1,3,4$.
Так как $1\le \tau_2(n)\le \tau(n)\le n$, должно быть $\tau(n)>n/2$, это при $n>4$ выполняется только для $n=6$.

[Ktina]

Руст в сообщении #684769 писал(а):

$n=1,3,4$.
Так как $1\le \tau_2(n)\le \tau(n)\le n$, должно быть $\tau(n)>n/2$, это при $n>4$ выполняется только для $n=6$.

Это да.
$\tau(n)\le 2\sqrt{n}\to n\le 16$
Можно было даже тупо перебрать 16 чисел.
Второй пункт поинтересней будет.

[Руст]

Там перебор больше. Я тут задавал задачу, что $\tau(n)=o(n^{\epsilon})$ при любом $\epsilon$. И даже оценивали наибольшее значение, при котором $\tau(n)>n^{1/4}$.

[ИСН]

Музыкой навеяло родственную задачу: при каких n у нас $n,\,\varphi(n)\;\text{и}\;\varphi(\varphi(n))$ будут образовывать арифметическую прогрессию?
...а геометрическую?

[Ktina]

Геометрической не будет, кроме всех степеней 2

-- 17.02.2013, 00:32 --

Э, нет.
18, 6, 2...

-- 17.02.2013, 00:34 --

Короче, так, геометрическая будет только либо при $2^n$ ($n\ne 1$), либо при $3\cdot 2^n$ ($n\ne 1$)

-- 17.02.2013, 00:36 --

$2^n\cdot 3^m$ ($n, m\ne 1$)

[ИСН]

Как насчёт 50, 20, 8?

[Руст]

Таких чисел слишком много. Для этого необходими и достаточно, чтобы $n$ и $\phi(n)$ имели одни и те же простые множители. Тогда происходит умножение на одно и то же число $\prod_{p|n}\frac{p-1}{p} =\prod_{p|\phi(n)}\frac{p-1}{p}$. Например берем произвольное простое число $p$, умножаем на простые делители числа $p-1$, потом на простые делители чисел вида $p-1$. не включенных в множители и т.д. Первое простое берем как минимум во второй степени. Начав с 7 получаем 2, 3 и новых простых не появится. Соответственно годится $n=7^{k_1}3^{k_2}2^{k_3}, k_1\ge 2, k_2\ge 1, k_3\ge1.$

[ИСН]

Ну как это слишком много. Бесконечно их было с самого начала, со степеней двойки. А описать - вот Вы и описали. Я для себя так формулировал: чтобы все простые входили туда вместе со своими субделителями (избыточное пояснение: а те - со своими, и так далее до самого низа), причём те, которые не являются ничьими субделителями, должны входить как минимум во второй степени.
Слово "субделитель" я придумал только что, и оно мне нравится.

[Ktina]

ИСН в сообщении #684868 писал(а):

Слово "субделитель" я придумал только что, и оно мне нравится.

(Оффтоп)

Мне тоже. И даже очень сильно.

[ИСН]

(Оффтоп)

-- Пн, 2013-02-18, 14:07 --

Ещё можно задать те же вопросы про последовательность $n,\,\sigma(n),\,\sigma(\sigma(n))$.
Или вот тоже - $\varphi(n),\,n,\,\sigma(n)$.
Но во всех этих вариантах, по-моему, ответ будет какой-нибудь банальный.