Имеются гири с массами 1 г,2 г,...,n г (n<=10000).
Написать алгоритм, распределяющую эти гири на максимально возможное кол-во пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом. Т.е. определить это количество пар.
Интересно, есть такой алгоритм или это чисто переборная задача?
Здравствуйте Vi2, Вы писали:
Vi2>Имеются гири с массами 1 г,2 г,...,n г (n<=10000). Vi2>Написать алгоритм, распределяющую эти гири на максимально возможное кол-во пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом. Т.е. определить это количество пар.
Vi2>Интересно, есть такой алгоритм или это чисто переборная задача?
Если решение существует, то число пар равно n/2.
Или я неправильно понял условия?
Здравствуйте 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;
Здравствуйте Vi2, Вы писали:
Vi2>Для любого n решение существует, если в интервале (n,2n-1] есть простое число p. Vi2>Интересно, можно ли это доказать.
промелькнуло сообщение что плотность простых чисел убывает очень медленно : 1/log(n), так-что, статистически, число простых чисел попадающих в отрезок [n, 2n], с ростом n будет только рости.
Здравствуйте Chorkov, Вы писали:
C>Здравствуйте Vi2, Вы писали:
Vi2>>Для любого n решение существует, если в интервале (n,2n-1] есть простое число p. Vi2>>Интересно, можно ли это доказать.
C>Доказателства не знаю, но тут
промелькнуло сообщение что плотность простых чисел убывает очень медленно : 1/log(n), так-что, статистически, число простых чисел попадающих в отрезок [n, 2n], с ростом n будет только рости.
О боже ну вы сказанули
Число простых чисел с ростом n падает ОЧЕНЬ быстро
Но факт что пробегатьься надо по простым числам и затем искать соответствующие им пары.
Для поиска надо идти шагами +2 +4 +2 +4 ... от 5-ки.
Здравствуйте adontz, Вы писали:
A>Здравствуйте Vi2, Вы писали:
A>Между [1,n] значительно больше чем между [n+1,2*n]
Теорема Чебышева: \pi(x) = n/ln(n), \pi(x) — количество простых чисел меньших х.
Так же верно утверждение, что между n и 2n всегда есть простое число, n>3 (я не проверял, но похоже на следствие из теоремы).
Кроме того, видно, что простых чисел _очень_ много.
Re[8]: Да, их n/2
От:
Аноним
Дата:
12.08.02 17:53
Оценка:
Здравствуйте 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, формально отсюда не следует и то, что там вообще есть простые числа.
Re[9]: Да, их n/2
От:
Аноним
Дата:
12.08.02 18:49
Оценка:
А>То что между [n,2n] существует хотя бы одно число может и правда, но это не следствие теоремы Чебышева, или поясните, что вы понимаете под теоремой Чебышева. Мне кажется, что она говорит об асимптотическом росте! А отсюда нельзя сделать вывода о количестве чисел на [n,2n] для некоторого n, формально отсюда не следует и то, что там вообще есть простые числа.
Верно, ассимптотическая. К сожалению, у меня нет под рукой книжки по теории чисел, но я помню, что есть еще одна теорема, где задаются две константы т.е. типа a*n/ln(n) < p(x) < b*n/ln(n). Ассимптотическая это или нет оценка я не помню :(. К тому же, наверняка, для p(x) известна погрешность и скорость ее убывания. Полно теорем и с менее точными оценками, но надо искать соответствующую литературу.
Re[10]: Да, их n/2
От:
Аноним
Дата:
12.08.02 18:59
Оценка:
Здравствуйте Аноним, Вы писали:
А>>То что между [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,...