Factorials

[Nataly-Mak]

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

I am guessing Al changed the rankings page to make it display the raw score, instead of a relative score.

Так намного лучше - информативнее, сразу видно, у кого какое решение:

Цитата:

1 244 Wes Sampson La Jolla, California, United States 30 Apr 2013 00:12
2 248 Robert Gerbicz Halasztelek, Hungary 27 Apr 2013 23:05
3 252 Helge Keller Karlsruhe, Germany 28 Apr 2013 08:21
4 269 Jarek Wroblewski Wroclaw, Poland 28 Apr 2013 09:35
5 280 Vladimir Chirkov Bobruisk, Russia 29 Apr 2013 13:03
6 292 Michael Hürter Saarbrücken, Germany 28 Apr 2013 16:36
7 312 Lars Nagel Mainz, Germany 29 Apr 2013 00:14
8 314 Alex Chernov Penza, Russia 28 Apr 2013 15:41
9 373 James Buddenhagen Xico, Veracruz, Mexico 28 Apr 2013 15:15
10 379 Valery Pavlovsky Ekaterinburg, Russia 24 Apr 2013 11:06

Это топ-10.
Итак, 244 шага есть. Будет ли 200

-- Вт апр 30, 2013 05:40:33 --

(Оффтоп)

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

(Gerbicz)

В этом конкурсе я поставил на Вас, Уважаемый.
Ваш проигрыш -- это мой проигрыш.

whitefox
Много проиграли?
Ну, не расстраивайтесь. Он ещё, возможно, отыграется
Ведь конкурс ещё не закончился.
Это такой закон жизни --- кто-то выигрывает, кто-то проигрывает. Всем выиграть невозможно, увы.

[Pavlovsky]

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

I could raise it to 32 steps

32 шага мало. Спасибо за попытку помочь. Придется все делать самому.

[whitefox]

(Оффтоп)

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

whitefox
Много проиграли?

Ещё не вечер

Но похоже Gerbicz уже выдохся, увы
Как верно заметил Pavlovsky, Gerbicz далеко не стайер.
Его удел спринт.

[Pavlovsky]

Чего то сильно опустился в рейтинге. Хотя все идет по плану. Идет первый этап оптимизации. В результате будет решене в районе 280 операций. Правда сейчас этим уже никого не удивишь.
После завершения первого этапа оптимизации, начну охоту за золотой рыбкой. Буду искать решение в районе 230 операций. Пакет идей уже сформирован.

PS Игра пошла в открытую. Думаю, может и мне опубликовать свой пакет идей?!

[dimkadimon]

Полезные тождества. Для 1000:

106890007738661124410157 = 83^12-4 = 3*31*43*131*137*223*239*283*433*457*499
1560496482665168880 = 188^8-16 = 2^4*3*5*13*41*43*53*137*269*337*431
10260628712958602160 = 29^13-29 = 2^4*3^2*5*7*13*29*37*61*67*271*313*421
353814783205469040 = 29^12-1 = 2^4*3^2*5*7*13*37*61*67*271*313*421
174859124550883185 = 143^8-16 = 3*5*7*17*23*37*89*109*127*233*401
103953325454500080 = 134^8-16 = 2^4*3*5*13*29*41*47*61*73*191*701
899194740203760 = 74^8-16 = 2^4*3*5*7*11*13*17*23*29*41*83*97
876488338465357800 = 24^13-24 = 2^3*3*5^2*7*13*23*73*79*349*577*601
1698356304099999936 = 190^8-64 = 2^6*3^2*7*23*31*127*131*233*257*593
1677721599999900 = 80^8-100 = 2^2*3^2*5^2*7*13*19*23*31*53*103*277
36520347436056575 = 24^12-1 = 5^2*7*13*23*73*79*349*577*601
26584441929064305 = 113^8-16 = 3^3*5*11*13*17*41*43*193*317*751
2684354559999840 = 160^7-160 = 2^5*3^2*5*7*13*19*23*31*53*103*277
124097929967680200 = 137^8-121 = 2^3*3^3*5^2*7*37*43*89*199*263*443
21611482313284149 = 43^10-100 = 3*11*13*19*23*29*47*317*479*557
16777215999999 = 160^6-1 = 3^2*7*13*19*23*31*53*103*277
2569093262823360 = 159^7-159 = 2^6*3*5*7*13*19*37*53*79*97*103
350749278894882800 = 156^8-16 = 2^4*5^2*17*23^3*29*41*43*283*293
18509302102818800 = 108^8-16 = 2^4*5^2*7^3*13*17*19*229*307*457
18014398509481920 = 64^9-64 = 2^6*3^2*5*7*13*17*97*241*257*673

