заплати мне, загружу свой ;)

> Купить компьютер не предлагать.
Ты-таки намекаешь на ботнет? :)

раздобыть доступ в ближайший университетский кластер?

Я вижу три варианта:

1. Пересмотреть алгоритм программы, чтобы вместо перебора использовалось что-нибудь более разумное и быстрое. Посчитать за минуты.
2. Переписать на MPI и разыскать поблизости ближайший вычислительный кластер, страдающий от недостатка считающихся на нём прикладных программ.
3. Отдать бинарник знакомому, которому не жалко несколько дней подержать включённым мощный комп.

Купи компьютер.

тебе надо что-то вроде этого

http://www.google.com/search?q=%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%...

Ботнет.

У меня тут простаивают QX6850, Q9650 и Phenom FX5000.

У меня скоро появится 2xXeon 2.66GHz, на пару дней смогу там практически всё, что угодно запустить :) Если обоснуешь, пущу.

Ваш город.

Вот создаётся ботнет. Что вы думаете он там перебирает? Пароли же.

А чо не BOINC?

>Вот создаётся ботнет. Что вы думаете он там перебирает? Пароли же.

Вы так говорите, будто это единственная NP-полная задача :)

Зато самая распространённая среди деятелей школьного возраста :)

4 проца и до 8 гигов памяти в полную загрузку на 5 дней могу дать при условии открытых исходников

проще говоря: мне исходники, с меня сборка и файлы, которые прога выдаст. если за 5 дней она отстучит.

Q9450 @ 2.66GHz о 4х головах

Да не-не. Просто разбирая в Конкретной Математике задачу 9.68 (последнюю! наконец-то я дочитал этот трактат!) наткнулся в ответе на фразу, что неизвестно ни одного контрпримера к тамошнему равенству, хотя доказано, что он есть. Задача перебора тривиальная. Я конечно понимаю, что мои шансы найти контрпример можно округлить до 0 (сколько лет книге, а задача все ещё актуально, её наверняка преребиарли и не раз), но попытка не пытка. Вот думаю найти какую-нибудь зверскую машину и пущай брутофорс там паработает несколько дней. Ну и, в конце концов, отрицательный результат — тоже результат. (В идеале бы конечно пустить это на какой-нибудь заброшенный комп и пускай работает дни, месяцы, годы... Может что и найдёт. Это я веду к бесплатным хостингам с поддержкой пхп, но не думаю, что пхп лучший выбор для брутофорса, да и забанят почти сразу за такое).

Хотя скорее всего ограничусь собственным компом, шобы не тревожить людей. Буду оставлять на ночь.

А сохранение состояния прогресса перебора нельзя дописать, что ли? И запускай хоть каждый день по 15 минут. Если лень, можно попробовать закинуть в виртуальную машину и сохраняться на диск вместо выключения ее...

> Это я веду к бесплатным хостингам с поддержкой пхп

Обычно там правилами запрещено кушать слишком много cpu time.

неизвестно ни одного контрпримера к тамошнему равенству, хотя доказано, что он есть

Что за равенство? Опубликуй .)

devio.us!

Пусть Q_n — минимальное целое m такое, что H_m > n. Надо найти наименьшее n, для которого Q_n не равен полу от e^{n-\gamma}+1/2.

Для справок: H_m — гармонические числа, \gamma — константа Эйлера (0.57...), пол — ближайшее меньшее целое. --------------

И хотя я не программист, по-моему запрограммировать тут достаточно легко. Надо вычислять очередное Q_n и проверять равенство. Сначала хотел писать на си, но поняв, что маленькими числами тут дело не ограничится, взял Ruby (в нём длинная арифметика встроена). Пусть в ущерб скорости, но времени у меня море.

> Сначала хотел писать на си, но поняв, что маленькими числами тут дело не ограничится, взял Ruby. Пусть в ущерб скорости

Тебе сюда: http://gmplib.org/

> времени у меня море.

Параллельно прикинь вычислительную сложность своего алгоритма. Как бы не оказалось, что при больших n на вычисление Q_n будут уходить тысячелетия ;)

Ну при больших n по любому будет уходить уйма времени, так как гармонические числа с увеличением n мало изменяются (разница — 1/n). Даже Q_{10} = 12367, Q_{11}=33617 ... т.е. растут очень быстро.

> по любому будет уходить уйма времени

Ума уйме рознь. Начиная с какой-то величины (1000 лет, к примеру), всякий практический интерес исчезает.

т.е. растут очень быстро

Судя по предлагаемому к опровержению равенству, _экспоненциально_ быстро. Поэтоу при подходе «в лоб» будет та самая «уйма», при которой на помощь компьютера можно не надеяться.

Хотя ничто не мешает проверить равенство для отонсительно маленьких n. Вдруг повезет?

до 19 (вычислялось минут 7) проверил только, каждое следующее Q_n вычисляется ЗНАЧИТЕЛЬНО дольше. Похоже гиблая затея. Даже сам Кнут наверняка пробовал (в стенфорде наверняка какой-нибудь суперкомпьютер есть). Но раз задача висит до сих пор, значит уже можно не надеятся что-то найти.

> значит уже можно не надеятся что-то найти

найти что-то методами влоб. если интересна задача - ищите пути. в мат журнале публикация по нелобовому методу точно будет воспринята на ура и с апплодисментами

Тогда только кластер, ну а по хорошему всё нужно делать через теорию как Перельман.

Через теорию там хрень докажешь. Это задача явно переборная, но всё омрачает то, что H_n растут медленно, а следовательно вычисление Q_n занимает много времени при больших n (я больше Q_{20} ждать не стал, даже если оставлю на неделю, то может до Q_{30} дойдёт. Но это задача из довольно солидной книжки, её проверили до сотни или тысячи по любому и в домашних условиях проверять бессмысленно. Только ради спортивного инетреса, но его я уже получил ;))

По поводу упрощения вычисления Q_n — вряд ли что-то можно придумать. Поначалу была идея сделать что-то типа дихотомии: сначала прикидывать приблизительно значение Q_n*, если Q_n* < Q_n, то делаем прикидку больше, если > — меньше. И так Q_n* сходится к Q_n.
Но: надо считать ТОЧНО H_m, никуда не денешся, а это занимает очень много времени, т.к. единственный способ его вычислить — в лоб. Есть асимптотическая формула для H_n, с ней можно организовать такую дихотомию с Q_n*, но в конце концов нам ПО ЛЮБОМУ понадобится точное значение H_n и асимпотическая формула тут бессильна. Так что перебор — единственный вариант. А если контрпример находится в районе Q_{100000}, то вычислить это нереально.

У меня тут простаивают QX6850, Q9650 и Phenom FX5000.

Пошто человека мучаешь? (:

Переписать для CUDA и дать любому знакомому с мощной видеокартой?

сабж

Может на каком-нибудь халявном хостинге (только придётся наверное писать прогу на php, а это её замедлит.

ОМГОМГОМГ... Почему php?

А разве за халяву разрешать запускать бинарники?

Ну, это… Да. По мне, так лучше бинарики, чем тормозное пхп.

http://devio.us - залил и запустил. Правда, они тебе особых мощностей не предоставят. Не для того задумывалось.

p.s. чота мне кажется, что тебе нужен всего лишь брутфорсер мд5.