Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Re: Triangle Numbers Revisited

by hv (Parson)
on Oct 14, 2004 at 12:47 UTC ( #399183=note: print w/ replies, xml ) Need Help??


in reply to Triangle Numbers Revisited

I'm not sure quite how you might take advantage of it for optimisation, but the possible decompositions are restricted by the mod 3 equivalences. That is:

T_n == 1 (mod 3) when n == 1 (mod 3) T_n == 0 (mod 3) otherwise
so if we split the T_n sequence into A_n (== 0) and B_n (== 1) the possible decompositions are restricted such that:
if n == 0 (mod 3), require A A A or B B B if n == 1 (mod 3), require A A B if n == 2 (mod 3), require A B B

You can get similar restrictions by considering other prime moduli, but 3 is likely to be the most beneficial because it has a shorter than possible cycle in T_n.

Also, a word of warning on your p_tri() routine - the final result relies on comparing a floating point number for equality, normally considered a bad idea. It would be preferable to do the test instead by calculating from $t back up to the last known integer value, something like:

sub p_tri { my $num = shift; my $x = 8 * $num + 1; my $t = int((sqrt($x) + 1)/2); return +((2 * $t - 1) * (2 * $t - 1) == $x) ? 0 : --$t; }

Hugo


Comment on Re: Triangle Numbers Revisited
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://399183]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (7)
As of 2015-07-30 04:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (270 votes), past polls