Factorials

[ben_burrows]

I impose a pruning rule that eliminates any number which is not a factor of the target (using the slow % operator). This is sufficient up to N=12! ... but I am becoming concerned that 13! requires more "exotic" calculations.

[Pavlovsky]

Продолжение темы "Метод Лемана"
post688341.html#p688341
$x^2-y^2=4srqp$
$y+qr=ps$
q,p нечетны и взаимнопросты, $(pq)^{1/3}<p<q<(pq)^{2/3}$.

Как это можно применить к нашим баранам. Пусть мы хотим получить число кратное, например 11*13*17*19.
1) Выбираем p и q, так чтобы pq=11*13*17*19.
2) Выбираем небольшое число для y. Например 1 или 2.
3) Решаем уравнение в целых числах $y+qr=ps$. Это легко делается алгоритмом Эвклида или цепными дробями.
4) Вычисляем x.
5) Строим последовательность 1,2,...,y^2,...x,x^2,x^2-y^2.

-- Ср фев 27, 2013 13:55:30 --

Пример. Пусть мы хотим построить число кратное 7*11.
1) p=7, q=11
2) y=1
3) r=5, s=8
4) x=111

111^2 - 1 = 4*8*5*7*11

[Herbert Kociemba]

ben_burrows в сообщении #688711 писал(а):

I impose a pruning rule that eliminates any number which is not a factor of the target (using the slow % operator). This is sufficient up to N=12! ... but I am becoming concerned that 13! requires more "exotic" calculations.

No, it is sufficient for many cases. I can confirm, that with this restriction it is possible to get for N=13 to N=37
11 11 12 12 12 13 13 14 14 15 15 15 16 17 17 17 18 19 20 18 20 18 20 20 20

[mertz]

Searched 79 of 663 base 6 sequences. 10 hours 2.65 trillion nodes. 15! 188 solutions, 16! 125 solutions and 17! 3 solutions.

[mertz]

Tests on 12! and 13! only show 30% time improvement for pruning non-factors. I must be missing something.

[mertz]

Found my error. 10 people > 24 points. Close to 400 total in contest.

[ben_burrows]

mertz в сообщении #689001 писал(а):

Found my error. 10 people > 24 points. Close to 400 total in contest.

Are you participating? If so, what's your rank so far?

[dimkadimon]

mertz в сообщении #688851 писал(а):

Searched 79 of 663 base 6 sequences. 10 hours 2.65 trillion nodes. 15! 188 solutions, 16! 125 solutions and 17! 3 solutions.

I have 12 solutions for 17!. What do you mean by "base 6 sequences"?

[mertz]

(base 5)   1,2,3,4,5    59 unique
(base 6)   1,2,3,4,5,6   663 unique

I can run 12 threads so I break the problem up.

I have 3 for 17!, but I only searched a dozen base 7 sequences.

Pruning numbers that are not a factor is about 60 times faster. But it doesn't find all solutions. 12! 48 of 56, 13! 152 of 445, 14! 62 of 65.

Just found 274 for 15!, but I am sure there are many more.

I am not participating. I never wrote a depth first search, so I thought I would give it a try. I have no idea how to attack the problem.

[dimkadimon]

mertz в сообщении #689017 писал(а):

I am not participating.

Sounds like you have some good results. You should definitely compete!

[mertz]

16!, 215 solutions. 17!, 13 solutions.

Neil and Al were going to alternate contests. What is the plan now?

[Nataly-Mak]

mertz в сообщении #689028 писал(а):

16!, 215 solutions. 17!, 13 solutions.

Отличные результаты.

Цитата:

Neil and Al were going to alternate contests. What is the plan now?

Я хотела бы, чтобы эти конкурсы были не одновременно.

-- Чт фев 28, 2013 10:45:36 --

Возвращаясь к алгоритму №1...

Берём последовательность, представляющую $(9!)^2$:

1,2,4,16,18,72,70,5040,362880,131681894400

Здесь 9 шагов (10 членов).
Теперь надо представить число 923780, используя члены этой последовательности и операции сложения/вычитания/умножения. Для рекордного решения в 13 шагов это представление должно быть в 3 шага (операции).

Вопрос: реально ли это
Надо проверить все решения для $N=9$ в качестве начальной последовательности.
В найденном решении в 15 шагов мне удалось сформировать число 923780 за 5 шагов.
Решение имеет вид (уже показывала его):

1,2,4,16,18,72,70,5040,362880,131681894400,_, _, _, _, _,121645100408832000

Хотя бы в 4 шага сформировать число 923780 у меня не получилось (это дало бы решение в 14 шагов). Но я использовала всего один вариант решения для $N=9$. Вручную все варианты трудно проверить.

[Zealint]

Пользуясь вашей снисходительность, позволю себе обратить внимание программистов на эту мою тему, где я презентую альфа-версию нашей системы сравнения эффективности программ. Мало ли, не заметили, будучи увлечёнными текущим конкурсом.

[Nataly-Mak]

В десятке жарко
Уже 11 конкурсантов имеют больше 24 баллов.
А вот 25 баллов пока только у лидера.

Цитата:

1 25.00 Tomas Rokicki Palo Alto, California, United States 22 Feb 2013 03:36
2 24.88 Hermann Jurksch Recklinghausen, Germany 27 Feb 2013 04:54
3 24.79 Lars Nagel Mainz, Germany 28 Feb 2013 13:33
4 24.74 Martin Piotte Montreal, Quebec, Canada 21 Feb 2013 23:38
5 24.38 Gil Dogon Jerusalem, Israel 1 Mar 2013 08:50
6 24.37 Andy Sloane Sunnyvale, California, United States 8 Feb 2013 21:39
7 24.36 Dmitry Kamenetsky Adelaide, Australia 25 Feb 2013 22:49
8 24.23 John Morris Simi Valley, California, United States 28 Feb 2013 02:09
9 24.22 Valentin Dobrota Constanta, Romania 7 Feb 2013 11:05
10 24.13 Herbert Kociemba Darmstadt, Germany 10 Feb 2013 07:31
11 24.01 Lucien Pech Zürich, Switzerland 1 Mar 2013 08:48

[Pavlovsky]

В конкурсе стран и континентов, организаторы поместили Россию в Азию. Ну что бы первое место было гарантированным. Увы в чемпионате Азии Россию обогнал Израиль. Надо попроситься в Африку...

-- Пт мар 01, 2013 16:36:33 --

mertz в сообщении #688529 писал(а):

I think I have a complete search now. No duplicate work.

8!  40320  [8] 1,2,4,6,36,32,35,1120,40320
8!  40320  [8] 1,2,4,6,36,32,35,1152,40320
8!  40320  [8] 1,2,4,6,36,32,35,1260,40320

Будет правильным считать эти решения тоже дубликатами. Когда в конце последовательности идет серия умножений, то порядок умножений не важен. Вышеприведенные решения отличаются только порядком перемножения чисел: 32*35*36=40320.