Factorials

[mertz]

+ addition

* multiplication

No + in your example.

illogical name.

[Nataly-Mak]

Почему нелогичное название?

Цитата:

Дана аддитивная последовательность:
v = (1,2,3,6,12,24,30,31)

$2=1+1$
$3=1+2$
$6=3+3$
$12=6+6$
$24=12+12$
$30=6+24$
$31=1+30$

Все члены этой последовательности получены сложением. Поэтому последовательность называется аддитивной.

$5^2=5^1 \cdot 5^1= 5^{1+1}$
$5^3=5^1 \cdot 5^2=5^{1+2}$
$5^6=5^3 \cdot 5^3=5^{3+3}$

etc

Это другая аддитивная последовательность:

1,2,4,8,9,11,20,31

А это не аддитивная последовательность:

1,2,4,8,9,10,40,31

$40=4 \cdot 10$

[Xaositect]

mertz
An addition chain is a sequence of integers $a_0,a_1,\dots,a_l$ such that $a_0 = 1$ and each $a_i$ is a sum of two preceding elements.

But since the most important practical application of addition chains is fast exponentiation, they are often described in terms of multiplication of powers: if $a_0,a_1,\dots,a_l$ is an addition chain, then the sequence $x, x^{a_1}, \dots, x^{a_l}$ describes a program that raises $x$ to the power of $a_l$ using multiplications.

[Nataly-Mak]

Xaositect в сообщении #715948 писал(а):

... and each $a_i$ is a sum of two preceding elements.

В том и дело, что не всегда сумма двух предыдущих членов
Именно это, видимо, и сбило с толку mertz в приведённой последовательности

1,2,3,6,12,24,30,31

Можно ведь считать, что 6=2*3, 12=6*2 и т.д.
Но также 6=3+3, 12=6+6 и т.д.

[mertz]

Цитата:

Tom Rikicki --

For instance, the best length-37 solution I found ended in a
chain of 7 additions, so my primary search only had to consider a
depth of 13 operations.

For N < 20, is there and example of this. looking at all my solutions, they seem to end with 2- 6 multiplies.

[Gerbicz]

The contest is over?

Jarek Wroblewski: "264 may be impossible to be reached by the human race, but I can believe it may be close to the actual optimum."

1 1.000 Robert Gerbicz Halasztelek, Hungary 26 Apr 2013 20:12
13 .264 Raw Score = 1000 Adelaide, Australia 20 Apr 2013 16:00

Probably no.

[mertz]

Is anything less than 264 possible?

[dimkadimon]

Great work Robert. See how much further you can push it.

[dimkadimon]

На Yahoo я описал свой Dynamic Programming метод: http://tech.groups.yahoo.com/group/AlZi ... ssage/5629

Суть в том что мы можем решить упрощенную задачу: найти оптимальное SLP в котором все операции используют одно из чисел в последовательности S=a1, a2, ..., ai. Tо есть мы берем S и оптимально достраиваем еe до N! используя числа из S. Чтобы реализовать этот метод надо использовать условие что все числа делители N!.

[Nataly-Mak]

whitefox в сообщении #715281 писал(а):

Вот когда Gerbicz молчит, он делает успехи:

1    1.000    Robert Gerbicz    Halasztelek, Hungary    25 Apr 2013 00:58
11    .270    Raw Score = 1000    Adelaide, Australia    20 Apr 2013 16:00

Или наоборот?
Когда делает успехи -- молчит

whitefox
надеюсь, вы получили ответ на свой вопрос

Gerbicz в сообщении #716041 писал(а):

1 1.000 Robert Gerbicz Halasztelek, Hungary 26 Apr 2013 20:12
13 .264 Raw Score = 1000 Adelaide, Australia 20 Apr 2013 16:00

Насчёт рубежа в 250 шагов, который вас так сильно интересует...
Гении в сотрудничестве с марсианами с небольшой помощью кластера могут всё
Будет вам и 250 шагов.
Погодите чуток - будет и белка и свисток.
[насчёт белки --- бабушка надвое сказала, а вот свисток будет точно ]

P.S. За последние сутки кластер наскрёб всего одну операцию.

-- Сб апр 27, 2013 06:02:01 --

dimkadimon в сообщении #716120 писал(а):

На Yahoo я описал свой Dynamic Programming метод: http://tech.groups.yahoo.com/group/AlZi ... ssage/5629

Суть в том что мы можем решить упрощенную задачу: найти оптимальное SLP в котором все операции используют одно из чисел в последовательности S=a1, a2, ..., ai. Tо есть мы берем S и оптимально достраиваем еe до N! используя числа из S. Чтобы реализовать этот метод надо использовать условие что все числа делители N!.

А разве алгоритм, представленный Pavlovsky, не то же самое?
Вы писали, что с трудом нашли решение в 430 шагов.

Pavlovsky в сообщении #714391 писал(а):

Прибросил алгоритм для 1000! Построить решение длиной около 400 операций легко. Но я так понял лучшее решение сейчас в районе 300 операций.

dimkadimon в сообщении #714400 писал(а):

Мне было не так легко. Я с трудом построил 430. Лучшее сейчас 292. Jarek построил 297 как я понял практически вручную!

