Здравствуйте, Pro100Oleh, Вы писали:

PO>Здравствуйте, Roman Odaisky, Вы писали:

RO>>Кстати, задача довольно легко параллелизуется. Как удвоение, так и поиск нулей можно поручить разным процессорам, разделив число на части. Чьи программы здесь масштабируются при наличии нескольких процессоров?

PO>Распараллерировать не интересно. Здесь нужен математических подход в решении задачи, который бы позволил на порядок уменьшить сложность вычислений. Играться же в командах, чтобы выполнить оператор не за 5 тактов, а за 4 — малоэффективно (пусть и увеличится скорость работы в 2-3 раза). Возращаясь к параллельности — распараллерировать нужно не саму итерацию умножение числа 2^x на 2 и далее проверку на нули. Нужно, чтобы был один главный поток, который бы давал своим рабочим потокам задачу: проверитьвсе числа в диапазоне 2^x ... 2^(x+1000) например. Здесь бы ядра использовались в полную силу.

Да, если бы, например, были какие-то верхние и нижние границы. Хотя бы рекурсивные...

Здравствуйте, vadimcher, Вы писали:

RO>>На Pentium 4 (3 ГГц, мегабайт кеша L2) считает a(8) за 6,7 с (при -DLOG_BASE=7), интеловский компилятор справляется за 6,3 с. На сервере, где Intel Q6600 и 4 МБ кеша, работает за 2,6 с. a(10) — 379 с здесь и 74 с там.

V>Странно, в твоей предыдущей "неоптимизированной" версии a(8) считалось за 0.46 секунд...

Прошу прощения, не a(8) за 6,7 с, а a(9).

Здравствуйте, Roman Odaisky, Вы писали:

RO>Здравствуйте, vadimcher, Вы писали:

RO>>>На Pentium 4 (3 ГГц, мегабайт кеша L2) считает a(8) за 6,7 с (при -DLOG_BASE=7), интеловский компилятор справляется за 6,3 с. На сервере, где Intel Q6600 и 4 МБ кеша, работает за 2,6 с. a(10) — 379 с здесь и 74 с там.

V>>Странно, в твоей предыдущей "неоптимизированной" версии a(8) считалось за 0.46 секунд...

RO>Прошу прощения, не a(8) за 6,7 с, а a(9).

Да, я так и подумал...

Здравствуйте, vadimcher, Вы писали:

V>Да, если бы, например, были какие-то верхние и нижние границы. Хотя бы рекурсивные...

Судя по этому графику есть логарифмическая зависимость степени от k. Только это нужно доказать

Здравствуйте, Roman Odaisky, Вы писали:

RO>Хм, надо было смотреть на название функции...
+1, ну вообще весь остальной код

E>>Ну и хрен ли тогда советовать заменить корректный С++ цикл на некорректное использование стандартного алгоритма?
RO>А хрен ли слушать всякие вредные советы?

Ну так я и не послушал. Зато теперь я ещё больше углубился во мнении, что прежде чем куда совать STL надо пару раз подумать
А то даже такие последовательные поклонники этой библиотеки, как ты, на ровном месте с ней лажают Куда уж нам, простым привыкшим к MFL парням?

Здравствуйте, Roman Odaisky, Вы писали:

RO>Данные из n у меня берутся последовательно, а вот из mdczt — случайным образом, поэтому именно таблица должна полностью помещаться в кеше, не число.
Ну если в кэш помещается всё, то быстрее получится, чем, если не всё. Я так думаю, что пока всё число лезет в кэш вместе с таблицами, не имеет смысла ускорять обработку одной цифры, за счёт риска перестать помещаться в кэш...

Здравствуйте, Pro100Oleh, Вы писали:

