Factorials

[Pavlovsky]

Будем искать последовательность для 19! длиной 13 с двумя последними операциями умножения: 19!=ABC. Так же предполжим, что A,B,C различны.
Тогда последовательность будет выглядеть так:
..,A,..,B,..,C,AB,ABC=19!.
Все что мы можем достоверно сказать об этой последовательности, это то что C получено операцией сложения/вычитания. В противном случае у нас будет три операции умножения в конце.

Конечно мы можем выдвигать различные эвристичекие гипотезы. Например такую:
..,A,B,C,AB,ABC=19!. A,B,C - получены операциями сложения/вычитания.

[Nataly-Mak]

dmd
что-то у меня ничего не получается с вашей идеей.

Например, берём такое разложение

19! = 167960*225280*3214890

Далее берём последовательность, выстраивающую число А, например:

1,2,4,16,20,400,398,7960,160000,167960

И далее мне совсем не очевидно, что из чисел этой последовательности запросто можно получить числа 225280 и 3214890, используя не более двух операций сложения/вычитания/умножения.

Пусть даже не запросто, возможно ли вообще получить?
Я не вижу, откуда такое утверждение следует.

-- Пн фев 25, 2013 09:26:44 --

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

Тогда последовательность будет выглядеть так:
..,A,..,B,..,C,AB,ABC=19!.
Все что мы можем достоверно сказать об этой последовательности, это то что C получено операцией сложения/вычитания. В противном случае у нас будет три операции умножения в конце.

Почему число С не может быть получено так: сначала умножение каких-то двух чисел, потом сложение или вычитание (как написано в сообщении dmd - первый вариант)?

Кстати, интересно: вчера по программе mertz нашла решения для каждого из трёх чисел в приведённом разложении. Для числа 3214890 найдено более 1000 решений в 10 шагов! И даже не до конца программа работала, прервала.
Сейчас попробую искать решения для этого числа в 9 шагов.

Найдено 66 решений в 9 шагов. Несколько первых решений:

(Оффтоп)

found 66 solutions for 3214890 in 9 steps
3214890 = [9] 1,2,3,6,9,27,729,735,4374,3214890
3214890 = [9] 1,2,3,6,9,27,729,735,4410,3214890
3214890 = [9] 1,2,3,6,9,27,729,735,535815,3214890
3214890 = [9] 1,2,3,6,9,81,729,735,4374,3214890
3214890 = [9] 1,2,3,6,9,81,729,735,4410,3214890
3214890 = [9] 1,2,3,6,9,81,729,735,535815,3214890
3214890 = [9] 1,2,3,9,10,90,180,189,17010,3214890
3214890 = [9] 1,2,3,9,10,90,180,189,35721,3214890
3214890 = [9] 1,2,3,9,10,90,99,189,17010,3214890
3214890 = [9] 1,2,3,9,10,90,99,189,35721,3214890
3214890 = [9] 1,2,3,9,11,99,90,189,17010,3214890
3214890 = [9] 1,2,3,9,11,99,90,189,35721,3214890
3214890 = [9] 1,2,3,9,12,21,189,1701,1890,3214890
3214890 = [9] 1,2,3,9,18,21,189,1701,1890,3214890
3214890 = [9] 1,2,3,9,27,243,245,486,119070,3214890
3214890 = [9] 1,2,3,9,27,243,245,486,13122,3214890
3214890 = [9] 1,2,3,9,27,243,245,486,6615,3214890
3214890 = [9] 1,2,3,9,27,243,245,490,119070,3214890
3214890 = [9] 1,2,3,9,27,243,245,490,13230,3214890
3214890 = [9] 1,2,3,9,27,243,245,490,6561,3214890
...

[dmd]

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

Например, берём такое разложение

19! = 167960*225280*3214890

Далее берём последовательность, выстраивающую число А, например:

1,2,4,16,20,400,398,7960,160000,167960

И далее мне совсем не очевидно, что из чисел этой последовательности запросто можно получить числа 225280 и 3214890, используя не более двух операций сложения/вычитания/умножения.

Так проверьте! Всего три вложенных цикла и количество проверок не более $9^3$. На достройку последовательности 6 шагов, входная - 9 шагов. Соответственно, если решение есть, то оно в итоге будет длиной 15. У меня таким способом легко получаются решения нерекорды, отстающие от рекордов на 1-2 шага.

Вернее количество проверок не более $10^3$, т.к. единичку тоже стоит учесть на всякий случай.

[Nataly-Mak]

А, насчёт "проверьте" я догадываюсь
Но вы написали, что это очевидно!

У меня тоже решения близкие к рекордным (меньше на 1-2 шага для N<26), но получаю я их по другим алгоритмам (они описаны тут).

[Pavlovsky]

Изобретаем велосипед. Забавное свойство.
Если НОД(A,B)=1 ,тогда НОД(A+B,B)=1,НОД(A+B,A)=1,НОД(|A-B|,B)=1,НОД(|A-B|,A)=1.

Словами. Пусть у нас есть числа A,B. Пусть D=НОД(A,B). Тогда A+B=D(A'+B'). Причем, если (A'+B') разложить на простые множители, то среди них не будет простых чисел, которые есть в разложиении чисел A,B на простые множители.

