Числовой корень

[wpoms.]

Для натурального числа `a_1` образуем последовательность `a_1, a_2, a_3, ...` по следующему принципу: `a_k` равно произведению цифр числа `a_{k-1}` при `k >= 2`. Если для некоторого `k >= 1` `a_k` является однозначным числом, то `a_k` называется числовым корнем `a_1`. Легко проверить, что для каждого натурального числа существует единственный числовой корень. (например, если `a_1 = 24378`, то `a_2 = 1344`, `a_3 = 48`, `a_4 = 32`, `a_5 = 6`, и, таким образом, `6` является числовым корнем для `24378`.) Докажите, что числовой корень натурального числа `n` равен `1` тогда и только тогда, когда все цифры `n` равны `1`.

@темы: Теория чисел

Comments

[Trotil]

Задача сводится к тому, чтобы доказать, что factor(11..1) будет содержать как минимум один двузначный делитель.

а=10^(n-1)+10^(n-1)+...1
Заметим, что a mod 5 != 0
Заметим, что a mod 2 != 0

0) n=2..5 - проверяется вручную.
1) для n = 6k справедливо
a mod 37 = 0.
a mod 3 = 0
a mod 7 = 0
(111111=3*7*11*13*37, 111=3*37, a=111111*(10^6(k-1)+10^6(k-2)+...+1))

2) n=6k+1:
a mod 3 = 10^(6k+1) = 1
a mod 7 = 10^(6k+1) = 3
не содержит делителей 3,7.

2) n=6k+2:
a mod 3 = 1+10^(6k+2) = 2
a mod 7 = 3+10^(6k+2) = 5
не содержит делителей 3,7.

3) n=6k+3:
a mod 37 = 0.
4) аналогично, n=6k+4, n=6k+5 не содержит делителей 3,7.

[Груша Вильямс]

Trotil, а factor(11..1) это число состоящее из k единиц? Честно говоря условие задачи меня неслабо напугало)

[Trotil]

factor(11..1)

это факторизация числа, состоящего из одних единиц, то бишь разложение числа на множители.