Для 37:

1330863360 = 191^4-1 = 2^8*3*5*17*19*29*37
8031810150 = 26^7-26 = 2*3^4*5^2*7*13*19*31*37
19770609600 = 52^6-64 = 2^6*3^4*5^2*7*19*31*37
308915775 = 26^6-1 = 3^4*5^2*7*19*31*37
9509900400 = 99^5-99 = 2^4*3^2*5^2*7^2*11*13^2*29
214358760 = 121^4-121 = 2^3*3^2*5*7*11^2*19*37
99999900 = 100^4-100 = 2^2*3^3*5^2*7*11*13*37
214358760 = 11^8-121 = 2^3*3^2*5*7*11^2*19*37
99999900 = 10^8-100 = 2^2*3^3*5^2*7*11*13*37
6967870 = 191^3-1 = 2*5*7*13^2*19*31
1771560 = 121^3-1 = 2^3*3^2*5*7*19*37
601692000 = 57^5-57 = 2^5*3*5^3*7*13*19*29
19487160 = 11^7-11 = 2^3*3^2*5*7*11*19*37
1771560 = 11^6-1 = 2^3*3^2*5*7*19*37
855036000 = 171^4-81 = 2^5*3^4*5^3*7*13*29
96059600 = 99^4-1 = 2^4*5^2*7^2*13^2*29
4879680 = 47^4-1 = 2^6*3*5*13*17*23
63999936 = 20^6-64 = 2^6*3^3*7*11*13*37
9999990 = 10^7-10 = 2*3^3*5*7*11*13*37
7999992 = 200^3-8 = 2^3*3^3*7*11*13*37

Сейчас ищу более крупные числа.

[Pavlovsky]

Ловим золотую рыбку.

Пусть у нас есть разложние 1000! Я использую разложение на простые множители, но это не обязательно.
Вот множители в степени 3,2,1

(251*257*263*269*271*277*281*283*293*307*311*313*317*331)^3*
(337*347*349*353*359*367*373*379*383*389*397*401*409*419*421*431*433*439*443*449*
457*461*463*467*479*487*491*499)^2
*(503*509*521*523*541*547*557*563*569*571*577*587*593*599*601*607*613*617*619*631*
641*643*647*653*659*661*673*677*683*691*701*709*719*727*733*739*743*751*757*761*
769*773*787*797*809*811*821*823*827*829*839*853*857*859*863*877*881*883*887*907*
911*919*929*937*941*947*953*967*971*977*983*991*997)

Простейший способ вычислить это выражение, это сформировать все простые числа и их перемножить. Но можно значительно уменьшить количество используемых операций.
Сформируем все возможные произведения для каждой группы 1,2,3 в отдельности. Далее необходимо найти из полученных чисел число A, которое можно получить из остальных чисел за небольшое количество операций. Тогда нет необходимости формировать простые числа вошедшие в A и их перемножать. Пусть A получено перемножением N чисел и получить его из других чисел можно за K операций. Тогда экономия операций будет равняться 2N-1-K. Естественно, чем больше N тем больше экономия.

Подсчеты показывают, чтобы выйти на результат 230 операций достаточно найти 5 чисел которые получены умножением 6-ти (или более) простых чисел и которые получаются из других чисел за две операции.

