В ячейку памяти  компьютера  записали  число  6.  Далее компьютер делает миллион шагов. На шаге номер n он увеличивает число в ячейке на  наибольший  общий  делитель этого числа и n.  Докажите, что на любом шаге компьютер увеличивает число в ячейке либо на 1,  либо на  простое число.
Размер ячейки достаточно велик - переполнения за миллион шагов не происходит.

Начинается с первого шага:
7,8,9,10,15,18,19,....
приращения:
1,1,1,1,5,3,1,....

(1) это расскажи мне, пожалуйста, с каким числом у числа 6 есть НОД 5?... ты в условие сам вчитайся...

+(2) у 6 делители только: 1,2,3,6
а соответственно у чисел, кратных 6, НОД с числом 6 будет 6! как-то в условие не вяжется...

(2) это ты сам прочти условие, как бы. 6 только первоначально в ячейки, потом уже нет

"На шаге номер n он увеличивает число в ячейке на  наибольший  общий  делитель этого числа и n."

(5) а, этого числа.... :)

(6) отож

(1) "Начинается с первого шага:
7,8,9,10,15,18,19" - У 18 есть делитель 9. Почему на него не увеличило? Почему после 8 идет 9, а не 12?

(8) ищется наибольший ОБЩИЙ делитель с НОМЕРОМ шага

7,8,9,10,15,18,19,20,21,22,33,35,36,...
надо программку написать, больно забавный факт

(9) Ну и куй с ним. На 8 шаге надо увеличивать на 4. 4 - не простое число. Или я опять чего-то не уловил?

Че за народ. Им задачку задаешь, а они ошибку в условии ищут ))

(11) перед началом восьмого шага у нас 19, а НОД(8,19)=1

(12) привычка, из 1С

(14) Это назаывается: Найти сто причин чтобы не делать ))

это вам не тут http://wwwboards.auto.ru/housing/2748688.html

Очень похоже, что это верно не только для 6 в качестве начального

Интересно было бы получить распределение таких простых чисел

получаемая последовательность "почти монотонно увеличивается на единицу", небольшие скачки вначале поддаются определенной закономерности, но далее закономерность их исчезает

мозговой штурм!

ни х.. непонятно почему

Идеи есть куда копнуть?

(22) если честно - нет

что-то раньше народ больше математикой интересовался

(24) На эту задачу нужно время потратить, а она не простая хоть и на уровне знаний школьника, как понял олимпиадная. А чем еще на работе заниматься кроме как математикой? :)

шаг номер 1 НОД(1,6)=1
шаг номер 2 НОД(2,6)=2, а у тебя 1?
З.Ы. заранее признаю, что тупой, просто объясните где ошибка?

Всё, понял, на втором шаге НОД(2,7) ?

(27) да

(27) ты с кубань.ру?

Под БТР только здесь постил, на кубани уже сто лет не был.

(26)
на втором шаге прибавляем к 6 НОД от первого шага, получается
шаг номер 2
НОД(2,7)=1

Вроде по условию должно быть:
если а_i=n*p и i=m*p, то НОД(n,m)=1
и
НОД(n+1,mp+1)=1 или простое число.

(32) правильнее так формулировать:
если а_i=n*p и i=m*p, то НОД(n,m)=1, где p-простое или 1
и
НОД(n*p+p,m*p+1)=1 или простое число.

или так:
если НОД(a_i,i)=p, где p-простое или 1
то
НОД(a_i+p,i+1)=1 или простое число.

у меня правильно последовательность получается или как?
шаг - значение - НОД
1 - 6 - 1
2 - 7 - 1
3 - 8 - 1
4 - 9 - 1
5 - 10 - 5
6 - 15 - 1
7 - 16 - 1
8 - 17 - 1
9 - 18 - 9
10 - 27 - 1

(0)Ставлю на ноль :)

надо доказывать методом итераций!

(34) НОД(6,15)=3

(34)
1 - 6 - 1
2 - 7 - 1
3 - 8 - 1
4 - 9 - 1
5 - 10 - 5
6 - 15 - 3
7 - 18 - 1
8 - 19 - 1
9 - 20 - 1
10 - 21 - 1
11 - 22 - 11
12 - 33 - 3
13 - 36 - 1

