Уравнение на число делителей.

[Руст]

При каких натуральных m, существует натуральное n, удовлетворяющее уравнению:
$\frac{\tau(n^2)}{\tau(n)}=m$?
Здесь $\tau(n)$ -число всех дедителей числа n.
Существует ли решение при m=23?

[Macavity]

Руст писал(а):

При каких натуральных m, существует натуральное n, удовлетворяющее уравнению:
$\frac{\tau(n^2)}{\tau(n)}=m$?
Здесь $\tau(n)$ -число всех дедителей числа n.
Существует ли решение при m=23?

Похоже, что минимальное n=144 и для него m=3.
Известно, что если число разложимо на простые делители
n=p_1^{a_1}...p_s^{a_s}, то
\tau(n)=(a_1+1)...(a_s+1)
То есть \tau(n^2)=(2a_1+1)...(2a_s+1)

Отсюда, похоже, получается, что m не может быть четным, а n это полный квадрат.
Дополнительная хитрость, что 2x+1 не может нацело делится на x+1.

Для n=144 имеем n=2^4*3^2 и n^2=2^8*3^4

\tau(n)=(4+1)*(2+1)=15, \tau(n)=(8+1)*(4+1)=45 -> m=3
Для m=3 существует бесконечное число "изоморфных" решени: n=a_1^4*a_2^2, где a_1, a_2 - простые числа.

Легко находятся решения для
m=5,9,15,25
например, для m=5, n=2^4*3^2*5^2=25*144=3800
Дальше сложнее - надо думать
если для m=23 и существует решение (точнее бесконечно много решений), то даже минимальное из них будет весьма большим числом.

[maxal]

$m=23$ получается, например, для $n=p_1^{34} p_2^{16} p_3^{10} p_4^8 p_5^2,$ где $p_j$ - различные простые.

[незваный гость]

Macavity писал(а):

Легко находятся решения для
m=5,9,15,25

Очевидно (прямо из Вашего построения), что если $m_1, m_2 \in M=\{m: \exists n \ \frac{\tau(n^2)}{\tau(n)}=m} \}$, то $ m_1 m_2 \in M$, то есть $M$ образует полугруппу по умножению (кстати, $1 \in M$ ). Поэтому, если удастся показать, что ответ положительный для любого простого нечетного $p$, то ответом в задаче будет любое нечетное число.

Пока мне известно, что $\{1,3,5,7,11,13,17,19,23,29,53,59,61,67,71\} \subset M$. Бомба продолжает прыгать (а процессор — считать ). Через пару часов обновлю…

[maxal]

Вообще, если показать, что из представимости целого нечетного числа $m\geq 3,$ следует представимость числа $\frac{m}{3},$ то представимость всех нечетных чисел будет следовать из гипотезы Коллаца.

Добавлено спустя 10 минут 52 секунды:

незваный гость писал(а):

Пока мне известно, что $\{1,3,5,7,11,13,17,19,23,29,53,59,61,67,71\} \subset M$.

Моя программка быстро находит представления для любого m. Например,
для $m=31$ получается $n=p_1^{160} p_2^{106} p_3^{80} p_4^{70} p_4^{46}.$

Добавлено спустя 11 минут 33 секунды:

Вот степени простых в разложении $n$ для $m$ пробегающих простые числа меньшие 100:

3: [2, 4]
5: [2, 2, 4]
7: [8, 10, 16]
11: [2, 4, 8, 16]
13: [6, 8, 10, 16]
17: [2, 2, 4, 4, 8]
19: [2, 2, 4, 14, 28]
23: [2, 4, 26, 34, 52]
29: [14, 22, 26, 34, 52]
31: [46, 70, 80, 106, 160]
37: [2, 2, 4, 14, 18, 28]
41: [2, 4, 8, 10, 16, 20]
43: [2, 4, 8, 16, 32, 64]
47: [2, 4, 70, 80, 106, 160]
53: [8, 10, 16, 20, 26, 40]
59: [22, 26, 34, 44, 52, 88]
61: [30, 46, 70, 80, 106, 160]
67: [2, 2, 4, 4, 8, 50, 100]
71: [2, 2, 4, 4, 80, 106, 160]
73: [2, 2, 4, 14, 18, 28, 36]
79: [2, 2, 4, 118, 134, 178, 268]
83: [2, 4, 8, 10, 16, 62, 124]
89: [2, 4, 22, 26, 34, 44, 52]
97: [6, 8, 10, 12, 16, 24, 48]

