Re: Re: Working with factors of triangular numbers.

*To*: mathgroup at smc.vnet.net*Subject*: [mg80033] Re: [mg79864] Re: Working with factors of triangular numbers.*From*: Carl Woll <carlw at wolfram.com>*Date*: Sat, 11 Aug 2007 02:04:56 -0400 (EDT)*References*: <200707030923.FAA17995@smc.vnet.net> <24165820.1186478071750.JavaMail.root@m35> <op.twtzghhtqu6oor@monster.gateway.2wire.net>

Nice. I have some comments below, and a suggestion for further speed improvements. DrMajorBob wrote: > Here's a significantly faster code (for n=12,13 anyway). > > Clear[lldaux5, lld5, t5, factorCounts] > factorCounts[1] = factorCounts[2] = factorCounts[3] = {1}; > factorCounts[4] = {2}; > factorCounts[7] = {3}; > factorCounts[k_Integer] := > If[EvenQ@k, factorCounts[(k + 2)/2, k - 1], > factorCounts[(k - 1)/2, k + 2]] > factorCounts[j_Integer, k_Integer] := > Switch[GCD[j, k], > 1, > Join[FactorInteger@j, FactorInteger@k], > 3, Replace[ > Join[FactorInteger[j/3], > FactorInteger[k/3]], {3, s_} :> {3, s + 2}, {1}]][[All, -1]] // > Sort > lldaux5[{}] := 0 > lldaux5[x_List] /; MemberQ[x, 1] := > Count[x, 1] + lldaux5@DeleteCases[x, 1] > lldaux5[Lpow_] := > lldaux5[Lpow] = > With[{Mtup = Tuples[Range[0, #] & /@ Lpow]}, > Total[Quiet@ > LinearProgramming[ConstantArray[-1, Length[Mtup]], > Transpose@Mtup, Thread@{Lpow, 0}, > Array[{0, 1} &, Length[Mtup]], Integers]] - 1] > lld5[n_Integer] := lldaux5@factorCounts@n > t5[n_] := # (# + 1)/2 &@NestWhile[# + 1 &, 2, lld5[#] < n &] > > T2c /@ Range[10] // Timing > t5 /@ Range[10] // Timing > > {0.422, {3, 15, 55, 253, 1081, 13861, 115921, 665281, 18280081, > 75479041}} > > {1.046, {3, 15, 55, 325, 1081, 18145, 226801, 665281, 18280081, > 75479041}} > > T2c[11] // Timing > t5[11] // Timing > > {1.625, 2080995841} > > {3.063, 2080995841} > > Timing differences aren't reliable either way for n<=11, but beyond > that it's a different story: > > T2c[12] // Timing > t5[12] // Timing > > {27., 68302634401} > > {17.187, 68302634401} > > T2c[13] // Timing > t5[13] // Timing > > {150.172, 924972048001} > > {64.032, 924972048001} > > t5[14] // Timing > > {516.546, 48318396825601} > > The trick (already used by someone else, I think) > > lldaux5[x_List] /; MemberQ[x, 1] := > Count[x, 1] + lldaux5@DeleteCases[x, 1] > > means that if the factor counts includes n ones, the LP problem used > by T2c has 2^n times as many variables as the one used by t5. Yet > this yielded only a 10-15% improvement, by itself. It might be possible to speed up this even further by figuring out how to get the longest pairs, longest triplets, etc approach to work. I have an idea on how to do this, but it'll need to wait until I have more spare time. On the other hand, I think the majority of time is spent factoring integers, so speeding up this portion of the algorithm may not be so important. > > A bigger gain was achieved in factorCounts, based on one of Carl > Woll's ideas in > > http://forums.wolfram.com/mathgroup/archive/2007/Jul/msg00411.html > > factorCounts[k_Integer] := > If[EvenQ@k, factorCounts[(k + 2)/2, k - 1], > factorCounts[(k - 1)/2, k + 2]] > > Several fine adjustments were required to get any improvement at all. > Defining factorCounts for 1,2,3,4, and 7 removed steps from the code > for other cases, and it was crucial to take full advantage of the > fact that the GCD of the two factors could only be 1 or 3. Clever use of GCD so that you can just use Join. One other idea I had here was the following. As you run through k you are essentially using FactorInteger twice, once for the larger factor of k, and then for the smaller factor of k+3 (up to a factor of 2 or 3). By increasing k in steps of 3, you can remember the FactorInteger results of the larger factors, so that in the next step you don't need to use FactorInteger on the smaller factors. Since FactorInteger is the most expensive operation on average, this might produce another factor of ~2 speedup. Carl > > Bobby > [snip]