Re: Triangle Numbers Revisited

[Limbic~Region]

in reply to Triangle Numbers Revisited

All,
I was having a conversation with blokhead in the CB concerning the most efficient solution to this problem. Not having any idea how to determine the big O notation, I ran a few tests to see how well my solution scaled.

The first thing I noticed was the average number of guesses doubled every time I increased the search group by a factor of 10. Then I noticed something really cool - it also corresponded to a power of 2. This allowed me to calculate the average case scenario for any number

#!/usr/bin/perl
use strict;
use warnings;

my $num       = $ARGV[0] || 47;
my $length    = length $num;
my $base      = 10 ** ($length - 1);
my $base_ave  = 2  ** ($length - 1);
my $next      = 10 ** $length;
my $next_ave  = 2  ** $length;
my $ave_diff  = $next_ave - $base_ave;
my $tot_diff  = $next     - $base;
my $distance  = $num - $base;
my $guess     = $base_ave + ($distance * $ave_diff) / $tot_diff;
print "$guess\n";

So for 12_345 you can expect 16.42, and for 123_456_789 you can expect 262.67 As you can see this scales quite well. While this is the average case, the worst case scenario should still scale reasonably well.