Наименьшая степень простого числа, факторизации которого не имеют различных сумм множителей
Проблема
Учитывая простое $p$найди наименьшее $n$ такие, что некоторые неупорядоченные факторизации $p^n$ имеют равные суммы факторов.
Неупорядоченные факторизации - это факторизации, в которых порядок факторов не имеет значения, и они не включают тривиальный фактор $1$. Заметить, что$n\gt 1$ для всех простых чисел $p$ потому что простые числа имеют только одну неупорядоченную факторизацию.
Примеры
Prime $p=2$. Это тривиально, что$n=2$ за $p=2$ потому как $2+2=2\cdot 2$. То есть неупорядоченные факторизации$2^2$ находятся $4$ и $2\cdot 2$, и у них обоих одинаковая сумма факторов $4 = 2+2$.
Prime $p=3$. Но,$n=2$ не решение для $p=3$ потому как $9\ne 3+3$. Ни то, ни другое$n=3$ потому как $27\ne 3+9 \ne 3+3+3$. Ни то, ни другое$n=4$ потому как $81\ne 27 + 3\ne 9 + 9\ne 9 + 3 + 3\ne 3 + 3 + 3 + 3$. В конце концов, мы обнаруживаем, что$n=12$ является наименьшим из подходящих, потому что тогда существуют следующие повторяющиеся суммы факторов:
$$\begin{align}{} 3^{12}&=&27\cdot3^9&=&9^6 &\implies& 27+\sum_{i=1}^{9}3 &=& \sum_{i=1}^{6}9 &=& 54 \\ 3^{12}&=&81\cdot9\cdot 3^6&=&27^4 &\implies& 81+9+\sum_{i=1}^{6}3 &=& \sum_{i=1}^{4}27 &=& 108 \end{align}$$
Обратите внимание, что если $p^{n}$ или любое число в целом удовлетворяет этому свойству, то ему также удовлетворяют все кратные этому числу.
Решение?
Prime $p\in\mathbb P$. Позволять$a(k)$ быть самым маленьким из таких $n_k$ Учитывая $k$й прайм$p_k$. У нас есть:
$$a(k) = 2, 12, 26, 34, 50, 58, 74, 82, \dots$$
Можно ли найти и доказать формулу этой последовательности?
Я заметил, что до сих пор сохраняется следующее: $a(1)=2,a(2)=12,a(k)=4p_k+6,k\ge 3$.
Это из-за следующих неупорядоченных факторизаций:
$$\begin{align} p_k &\quad n &\quad \\ 2 &\quad 2 &\quad (2)(2) &=(2^2) \\ 3 &\quad 12 &\quad (3)^9(3^3) &= (3^2)^6 &\quad (3)^6(3^2)(3^4) &= (3^3)^4 \\ 5 &\quad 26 &\quad (5^2)^{11} (5^4) &= (5)^5(5^3)^7 \\ 7 &\quad 34 &\quad (7)^{15}(7^4) &= (7)^7(7^3)^9 \\ 11 &\quad 50 &\quad (11^2)^{23}(11^4) &= (11)^{11}(11^3)^{13}\\ 13 &\quad 58 &\quad (13^2)^{27}(13^4) &= (13)^{13}(13^3)^{15}\\ 17 &\quad 74 &\quad (17^2)^{35}(17^4) &= (17)^{17}(17^3)^{19}\\ 19 &\quad 82 &\quad (19^2)^{39}(19^4) &= (19)^{19}(19^3)^{21}\\ \end{align}$$
Обратите внимание, что простые числа $p_k\ge 5$ следуйте следующей схеме:
$$ (p^2)^{2p+1}(p^4) = (p)^{p}(p^3)^{p+2} \implies (p^2)\cdot(2p+1)+(p^4) = (p)\cdot p+(p^3)\cdot(p+2) $$
Это дает нам верхнюю границу $a(k)\le 4p_k+6$ потому что шаблон верен для всех натуральных чисел.
Равенство было доказано вычислительными методами для некоторых маленьких простых чисел (как вы можете видеть выше).
Можем ли мы доказать, что равенство всегда выполняется? Т.е. можем ли мы доказать$a(k)\ge 4p_k+6, k\ge 3$ ?
То есть остается доказать, что все неупорядоченные факторизации чисел вида
$$ p^{4p+5} $$
иметь различные суммы множителей для всех простых чисел $p\ge 5$.
Другими словами, нам нужно доказать, что $\text{A001055}$$(p^{4p+5})$ $=$ $\text{A069016}$$(p^{4p+5})$.
Или, может быть, существует прайм $p$это контрпример? Т.е.$p_k : a(k)\lt 4p_k+6$ ?
Ответы
Примечание: мое решение довольно длинное и содержит множество кейсов, поэтому некоторые ошибки неизбежны. Дайте мне знать, если есть что-нибудь, что нужно объяснить.
Позволять $n$ наименьшее число такое, что $p^n$имеют две неупорядоченные факторизации с равной суммой множителей. Будем считать, что$n \le 4p+5$ и приходим к противоречию.
Обозначим через $A=(p^{a_1})^{n_1}\dots (p^{a_k})^{n_k}$ и $B=(p^{b_1})^{m_1}\dots(p^{b_l})^{m_l}$ две неупорядоченные факторизации, с $a_1 > \dots > a_k$ и $b_1 > \dots > b_l$. Без ограничения общности предположим, что$A$ имеет высшую силу $p$, т.е. что $a_1 \ge b_1$.
Наблюдение 1: $\{a_1,\dots,a_k\} \cap \{b_1,\dots,b_l\}=\emptyset$.
Это потому, что если $a_i=b_j$ для некоторых $i,j$, то мы можем вычесть $p^{a_i}$ из обеих факторизаций, чтобы получить две неупорядоченные факторизации с равной суммой для $p^{n-a_i}$, что противоречит минимальности $n$.
Наблюдение 2: $a_1 \le 5$.
Это происходит из рассмотрения уравнений $$\begin{equation}\label{eqn1} b_1m_1+\dots+b_lm_l=n \qquad (1)\end{equation}$$ и $$ \begin{equation} m_1p^{b_1}+\dots+m_lp^{b_l}=n_1p^{a_1}+\dots+n_kp^{a_k}\qquad (2)\end{equation}$$ Если вы решите максимум LHS из (2) с учетом (1) (и с $m_j \in \mathbb{R}$ вместо этого), то максимум достигается при $m_1=n/b_1$ и $m_j=0$ для всех $j \ge 2$, где максимальное значение $\frac{n}{b_1}p^{b_1}$. С другой стороны, правая часть (2) дает нижнюю оценку$p^{a_1}$, следовательно, мы должны иметь $$ \frac{n}{b_1} p^{b_1} \ge p^{a_1} \iff n \ge b_1 p^{a_1-b_1} .$$ поскольку $n \le 4p+5 \le p^2$ за $p \ge 5$у нас есть это $$ a_1-b_1=2, b_1=1 \qquad \text{or} \qquad a_1-b_1=1, b_1 \le 4$$ и в обоих случаях $a_1 \le 5$.
Теперь рассмотрим различные случаи $a_1 \in \{2,3,4,5\}$, с участием $a_1=4$ быть самым тяжелым.
Если $a_1=2$, тогда $b_1=1$ и мы получаем две факторизации $(p^2)^{n/2}$ и $p^n$. У них нет одинаковой суммы факторов для$p>2$.
Если $a_1=3$, то у нас есть следующие варианты:
- $a_2=2$, $b_1=1$. Получаем две факторизации$(p^3)^{n_1}(p^2)^{n_2}$ и $p^n$. У них нет одинаковой суммы, поскольку$$np \le (4p+5)p < p^3$$ за $p \ge 5$.
- $a_2=1$, $b_1=2$. Получаем две факторизации$(p^3)^{n_1}p^{n_2}$ и $(p^2)^{n/2}$. поскольку$$\frac{n}{2}p^2 \le \frac{4p+5}{2}p^2 < 3p^3$$ за $p \ge 5$у нас есть это $n_1 \in \{1,2\}$. Либо значения не приводят к равной сумме.
- $b_1=2$, $b_2=1$. Получаем две факторизации$(p^3)^{n/3}$ и $(p^2)^{m_1}p^{m_2}$. потом$$ m_1 p^2+m_2p \le \frac{n}{2}p^2 < \frac{n}{3}p^3. $$
- $b_1=2$. Мы получили$(p^3)^{n/3}$ и $(p^2)^{n/2}$, суммы которых не равны.
- $b_1=1$. Мы получили$(p^3)^{n/3}$ и $p^n$, суммы которых не равны.
Если $a_1=5$, тогда $b_1=4$как мы утверждали выше. Используя те же аргументы, мы видим, что$$ m_1p^4+\dots +m_l p^{b_l} < 2p^5 $$ для всех вариантов $m_1,\dots,m_l$, так $n_1=1$, и $$ m_1p^4+\dots +m_l p^{b_l} \ge p^5 $$ только когда $m_1 \ge p$. Следовательно, мы имеем$$ A = (p^5)\cdot(\text{unordered factorization of }p^{n-5}) \quad \text{and} \quad B= (p^4)^p\cdot(\text{unordered factorization of }p^{n-4p}).$$ В частности, это означает, что $n \in \{4p, \dots, 4p+5\}$. Еще одна проверка показывает, что для таких$n$, без факторизации $p^{n-5}$ имеет ту же сумму факторов, что и любая факторизация $p^{n-4p}$.
Если $a_1=4$, тогда $b_1=3$ из аргумента в наблюдении 2. Используя те же аргументы, что и в предыдущем случае, мы заключаем, что $n_1=1$ и $m_1 \ge p$. Следовательно, мы имеем$$ A = (p^4)\cdot(\text{unordered factorization of }p^{n-4}) \quad \text{and} \quad B= (p^3)^p\cdot(\text{unordered factorization of }p^{n-3p}).$$ Осталось рассмотреть следующие варианты $a_2,\dots,a_k$:
- $a_2=1$. Тогда если$A=(p^4)p^{n-4}$ и $B=(p^3)^{m_1}(p^2)^{m_2}$ иметь равную сумму, мы должны иметь $$ (n-4)p=(m_1-p)p^3+m_2p^2 \ge \frac{n}{2} p^2,$$ что неверно для $p \ge 5$ и $n \le 4p+5$.
- $a_2=2$, $a_3=1$. потом$A=(p^4)(p^2)^{n_2}p^{n_3}$ и $B=(p^3)^{n/3}$. Если их суммы равны, то$$ (n/3-p)p^3=n_2p^2+n_3p$$ так, в частности $p \mid n_3$. поскольку$n_3 \le n-4 \le 4p+1$ мы должны иметь $n_3 \in \{p,2p,3p,4p\}$. Подключаем каждое значение$n_3$ и $n_2=n-4-n_3$ в уравнение, мы обнаруживаем, что ни один из них не дает целочисленного значения для $n$.
- $a_2=2$. потом$A=(p^4)(p^2)^{(n-4)/2}$ и $B=(p^3)^{m_1}p^{m_2}$. Если их сумма равна, то$$\frac{n-4}{2}p^2=(m_1-p)p^3+m_2p$$ так $p \mid m_2$, и аналогично предыдущему получаем $m_2 \in \{p,2p,3p\}$. Опять же, вставляя каждое значение$m_2$ и $m_1=n-m_2$ в уравнение, мы обнаруживаем, что ни один из них не дает целочисленного значения для $n \le 4p+5$.