Pavlovsky по этому алгоритму нашёл решение в 389 шагов, как я понимаю, без особого труда.

-- Сб апр 27, 2013 06:30:17 --

У-р-р-р-а-а-а! В борьбу включился Алексей Чернов!

Цитата:

4 .721 Alex Chernov Penza, Russia 26 Apr 2013 19:32

Боле-е-е-ю-ю о-ч-ч-ч-е-н-ь.

Удачи вам, Алексей!

[whitefox]

dimkadimon писал(а):

for k=1 to N!
for ai in S
V[k+ai]=min(V[k+ai],V[k]+1) //for addition
V[k*ai]=min(V[k*ai],V[k]+1) //for multiplication
end
end

dimkadimon писал(а):

I have successfully implemented this method and used it in my beam
search.

Только во внешнем цикле нужно выполнить порядка $4\cdot10^{2567}$ итераций.
Какой фильтр для $k$ Вы использовали?

-- 27 апр 2013, 09:52 --

Даже инициализация

dimkadimon писал(а):

V[k]=10000 for all k<=N!

займёт вечность.

-- 27 апр 2013, 10:01 --

dimkadimon писал(а):

k=1
while k<=N!
..next=k+1
..for ai in S
....V[k+ai]=min(V[k+ai],V[k]+1) //for addition
....V[k*ai]=min(V[k*ai],V[k]+1) //for multiplication

....if V[k]+1<V[abs(k-ai)] //for subtraction
......V[abs(k-ai)]=V[k]+1
......next=min(next,abs(k-ai)) //opportunity to go back
....end
..end
..k=next
end

Так, понятно, здесь мы уже не обязаны проходить по всем $k$.
Но проблема с инициализацией остаётся.
Да и хватит ли во Вселенной места, чтобы разместить массив V[k]?

[Nataly-Mak]

whitefox в сообщении #716141 писал(а):

Даже инициализация

dimkadimon писал(а):

V[k]=10000 for all k<=N!

займёт вечность.

dimkadimon
я что-то вообще не понимаю, что за странный массив такой.
Объявляется некоторый одномерный массив по переменной k.
Но на фига он такой огромный? Неужели в программе будут использованы все элементы этого мамссива для k=1,2,3,...,N!

-- Сб апр 27, 2013 11:15:50 --

Ещё одна хорошая новость - Jarek Wroblewski не стал зрителем:

Цитата:

2 .917 Jarek Wroblewski Wroclaw, Poland 27 Apr 2013 06:17

Молодец!

Так что, конкурс не закончился, господин юный Гений
Конкурс продолжается!

(Оффтоп)

Цитата:

Jarek Врублевский: "264 может быть невозможно быть достигнут человеческой расы, но я могу поверить, что она может быть близка к фактической оптимальной".

Здесь как бы намекается на вмешательство неземных цивилизаций
Созвучно предположению whitefox.

[dimkadimon]

whitefox
Метод которой я описал я создал для N<=37, не вижу как он может работать для N=1000. Я просматривал не все k, а только те которые делители N!. Поэтому размер массива V не такой большой как кажется. Если еще ограничить k тогда N>37 будет возможно.

[whitefox]

dimkadimon в сообщении #716180 писал(а):

Я просматривал не все k, а только те которые делители N!. Поэтому размер массива V не такой большой как кажется.

1000! имеет порядка $3\cdot10^{106}$ делителей, что всё равно чудовищно много.

dimkadimon в сообщении #716180 писал(а):

Метод которой я описал я создал для N<=37, не вижу как он может работать для N=1000.

Думаю можно массив V заменить ассоциативным массивом.
Инициализацию V[k]=10000 for all k<=N! не выполнять,
выполнить только V[ai]=0 for all i.
В самом алгоритме рассматривать только те k для которых V[k] уже определено, то есть пара (k,V[k]) принадлежит ассоциативному массиву.

-- 27 апр 2013, 12:49 --

(Оффтоп)

Забавная игра слов:

Nataly-Mak в сообщении #716160 писал(а):

человеческой расы

в оригинале:

Gerbicz в сообщении #716041 писал(а):

human race

Словарь
race [reɪs]
/существительное/
1. гонка, гонок
(racing)
guv race — гонка GUV
2. раса, род, расовая принадлежность
(kind, ethnicity)
Sangik race — сангикская раса
human race — человеческий род
3. соревнование, состязание
(competition, contest)
horse races — конные соревнования

[Pavlovsky]

Цитата:

264 may be impossible to be reached by the human race, but I can believe it may be close to the actual optimum.

Не согласен!
Очень грубо оценил потенциал подхода который я использую для решения задачи 1000!
Результат 300 операций практически гарантирован, нужно только время. 280 операций наиболее вероятный результат. 240 операций оптимистический прогноз, нужно что бы хорошо повезло.
И это в рамках подхода, который априори не ищет оптимального решения. И без учета возможности тонкой оптимизации последовательностей.
Полагаю, что оптимальное решение где то в районе 200 операций.

Повторяю, это очень грубая оценка. Требования предъявить доказательства и претензии когда прогноз не сбудется не принимаются!