PO>Распараллерировать не интересно. Здесь нужен математических подход в решении задачи, который бы позволил на порядок уменьшить сложность вычислений. Играться же в командах, чтобы выполнить оператор не за 5 тактов, а за 4 — малоэффективно (пусть и увеличится скорость работы в 2-3 раза). Возращаясь к параллельности — распараллерировать нужно не саму итерацию умножение числа 2^x на 2 и далее проверку на нули. Нужно, чтобы был один главный поток, который бы давал своим рабочим потокам задачу: проверитьвсе числа в диапазоне 2^x ... 2^(x+1000) например. Здесь бы ядра использовались в полную силу.

Можно хорошо распарарллелить, на самом деле. И просто довольно. Только мне пока некогда и машин многоголовых всё равно нету.
Могу отладить на двухголовой, и выложить, если есть желающие/могущие на кластере запустить...

Общая идея такая, что тормоза начинаются на реально длинных числах. Скажем на числах длинною в десятки миллионов цифр. Соответственно такую задачу и надо параллелить. Параллелить надо так. Каждый процесс идёт по куску числа и всё что надо считает. Доходит до какой-то границы, скажем в миллион цифр, и отдаёт задание в очередь для следующего процесса. А сам возвращается ждать задания от предыдущего. Будет линейно масштабироваться...

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Pro100Oleh, Вы писали:

PO>>Распараллерировать не интересно. Здесь нужен математических подход в решении задачи, который бы позволил на порядок уменьшить сложность вычислений. Играться же в командах, чтобы выполнить оператор не за 5 тактов, а за 4 — малоэффективно (пусть и увеличится скорость работы в 2-3 раза). Возращаясь к параллельности — распараллерировать нужно не саму итерацию умножение числа 2^x на 2 и далее проверку на нули. Нужно, чтобы был один главный поток, который бы давал своим рабочим потокам задачу: проверитьвсе числа в диапазоне 2^x ... 2^(x+1000) например. Здесь бы ядра использовались в полную силу.

E>Можно хорошо распарарллелить, на самом деле. И просто довольно. Только мне пока некогда и машин многоголовых всё равно нету.
E>Могу отладить на двухголовой, и выложить, если есть желающие/могущие на кластере запустить...

E>Общая идея такая, что тормоза начинаются на реально длинных числах. Скажем на числах длинною в десятки миллионов цифр. Соответственно такую задачу и надо параллелить. Параллелить надо так. Каждый процесс идёт по куску числа и всё что надо считает. Доходит до какой-то границы, скажем в миллион цифр, и отдаёт задание в очередь для следующего процесса. А сам возвращается ждать задания от предыдущего. Будет линейно масштабироваться...

Мне тоже подумалось сначала что-то навроде этого. Т.е. если длина n*k цифр, то n головам отдаем по k цифр на растерзание, причем следующим образом: i-я голова получает на вход цифры c (i-1)*k+1 по i*k а также перенос от правого соседа, который можно тут же вычислить (если правое число начинается с 5 или больше, то будет перенос в эту часть, если нет -- то не будет), далее умножает свою часть на два с прибавлением полученного переноса, а также игнорируя возможный перенос в левую часть (он уже учтен у соседа слева при получении задания) и возвращает вектор значений (l, lb, le), где l -- максимальная найденная строка из нулей, lb -- длина строки из нулей в начале, le -- длина строки из нулей в конце. Все, что остается, только "скомпостировать" результаты, пока головы трудятся над своей частью дальше. Далее, если грамотно организовать, то можно сначала самой левой голове выделить кусок поменьше, а остальным -- одинаковые большие. Тогда в течение многих циклов все могут трудиться над своим куском без остановок, ну а у самого левого длина куска будет расти. Как только она достигнет длины всех остальных кусков происходит синхронное перераспределение кусков.

