Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

Re: Triangle Numbers Revisited

by TedPride (Priest)
on Oct 14, 2004 at 11:21 UTC ( #399165=note: print w/ replies, xml ) Need Help??

in reply to Triangle Numbers Revisited

EDIT: For some reason, a few numbers such as 1035 are causing errors (Can't take sqrt of -1, <STDIN> line 1.) Going to have to hunt down the bug and fix it...

EDIT: Just needed a slight change to the first line after BING to prevent tget calls for 0:

use strict; use warnings; my ($i, $j, $inum, $jnum, $left); $| = 1; print "Enter the number to check : "; my $inp = <STDIN>; BING: for ($i = tget($inp-2); $i; $i--) { $inum = tmake($i); $left = tget($inp - $inum - 1) + 1; for ($j = 1; $j < $left; $j++) { $jnum = tmake($j); last BING if (tis($inp - $inum - $jnum)); } } print " Your triangles are : $inum $jnum " . ($inp - $inum - $jnum) . "\n"; sub tget { return int(sqrt(1 + $_[0] * 2) - .5); } sub tmake { return (.5 * $_[0] * ($_[0] + 1)); } sub tis { my $n = shift; return ($n == tmake(tget($n))); }
Incidently, I ran a looped version of this for all numbers 3-100000, and only the following could not be made with sums of three triangles:

4, 6, 11, 20, 29

As far as I can tell, all integers after 29 can be made with at least one sum of three triangles. The number of sums increases as you go along.

Comment on Re: Triangle Numbers Revisited
Download Code
Replies are listed 'Best First'.
Re^2: Triangle Numbers Revisited
by Limbic~Region (Chancellor) on Oct 14, 2004 at 12:53 UTC
    Good catch! I didn't have time to track it down myself this morning as I was supposed to be getting ready for work. For the purposes of the original thread, it appears that 0 was being allowed as a triangular number. With that allowance, all numbers can indeed be the sum of 3 triangles.

    As far as speed, you are right that this is quite fast. If it was not fast enough in a real problem you would likely use C as tachyon, the cheater, did ;-)
    I have no idea about how to figure out the big O of either solution, but I did want to mention that my solution is more than a constant factor faster in case you decided to spend the time optimizing. At 5_000 random targets between 1 and 5_000_000 it was twice as fast, but for 10_000 random targets between 1 and 987_654_321 it was three times as fast. I didn't want to come off as offensive - I just like silly challenges like this.

    Cheers - L~R

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (4)
As of 2016-05-31 03:00 GMT
Find Nodes?
    Voting Booth?