Делимость знаменателя H_n

[Руст]

Пусть $H_n=1+\frac 12 +...+\frac 1n =\frac{p_n}{q_n}$ несократимое представление.
Для каких простых p, существует бесконечно много n, что $p\not |q_n$?

[Kid Kool]

Если n делится на p, то либо $q_n$, либо $q_{n-1}$ также делится на p.

[Руст]

Kid Kool писал(а):

Если n делится на p, то либо $q_n$, либо $q_{n-1}$ также делится на p.

А что это даёт?
Речь идёт о бесконечности n, для которых $q_n$ не делится на p.

Красный цвет зарезервирован для модераторов. // нг

[aadamchuk]

ну например, такие простые p = {7, 11, 1093, 3511, 5557} являются решениями этой задачи

Ref: http://www.research.att.com/~njas/sequences/A125581

[Руст]

Обоснуйте.

[aadamchuk]

я не совсем уверен, что это будет ответом на ваш вопрос, но я когда-то сам заметил, что знаменатели чисел H(n) и H'(n) одновременно не делятся на порядковый номер n при n = {77, 847, 9317}, то есть n = {7*11, 7*11^2, 7*11^3}.

я сформулировал, как мне тогда показалось вполне правдоподобное предположение, что таким свойством обладают все гармонические числа с номерами, принадлежащими бесконечной геометрической прогрессии n = 7*11^k и только они

через какое-то время частично моё предположение было подтверждено, но и были найдены другие прогрессии с такими же свойствами

скетч доказательства, сделанный Максом Алексеевым, есть в комментариях по ссылке A125581, приведённой выше

может у вас получится как-то элегантно доказать то же самое и для других простых p

Макс с Таней Ховановой нашли ещё несколько таких простых чисел, два из которых оказались хорошо известными {1093, 3511}, а ещё два оказались совершенно новыми {5557, 104891}
http://www.research.att.com/~njas/sequences/A126197

увидев вашу задачку, я подумал, что найденные нами геометрические последовательности индексов гармонических чисел H(n) и H'(n) годятся в качестве возможных решений вашей задачки

конечно же могут быть и другие решения, ведь вас здесь не интересует неделимость знаменателей знакопеременных гармонических чисел H'(n), а меня как раз интересовала одновременная неделимость знаменателей H(n) и H'(n) на их индекс

поэтому я сам и предложил когда-то последовательность A125581 в OEIS

меня, кстати, интересовали и подобные последовательности для обобщённых гармонических чисел

там тоже, как оказалось, вылазят геометрические прогрессии с интересными простыми числами

самое интересное вроде получается в третьем порядке с кубами в знаменателе H(n,3) и H'(n,3)
http://www.research.att.com/~njas/sequences/A128673

доказательств я не видел, но просто обнаружил эти странные геометрические прогрессии неделящихся на собственные индексы обобщённых гармонических знаменателей

вот тут есть кое-какая прошлогодняя эмпирика, годящаяся для размышлений и доказательств
http://www.research.att.com/~njas/seque ... &go=Search

примерно вот так

пардон, если получился off-topic и мои наблюдения не совсем в тему вашей задачки

[Руст]

Мне кажется вы несколько заменили задачу. Для любого нечётного простого числа р и $n=(p-1)p^k$ знаменатель $q_n$ числа $H_n$ не делится на n. Здесь речь идёт о простых числах p на которые не делятся бесконечно много знаменателей $H_n$.
Очевидно проверяется, что р=2 не годится. Соответственно p>2 и для любого $k$ должен существовать $p^k\le n<p^{k+1}$, что $p\not |q_n$. Если $ap^k\le n<(a+1)p^k$, то отсюда получается $p|q_a$. Поэтому, впервую очередь надо вычислить p-адические разложение $H_{ap^k}$, чтобы в случае p-адической нецелости можно было выяснить, что надо добавить $n=ap^k+n_1$, чтобы $H_n$ был p-адической целой.
Почему maxal не откликнулся, если в этих вопросах он уже разбирался.

[maxal]