К сожалению, глобально это проблемы не решит. Действительно, как уже обратили внимание, a(n) растет экспоненциально. loga(n) выглядит как прямая, допустим, что она такая и есть, по крайней мере для "видимого диапазона" это почти так (далее никто не бывал, так что остается только догадываться). Вот результат, полученный на коленке в Excel: log[a(n)+1]=n/2+1/2 (на самом деле полученные коэффициент и константа оба равны 0.497), короче a(n)=sqrt(10^(n+1)). Число цифр m в таких числах связано соотношением m-1<lg2*a(n)~0.30103*a<m, т.е.
m~0.3*a(n)~0.3*10^[(n+1)/2]. Т.е. при увеличении n на два, число цифр увеличивается где-то в десять раз. А значит, чтобы просчитать очередные две цифры с той же скоростью надо в десять раз больше компов (голов). Не хило. Т.е. если хотим до a(17) быстренько досчитать, то надо найти 100 добровольцев . Причем подключать их будем последовательно по мере роста числа.

Кстати, последнюю аппроксимацию можно проверить:
для n=11 дает 0.3*10^6=300000 цифр, истинное значение 345674
для n=12 дает 0.3*10^6.5=948683 цифр, истинное значение 1215059
для n=13 дает 0.3*10^7=3000000 цифр, истинное значение 1215060 -- в 2 с половиной раза меньше, но a(13) на самом деле оказалось равным a(12)+1
А так порядок держит вроде.

Здравствуйте, vadimcher, Вы писали:

V>Здравствуйте, Erop, Вы писали:

E>>Здравствуйте, Pro100Oleh, Вы писали:

PO>>>Распараллерировать не интересно. Здесь нужен математических подход в решении задачи, который бы позволил на порядок уменьшить сложность вычислений. Играться же в командах, чтобы выполнить оператор не за 5 тактов, а за 4 — малоэффективно (пусть и увеличится скорость работы в 2-3 раза). Возращаясь к параллельности — распараллерировать нужно не саму итерацию умножение числа 2^x на 2 и далее проверку на нули. Нужно, чтобы был один главный поток, который бы давал своим рабочим потокам задачу: проверитьвсе числа в диапазоне 2^x ... 2^(x+1000) например. Здесь бы ядра использовались в полную силу.

E>>Можно хорошо распарарллелить, на самом деле. И просто довольно. Только мне пока некогда и машин многоголовых всё равно нету.
E>>Могу отладить на двухголовой, и выложить, если есть желающие/могущие на кластере запустить...

E>>Общая идея такая, что тормоза начинаются на реально длинных числах. Скажем на числах длинною в десятки миллионов цифр. Соответственно такую задачу и надо параллелить. Параллелить надо так. Каждый процесс идёт по куску числа и всё что надо считает. Доходит до какой-то границы, скажем в миллион цифр, и отдаёт задание в очередь для следующего процесса. А сам возвращается ждать задания от предыдущего. Будет линейно масштабироваться...

V>Мне тоже подумалось сначала что-то навроде этого. Т.е. если длина n*k цифр, то n головам отдаем по k цифр на растерзание, причем следующим образом: i-я голова получает на вход цифры c (i-1)*k+1 по i*k а также перенос от правого соседа, который можно тут же вычислить (если правое число начинается с 5 или больше, то будет перенос в эту часть, если нет -- то не будет), далее умножает свою часть на два с прибавлением полученного переноса, а также игнорируя возможный перенос в левую часть (он уже учтен у соседа слева при получении задания) и возвращает вектор значений (l, lb, le), где l -- максимальная найденная строка из нулей, lb -- длина строки из нулей в начале, le -- длина строки из нулей в конце. Все, что остается, только "скомпостировать" результаты, пока головы трудятся над своей частью дальше. Далее, если грамотно организовать, то можно сначала самой левой голове выделить кусок поменьше, а остальным -- одинаковые большие. Тогда в течение многих циклов все могут трудиться над своим куском без остановок, ну а у самого левого длина куска будет расти. Как только она достигнет длины всех остальных кусков происходит синхронное перераспределение кусков.

