Вычислить арифметические функции для большого целого числа в Mathematica быстрее?

Question

Пусть f - арифметическая функция, а A={k1,k2,...,kn} - целые числа в порядке возрастания.

Теперь я хочу начать с k1 и сравнить f(ki) с f(k1). Если f(ki)>f(k1), укажите ki как k1.

Теперь начните с ki и сравните f(kj) с f(ki), для j>i. Если f(kj)>f(ki), укажите kj как ki и повторите эту процедуру.

В конце у нас будет подпоследовательность B={L1,...,Lm} из A с этим свойством:

L1=k1
L2=ki
L3=kj
...

, где

f(L(i+1))>f(L(i)), для любого 1<=i<=m-1

Например, пусть f - функция делителей целых чисел.

Я думаю, что должен быть какой-то способ сделать это более эффективно и быстрее, чем я.

Вы знаете, как написать код для моей цели в Mathematica или Matlab.

Mathematica предпочтительнее.

«« «« «« «« «« «« «« «« «« «« «« «« «« «« «« «

Я написал код для этой программы с Mathematica, и потребовалось несколько часов, чтобы вычислить f из ki или множество B для больших чисел.

Здесь я поместил некоторую часть своего кода, и это всего лишь пример, и вопрос в моей программе может быть больше, чем они:

пробел между g - это произведение. например:

г [67757] г [353] = г [67757] * г [353]

«« «« «« «« «« «« «« «« «« «« «« «« «« «« «« «« «« ««

f[n_] := DivisorSigma[0, n];
g[n_] := Product[Prime[i], {i, 1, PrimePi[n]}];

k1 = g[67757] g[353] g[59] g[19] g[11] g[7] g[5]^2 6^3 2^7;
k2 = g[67757] g[353] g[59] g[19] g[11] g[7] g[5] 6^5 2^7;
k3 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5] 6^4 2^7;
k4 = g[67759] g[349] g[53] g[19] g[11] g[7] g[5] 6^5 2^6;
k5 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5] 6^4 2^8;
k6 = g[67759] g[349] g[53] g[19] g[11] g[7] g[5]^2 6^3 2^7;
k7 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5] 6^5 2^6;
k8 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5] 6^4 2^9;
k9 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5]^2 6^3 2^7;
k10 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5] 6^5 2^7;
k11 = g[67759] g[349] g[53] g[19] g[11] g[7] g[5]^2 6^4 2^6;
k12 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5]^2 6^3 2^8;
k13 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5]^2 6^4 2^6;
k14 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5]^2 6^3 2^9;
k15 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5]^2 6^4 2^7;
k16 = g[67757] g[359] g[53] g[23] g[11] g[7] g[5] 6^4 2^8;
k17 = g[67757] g[359] g[59] g[19] g[11] g[7] g[5] 6^4 2^7;
k18 = g[67757] g[359] g[53] g[23] g[11] g[7] g[5] 6^4 2^9;
k19 = g[67759] g[353] g[53] g[19] g[11] g[7] g[5] 6^4 2^6;
k20 = g[67763] g[347] g[53] g[19] g[11] g[7] g[5] 6^4 2^7;

k = Table[k1, k2, k3, k4, k5, k6, k7, k8, k9, k10, k11, k12, k13, k14, k15, k16, k17, k18, k19, k20];

i = 1;
count = 0;
For[j = i, j <= 20, j++, 
  If[f[k[[j]]] - f[k[[i]]] > 0, i = j; Print["k",i];
   count = count + 1]];

Print["count= ", count]

«« «« «« «« «« «« «« «« «« «« «« «« «« «« «« «« «« ««

Answer 1

DivisorSigma должен учитывать числа (он не знает, как они были построены). Вы можете существенно ускорить это, удалив gcd из списка. Подробно:

Вычислить новый список как старый список / gcd.

Фактор ЖКД.

Используйте функцию, которая, учитывая пару целых чисел в факторизованной форме, объединяет факторизацию (поэтому у вас есть их произведение в факторизованной форме).

Затем для любых двух элементов в сокращенном списке вы сравниваете их путем объединения их факторизаций с факторизацией в gcd и вызова функции для вычисления количества делителей, когда дана факторизованная форма. Это последнее - просто произведение показателей, каждое из которых увеличилось на единицу.

В коде:

kgcd = GCD @@ k;
newk = k/kgcd;
gcdfacs = FactorInteger[kgcd];

sumDivisors[faclist_] := Times @@ (1 + faclist[[All, 2]])

mergeFactorLists[fl1_, fl2_] := 
 Flatten[GatherBy[Join[fl1, fl2], First] /.
{{p1_Integer,e1_Integer}, {p1_,e2_Integer}} -> {{p1,e1+e2}}, 1]

f2[v1_] := sumDivisors[mergeFactorLists[FactorInteger[v1], gcdfacs]]

Вот ваш пример с f2, примененным к элементам newk.

