Распределение в (n,2n) значений функций Эйлера кратных 3

[ananova]

Добрый день!

Вот такая задача. Не смог найти на нее ответ в Википедии: http://en.wikipedia.org/wiki/Euler%27s_totient_function.

Примеры.
пусть число $n=7$
в интервале $(n, 2n)=(7,14)$ присутствует 3 простых числа $7, 11$ и $13$, а также 4 числа, имеющих функцию Эйлера кратную 3: $7, 9, 13, 14$.
$n=13$
в интервале $(n, 2n)=(13,26)$ присутствует 4 простых числа $13, 17, 19, 23$, а также 6 чисел, имеющих функцию Эйлера кратную 3: $13, 14, 18, 19, 21, 26$.
$n=19$
в интервале $(n, 2n)=(19,38)$ присутствует 5 простых чисел $19, 23, 29, 31, 37$, а также 11 чисел, имеющих функцию Эйлера кратную 3: $19, 21, 26, 27, 28, 26, 31, 35, 36, 37, 38.$

(Оффтоп)

(пока "на пальцах" соотношение не в пользу простых чисел) .

В общем-то, меня интересует не это. Мне нужно доказать или дать ссылку на доказательство, что в интервале $(n, 2n)$ не может находиться $n$ чисел (т.е. во всем интервале), имеющих функцию Эйлера кратную 3. Т.е. в заданном интервале $(n, 2n)$ всегда будет присутствовать хоть одно число, не имеющее функцию Эйлера кратную 3. На сколько это сложно доказать или есть простое доказательство этому наблюдению?

Deggial: формулы поправил. В случае повторного неоформления формул утащу тему в Карантин.

[vorvalm]

По крайней мере, это может быть в тех интервалах $(n,2n)$,
где есть простые числа типа $6k-1$ или их произведения.
Число $p=3$ может входить в эти произведения в степени 1,
а $p=2$ - в любой.

[vorvalm]

Числа $2^k\cdot 5$ наверное будут во всех интервалах $(n,2n)$ при $n>2.$
$(k=0,1.2...)$

[ananova]

Не понял однако..
Попробую переформулировать вопрос:

$\varphi(m)$ - значение функции Эйлера числа $m$
$(\varphi(m),3)=1$
$m \in (n,2n)$

всегда ли найдется такое $m$?

Правильно ли я понял, что числа вида $5 \cdot 2^{k}$ всегда будут попадать в заданные интервалы?

[venco]

vorvalm прав, хотя есть и проще вариант.

-- Вт апр 23, 2013 09:17:48 --

Только сейчас заметил, что у вас интервалы открытые, т.е. к тому, что предложил vorvalm надо добавить вариант попроще, и доказательство готово.

[Deggial]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Помогите решить / разобраться (М)»
Перенёс в соответствующий раздел

[ananova]

venco в сообщении #714582 писал(а):

vorvalm прав, хотя есть и проще вариант.

-- Вт апр 23, 2013 09:17:48 --

Только сейчас заметил, что у вас интервалы открытые, т.е. к тому, что предложил vorvalm надо добавить вариант попроще, и доказательство готово.

Спасибо большое!

[Sonic86]

vorvalm в сообщении #714553 писал(а):

Числа $2^k\cdot 5$ наверное будут во всех интервалах $(n,2n)$ при $n>2.$
$(k=0,1.2...)$

Можно рассмотреть объединение множеств чисел $2^k\cdot P$, где $P$ - произвольное произведение простых вида $6k-1$ (даже необязательно различных, т.е. $\{5;5^2;5^3;...;11;11^2;11^3;...5^a\cdot 11^b;...; 5^a\cdot 11^b\cdot 17^c;...\}$) - такое множество будет еще плотнее
А хотя не факт даже... Надо явно посчитать...
Может у него даже ненулевая плотность будет?

[vorvalm]

Плотнее, чем $2^k\cdot 5$ ?

[venco]

Только сейчас заметил, что спрашивается о кратных 3, а не наоборот.
Т.е. $7k$, $9k$, $13k$, $19k$ и т.д.

[ananova]

venco в сообщении #714698 писал(а):

Только сейчас заметил, что спрашивается о кратных 3, а не наоборот.
Т.е. $7k$, $9k$, $13k$, $19k$ и т.д.

Почему кратных 3?
Условие как раз не для них:

НОД $(\varphi(m),3)=1$

Для кратных бы написал:
$(\varphi(m),3)=3$

[venco]

А в названии темы что написано?

[ananova]

venco в сообщении #715033 писал(а):

А в названии темы что написано?

Согласен! Формулировка неоднозначна, но тема верная.

Согласно темы - интересует распределение чисел, с подобными свойствами - оно возможно с "дырками" в заданном диапазоне чисел или существуют диапазоны, где таких "дырок" нет.

Как вариант решения - поиск чисел в заданном диапазоне - не обладающих такими свойствами (указанными в теме). Отсюда и определение таких чисел - неудовлетворяющих заданному свойству.