在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为这个程序编写了一个代码,计算k的f或大数的集合B需要几个小时.

在这里我放了部分代码,这只是一个示例,我的程序中的问题可能比这些更大:

g之间的空间是产品.例如:

g [67757] g [353] = g [67757]*g [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.

使用一个函数,给定一对因子形式的整数,合并分解(因此你的产品是因子形式).

然后对于简化列表中的任何两个元素,通过将它们的每个因子分解与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 []的定义中轻松构造.

logarithm [fl_]:= fl [[All,2]].登录[FL [[全部,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))

我以类似于上面使用g []的方式使用factorlist,但是要获得因式列表而不是整数本身.为了便于转换代码,您可以执行以下操作.

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]中:= example = mergeFactorLists [g [59],g [19],g [11],g [7],g [5,2],g [4,3],g [2,7] ]出[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,示例]输出[83] = 8309625653259163198663074449058595410045270294408417958734031\0136565010401600000000

在[92]中:= eulerPhi [示例]输出[92] = 30117106786279162451552137484697600000000

在[95]:= examplenumber = Times @@ Map [#[[1]] ^#[[2]]&,示例] Out [95] = 225123336762006539948611826706656256000000

在[99]:= DivisorSigma [2,examplenumber] Out [99] = 8309625653259163198663074449058595410045270294408417958734031\0136565010401600000000

在[100]中:= EulerPhi [examplenumber] Out [100] = 30117106786279162451552137484697600000000

- 更新 -

Daniel Lichtblau Wolfram Research