Заодно и потренируемся вычислять НОД

(36) Скорее по индукции
(39) Точно )

вот таблица "скачков" (когда НОД>1) для первых 100000000 шагов:
первое число - номер шага, второе - значение перед шагом, третье - НОД
5 10 5
6 15 3
11 22 11
12 33 3
23 46 23
24 69 3
47 94 47
48 141 3
50 145 5
51 150 3
101 202 101
102 303 3
105 308 7
110 319 11
111 330 3
117 338 13
233 466 233
234 699 3
467 934 467
468 1401 3
470 1405 5
471 1410 3
941 1882 941
942 2823 3
945 2828 7
1889 3778 1889
1890 5667 3
3779 7558 3779
3780 11337 3
7559 15118 7559
7560 22677 3
7566 22685 13
15131 30262 15131
15132 45393 3
15158 45421 53
15159 45474 3
15162 45479 7
30323 60646 30323
30324 90969 3
60647 121294 60647
60648 181941 3
60650 181945 5
60651 181950 3
60701 182002 101
60702 182103 3
121403 242806 121403
121404 364209 3
242807 485614 242807
242808 728421 3
242810 728425 5
242811 728430 3
242820 728441 19
242823 728462 7
242825 728470 5
242826 728475 3
242849 728500 47
242850 728547 3
242868 728567 37
242870 728605 5
242871 728610 3
242879 728620 17
242880 728637 3
242979 728738 199
243005 728962 53
243006 729015 3
243020 729031 29
243021 729060 3
486041 972082 486041
486042 1458123 3
486045 1458128 7
486255 1458344 421
486266 1458775 23
486267 1458798 3
972533 1945066 972533
972534 2917599 3
972822 2917889 577
972825 2918468 7
1945649 3891298 1945649
1945650 5836947 3
1945731 5837030 163
1945734 5837195 7
3891467 7782934 3891467
3891468 11674401 3
3891470 11674405 5
3891471 11674410 3
3891534 11674475 127
3891755 11674822 443
3891756 11675265 3
3891771 11675282 31
7783541 15567082 7783541
7783542 23350623 3
7783545 23350628 7
15567089 31134178 15567089
15567090 46701267 3
15567099 46701278 19
15567113 46701310 29
15567114 46701339 3
15569775 46704002 5323
15569778 46709327 7
15569780 46709335 5
15569781 46709340 3
31139561 62279122 31139561
31139562 93418683 3
31139582 93418705 41
31139583 93418746 3
31139585 93418750 5
31139586 93418755 3
62279171 124558342 62279171
62279172 186837513 3
62279175 186837518 7
62279216 186837565 83
62279217 186837648 3
62279226 186837659 19
62279240 186837691 29
62279241 186837720 3
62279792 186838273 1103
62279793 186839376 3
62279795 186839380 5
62279796 186839385 3
62279802 186839393 13
62279805 186839408 7

как видно скачки расположены в областях шагов, номера которых примерно в 2 раза увеличиваются относительно предыдущих значений
видно, что НОД=2 нет (очевидно), очень часто встречается 3

Похоже получается, что предел отношения следующего максимума к предыдущему будет 2.

62279171/31139561~2,0000015...

Плюс максимумы достаточно просто рассчитываются (наверное). Берем первый простой номер шага, умножаем его на 2, и следующее простое число будет максимумом.

(44) нет, не так

очуметь!
http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Rowland/rowland21.pdf

+(46) но там правда для 7
задача со школьного турнира городов, неужели такую сложную задачу дали детям?

хотя да http://ru.wikipedia.org/wiki/Турнир_городов
Многие задачи в качестве одного из пунктов имеют открытые математические проблемы.

(0)
Вот вы блин одинэсники...
Как старый сиплюсплюсник скажу, что комп вылетит на нулевом шаге, ибо НОД с 0 не существует.

(49) все начинается с 1 шага
а на счет 0 Вы не правы НОД(0,х)=х при x>0

Насчет НОД с нулем затупил, каюсь.