[Gerbicz]

mertz: "Only the Rule of this Challenge is there are no rules"

So you are not right, we have a rule.

whitefox: "The night is young but seems Gerbicz already exhausted, alas As rightly pointed Pavlovsky , Gerbicz not stayer. His destiny sprint"

No, I haven't finished. Moreover I could easily win the previous contest also in one day, but recognized that the range of N values is too small and lots of contestant will reach the perfect score. I'm a gentleman, and I have given you a chance to win the contest.

[whitefox]

(Оффтоп)

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

Moreover I could easily win the previous contest also in one day, but recognized that the range of N values is too small and lots of contestant will reach the perfect score.

"Кислый виноград"

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

I'm a gentleman

[Gerbicz]

5 280 Vladimir Chirkov Bobruisk, Russia 29 Apr 2013 13:03
6 280 Valery Pavlovsky Ekaterinburg, Russia 30 Apr 2013 12:06

Look at the country, the time, the result. After it I have only one question. Why they are not in a team? Please comment!

[dimkadimon]

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

Look at the country, the time, the result. After it I have only one question. Why they are not in a team? Please comment!

Why can't two people have the same score? At one stage I saw that Wes had the same score as Helge.

Robert, why don't you concentrate on the competition instead of accusation.

[whitefox]

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

Look at the country, the time, the result.

Ну посмотрел, ну и что?
От Бобруйска до Екатеринбурга чуть ближе чем до Китая (да и Бобруйск в Белоруссии, а не в России), разница во времени почти сутки -- в чём Вы увидели криминал?

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

After it I have only one question.

У меня тоже только один вопрос -- Вы считаете своё поведение джентльменским?

[Gerbicz]

dimkadimon: "At one stage I saw that Wes had the same score as Helge."

Yes, after Helge posted his/her method.

whitefox: "From Bobruisk to Yekaterinburg little closer than to China (and Bobruisk in Belarus, not Russia)"

In that case Al hasn't got a Belarus country flag?

[whitefox]

(Оффтоп)

Предсказание Nataly-Mak сбывается.
Художественный свист мы уже имеем, а белки, похоже, не будет.
Товарищ спёкся.

В.Высоцкий писал(а):

Я на десять тыщ рванул как на пятьсот, и спекся
Подвела меня, ведь я предупреждал, дыхалка
Пробежал всего два круга и упал, а жалко

Одним словом спринтер.

[mertz]

Last version. Added Chain Search. 30 steps. Twice as fast is some cases. Chain search with pruning found solutions for 21! and 22! in 6 hours.

https://www.dropbox.com/s/tlxvelhrfwav3im/Factorials_win64.zip

https://www.dropbox.com/s/t1uihaxxazv5onb/Factorials_win32.zip

[Nataly-Mak]

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

Chain search with pruning found solutions for 21! and 22! in 6 hours.

mertz
для N=21 и N=22 найдено только одно решение или несколько решений?

Мне интересно, какое вы получили решение для 22!
Пожалуйста, покажите.

P.S.
Чтобы ссылки были рабочими здесь, не надо использовать тег [code][/code].
Пишите так:

https://www.dropbox.com/s/tlxvelhrfwav3 ... _win64.zip
https://www.dropbox.com/s/t1uihaxxazv5o ... _win32.zip

Это работает. Я уже скачала программу для win64.
Завтра опробую её. Спасибо вам, что вы всё ещё работаете.

-- Ср май 01, 2013 03:01:11 --

Цитата:

4 269 Jarek Wroblewski Wroclaw, Poland 28 Apr 2013 09:35
5 269 Vladimir Chirkov Bobruisk, Russia 30 Apr 2013 17:42

Почему они не в команде?

Vovka17
признайтесь: вам Jarek рассказал свой алгоритм? (шутка)

Pavlovsky
ждём 230 шагов

У лидера уже 241. Класс!