Форум умных людей

Задачи и головоломки => Помогите решить! => Тема начата: Sirion от Январь 15, 2012, 16:10:43



Название: Хорошие числа
Отправлено: Sirion от Январь 15, 2012, 16:10:43
Определим множество хороших чисел следующим образом:

    1 - хорошее число;
    если p и q - хорошие числа, и r=pq+2 - простое число, то r - хорошее число;
    множество хороших чисел - наименьшее по включению множество, удовлетворяющее этим требованиям.


Верно ли, что хороших чисел бесконечно много?


Название: Re: Хорошие числа
Отправлено: Seamew от Январь 16, 2012, 18:15:25
тогда хорошие числа:
1*1+2 = 3
3*1+2 = 5
3*5+2 = 17
17*5+2 = 87 - не простое
17*3+2 = 53
53*17+2 = 903 - не простое
5*53 +2 = 267 - не простое
3*53 + 2 = 161 - не простое
тупик.
 :-[


Название: Re: Хорошие числа
Отправлено: Sirion от Январь 16, 2012, 18:21:04
а где семёрка, например?


Название: Re: Хорошие числа
Отправлено: Seamew от Январь 16, 2012, 19:21:15
ну да, при умножении на 1 еще.. но оно тоже, мне кажется, вскоре зайдет в тупик


Название: Re: Хорошие числа
Отправлено: moonlight от Январь 16, 2012, 21:42:11
среди первых 300 000 000 чисел хороших 4712.


Название: Re: Хорошие числа
Отправлено: iPhonograph от Январь 17, 2012, 00:28:59
среди первого млрд чисел хороших чуть меньше 7 тыщщ
а вообще да, есть опасение что они когда-нибудь кончатся


Название: Re: Хорошие числа
Отправлено: Sirion от Январь 17, 2012, 21:34:31
если рассматривать частоту хороших чисел среди натуральных - то таки да, их как-то мало
но если смотреть, какое количество K новых хороших чисел непосредственно порождается множеством из N первых хороших чисел, то по опытным данным K растёт быстрее N


Название: Re: Хорошие числа
Отправлено: moonlight от Январь 20, 2012, 22:42:30
Почитал я то что написано на эту тему на dxdy (из 10000 получается 134315).
У меня получились другие цифры.
Из 10985 хороших чисел <2^32 можно получить 717305 новых в диапазоне 2^32...2^64.


Название: Re: Хорошие числа
Отправлено: Sirion от Январь 20, 2012, 22:45:42
тут просто немного разные подходы
я строил хорошие числа конструкивно, т.е. имелись в виду первые 10000 построенных
если брать 10000 первых - очевидно, коэффициент расширения будет больше