Re: Re: Working with factors of triangular numbers.

*To*: mathgroup at smc.vnet.net*Subject*: [mg80061] Re: [mg79864] Re: Working with factors of triangular numbers.*From*: DrMajorBob <drmajorbob at bigfoot.com>*Date*: Sat, 11 Aug 2007 02:19:28 -0400 (EDT)*References*: <200707030923.FAA17995@smc.vnet.net> <24165820.1186478071750.JavaMail.root@m35> <op.twtzghhtqu6oor@monster.gateway.2wire.net> <21337500.1186772308221.JavaMail.root@m35>*Reply-to*: drmajorbob at bigfoot.com

FactorInteger is eventually called twice for even numbers and four times for odd, but so far I haven't found a way to cache results more efficiently than Mathematica does on its own. Bobby On Fri, 10 Aug 2007 08:58:01 -0500, Carl Woll <carlw at wolfram.com> wrote: > 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 ha= ve = > 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 n= ot = > 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 fa= ct = >> 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] > -- = DrMajorBob at bigfoot.com

**Re: Cube codes just done in Mathematica**

**Re: Re: Working with factors of triangular numbers.**

**Re: Re: Working with factors of triangular numbers.**

**Re: Re: Working with factors of triangular numbers.**