Пример. Пусть либо A, либо B делятся на простые числа от 2 до 37. Тогда A+B (A-B) будет иметь в качестве делителя простое число большее 37 (либо равняться 1).

[Pavlovsky]

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

Почему то большинство моих лучших решений для N>=13 начинаются с 1, 2, 4 а не 1, 2, 3. Никто похожее не наблюдал?

Посмотрел свои лучшие решения. Большинство из них начинается с 1,2,4 и даже 1,2,4,16 и даже есть 1,2,4,16,256. Почему так происходит? Ответ очевиден!

[Pavlovsky]

Во многих языках программирования есть операция A%B, которая определяет остаток от деления A на B.

У меня возникла задача. Определить является число B делителем числа A? То есть мне не нужен остаток, мне нужно получить ответ "Да" либо "Нет". Существуют ли супер эффективные алгоритмы для такой процедуры?

[Nataly-Mak]

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

У меня возникла задача. Определить является число B делителем числа A? То есть мне не нужен остаток, мне нужно получить ответ "Да" либо "Нет". Существуют ли супер эффективные алгоритмы для такой процедуры?

Не поняла.
А чего тут надо суперэффективного? Элементарно делите число А на число В и смотрите остаток (точнее, остаток смотрит программа, ибо вам остаток неважен). Если остаток равен нулю, то ответ "Да", если остаток не равен нулю, то ответ "Нет".
Той же самой процедурой, о которой вы написали, и воспользуйтесь.

[dimkadimon]

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

Посмотрел свои лучшие решения. Большинство из них начинается с 1,2,4 и даже 1,2,4,16 и даже есть 1,2,4,16,256. Почему так происходит? Ответ очевиден!

Конечно А, А^2, А^4, А^8... даёт наиболее быстрый рост чисел, но это не значит что такие решения будут оптимальными. Например, для N>=13 у меня нет ни одного лучшего решения которое начинается с 1, 2, 4, 16, 256. Просмотрел первые 4 цифры лучших решений и получился вот такой интересный расклад:

1, 2, 4, 6: 64%
1, 2, 4, 16: 21%
1, 2, 3, 9: 8%
1, 2, 3, 5: 5%
1, 2, 4, 5: 2%

Поэтому рекомендую начинать с 1, 2, 4, 6.

[Pavlovsky]

Операция b mod a (a%b) весьма не быстрая процедура. Мне нужно что то ну очень быстрое.

[Nataly-Mak]

Pavlovsky
почему-то вспомнился Высоцкий:
"И вкусы, и запросы мои странны..."

Вам надо убыстрить элементарную операцию деления с остатком?
Хороший запрос!

[Pavlovsky]

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

Хороший запрос!

Когда операция a mod b = 0 выполняется миллионы раз и занимает 50% времени работы алгоритма, то подобные запросы нормальные.

[dimkadimon]

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

У меня возникла задача. Определить является число B делителем числа A? То есть мне не нужен остаток, мне нужно получить ответ "Да" либо "Нет". Существуют ли супер эффективные алгоритмы для такой процедуры?

Да, но они сложные: http://stackoverflow.com/questions/6896 ... 2-3-4-5-16
Народ пишет что хороший компилятор должен сам заметить что A%B==0 можно сделать быстрее. Кстати если B=2^k, тогда можно легко проверить: return !(A&(B-1))

[Pavlovsky]

http://ru.wikipedia.org/wiki/%D0%9C%D0% ... 0%BD%D0%B0
Метод Лемана

Теорема: Пусть n=pq составное число, являющееся произведением двух нечетных взаимно простых чисел, удовлетворяющих неравенствам $n^{1/3}<p<q<n^{2/3}$. Тогда, найдутся натуральные числа x, y и k такие, что

1. Выполнено равенство $x^2-y^2=4kn$ при $k<n^{1/3}$,
2. Выполнено неравенство $0 \le x-\lfloor \sqrt{4kn} \rfloor < \frac {n^{1/6}} {4 \sqrt{k}}+1$.

-- Вт фев 26, 2013 12:24:08 --

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

Да, но они сложные:

Может облегчит задачу? A=37! То есть задача получается такой:

Очень быстро определить является ли число B делителем 37!

-- Вт фев 26, 2013 12:31:00 --

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

Поэтому рекомендую начинать с 1, 2, 4, 6.

Мне с моего 54-го места трудно с вами спорить. При постороении последовательности рано или поздно у нас должны появиться числа делителями которых являются все простые числа от 2 до <=N. Но зачем с этим торопиться?! Зачем получать число 6 делителем которого является 3 на третьем шаге?

Начало 1,2,4,16 выглядит куда более переспективным.

[Nataly-Mak]

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

Очень быстро определить является ли число B делителем 37!

Факторизуйте 37!

37! = 2^34 * 3^17 * 5^8 * 7^5 * 11^3 * 13^2 * 17^2 * 19 * 23 * 29 * 31 * 37

Теперь смотрите на ваш делитель В: является ли он произведением степеней простых чисел, входящих в разложение 37! Для этого число В тоже факторизуйте.

Например, является ли число В=14504 делителем 37!?
Ответ очевиден: является, так как 14504=2^3*7^2*37

Я всё это вообще вручную определяю.
Мой "кластер" тоже выполняет эту процедуру, ну, не миллион раз, конечно, и не супербыстро. Но выполняет же