Factorials

[mertz]

looking at scores < 1.0 at AZPC, the current record for N=13 is 11. No information makes contest less enjoyable. Depth or breadth search with smart pruning might solve some of the lower N. Forward and backward search?

[Nataly-Mak]

На мой взгляд, задача очень тесно связана с факторизацией.
Вот сейчас представляла 13! вручную --- ручками, ручками пощупала задачу
В принципе понятно, как надо действовать.

Есть для 13! 12 ходов
А надо 11, mertz говорит.

[jcmeyrignac]

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

jcmeyrignac:
"I find it pretty cool to have a space for discussion."
After each contest there is a public discussion on yahoo about the contest. I really enjoed these, even when I have not participated on a contest. Why is not enough for them?

There is something that you forget: it's the momentum.
When you compete, you have a strong desire to perform at your maximum, and when the contest is finished, this desire has disappeared.
This is why I prefer to share some insights, without giving details. Too much details kills the fun.

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

"Such contests are here to stimulate imagination and coding performance."
I can only agree with you. But tell me, if you can get free the algorithms and ideas or even optimal sequences for factorials then what is improved? Nothing, only cheating capability.

Ok, I'll give you the algorithms to solve this problem:
1) BFS for small N
2) heuristics for larger N
Did I cheat ?

As long as people don't disclose their algorithm or publish their solution, I consider this as not cheating.
Also, I guess that leaders will never disclose their method, because winning AZPC's contest is a great achievement !

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

На мой взгляд, задача очень тесно связана с факторизацией.
Вот сейчас представляла 13! вручную --- ручками, ручками пощупала задачу
В принципе понятно, как надо действовать.

No, you are wrong.
Factorizing is not the only way to approach this problem, because it's not related to computing powers with the minimum number of multiplications.
Think about additions, and what to add !
And no, I won't participate in this contest, since I'm busy with other things.
Azpc's contests are very time-consuming.

[svb]

mertz

Цитата:

looking at scores < 1.0 at AZPC, the current record for N=13 is 11.

Я обратил на это внимание. Для N=$14,15$ также должны быть меньшие значения.

[Nataly-Mak]

jcmeyrignac в сообщении #674255 писал(а):

Factorizing is not the only way to approach this problem, because it's not related to computing powers with the minimum number of multiplications.

Может быть, это и не единственный метод найти оптимальное решение, но мне помогает

[svb]

Для $N=15$ имеется $step=13$

[Xaositect]

У меня есть 12 для 14!

[Scryer]

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

У меня есть 12 для 14!

Well done! I think the record for 14! is 11, from the score I got for my bad solution.

[Nataly-Mak]

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

У меня есть 12 для 14!

У меня тоже
14! как-то легко получилось с 12 ходами.
А вот для 13! 11 ходов никак не получается.

[Scryer]

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

But tell me, if you can get free the algorithms and ideas or even optimal sequences for factorials then what is improved? Nothing, only cheating capability.

It is not cheating. Al Zimmermann sets the rules, and he wrote "I’ve always encouraged that level of discussion. There are only two things I don’t want to see here: code and specific solutions."

So enough of the cheating talk. If you want to talk about ideas, feel free. If others want to, it's fine with Al Zimmermann.

[dimkadimon]

I am already loving this problem. Many things to think about:

1. Are there optimal solutions with negative values?
2. Are there optimal solutions with values greater than n! ?
3. How often do we need to use the negation? We know that we need it for some n.
4. How often do values need to decrease?

[Scryer]

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

I am already loving this problem. Many things to think about:

1. I have optimal solutions to N=8! with negative values.
2. I have an optimal solution to N=8! with value 41472 > 40320.
3. I think negation is needed for N=7! N=9! N=11! at least. I'll reserve my info N >= 13!
4. I haven't checked this.

I'm enjoying this also. Here's another question:

If we get a good solution to this (for a particular mathematical definition of "good"), does this automatically win us $1M for the first Millennium Prize solution?

[Gerbicz]

Scryer:
"If we get a good solution to this (for a particular mathematical definition of "good"), does this automatically win us $1M for the first Millennium Prize solution?"

With these small n values (13<=n<=37), even if you can get good results you prove nothing about P!=NP. This puzzle is good for small kids to play with numbers and operations. But I also like it.

[svb]

dimkadimon
Я не понял потребности в использовании отрицательных чисел.
У нас имеется операция вычитания, результат которой всегда можно сделать положительным изменением порядка ("Subtraction can be performed in either direction.").
Пример, который приведен в описании, легко переводится в положительные числа:

1, 2, 3, 6, -5, -30, 150, 120 

2 = 1 + 1
3 = 1 + 2
6 = 3 + 3
-5 = 1 - 6
-30 = 6 * -5
150 = -5 * -30
120 = -30 + 150


1, 2, 3, 6, 5, 30, 150, 120 

2 = 1 + 1
3 = 1 + 2
6 = 3 + 3
5 = 6 - 1
30 = 6 * 5
150 = 5 * 30
120 = 150 - 30

Где я ошибаюсь?

[Scryer]

svb в сообщении #674409 писал(а):

Где я ошибаюсь?

You're not wrong - it's always possible to use the absolute value and ignore negative numbers. Allowing them makes the problem statement simpler - no need to make exceptions. The same "programming language" can be used for positive and negative targets.

The main reason it's defined like this is historical, I imagine: "straight line programs" are a term of art, and it is already defined.

My current programs ignore negative numbers.

-- 20.01.2013, 16:30 --

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

Scryer:
"If we get a good solution to this (for a particular mathematical definition of "good"), does this automatically win us $1M for the first Millennium Prize solution?"

With these small n values (13<=n<=37), even if you can get good results you prove nothing about P!=NP. This puzzle is good for small kids to play with numbers and operations. But I also like it.

I understand and agree with "prove nothing about P!=NP" for these small n, but I disagree about the "small kids playing" part: serious mathematicians have looked carefully at this exact problem, and we have already extended the knowledge of OEIS.

However, I said "good solution" and "(for a particular mathematical definition of "good")" to suggest a general solution for arbitrary N! with an appropriate growth rate. What I wondered was whether this proves the same P != NP conjecture in the Millennium Prize problem, or whether it's a more restricted version of it. (I don't know the answer to this one, and would welcome insight from you or others.)