## Russian ##

## 1 Идея ##

1) Представим число A в виде 10x+m1, где x - число десятков
m1=2 (m1 не может быть равно 1, так как в этом случае искомое число A нечетное и на 2^N не разделится). Разделим число на 2, получим A=5x+1.
2) Пусть x=10y+m2, где y - число сотен. После подстановки получим A=5(10y+m2)+1=50y+5m2+1. Чтобы число A разделилось на 2, надо, чтобы m2 было нечетным. Следовательно выбираем m2=1. После деления на 2 получим: A=(50y+5*1+1)/2=25y+3.
3) Пусть y=10z+m3, где z - число тысяч. После подстановки получим A=25(10z+m3)+3=250z+25m3+3. Чтобы число A разделилось на 2, надо, чтобы m3 было нечетным. Следовательно выбираем m3=1. После деления на 2 получим: A=(250z+25*1+3)/2=125z+14.
4) Пусть z=10t+m4, где t - число десятков тысяч. После подстановки получим A=125(10t+m4)+14=1250t+125m4+14. Чтобы число A разделилось на 2, надо, чтобы m4 было четным. Следовательно выбираем m4=2. После деления на 2 получим: A=(1250t+125*2+14)/2=625t+132.

Далее процесс повторяется N раз. Последовательность mN...m4m3m2m1 образует ответ. Алгоритм требует применения длинной арифметики. Общее решение достигается за N шагов.

## 2 Алгоритм ##
Пусть m[1]=2; a_[1]=5; b_[1]=1;
Цикл i = от 2 до n
нц
  m_[i]=(если b_[i-1] нечетное, то 1, иначе 2)
  b_[i]=(если b_[i-1] нечетное, то (a_[i-1]+b_[i-1])/2, иначе (2*a_[i-1]+b_[i-1])/2)
  (так как a_[i-1] нечетное всегда по определению)
  a_[i]=a_[i-1]*5;
кц

## English (in short) ##

## 1 The Idea ##

1) Let me A = 10x+m1, where x - number of Tens
m1=2 (m1<>1, as A - odd). Division A in 2, let's receive A=5x+1.
2) Let me x=10y+m2, where y - number of Hundreds. Then A=5(10y+m2)+1=50y+5m2+1. if A%2==0, m2 is odd. Then m2=1 and A=(50y+5*1+1)/2=25y+3.
3) Let me y=10z+m3, where z - number of Thousand. Then A=25(10z+m3)+3=250z+25m3+3. if A%2==0, m3 is odd. Then m3=1 and A=(250z+25*1+3)/2=125z+14.
4) Let me z=10t+m4, где t - number of Tens thousand. Then A=125(10t+m4)+14=1250t+125m4+14. if A%2==0, m3 is even. Then m3=1 and A=(1250t+125*2+14)/2=625t+132.

Further process repeats N time. Sequence mN... m4m3m2m1 forms the answer. The algorithm demands application of long arithmetics.

## 2 The Algo ##
Let me m[1]=2; a_[1]=5; b_[1]=1;
for i = 2 to n
begin
  m_[i]=(if b_[i-1] is odd, then 1, else 2)
  b_[i]=(if b_[i-1] is odd, then (a_[i-1]+b_[i-1])/2, else (2*a_[i-1]+b_[i-1])/2)
  a_[i]=a_[i-1]*5;
end

thank you! excellent idea!

Можно проще.
Индукция: для любого n существует число x(n) из 1 и 2 длиной n, делящееся на 2^n.
База: n=1=>x(1)=2.
Переход n->n+1: если x(n) делится на 2^(n+1), то в качестве x(n+1) можно взять x(n+1)=2x(n) (т.е. слева приписать 2), иначе x(n+1)=1x(n).

Edited by author 10.03.2019 13:22