Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change

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.

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 all is quiet...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (5)
As of 2017-07-26 06:14 GMT
Find Nodes?
    Voting Booth?
    I came, I saw, I ...

    Results (383 votes). Check out past polls.