V>К сожалению, глобально это проблемы не решит. Действительно, как уже обратили внимание, a(n) растет экспоненциально. loga(n) выглядит как прямая, допустим, что она такая и есть, по крайней мере для "видимого диапазона" это почти так (далее никто не бывал, так что остается только догадываться). Вот результат, полученный на коленке в Excel: log[a(n)+1]=n/2+1/2 (на самом деле полученные коэффициент и константа оба равны 0.497), короче a(n)=sqrt(10^(n+1)). Число цифр m в таких числах связано соотношением m-1<lg2*a(n)~0.30103*a<m, т.е.
V>m~0.3*a(n)~0.3*10^[(n+1)/2]. Т.е. при увеличении n на два, число цифр увеличивается где-то в десять раз. А значит, чтобы просчитать очередные две цифры с той же скоростью надо в десять раз больше компов (голов). Не хило. Т.е. если хотим до a(17) быстренько досчитать, то надо найти 100 добровольцев . Причем подключать их будем последовательно по мере роста числа.

V>Кстати, последнюю аппроксимацию можно проверить:
V>для n=11 дает 0.3*10^6=300000 цифр, истинное значение 345674
V>для n=12 дает 0.3*10^6.5=948683 цифр, истинное значение 1215059
V>для n=13 дает 0.3*10^7=3000000 цифр, истинное значение 1215060 -- в 2 с половиной раза меньше, но a(13) на самом деле оказалось равным a(12)+1
V>А так порядок держит вроде.

Даже так: если просчитать a(14) за приемлемое время и привлечь 100 компов с rsdn, то мы получим a(18)... И опубликуем его на сайте at&t... И прославим rsdn как Дульсинею Тобосскую во веки веков!

Здравствуйте, Pro100Oleh, Вы писали:

1. Вы в каждом элементе храните число от 0 до 9? Или от 0 до 999999999?
2. Как у вас получилось вот это
PO>a(12) = 4036338. Time 00:46:04.8292335, Length 1215059
при вот этом
PO>

PO>        public static readonly int MaxSegments = 1000000;
PO>        m_number = new int[MaxSegments];
PO>

???
4. В функции Check — похоже на перевод из двоичной системы в десятичную... Но я не до конца понял что там происходит.. можете пояснить?

В общем идея понятна в таком смысле, поправьте если не так:

В каждом инте храним числа от 0 до 999999999. (только мне не понятно максвалуе = 9 )
+ легко умножать.
+ колоссальная экономия памяти
-- тяжело искать десятичные 0. для этого надо переводить в 10-ю каждый инт, при чем потом каждое переведенное число шерстить на нули.
не понятно как достигнута скорость (если не брать во внимание разгон )


и последнее: как на вашем мегакомпьютере будет работать версия, где 1 байт хранит 1 число от 0 до 9? (по скорости)

Здравствуйте, Seon, Вы писали:

S>Здравствуйте, Pro100Oleh, Вы писали:

S>1. Вы в каждом элементе храните число от 0 до 9? Или от 0 до 999999999?
S>2. Как у вас получилось вот это
PO>>a(12) = 4036338. Time 00:46:04.8292335, Length 1215059
S>при вот этом
PO>>

PO>>        public static readonly int MaxSegments = 1000000;
PO>>        m_number = new int[MaxSegments];
PO>>

S>???
S>4. В функции Check — похоже на перевод из двоичной системы в десятичную... Но я не до конца понял что там происходит.. можете пояснить?

S>В общем идея понятна в таком смысле, поправьте если не так:

S>В каждом инте храним числа от 0 до 999999999. (только мне не понятно максвалуе = 9 )
S>+ легко умножать.
S>+ колоссальная экономия памяти
S>-- тяжело искать десятичные 0. для этого надо переводить в 10-ю каждый инт, при чем потом каждое переведенное число шерстить на нули.
S>не понятно как достигнута скорость (если не брать во внимание разгон )