Добавлено спустя 42 минуты 35 секунд:

Все простые меньшие $10^7$ представимы в таком виде.

[незваный гость]

Я, как Вы понимаете, использовал brute force, по лености душевной и экономя время программирования.

maxal писал(а):

Вообще, если показать, что из представимости целого нечетного числа $m\geq 3,$ следует представимость числа $\frac{m}{3},$ то представимость всех нечетных чисел будет следовать из гипотезы Коллаца.

Отсюда два вопроса: 1) является ли результат известным или нет? 2) Вы не могли бы пояснить, как следует (особливо на примере простого $p$)?

[Руст]

И типов представления много. Например решением для 23 ещё является $n=p_1^{34}p_2^{24}p_3^{12}p_4^6p_5^4p_6^2p_7^2$.
Думаю результат известен. Пока забыли некоторые свойства представимых чисел. Самое простое из которых мультипликативность, вытекающая из мультипликативности числа делителей.

[maxal]

maxal писал(а):

Вообще, если показать, что из представимости целого нечетного числа $m\geq 3,$ следует представимость числа $\frac{m}{3},$ то представимость всех нечетных чисел будет следовать из гипотезы Коллаца.

незваный гость писал(а):

Отсюда два вопроса: 1) является ли результат известным или нет? 2) Вы не могли бы пояснить, как следует (особливо на примере простого $p$)?

Пусть нам надо для числа $m$ найти соответствующее $n$. Рассмотрим два случая:

если $m\equiv1\pmod4,$ то вместо $m$ будем искать решение $n'$ для числа $\frac{m+1}{2},$ а затем умножим его на новое простое в степени $\frac{m-1}{2}$ - и в резузьтате получится решение для $m.$

если $m\equiv3\pmod4,$ то вместо $m$ будем искать решение для $\frac{3m+1}{2},$ а затем из него получим решение для $\frac{3m+1}{2\cdot 3},$ а его умножим на новое простое в степени $\frac{3m-1}{2}$ - получится искомое $n$.

Нетрудно проверить, что сходимость указанного процесса равносильна гипотезе Коллаца.

А в своей программе, а использовал модификацию, при которой степени 3-ки сокращаются по мере возможности. Вот она (на PARI/GP):

? { rep(m) = local(a, k); 
  a=m[1]; k=m[2]; 
  while(k>0&&(a%3==0), a\=3; k-- ); 
  if(a==1 && k==0, return([]) ); 
  if(a%4==1, concat(rep([(a+1)/2,k]),[(a-1)/2]), concat(rep([(3*a+1)/2,k+1]),[(3*a-1)/2]) ) 
}
? forprime(p=3,100,print(p,": ",vecsort(rep([p,0]))))

Расширил проверку до всех простых меньших $10^8$ - все представимы.

[Руст]

maxal писал(а):

Нетрудно проверить, что сходимость указанного процесса равносильна гипотезе Коллаца.
Расширил проверку до всех простых меньших $10^8$ - все представимы.

1. Я не понял связи с гипотезой Коллатца. Так как нет возможности деления на 3.
2. Если есть связь то известна, что эта гипотеза ещё лет 20 назад была проверена до 2^{40}.
3. Задача решается безо всякой гипотезы. Вы близки к решению.

[Руст]

Закончу решение. Пусть n0 представляет m, возьмём новые k простых чисел и рассмотрим $n=n_0p_1^ap_2^{2a}...p_k^{2^{k-1}a},f(n)=\frac{\tau(n^2)}{\tau(n)}$.
Легко вычисляется, что n представляет $2^km-d, \ d|2^k-1$, если взять $a=m\frac{2^k-1}{d}.$
Нам достаточно использовать d=1 для доказательства по индукции, что любое нечётное число представимо в таком виде.
Число 1 представляется через n=1. Допустим, что все нечётные числа меньше m представимы в таком виде. Если наше m не простое, то представление получается из мультипликативности. Пусть m=p простое и p+1=2^km_0, \ m_0$ - нечётное число. По индукции $m_0$ представляется, а по доказанному ранее (d=1) $2^km_0-1=p$ так же представляется.