Помогите с задачей по программированию!

[JayDi]

Доброго времени суток вам. Зачетная неделя началась, а я только начал сдавать хвосты. Времени совсем мало...Есть задача : Среди простых чисел, не превосходящих заданного N, найти такое, в двоичной записи которого максимальное количество единиц. Задачу нужно сделать в Delphi. Кто-нибудь, помогите! Заранее благодарен.

[maxal]

Для небольших N, можно найти искомое число перебором всех чисел от 2 до N, проверяя на простоту и вычисляя число единичных разрядов в двочной записи. На простоту в этом случае можно проверять, например, заранее сгенерировав решетом Эратосфена битовый массив размерности N, в котором k-й элемент отвечает на за простоту числа k.

Для больших N лучше избрать другую стратегию: сначала находим m такое что $2^{m-1}\leq N<2^m$. Далее для каждого $k$ от $0$ до $m$ генерируем все числа $x$, содержащие $m$ двоичных разрядов, среди которых ровно $k$ нулей (количество таких чисел равно биномиальному коэффициенту ${m\choose k}$), для каждого такого $x$ проверяем выполняется ли $x\leq N$ и является ли x простым - если это так, то x - искомое.

Генерация всех сочетаний из m по k описана в книге "Программирование: теоремы и задачи"

Проверку на простоту можно осуществлять алгоритмом Миллера-Рабина, готовая реализация на Pascal есть тут (вопрос 2.3.3.1).

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

maxal писал(а):

Для больших N лучше избрать другую стратегию: сначала находим m такое что $2^{m-1}\leq N<2^m$

Тут надо осторожнее. $N$ может оказаться $2^{m-1}$. Поэтому надо проверять еще и $2^{m-2}\leq x <2^{m-1}$ (с соответственно меньшим количеством битов).

Кроме того, перебор можно уменьшить в два раза, если заметить, что первый и последний бит всегда 1. И, я не исключаю, что имеет смысл всегда сперва перебирать меньший диапазон — он задаст нижнюю границу, ниже которой не имеет смысла опускаться в большем диапазоне.

Кстати, мне неочевидно, достаточно ли опустить $m$ на $1$. Может статься, что $2^{m-2}-1$ простое число, а вот среди $2^{m-2}\leq x <2^{m-1}$ нет ни одного простого с $m-1$ битом. Поэтому, получив некоторый результат, надо двигаться по $m$ вниз, до тех пор, пока мы заведомо не попадем в меньшее количество бит…

[maxal]

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

Кстати, мне неочевидно, достаточно ли опустить $m$ на $1$.

Когда я говорил про числа $x$, содержащие $m$ двоичных разрядов, среди которых ровно $k$ нулей, я не ограничивал их теми, у которых старший бит равен 1. Поэтому m не надо никуда опускать.

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

Согласен.

И все-таки, младший бит можно считать $1$ …

Кстати, если $\Pi(k)$ — минимальное простое число, содержащее $k$ единичных бит, то как она растет? Есть ли какая-нибудь информация?

[maxal]

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

Кстати, если $\Pi(k)$ — минимальное простое число, содержащее $k$ единичных бит, то как она растет? Есть ли какая-нибудь информация?

Я думаю, что $\Pi(k)=2^{k+O(1)}$.

P.S. см. A061712.

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

Спасибо. Похоже, что $\max(\log_2 \Pi(j)-j) < 3$. По крайней мере, в практическом диапазоне. Так что $k$ (из Вашего решения) будет небольшим.

[JayDi]

Доброго вам времени суток...
Снова прошу вас о помощи. Просил помочь с решением задачки :Среди простых чисел, не превосходящих заданного N, найти такое, в двоичной записи которого максимальное количество единиц.
Я просто хотел узнать сами формулы для Delpi, а люди вместо этого устроили высокие научные суждения, из которых я понял, что я ничего не понял . Может кто скинет просто формулы. Буду очень благодарен.

[PAV]

Замечание за дублирование темы.
Тема объединена с предыдущей. // нг

Видимо, раз речь идет о хвостах, то большая теория Вам действительно не нужна.

Для решения задачи требуется написать две функции. Первая по заданному числу проверяет, простое оно или нет. Вторая по заданному числу возвращает количество единиц в его двоичном разложении. При наличии этих двух функций задача тривиальна - обычный цикл.

Какие из этих пунктов вызывают затруднения?

Можно также держать в голове пару тривиальных приемов, позволяющих ускорить выполнение. Надеюсь, очевидно, что проверять нужно только нечетные числа. Далее простое соображение гласит, что так как проверка числа на простоту занимает больше времени, чем подсчет числа единиц в двоичном разложении, то сначала имеет смысл подсчитать число единиц, сравнить его с найденным ранее максимальным, после чего проверять число на простоту только тогда, когда число единиц больше найденного ранее.

[JayDi]

Спасибо вам огромное!!! Задачу сделал. Вот это я понимаю, простое и понятное разъяснение.