S>и последнее: как на вашем мегакомпьютере будет работать версия, где 1 байт хранит 1 число от 0 до 9? (по скорости)

У меня переменная длинна используемых чисел в m_numbers[]. Эта длинна равна m_segmentLength. Соответсвенно m_maxValue = 10^m_segmentLength — 1. m_k — текущее количетсво нулей, которые нужно найти. При каждом следующем m_k я вычисляю m_segmentLength (функция Rebuild()) по формуле m_segmentLength = Round(m_k / 2) — округление вверх. Идея в том, что при представленни длинного числа сегментами длинной m_segmentLength последовательность из m_k нулей обязательно заполнит один сегмент нулями полностью. Поэтому я ищю лишь нулевые сегменты, а когда нашел, то парсю его соседей чтобы найти в них нули тоже.

Здравствуйте, Roman Odaisky, Вы писали:

RO>Хорошо бы запустить разные решения на одном компьютере, кое-чем померяться .

Вот мое решение здесь

Автор: Seon
Дата: 20.12.08

.
язык C++

Здравствуйте, vadimcher, Вы писали:

V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.

Решение этой части этюда

Предисловие. Пытаясь найти какие-нибудь зависимости в последовательности натолкнулся на интересный результат

Написал программку, которая вычисляет количество возможных остатков чисел 2^n при делении их на 10^k
Например 1, 2, 4, 8, 16, 32, 64, 128 ... при делении на 10^1 дает остатки 1, 2, 4, 8, 6, 2, 4, 8, 6 ...
После некоторого числа остатки начинают повторяться (в данном случае после 6).
Количество возможных остатков при делении на 10 равно 5. Это 1, 2, 4, 8 и 6
Аналогично для деления на 100 получаем 22 остатка, при делении на 1000 получаем 103 остатка.
Т.е. имеем последовательность f(k) = 5, 22, 103, 504, 2505, 12506, 62507, 312508 ...
Обобщив ее получаем f(k) = 100*5^(k-3) + k

Как уже сказал, остатки после некоторого числа начинают повторяться.
Найдя эти "последние" остатки получил еще одну интересную последовательность 6, 52, 504, 5008, 50016, 500032, 5000064 ...
Обобщив ее получаем g(k) = 5*10^(k-1) + 2^(k-1)

Вот такой вот результат.
Попытался доказать, что это верно не только для протестированных чисел (k <= 8), но и для всех.
Получилось вот что:

---

1. Докажем что, для любых целых m > 0, существует целое x, такое что 2^(f(m)-1) = x*10^m + g(m)

Итак f(m)-1 = 100 * 5^(m-3) + m - 1 и g(m) = 5*10^(m-1) + 2^(m-1). 

Подставляя в выражением получим
2^(100 * 5^(m-3) + m - 1) = x*10^m + 5*10^(m-1) + 2^(m-1)

Умножаем на 2 
2^(100 * 5^(m-3) + m) = 2x*10^m + 10^m + 2^m

Переносим 2^m в левую часть и выносим общий множитель
2^m * (2^(100 * 5^(m-3)) - 1) = 10^m * (2x + 1)

Делим на 10^m
(2^(100 * 5^(m-3)) - 1) / 5^m = 2x + 1

Обозначим 5^(m-1) = y, заметим, что y нечетно
(2^(4y) - 1) / 5y = 2x + 1

Откуда
x = (16^y - 1 - 5y) / (2*5y)

а) (16^y - 1 - 5y) делится на 2, т.к. 16^y четное, 5y - нечетное, 1 - нечетное
б) 5y делится на 5y :)
в) (16^y - 1) делится на 5y, т.к. 
16^y - 1 = (15+1)^y - 1, 
т.е. получим многочлен в котором y+1 членов, один из которых 1 (мы эту единицу отнимаем), 
а остальные члены являются степенью 15 (таких членов y). Значит и весь многочлен делится на 5y