Времени не так много свободного последнее время, на все откликнуться не успеваю. :(

По поводу исходной задачи, я думаю, что таких простых нет, то есть для любого простого $p$, начиная с некоторого $n$, $p|q_n$. Дело в том, что как нетрудно видеть, $p^k|q_{p^k}$, и полностью "сократить" эту степень из знаменателя в интервале $(p^k,p^{k+1})$ могут только $n$ вида $m\cdot p^k$. Однако с ростом $n$ это становится маловероятно. Грубо говоря, степень $p^t$ сокращается для $n\in (p^k,p^{k+1})$ с вероятностью $p^{-t+1}$ (то есть, с примерно такой вероятностью найдется $n$ в этом интервале, для которого $q_n$ делится лишь на $p^{k-t}$). Таким образом, за вероятность существования $n>p^k$, для которого $p\not| q_n$ отвечает хвост геометрической прогрессии: $\sum_{j=k}^{\infty} p^{1-j}$, который стремится к нулю с ростом $k$.

Другими словами, следующее утверждение становиться неверным при больших $k$:

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

Соответственно p>2 и для любого $k$ должен существовать $p^k\le n<p^{k+1}$, что $p\not |q_n$.

Например, оно неверно для $p=3$ и $k=4$ (и скорее всего для всех $k\geq 4$).

Добавлено спустя 28 минут 1 секунду:

Кстати, раз уж в этой теме всплыла последовательность A125581, предлагаю связанную с ней задачу:

Найти изолированный элемент A125581 или доказать, что таких нет.

Число $n$ называется изолированным элементом A125581, если $n$ является элементом A125581, но $n\cdot d$ не является элементом A125581 ни для какого собственного делителя $d|n$.

P.S. Решение этой задачи мне не известно - когда-то начинал поиск, но так и не довел до логического конца.

[Руст]

maxal писал(а):

Например, оно неверно для $p=3$ и $k=4$ (и скорее всего для всех $k\geq 4$).

Если для какого k это проверено (не обязательно для p=3), то очевидно, что оно выполняется для всех больших k. Таким образом устанавливаются, что p не "хорошее" в этой задаче для многих p уже при k=3 или k=4.

Цитата:

Кстати, раз уж в этой теме всплыла последовательность A125581, предлагаю связанную с ней задачу:

Найти изолированный элемент A125581 или доказать, что таких нет.

Число $n$ называется изолированным элементом A125581, если $n$ является элементом A125581, но $n\cdot d$ не является элементом A125581 ни для какого собственного делителя $d|n$.

P.S. Решение этой задачи мне не известно - когда-то начинал поиск, но так и не довел до логического конца.

Правильно я понимаю, что здесь n "хорошее", если он не один из знаменателей $q_n,q_n'$ соответствующих гармонических сумм. Если так, то я сомневаюсь в существовании изолированных "хороших".

[maxal]

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

maxal писал(а):

Например, оно неверно для $p=3$ и $k=4$ (и скорее всего для всех $k\geq 4$).

Если для какого k это проверено (не обязательно для p=3), то очевидно, что оно выполняется для всех больших k.

Очевидно ли? Можно увидеть доказательство?

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

Правильно я понимаю, что здесь n "хорошее", если он не один из знаменателей $q_n,q_n'$ соответствующих гармонических сумм. Если так, то я сомневаюсь в существовании изолированных "хороших".

Понимаете правильно. Но мне, наоборот, кажется, что изолированные элементы существуют. Разуверюсь только, если кто-то предъявит доказательство, что их нет

[Руст]

maxal писал(а):

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

maxal писал(а):

Например, оно неверно для $p=3$ и $k=4$ (и скорее всего для всех $k\geq 4$).

Если для какого k это проверено (не обязательно для p=3), то очевидно, что оно выполняется для всех больших k.

Очевидно ли? Можно увидеть доказательство?

Допустим, что для любых n из интервала $p^k\le n<p^{k+1}$ знаменатель делится на p. Тогда для $m=np+c, c<p$ получаем $H_m=H'_m+\frac 1p H_n$, где

$$H'_m=\sum_{x\le m, (x,p)=1}\frac 1x $$

p-aдический целое. Поэтому для любого m из интервала $p^{k+1}\le m<p^{k+2}$ знаменатель делится как минимум на $p^2$ а из интервала $p^l\le m<p^{l+1}$ как минимум на $p^{l-k+1}$.
Несуществование изолированных в твоей задаче доказывается примерно так же просто.

[maxal]

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

Допустим, что для любых n из интервала $p^k\le n<p^{k+1}$ знаменатель делится на p. Тогда для $m=np+c, c<p$ получаем $H_m=H'_m+\frac 1p H_n$, где

$$H'_m=\sum_{x\le m, (x,p)=1}\frac 1x $$

p-aдический целое. Поэтому для любого m из интервала $p^{k+1}\le m<p^{k+2}$ знаменатель делится как минимум на $p^2$ а из интервала $p^l\le m<p^{l+1}$ как минимум на $p^{l-k+1}$.

Убедил. Что-то я проглядел эту идею на этот раз, хотя похожая конструкция у меня используется в программе, которая эффективно вычисляет значения $m,\ k$ по заданным $n,\ p$ в сравнении:

$$H_n \equiv m p^k\pmod{p^{k+1}}$$

где $p$ - простое, $p\not|m$.

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

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

У меня все еще есть сомнения на этот счет. Хочу увидеть доказательство

[maxal]

Рустем, так что там насчет изолированных решений? Есть доказательство несуществования или хотя бы вероятностные соображения?