This sounds distinctly like homework, which you will not get a good response to here if you are asking us to do it for you.

If, as you say, you have been at this for hours, then you must have some code showing what you have tried so far. If you post that, and an explanation of what problems you are having with your code, people may be prepared to point you in the right direction.

Didn't think of it sounding like that, sorry.

#!perl
use strict;

my $x = 1;
my $y = 1;
my $total;

while ($x*$y ne 133745531) {
    $x++;
    $y++ if $x == 137745532;
    $x = 1 if $x == 137745532;
    $total = $x*$y;
    print $total."\n";
}
print "$x+$y";
exit;
[download]

This is all I have right now. Also, no. This is no homework -- don't know how else I can prove that to you though, except by that above code. That code that I have isn't very effective, and will take quite along time to actually come up with the (any) proper results. I'm currently working on another variation which will be alot faster, but I still have no guarantee it will work (although once it is done, I will post it here).

Okay. The process you describe is called factorisation. There is probably at least one module to do this on CPAN.

However, if you need to do it yourself, then my tip would be to start with the big number an work backwards using modulos rather than with 1 and multiplying.

Tips:

No factor of a number can be bigger than the square root of that number (excluding the number itself)

Update: As rightly pointed out by sauoq, the previous statement is a bunch of dingoes kidney's. The point I was trying to make in my clumsy way was.

In any pair of factors (f¹, f²) of N, one of the pair must be less than or equal to the square root of N. It therefore follows that by limiting the iteration of your search to 2..squareroot N, you are guarenteed to find all the smaller values in each pair of factors, and the larger may, by definition, be trivially found by divison of N by the smaller.

The square root can be found using

$sqrt=$number**0.5;

sauoq also pointed out that the line above can also be done using $sqrt = sqrt $number;

and

if ($number % $n == 0) { 
  ## $n is a factor of $number;
}
[download]

Put that together with a loop and it finds the factors in a blink of an eye.

Have fun:)

---

Nah! You're thinking of Simon Templar, originally played (on UKTV) by Roger Moore and later by Ian Ogilvy

Just a few pointers. You should be using != rather than ne in your while condition. ne is for string comparsion, and != is number comparison. Also, you don't need to increment both numbers. Just increment one, and divide into the total. If there's no remainder, you have one factor, which makes it easy to get the other one.

On a side note, to everyone else who's reading, I can attest that this isn't homework. It's one of the Geek Challenges; the second one, actually. A couple of the higher ones are quite fun.

kelan

---

Perl6 Grammar Student

Factoring large numbers is a difficult problem in general. The particular number you cite is small enough to be fairly easy. &Math::Pari::factor doesn't take much time to find that the prime factors of 133745531 are 467 and 286393. You may also have a system program called 'factor' which will give that result somewhat more slowly.

The difficulty of this problem is the basis of RSA public key cryptosystems.

After Compline,
Zaxo

That's far too many hints, I think...

--
IndyZ

Heh, thanks =) I don't want enough hints that the program is written, but enough for me to get on the right track (which there now is enough for).

use strict;

sub find_factors {
    my $number = shift;
    my $factors = shift;
    my $try;
    my $finished = 0;
    for ($try = 2; !$finished && ($try <= sqrt($number)); $try ++) {
        if (($number % $try) == 0) {
             push @{$factors}, $try;
             find_factors($number / $try, $factors);
             $finished = 1;                
        }
    }
    if (!$finished) {
        push @{$factors}, $number;
    }
}

my $factors = [];
find_factors(1024, $factors);
print join(",", @{$factors});
[download]

$n=133745531;
$n%$_||print"\n$_ x ",$n/$_ for 2..sqrt$n
[download]

cheers

tachyon

s&&rsenoyhcatreve&&&s&n.+t&"$'$`$\"$\&"&ee&&y&srve&&d&&print

kelan

Perl6 Grammar Student

as best as I can tell, it is to reveal the behavior of the * operator (which we already know). That way if 13 * 2 = 15 we would know that * represents addition rather than multiplication. That's my guess from just reading this here. I have no clue why it was actually included.

I wish I knew that, honestly. That makes no sense to me aswell. Basically, I'm running through a level system, that encourages programming through Perl, C#, C++, etc. This was one of the questions there, and that was given as relivent info. I was talking to a friend of mine (good math person), and he's the one that suggested another route to this (which I'm doing now, finding the prime numbers and multiplying that way). So if I can get this working, I'll find out if 13 * 2 = 26 has anything to do with this or not *lol*.

The relevance of 13*2=26 is that 13 and 2 are both primes and they are also factors of 26. That is supposed to help you figure what primes and factors are, which are needed to solve this problem.

Thanks BrowserUk -- I've about had it for tonight, so I'll try my hand at this again in the morning. If for some reason I still can't get it, I'll post back. However, with what is posted, I should have it. Thanks again.

Also, rbc -- don't worry about it now. BrowserUk answered the part that had me stumped.