Из этого следует, что x - целое число, для любых m>0

2. Очевидно, что в последовательности g(m) мы найдем число с k нулями.
А значит существует такое число n, что при делении 2^n на 10^k получим остаток, содержащий k нулей.
Из этого следует решение этюда :)

3. Более того, такие n не только существуют, но их существует бесконечное количество.

---

К сожалению, представленные выше рассуждения хотя и позволяют найти нужное n для k нулей,
но не позволяют высчитывать члены той-самой последовательности, которая обсуждается в этом топике.
Т.к. в последовательности присутствуют только минимальные 2^n содержащие k нулей.
Этот же алгоритм позволяет всего лишь доказать их существование

Спасибо за интересный этюд

Здравствуйте, Beam, Вы писали:

B>Здравствуйте, vadimcher, Вы писали:

V>>Докажите, что для любого k найдется такое число n, что в десятичной[i] записи числа 2^n, встречается k нулей подряд.

B>Решение этой части этюда

Мне твое доказательство пока не до конца ясно. Пройдемся...

B>Т.е. имеем последовательность f(k) = 5, 22, 103, 504, 2505, 12506, 62507, 312508 ...
B>Обобщив ее получаем f(k) = 100*5^(k-3) + k
B>Как уже сказал, остатки после некоторого числа начинают повторяться.
B>Найдя эти "последние" остатки получил еще одну интересную последовательность 6, 52, 504, 5008, 50016, 500032, 5000064 ...
B>Обобщив ее получаем g(k) = 5*10^(k-1) + 2^(k-1)
B>Вот такой вот результат.
B>Попытался доказать, что это верно не только для протестированных чисел (k <= 8), но и для всех.

Вопрос 1. Доказал ли ты в итоге, что остатки повторяются (это, впрочем, очевидно), и что формулы f() и g() верны?
Впрочем, может это и не важно для твоего доказательства, т.к. как я понял, то, что ты пытаешься доказать в пункте 1, означает, что g(m) -- возможный остаток при делении [i]некоторой степени двойки на 10^m. Этого достаточно, т.к. 10^m > g(m). Однако это может оказаться важным, если пункт 1 твоего доказательства неверен.

B>1. Докажем что, для любых целых m > 0, существует целое x, такое что 2^(f(m)-1) = x*10^m + g(m)
[]
B>в) (16^y — 1) делится на 5y, т.к.

Здесь прокол в доказательстве. Во-первых, ты нигде не использовал, что y нечетное, а утверждение очевидно неверное для четных y. Кроме того, 16^13-1 не делится на 65 (число 13 взял наобум, может еще для каких не выполняется).

B>2. Очевидно, что в последовательности g(m) мы найдем число с k нулями.
B>А значит существует такое число n, что при делении 2^n на 10^k получим остаток, содержащий k нулей.
B>Из этого следует решение этюда

Ты, видимо, имел в виду "при делении 2^n на 10^m получим остаток, сожержащий k нулей."

Тем не менее, интересный подход, и такое впечатление, что он может привести к решению.

Здравствуйте, vadimcher, Вы писали:

V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.

V>Этюд для программиста.
V>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д.
V>Найти a(1),...,a(7).

Теоретическая часть доказывается сразу. из утверждения, что степень 2 может начинаться на любую наперед заданную последовательность цифр (берем 10^k)

Схема доказательства первого утверждения — 2^n начинается на число x <=> {n*ln 2} (в смысле дробная часть) лежит в неком непустом интервале. собственно, все... всюду плотность доказывается вручную... ну или гуглом по "критерий Вейля"

Здравствуйте, vadimcher, Вы писали:

V>Вопрос 1. Доказал ли ты в итоге, что остатки повторяются (это, впрочем, очевидно), и что формулы f() и g() верны?
Представим 2^n в виде a*10^k + b (b — остаток от деления на 10^k).
Я говорю, что есть такое m при которых b содержит k нулей. В моем случае b = g(x).
И доказываю, что cуществует n, такое что 2^n можно представить в такой форме. В моем случае n=f(m)-1.
Чтобы доказать возможность представления 2^n в такой форме, я доказываю, что при заданных целых b и 2^n, вычисленных по этим формулам, частное "a" тоже будет целым.

B>>в) (16^y — 1) делится на 5y, т.к.

V>Здесь прокол в доказательстве. Во-первых, ты нигде не использовал, что y нечетное, а утверждение очевидно неверное для четных y. Кроме того, 16^13-1 не делится на 65 (число 13 взял наобум, может еще для каких не выполняется).

Я об этом говорил. y = 5^(m-1), а следовательно нечетно.
А пример не подходит, т.к. 13 не является степенью 5.

B>>2. Очевидно, что в последовательности g(m) мы найдем число с k нулями.
B>>А значит существует такое число n, что при делении 2^n на 10^k получим остаток, содержащий k нулей.
B>>Из этого следует решение этюда

V>Ты, видимо, имел в виду "при делении 2^n на 10^m получим остаток, сожержащий k нулей."

Да. Именно так.

Здравствуйте, Beam, Вы писали:

B>Здравствуйте, vadimcher, Вы писали:

V>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.

B>Решение этой части этюда

B>Предисловие. Пытаясь найти какие-нибудь зависимости в последовательности натолкнулся на интересный результат

B>Написал программку, которая вычисляет количество возможных остатков чисел 2^n при делении их на 10^k
B>Например 1, 2, 4, 8, 16, 32, 64, 128 ... при делении на 10^1 дает остатки 1, 2, 4, 8, 6, 2, 4, 8, 6 ...
B>После некоторого числа остатки начинают повторяться (в данном случае после 6).
B>Количество возможных остатков при делении на 10 равно 5. Это 1, 2, 4, 8 и 6
B>Аналогично для деления на 100 получаем 22 остатка, при делении на 1000 получаем 103 остатка.
B>Т.е. имеем последовательность f(k) = 5, 22, 103, 504, 2505, 12506, 62507, 312508 ...
B>Обобщив ее получаем f(k) = 100*5^(k-3) + k

B>Как уже сказал, остатки после некоторого числа начинают повторяться.
B>Найдя эти "последние" остатки получил еще одну интересную последовательность 6, 52, 504, 5008, 50016, 500032, 5000064 ...
B>Обобщив ее получаем g(k) = 5*10^(k-1) + 2^(k-1)

Ой. Примеры не привел.

2^(5-1)
16

2^(22-1)
2097152

2^(103-1)
5070602400912917605986812821504

2^(504-1)
261871248631691349601055175746207932177331363683445183158663309447690703712373
96439066160738607233257207093473020480568073738052367083144426628220715008

2^(2505-1)
60132483752768192589337987035581840778837848281481388329043814365157069039734033365
71723612042541509339239323992416924164947646261625884250430516975500483783435104693
05978499434759066365745810932149966577954528288850798772444024927951838520227542350
58879180375008327907459992704354324702525063610134325603963613584257226698077210866
97965594178563342037853359202620643016368419959048118246112515022278177758493915308
05029190273917571539320710435893386487658970495023503337021002531803558460354723583
98630634564189720424240469835564945762960051260079413879992251123446696070679668135
05060724474749961684572680842562091232767971493355989701146839512474920828253732280
043454304126203636001132485604207238035424461476759780217566076674821411534921911832150016

B>1. Докажем что, для любых целых m > 0, существует целое x, такое что 2^(f(m)-1) = x*10^m + g(m)

Здравствуйте, Beam, Вы писали:

Мне понравилась вот эта последовательность

B>Т.е. имеем последовательность f(k) = 5, 22, 103, 504, 2505, 12506, 62507, 312508 ...

