Имеются гири с массами 1 г,2 г,...,n г (n<=10000).
Написать алгоритм, распределяющую эти гири на максимально возможное кол-во пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом. Т.е. определить это количество пар.

Интересно, есть такой алгоритм или это чисто переборная задача?

Здравствуйте Vi2, Вы писали:

Vi2>Имеются гири с массами 1 г,2 г,...,n г (n<=10000).
Vi2>Написать алгоритм, распределяющую эти гири на максимально возможное кол-во пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом. Т.е. определить это количество пар.

Vi2>Интересно, есть такой алгоритм или это чисто переборная задача?

Если решение существует, то число пар равно n/2.
Или я неправильно понял условия?

Здравствуйте Chorkov, Вы писали:

C>Если решение существует, то число пар равно n/2.

Скорее, это верхняя граница.

Здравствуйте Vi2, Вы писали:

Vi2>Здравствуйте Chorkov, Вы писали:

C>>Если решение существует, то число пар равно n/2.

Vi2>Скорее, это верхняя граница.

т.е. В пары могу входить не все числа и заданного множества ?

Допустимо ли существование двух пар имеющих одно значение ?

Здравствуйте Vi2, Вы писали:

C>>Если решение существует, то число пар равно n/2.

Vi2>Скорее, это верхняя граница.

Вот для n=p-1: n и 1, n-1 и 2, n-2 и 3 и т.д. Число = n/2
Вот для n=p: n — не используется, а n-1 и 1, n-2 и 2, n-3 и 3 и т.д. Число = (n-1)/2, равное n/2, если делить нацело.

Здравствуйте Chorkov, Вы писали:

C>т.е. В пары могу входить не все числа и заданного множества ?
C>Допустимо ли существование двух пар имеющих одно значение ?

Да и да.
Вот например для n=p — простое:
n — не используется,
а n-1 и 1, n-2 и 2, n-3 и 3 и т.д. в сумме дают n или p, которое простое. И таких пар n/2

Здравствуйте Chorkov, Вы писали:

C>Если решение существует, то число пар равно n/2.

Для любого n решение существует, если в интервале (n,2n-1] есть простое число p.
Интересно, можно ли это доказать.

А дальше тривиально — есть разница p-n, тогда (n и p-n), (n-1 и p-n+1) и т.д. образуют пары. Остаются числа 1,2,...,p-n-1, которые уж точно раскладываются (шаг индукции).

Здравствуйте Vi2, Вы писали:

Vi2>Здравствуйте Chorkov, Вы писали:

C>>т.е. В пары могу входить не все числа и заданного множества ?
C>>Допустимо ли существование двух пар имеющих одно значение ?

Vi2>Да и да.

N[i]=n;

P[i]= самое большее простое число, такое что : P[i]<N[i]*2;

Выделяем K пар, с суммой P[i], K[i]=(2 N[i] -P[i] -1)/2;

Повторяем задачю для N[i+1] = P[i]-N[i]-1.

Свего n/2 или (n-1)/2 пар.

Здравствуйте Vi2, Вы писали:

Vi2>Для любого n решение существует, если в интервале (n,2n-1] есть простое число p.
Vi2>Интересно, можно ли это доказать.

Доказателства не знаю, но тут

Автор: flyker
Дата: 29.03.02

промелькнуло сообщение что плотность простых чисел убывает очень медленно : 1/log(n), так-что, статистически, число простых чисел попадающих в отрезок [n, 2n], с ростом n будет только рости.

Здравствуйте Chorkov, Вы писали:

C>Здравствуйте Vi2, Вы писали:

Vi2>>Для любого n решение существует, если в интервале (n,2n-1] есть простое число p.
Vi2>>Интересно, можно ли это доказать.

C>Доказателства не знаю, но тут

Автор: flyker
Дата: 29.03.02

промелькнуло сообщение что плотность простых чисел убывает очень медленно : 1/log(n), так-что, статистически, число простых чисел попадающих в отрезок [n, 2n], с ростом n будет только рости.

О боже ну вы сказанули
Число простых чисел с ростом n падает ОЧЕНЬ быстро
Но факт что пробегатьься надо по простым числам и затем искать соответствующие им пары.
Для поиска надо идти шагами +2 +4 +2 +4 ... от 5-ки.