Timing[i = 1;
  count = 0;
  For[j = i, j <= 20, j++,
    If[f2[newk[[j]]] - f2[newk[[i]]] > 0, i = j; Print["k", i];
      count = count + 1]];
  Print["count= ", count]]

Во время оценки In [140]: = k2

Во время оценки In [140]: = k5

Во время оценки In [140]: = k7

Во время оценки In [140]: = k8

Во время оценки In [140]: = k9

Во время оценки In [140]: = k10

Во время оценки In [140]: = k12

Во время оценки In [140]: = k13

Во время оценки In [140]: = k14

Во время оценки In [140]: = k15

Во время оценки In [140]: = k16

Во время оценки In [140]: = k17

Во время оценки In [140]: = k18

Во время оценки In [140]: = count = 13

Out [140] = {0.539918, Null}

Как прокомментировали другие, вместо этого вы можете захотеть сделать SortBy или, возможно,

sortedk = k[[Ordering[newk, All, f2[#1] < f2[#2] &]]];

- обновление 2011-02-01 -

Вот различные запрошенные функции, предназначенные для работы с целыми числами, представленными в виде списков их основных факторов и соответствующих степеней. Мы используем функции полезности для «умножения» двух или более таких представлений, чтобы их было легко построить из определения для g [] выше.

логарифм [fl_]: = fl [[All, 2]]. Log [П [[Все, 1]]]

divSigma[k_, fax_] := Times @@
  ((fax[[All, 1]]^(k*(fax[[All, 2]] + 1)) - 1)/(fax[[All, 1]]^k - 1))

mergeFactorLists[f1_,f2_,f3__] := 
  mergeFactorLists[mergeFactorLists[f1,f2],f3]

mergeFactorLists[fl1_, fl2_] := 
  Flatten[GatherBy[Join[fl1, fl2], First] /.
    {{p1_Integer,e1_Integer}, {p1_,e2_Integer}} -> {{p1,e1+e2}}, 1]

eulerPhi[fl_] := 
 Times @@ ((fl[[All, 1]] - 1)*fl[[All, 1]]^(fl[[All, 2]] - 1))

Я использую factorlist способом, аналогичным использованию g [] выше, но для получения факторизованных списков, а не самого целого числа. Для простоты преобразования кода вы можете сделать следующее:

g[n__] := factorList[n]

Тогда вы бы построили k1 и др. Как:

k1 = mergeFactorLists[g[67757], g[353], g[59], g[19], g[11], g[7], 
  g[5, 2], g[4, 3], g[2, 7]];

Замечу, что может быть лучше использовать индексацию, например k [1], k [2] и т. д. Таким образом, вы можете сохранить индекс вместо числа (представленного в виде факторизованного списка или полностью развернутого). Это было проблемой в ваших комментариях или личном письме, я не уверен.

Вот краткий пример, показывающий, что функции могут работать так, как объявлено.

В [77]: = пример = mergeFactorLists [g [59], g [19], g [11], g [7], g [5, 2], g [4, 3], g [2, 7]] Out [77] = {{2, 16}, {3, 9}, {5, 6}, {7, 4}, {11, 3}, {13, 2}, {17, 2}, {19, 2}, {23, 1}, {29, 1}, {31, 1}, {37, 1}, {41, 1}, {43, 1}, {47, 1}, {53, 1}, {59, 1}}

В [83]: = divSigma [2, пример] Out [83] = 8309625653259163198663074449058595410045270294408417958734031 \ 0136565010401600000000

В [92]: = eulerPhi [пример] Out [92] = 30117106786279162451552137484697600000000

В [95]: = examplenumber = Times @@ Map [# [[1]] ^ # [[2]] &, example] Out [95] = 225123336762006539948611826706656256000000

В [99]: = DivisorSigma [2, пример номера] Out [99] = 8309625653259163198663074449058595410045270294408417958734031 \ 0136565010401600000000

В [100]: = EulerPhi [пример номера] Out [100] = 30117106786279162451552137484697600000000

- конец обновления -

Даниэль Лихтблау Wolfram Research

Answer 2

В моей версии mathematica большая часть времени вычислений тратится на применение функции f [n]. Даже просто f [k1] занимает несколько секунд.

В любом случае вам нужно использовать SortBy . Это будет принимать список и функцию в качестве аргументов. Он применяет функцию к каждому члену списка и сортирует их по порядку от наименьшего к наибольшему, поэтому вам нужно поменять местами список с наименьшего к наименьшему. Не забудьте использовать k = List [k1, k2, ..., k20] вместо k = Table [k1, k2, ..., k20], и вы должны быть хорошими.

Answer 3

Одна из причин, почему это так медленно, в том, что вы используете for и if в Mathematica.Ни один из них не является особенно быстрым.

Обычно рекомендуется попробовать выполнить некоторую операцию со списком, так как это НАМНОГО быстрее.Я не уверен, как вы могли бы сделать это от руки, но вы можете посмотреть на это.