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

```

• Prev by Date: Re: Cube codes just done in Mathematica
• Next by Date: Re: Re: Working with factors of triangular numbers.
• Previous by thread: Re: Re: Working with factors of triangular numbers.
• Next by thread: Re: Re: Working with factors of triangular numbers.