Здравствуйте adontz, Вы писали:

A>О боже ну вы сказанули
A>Число простых чисел с ростом n падает ОЧЕНЬ быстро

Очень быстро падает число простых чисел в каком промежутке?

Или этим ты хочешь сказать, что между [10,20) больше чисел, чем между [100,200), или [1000,2000), или [1000000,2000000)? С трудом верится.

Мне же достаточно наличие одного простого числа.

Здравствуйте Vi2, Вы писали:

Между [1,n] значительно больше чем между [n+1,2*n]

Здравствуйте adontz, Вы писали:

A>Здравствуйте Vi2, Вы писали:

A>Между [1,n] значительно больше чем между [n+1,2*n]

Теорема Чебышева: \pi(x) = n/ln(n), \pi(x) — количество простых чисел меньших х.
Так же верно утверждение, что между n и 2n всегда есть простое число, n>3 (я не проверял, но похоже на следствие из теоремы).

Кроме того, видно, что простых чисел _очень_ много.

Здравствуйте Colimit, Вы писали:

C>Здравствуйте adontz, Вы писали:

A>>Здравствуйте Vi2, Вы писали:

A>>Между [1,n] значительно больше чем между [n+1,2*n]

C>Теорема Чебышева: \pi(x) = n/ln(n), \pi(x) — количество простых чисел меньших х.
C>Так же верно утверждение, что между n и 2n всегда есть простое число, n>3 (я не проверял, но похоже на следствие из теоремы).

C>Кроме того, видно, что простых чисел _очень_ много

То что между [n,2n] существует хотя бы одно число может и правда, но это не следствие теоремы Чебышева, или поясните, что вы понимаете под теоремой Чебышева. Мне кажется, что она говорит об асимптотическом росте! А отсюда нельзя сделать вывода о количестве чисел на [n,2n] для некоторого n, формально отсюда не следует и то, что там вообще есть простые числа.

А>То что между [n,2n] существует хотя бы одно число может и правда, но это не следствие теоремы Чебышева, или поясните, что вы понимаете под теоремой Чебышева. Мне кажется, что она говорит об асимптотическом росте! А отсюда нельзя сделать вывода о количестве чисел на [n,2n] для некоторого n, формально отсюда не следует и то, что там вообще есть простые числа.

Верно, ассимптотическая. К сожалению, у меня нет под рукой книжки по теории чисел, но я помню, что есть еще одна теорема, где задаются две константы т.е. типа a*n/ln(n) < p(x) < b*n/ln(n). Ассимптотическая это или нет оценка я не помню :(. К тому же, наверняка, для p(x) известна погрешность и скорость ее убывания. Полно теорем и с менее точными оценками, но надо искать соответствующую литературу.

Здравствуйте Аноним, Вы писали:

А>>То что между [n,2n] существует хотя бы одно число может и правда, но это не следствие теоремы Чебышева, или поясните, что вы понимаете под теоремой Чебышева. Мне кажется, что она говорит об асимптотическом росте! А отсюда нельзя сделать вывода о количестве чисел на [n,2n] для некоторого n, формально отсюда не следует и то, что там вообще есть простые числа.

А>Верно, ассимптотическая. К сожалению, у меня нет под рукой книжки по теории чисел, но я помню, что есть еще одна теорема, где задаются две константы т.е. типа a*n/ln(n) < p(x) < b*n/ln(n). Ассимптотическая это или нет оценка я не помню :(. К тому же, наверняка, для p(x) известна погрешность и скорость ее убывания. Полно теорем и с менее точными оценками, но надо искать соответствующую литературу.

Возможно есть какие-то теоремы говорящие, что начиная с такого-то n то-то и то-то. Отсюда можно все и получить. Правда я их не помню, и они конечно будут посильнее теоремы Чебышева. А вообще наверняка про интервал [n,2n] --- какая-нибудь классическая вещь, про которую уже все знают.

Здравствуйте Colimit, Вы писали:

C>Кроме того, видно, что простых чисел _очень_ много.

Да не просто "_очень_ много", а бесконечно много. А в силу этого их континуум равен континууму целых чисел. Откуда и попытки их нумерации n -> p(n), n = 1,2,...