Здравствуйте, Seon, Вы писали:

S>Мне понравилась вот эта последовательность

B>>Т.е. имеем последовательность f(k) = 5, 22, 103, 504, 2505, 12506, 62507, 312508 ...

Этот кусок последовательности сломается после 598, 599, ...

Здравствуйте, Spiceman, Вы писали:

S>Больше всего понравилось решение на Хаскеле. В одну строчку — впечатлило!
S>Ради интереса написал на Лиспе (DrScheme):
S>[skip]
S>Работает очень медленно. Зато функционально И что интересно, сам распараллелился на два потока — один строит степени двойки, а другой эти степени фильрует.

Новое решение на лиспе:

#lang scheme
(require srfi/40/stream)
(require srfi/19)

;Числа представлены по основанию k в виде списка.

(define (base k)
  (if (< k 14)
      (cond ((= k 0) 1)
            ((= k 1) 10)
            ((= k 2) 100)
            ((= k 3) 1000)
            ((= k 4) 10000)
            ((= k 5) 100000)
            ((= k 6) 1000000)
            ((= k 7) 10000000)
            ((= k 8) 100000000)
            ((= k 9) 1000000000)
            ((= k 10) 10000000000)
            ((= k 11) 100000000000)
            ((= k 12) 1000000000000)
            ((= k 13) 10000000000000))
      (cond ((= k 14) 100000000000000)
            ((= k 15) 1000000000000000)
            ((= k 16) 10000000000000000)
            ((= k 17) 100000000000000000)
            ((= k 18) 1000000000000000000)
            ((= k 19) 10000000000000000000))))

;p - показатель степени двойки, b - основание системы.
(define (make-number p b)
  (define (iter n)
    (if (= n 0)
        '()
        (cons (remainder n b)
              (iter (quotient n b)))))
  (iter (expt 2 p)))

;s - список, m - знак переноса разрядов, b - основание системы.
(define (double-list s m b)
  (if (null? s)
      (if (= m 0)
          '()
          (cons m '()))
      (let ((n (* (car s) 2)))
        (let ((c (+ n m)))
          (if (>= n b)
              (cons (- c b)
                    (double-list (cdr s) 1 b))
              (cons c
                    (double-list (cdr s) 0 b)))))))

(define (order n k)
  (if (>= n (base k))
      (+ k 1)
      (order n (- k 1))))

(define (mult n p)
  (if (odd? n)
      false
      (let ((b (base p)))
        (if (= (remainder n b) 0)
            true
            false))))

;s - список, p - порядок предыдущего числа в списке, k - проверяемое число нулей.
(define (check s p k)
  (if (null? s)
      false
      (if (= (car s) 0)
          true
          (if (mult (car s) p)
              true
              (check (cdr s) (order (car s) k) k)))))

;k - проверяемое число нулей, s - текущее число, p - показатель степени двойки этого числа.
(define (start k s p)
  (if (check s k k)
      (begin ((println (cons p k))
              (start (+ k 1) (make-number (+ p 1) (base (+ k 1))) (+ p 1))))
      (start k (double-list s 0 (base k)) (+ p 1))))

(define (println x)
  (newline)
  (display x)
  (display (date->string (current-date) "~r")))

(define run (start 1 '(1) 0))

Числа представлены списком. Каждый элемент — это разряд числа в системе по основанию 10^k, где k — проверяемое число нулей.

Уже не стыдно показать результаты (виртуальный сервер Xeon 3ГГц, 384Мб):
(10 . 1)01:12:57 PM
(53 . 2)01:12:57 PM
(242 . 3)01:12:57 PM
(377 . 4)01:12:57 PM
(1491 . 5)01:12:57 PM
(1492 . 6)01:12:57 PM
(6801 . 7)01:12:57 PM
(14007 . 8)01:12:58 PM
(100823 . 9)01:14:16 PM
(559940 . 10)02:49:41 PM