How to find the smallest number that is evenly divisible by all of the numbers from 1 to 20



  • At my work when interviewing people we give them simple programming tasks just to check their ability. This was an attempt to solve a problem I found on Project Euler (http://projecteuler.net/index.php?section=problems&id=5). It was given to us by a candidate for a senior development position with "10 years of using PHP". This is what he turned in. OK, it works, but ...

    
    	for ($i=1;$i<=99999999999;$i++) { 
    		
    		$num = 20*$i;
    		if ($num%19 == 0) {
    			if ($num%18 == 0) {
    				if ($num%17 == 0) {
    					if ($num%16 == 0) {
    						if ($num%15 == 0) {
    							if ($num%14 == 0) {
    								if ($num%13 == 0) {
    									if ($num%12 == 0) {
    										if ($num%11 == 0) {	
    											if ($num%9 == 0) {
    												if ($num%8 == 0) {
    													if ($num%7 == 0) {
    														if ($num%6 == 0) {
    															if ($num%3 == 0) {
    																echo $num;
    																exit();
    															}
    															
    														}
    													}
    												}
    											}
    										
    										}
    										
    									}
    								}
    							}
    						}
    					}
    					
    				}
    			}
    		}
    	
    	}
    	
    


  •  Maybe he meant "10 years of using websites written in PHP".



  • Wow. There are a lot of problems with that code... The for loop is the biggest one. I mean, that's just about the first thing you learn in any language, and he doesn't get it.

    Also, what's with skipping 1, 2, 4 and 5, but not 3, 6, 8 or 9?  If it weren't for the 8, it almost seems like he never learned how to divide or multiply by 3. Confusing...

    TBH, I wonder if he knows what && is, or if he thinks that 15 nested loops are really more readible.



  • To be honest, after thinking about it I think the only real issue is the for loop. Everybody locks up in an interview, and the nested if blocks ***may*** be for simplicity in describing a solution, rather than a practical application of that solution.

    If the for loop were written correctly:
    for ($i=20; ; $i+=20)
    ...then I'd ask him about the rest, and give him a shot to redeem himself.

    But with the whole thing written like that... I would bet he's never done more than hack.



  • @mann_jess said:

    To be honest, after thinking about it I think the only real issue is the for loop. Everybody locks up in an interview, and the nested if blocks may be for simplicity in describing a solution, rather than a practical application of that solution.

    If the for loop were written correctly:
    for ($i=20; ; $i+=20)
    ...then I'd ask him about the rest, and give him a shot to redeem himself.

    But with the whole thing written like that... I would bet he's never done more than hack.

    Well, in our discussion afterwards I asked him if he could think of any shorter or more efficient ways to write the code. He responded that maybe he would have considered writing a 'while' block to generate the if statements.



  • print 16*9*5*7*11*13*17*19

    probably doesn't qualify, I guess? Because if you are using a loop for such a problem at all, it should be done properly.



  • Out of curiosity, would you accept a pen and paper solution by hand? That's how I solved it way back.



  • @mann_jess said:

    To be honest, after thinking about it I think the only real issue is the for loop.

    Are you fucking serious?  The real issue is that the guy doesn't even understand basic math, let alone basic coding.  Here's the right solution, lazily done: 

    function foo($num)
    {
    
        $all_factors = array();
    
        for ($i = 2; $i &lt;= $num; $i++) {
                $tmp = preg_split('/\s+/', trim(`factor $i`));
                $my_factors = array();
    
                for ($j = 1; $j &lt; count($tmp); $j++) {
                        $my_factors[$tmp[$j]]++;
                }
    
                foreach ($my_factors as $factor =&gt; $occur) {
                        if ($all_factors[$factor] &lt; $occur) {
                                $all_factors[$factor] = $occur;
                        }
                }
        }
    
        $result = 1;
    
        foreach ($all_factors as $factor =&gt; $occur) {
                $result *= pow($factor, $occur);
        }
    
        return $result;
    

    }



  • @ammoQ said:

    print 16*9*5*7*11*13*17*19

    Not generic enough! 



  • @ammoQ said:

    print 16957111317*19

    probably doesn't qualify, I guess? Because if you are using a loop for such a problem at all, it should be done properly.


    @wybl said:
    Out of curiosity, would you accept a pen and paper solution by hand? That's how I solved it way back.

    I'd be happy with either of these (assuming the pen and paper solution had some form of ammoQ's solution). Our applications are written C++ or PHP, but I'm happy for people to give me their answers in Python/Perl/Ruby/any other language/any other format. This was one of twenty tasks that increased in difficulty. This was the easiest, so you can probably guess how horrific his attempts at the rest were. The tasks are mostly to check their mathematical ability rather than their programming chops, as the job involves a LOT of mathematical stuff, but this guy really took the piss.

    Suprisingly (or not), I had to fight pretty hard with HR to reject him. His resume was pretty 'impressive' in their eyes - he'd had a long stream of jobs at various semi-well known companies. They didn't think to wonder why he'd only spent six months at each.



  • Here's another one he did for me from Euler:

    What is the largest prime factor of the number 600851475143?

    function IsPrime($Num)
    
    {
         $No = 0;
           for($CurrNum = 2; $CurrNum <= $Num; $CurrNum++)
            {
                  for($Divisor = 2; $Divisor  < $CurrNum; $Divisor++)
                    {
                    	$Res = $CurrNum / $Divisor;
                    }
    
    				if($Res != 1 && intval($Res) == $Res)
                           {
                                  $No = 1;
                                  $Divisor = $CurrNum;
    						}
    				}
    		
    		
    	if($No != 1) {
    		$Result = $CurrNum;
    	}
    	
    	$No = 0;
        if($Result == $Num) { return 1;}
         else { return 0; }
    }
    
            
            
    $composite = 600851475143;
    $halfComposite = 300425737571;
    
    for ($i=501;$i <=$halfComposite;$i+=2) {
    	if (IsPrime($i)) {
    		$prime = $i;
    	}
    }
    
    echo $prime;
    

    The code timed out after 30 seconds. I'm pretty sure he copied his function from here: http://www.geekpedia.com/code14_Check-for-prime-numbers.html. What got me was that in this one he shows that he knows how to use $i+=, and yet still did it wrong.

    I know I said above that I'm happy for people to use any language, but I can't help but wonder why he didn't write it in C++ or something similar (he professed to having five years of experience with C++ on his resume) which would have been way faster than looping 30,042,573,571 times in PHP. I know it's been said a lot of times before on these forums, but it never ceases to amaze me that these people never stop and think, "hang on, there must be a better way of doing this".



    His code for calculating the Fibonnaci sequence didn't work either - it printed '2' 40,000,000 times. I can't help but conclude that his CV was a complete fabrication.



  • @mann_jess said:

    Also, what's with skipping 1, 2, 4 and 5, but not 3, 6, 8 or 9?  If it weren't for the 8, it almost seems like he never learned how to divide or multiply by 3. Confusing...

    Since he starts off by making $num a multiple of 20, it's already guaranteed to be divisible by 2, 4, 5, and 10, so he skipped those tests.

    Since the factors start at 1, though, it's vastly, vastly more efficient to build a list of the necessary prime factors and create the result by multiplying through the list. Iterating and checking modulus results like that is a major waste of time, and will fail if the upper limit is set much higher than 20 because of the limitations of standard integer math (say 100 instead of 20 -- although in that case even if you were working with very fast arbitrary-precision integer math, iteration would still be impractical because it would be so slow). In Perl -- and I'm not claiming that this is the fastest way to do this:

    my( @primes, %powers );
    for ( $i = 2; $i <= 20; $i++ )
    {
        my( $prime, $j ) = ( 1, $i );
        foreach my $x ( @primes )
        {
            my $power = 0;
            while ( ( $j % $x ) == 0 )
            {
                $power++;
                $j /= $x;
                $prime = 0;
            }
            if ( $power > $powers{ $x } )
            {
                $powers{ $x } = $power;
            }
        }
        if ( $prime )
        {
            push( @primes, $i );
            $powers{ $i } = 1;
        }
    }
    my $out = 1;
    foreach my $x ( @primes )
    {
        $out *= ( $x ** $powers{ $x } );
    }
    print $out;
    

    ...Of course, in a standard Perl install, Math::BigInt will be present, and the interviewee can just write:

    use Math::BigInt;
    print 'You didn\'t say I couldn\'t use existing libraries, and you let me use Perl, so my answer is ' . ( Math::BigInt::blcm( 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ) )->bstr();


  • "His code for calculating the Fibonnaci sequence didn't work either - it printed '2' 40,000,000 times"

     Ha ha ha ha ha ha ha ha ha! Oh wow.



  • He had a 'for' loop that looped 40,000,000 times to calculate the sequence and store it in an array. The code inside the loop didn't actually work (hence the repetition of 2's), but I think his intention was to calculate the first 40,000,000 terms of the Fibonacci sequence and then locate the required terms (the task was to create a function that would take 2 args and find the terms of the fibonacci sequence across those terms - so for ex, fibonacci(2,5) should give "1,2,3,5").



  • @cablecar said:

    Here's another one he did for me from Euler:

    What is the largest prime factor of the number 600851475143?

    echo(end(preg_split('/\s+/', trim(factor 600851475143))) . "\n");


    Returns instantly, and that's with the fairly naive algorithm GNU factor uses.



  • this is my javascript solution.

    I had a more 'elegant' solution with a closure to check the numbers 2..maxFactor but I wanted to condense it

    function findProduct( maxFactor )
    {
        for ( var n = maxFactor; ; n += maxFactor )
            for ( var i = 2; i <= maxFactor; i++ )
                if ( n % i > 0 ) break;
                else if ( i == maxFactor ) return n;
    }
    
    print( findProduct( 20 ));
    


  • @morbiuswilters said:

    @mann_jess said:

    To be honest, after thinking about it I think the only real issue is the for loop.

    Are you fucking serious?  The real issue is that the guy doesn't even understand basic math, let alone basic coding.  Here's the right solution, lazily done:

    You think that, for a programming position, not knowing a basic programming concept is less serious than not knowing basic math? He's a programmer. I'd say programming is more important. He can't use a for loop! What kind of senior programmer of 10 years doesn't know how to use "for"?

    The slipups with including unnecessary factors is an optimization issue which has no impact on the resulting answer. 

    BTW, is *your* answer serious? Yours has problems of its own. At least his is cross-platform, even if messy.

    @The Vicar said:

    Since he starts off by making $num a multiple of 20, it's already guaranteed to be divisible by 2, 4, 5, and 10, so he skipped those tests.

    You're probably right. He figured that out for 20 and then didn't think about doing it for the rest. All the more reason it could have been a slipup (if we were to ignore his "while" statement, of course).



  • @mann_jess said:

    You think that, for a programming position, not knowing a basic programming concept is less serious than not knowing basic math? He's a programmer. I'd say programming is more important. He can't use a for loop! What kind of senior programmer of 10 years doesn't know how to use "for"?

    You said the only real issue is the for loop.   Not even close.  And yes, I think not knowing 5th-grade math is pretty pitiful.  The for loop is stupid as well, but it could have been an honest slip-up.  The methodology itself is dozens of lines of completely brain-dead code.

     

    @mann_jess said:

    The slipups with including unnecessary factors is an optimization issue which has no impact on the resulting answer. 

    Sure, it's just that he's looping through every fucking number and testing it against hard-coded values, which shows an extreme lack of comprehension.

     

    @mann_jess said:

    BTW, is *your* answer serious? Yours has problems of its own. At least his is cross-platform, even if messy.

    Of course my answer is serious.  What the hell is wrong with it?  It actually answers the problem correctly, shows an understanding of the point of the exercise, is a hell of a lot faster and more generic than his solution and doesn't waste time on redundant bullshit, like writing a factorization function.



  • @morbiuswilters said:

    You said the only real issue is the for loop.   Not even close.  And yes, I think not knowing 5th-grade math is pretty pitiful. 

    No, I said it's the only real issue within the context of an interview question, and without other context. People freeze up in interviews; That's to be expected. Plus, I explained it might have been his intention to show the concept, rather than the application of the concept. He also might have been ~really~ pressed for time. Who knows? The for loop, however, is undeniably idiotic, regardless of context.

    And he showed knowledge of the math concept by eliminating 2, 4, 5 and 10. Including the rest is sloppiness, not idiocy. Including $num = $i*20 in the loop very clearly shows he has no idea how to use "for". There's no excuse. That's ignorance, showing he's not a junior programmer, much less senior.

    @morbiuswilters said:

    Of course my answer is serious.  What the hell is wrong with it? 

    1) It only works on a specific platform. It's complete garbage elsewhere.
    2) It raises 234 lines of notices for its intended purpose
    3) Despite his being junk, it's much more intuitive than yours, which says quite a bit.

    Yea, yours is faster. Good job. You beat up the pre-entry level php hacker. You should feel proud.



  • When I saw the title of this post I thought "Uh oh, here come a bunch of people that don't know how to calculate the LCM". I am proud to say that my expectations were completely smashed.



  • @mann_jess said:

    No, I said it's the only real issue within the context of an interview question, and without other context. People freeze up in interviews; That's to be expected. Plus, I explained it might have been his intention to show the concept, rather than the application of the concept. He also might have been ~really~ pressed for time. Who knows? The for loop, however, is undeniably idiotic, regardless of context.

    And he showed knowledge of the math concept by eliminating 2, 4, 5 and 10. Including the rest is sloppiness, not idiocy. Including $num = $i*20 in the loop very clearly shows he has no idea how to use "for". There's no excuse. That's ignorance, showing he's not a junior programmer, much less senior.

    I'm not disputing the he doesn't know how to use a for loop, but that's a minor point compared to the fact that everything else about his solution is retarded.  It does not work in the generic case and he hard-codes every value.  If he truly understood what he was doing, he never would have written a bunch of modulus checks while checking every single multiple of twenty until he found an answer.  And don't give me the "pressed for time" bullshit -- his answer would have taken a lot longer to fumble through than my one-minute quick-and-dirty.

     

    @mann_jess said:

    1) It only works on a specific platform. It's complete garbage elsewhere.

    There was no requirement it had to run on a particular platform and since the point is to illustrate knowledge of the mathematical concept, there is no point in senselessly writing a function to factor a number.  Of course, if this was given as a requirement then it should be followed, but obviously the point here was to demonstrate problem-solving methodology and familiarity with the problem domain.  Also, any solution will only work on a platform that runs PHP.  Gasp!  The horror!

     

    @mann_jess said:

    2) It raises 234 lines of notices for its intended purpose

    Then either turn off notices or wrap the appropriate lines in isset() checks.  Since executing without notices was not given as a requirement, I didn't bother writing the isset() code.  That is because, unlike yourself, I am capable of realizing the point of this exercise and demonstrating this knowledge efficiently.  Oftentimes, these kinds of questions just use pseudo-code for the answer.  Still, I always turn off notices because they are not errors and I find them pointless and annoying .  Additionally, I would not be too keen on working for a company that blindly followed a "no notices" policy as it is surely a major WTF factory staffed by mindless standards Nazis.

     

    @mann_jess said:

    3) Despite his being junk, it's much more intuitive than yours, which says quite a bit.

    Mine is a generic solution, for one.  I suppose it could have better-named variables, but since the interviewer is looking for familiarity with the concept it's not like they should be surprised by what is pretty much the only correct answer.  Also, this isn't really the type of function anyone would write outside of a hypothetical situation.

     

    @mann_jess said:

    Yea, yours is faster. Good job. You beat up the pre-entry level php hacker. You should feel proud.

    I think you are just angry because you didn't know the answer either and you piped up with commentary that essentially supported the original approach.  I called you on it and made you look like the idiot you so clearly are.  Instead of backing down, though, you came up with this childish defense and continue to act as if you have a clue what the adults are talking about.  Please, recant now and bite your tongue for the rest of this thread so it doesn't turn into a fucking flamewar and get locked, ruining the fun for everyone else.



  • @Howi said:

    this is my javascript solution.

    Looks nice. Doesn't really work, though.



  • @morbiuswilters said:

    Are you fucking serious?  The real issue is that the guy doesn't even understand basic math, let alone basic coding.  Here's the right solution, lazily done: 

    For the generic case, it's still not optimal. Because finding the factors for all numbers 2..n is not necessary. And, with greater n, becomes expensive.

    Pseudocode for a faster approach:

    number smallestnumberexample(number n) {
    number result = 1;
    for (number i=2; i<=n; i++) {
    if (isprime(i)) {
    number f = trunc(log(i,n));
    result *= exp(i, f);
    }
    }
    }

    where

    isprime() is a prime test (for large numbers, prime testing is much faster than actually finding the prime factors)

    trunc(x) finds the largest integer smaller than x

    log(i,n) is the logarithm of n base ib



  • @morbiuswilters said:

    I'm not disputing the he doesn't know how to use a for loop, but that's a minor point compared to the fact that everything else about his solution is retarded.

    That's like saying that him not knowing the semantics of the language he supposedly devoted 10 years to is minor in comparison to having little knowledge of theoretical physics, an area completely outside the scope of the question. Yes, there are tons of issues with what he posted. Were this production code, those would be massive problems... but this is an interview question. It's intended to guage the candidates knowledge of programming primarily. His lack of knowledge of a for loop is as telling as you're going to get.

    @morbiuswilters said:

    his answer would have taken a lot longer to fumble through than my one-minute quick-and-dirty.

    His solution is braindead... you've said this yourself. Why would implementing what amounts to 3 lines of "braindead" code take "a lot longer to fumble through" than an actual, optimized, 30(?) line function? His is the most straighforward approach... it even runs in the same method the question is worded. 

    @morbiuswilters said:

    There was no requirement it had to run on a particular platform

    That's a really idiodic argument. There's no requirements on how much time the solution should take, or how general it should be either, but you seem to find those important. If the platform isn't specified, it matters more, not less. Your code is useless on many environments which are very common. His, on the other hand, works exactly as intended. You called him out as an idiot, and then broke the code in your improvement.

    @morbiuswilters said:

    and since the point is to illustrate knowledge of the mathematical concept

    It's an interview question for a programming position. Somehow I'm guessing the programming has something to do with it.

    @morbiuswilters said:

    Also, any solution will only work on a platform that runs PHP.

    Yea... and any program is going to take some time to complete, so optimization is never important either. Or, you could just submit an answer of a single function call, and say it requires the correct library be installed to work.

    @morbiuswilters said:

    Additionally, I would not be too keen on working for a company that blindly followed a "no notices" policy

    That's your perrogative, but they are implemented in the language for a reason, and they are useful, in the same way IDEs can be awesome tools, and debuggers help save a lot of time when working through problems. I would not be too keen on working with anyone who blindly ignored any coding standards he didn't personally like, even when walking into a new environment looking to work on a new team.

    @morbiuswilters said:

    Also, this isn't really the type of function anyone would write outside of a hypothetical situation.

    Sure, but when I said that it was an interview question, not code pulled from production, you still seemed pretty insistent on how it not being optimized is a major problem showing this guy is a moron. Now, when your code is shown to have problems, that doesn't apply?

    @morbiuswilters said:

    I think you are just angry because you didn't know the answer either and you piped up with commentary that essentially supported the original approach.

    That's a pretty broad assumption given that I never provided an answer... and entirely wrong considering the first thing I said was that the posted code is idiotic on numerous levels.

    Besides which, I'm not particularly angry about this. That would be a little silly. TBH, I think it's funny how superior you're playing yourself off to be, in comparison to an entry-level php hacker who can't even find himself a job. I've read your stuff elsewhere. You're better than that... and I mean all of that in the best way possible. I'm just getting a bit of amusement out of how you're playing off something so trivial as an ego boost.



  • #!/usr/bin/perl
    $max = 20*19*18*17*16*15*14*13*12*11;
    print "Max: $max\n";
    $starttime = time();
    LOOP: while($i+=20)
    {
      for(11..19)
      {
        next LOOP if($i%$_);
      }
      print "Min: $i\nRunning time: ".(time()-$starttime)." seconds\n";
      exit(0);
    }

     End result:

    ~$ ./asd.pl
    Max: 670442572800
    Min: 232792560
    Running time: 6 seconds

     I'm lazy, so yes, I most definitely would have done it like this. Surprise surprise, I used in it a for loop with a 'step 1'. You know why? It's easy, readable and reliable. 6 seconds run-time? Boo-hoo. The only optimization you really need is the +=20. Seriously. Well, stripping the 'interesting' moduli to 11..19 helps but isn't necessary.

     Personally I don't think much of problems like this, especially if what you're looking for is magic with prime numbers. I can honestly say that in our product group we do not have a single application of prime numbers (well, I haven't read through all of the 10 million lines of code, but I'm pretty sure ;) ).  Last time I used prime numbers was years back in high school. Oh, once after that when I had to talk a friend out of storing flags with primes ("Use binary!" "No, primes!"). After that I've run into primes in programming solutions and through my spouse (who's currently teaching high school math and finishing some uni courses). In general, my familiarity with primes ends with "what, 1 isn't a prime?" If I really need a prime solution (pun intended), I'll use my advanced google skills and find a nice formula which I'll test and then apply.

    I'd be interested in hearing the rest of the 20 questions, and how many of those involved prime numbers. And, of course, what applications prime numbers have in the position he was being interviewed.



  •  Simplest solution I could come up with... (using the power of lisp number types)

    (defun find-seq-lcd (start end)
        (loop for m from start to end with r = 0
            do (setf r (+ r (/ 1 m)))
            finally (return (denominator r))))


    Examples:

     

    [14]> (find-seq-lcd 1 5)
    60
    [15]> (find-seq-lcd 4 5)
    20
    [16]> (find-seq-lcd 4 7)
    420
    [17]> (find-seq-lcd 1 10)
    2520
    [18]> (find-seq-lcd 1 20)
    15519504

     


  • @seconddevil said:

    [14]> (find-seq-lcd 1 5)
    60
    [15]> (find-seq-lcd 4 5)
    20
    [16]> (find-seq-lcd 4 7)
    420
    [17]> (find-seq-lcd 1 10)
    2520
    [18]> (find-seq-lcd 1 20)
    15519504

     

     

    Um... are you missing something? 1..10 seems to be right, but something ending with a '4' doesn't seem to be divisible by 20 to me...

     



  • @ammoQ said:

    For the generic case, it's still not optimal.

    What part of "lazily done" did you not understand?  Of course my approach isn't optimal, I wrote it in less than a minute and I simply called out to the factor binary for the actual maths.  Your point about larger numbers is pretty arbitrary as well, since this is PHP and it natively only handles signed 32-bit ints.  Oh, and it's great to be lectured on optimization by a guy who checks "isprime()" for every single number instead skipping all the even numbers.  Lame.



  • @mann_jess said:

    His solution is braindead... you've said this yourself. Why would implementing what amounts to 3 lines of "braindead" code take "a lot longer to fumble through" than an actual, optimized, 30(?) line function? His is the most straighforward approach... it even runs in the same method the question is worded.

    Because he actually wrote out every fucking modulus.  Are you blind or something?  Mine took less than a minute to throw together.

     

    @mann_jess said:

    That's a really idiodic argument. There's no requirements on how much time the solution should take, or how general it should be either, but you seem to find those important. If the platform isn't specified, it matters more, not less. Your code is useless on many environments which are very common. His, on the other hand, works exactly as intended. You called him out as an idiot, and then broke the code in your improvement.

    So when given a hypothetical interview question meant to demonstrate mathematical skill and the approach to problem-solving, you think using a common but not-universal binary is much worse than showing a complete lack of comprehension of the topic and of concepts like generalization and optimization?  Alrighty.  Would you mind giving us your real name so everyone on this forum can avoid ever hiring you, consulting you for advice or associating with you in any way?

     

    @mann_jess said:

    @morbiuswilters said:
    Also, any solution will only work on a platform that runs PHP.

    Yea... and any program is going to take some time to complete, so optimization is never important either. Or, you could just submit an answer of a single function call, and say it requires the correct library be installed to work.

    My comment had nothing to do with execution time.  It was clearly directed at your whining about me using the factor binary.  Oh noes!   There's a difference between referencing an assumed function -- like a primality test or a factoring program -- and just avoiding the entire question.  Obviously anyone who turned in a blank answer is a no-go and a smartass to boot.  If you need to eliminate all external libraries because you cannot distinguish between a candidate who relies on external functionality for extremely simple pieces that there is no point in re-writing and a candidate that turns in a joke, then that is your problem.  If asked, I could have written my own factor function but it just seems pointless.  And if the interviewer disqualified me for using the factor binary, I'd be quite glad as obviously the place is run by morons such as yourself.

     

    @mann_jess said:

    That's your perrogative, but they are implemented in the language for a reason, and they are useful, in the same way IDEs can be awesome tools, and debuggers help save a lot of time when working through problems. I would not be too keen on working with anyone who blindly ignored any coding standards he didn't personally like, even when walking into a new environment looking to work on a new team.

    No, they are useless.  The isset() nonsense destroys the simplicity and ease of PHP's arrays for no good reason.  There are a few notices that are probably useful, but they get drowned out by all the bullshit notices, so I always turn them off.  If someone isn't smart enough to see that a dynamic scripting language should not have all of this gnat's ass checking then I would not want to work with them.  These are the same people who write PHP as if it were Java and keep trying to turn PHP into Java.

     

    @mann_jess said:

    Sure, but when I said that it was an interview question, not code pulled from production, you still seemed pretty insistent on how it not being optimized is a major problem showing this guy is a moron. Now, when your code is shown to have problems, that doesn't apply?

    His solution is so ridiculously slow and retarded and it completely misses the point of the exercise, not to mention fundamental programming concepts like generalization and optimization which are far more important than some bungled for loop.

     

    @mann_jess said:

    That's a pretty broad assumption given that I never provided an answer... and entirely wrong considering the first thing I said was that the posted code is idiotic on numerous levels.

    Sure it's a broad assumption, but you're the one who started lobbing all kinds of silly assumptions at me.  Maybe you did know, but a statement like "the only real problem is the for loop" is disturbing to me.   If I was a developer sitting in on the interview and another developer looked at candidate code just like this and said the same thing, I would give a look so full of hatred that his face just might melt.

     

    @mann_jess said:

    TBH, I think it's funny how superior you're playing yourself off to be, in comparison to an entry-level php hacker who can't even find himself a job.

    That's kind of the point of this site.  We mock stupid people who should not be in the industry they are in.  Obviously the guy lied about his experience and tried to fudge the interview and in the process a beautiful baby WTF was born.  I'm not sure why you think I'm acting all that superior, either.  My solution was quick and dirty and I certainly am not pretending it was all that fantastic, but it was the right answer.  By most standards, ammoQ's later solution was better than mine.  The problem is that the candidate was clearly in way over his head and botched it badly.  That much should be obvious and pointing it out does not mean someone is angling for an ego boost.



  • @morbiuswilters said:

    Because he actually wrote out every fucking modulus.  Are you blind or something?  Mine took less than a minute to throw together.

    @morbiuswilters said:
    you think using a common but not-universal binary is much worse than showing a complete lack of comprehension of the topic and of concepts like generalization and optimization?
     
    You're totally missing the point. I'm not even completely sure you're trying to understand what I'm writing, so this is really getting nowhere.

    This guys code sucked. It sucked just about as badly as it could possibly suck. There are only a few things I could think of that could make it suck any more than it already does. It shows that he's sloppy and inexperienced, and very clearly not a professional programmer. Yet, you're competing with him. You're gloating that your code is better than some non-programmer. 

    You are a better programmer than he is, and probably will ever be. You are not on the same level. That a non-programmer would apply for a position with written questions, citing 10 years of experience, is amusing, but it happens every day. Once we get past that, from a non-programmer, sitting in a stressful interview, given a timed question, his code seems about right. It's a hack. It does the job, albeit sloppy and unoptimized. It's funny to read (and a good WTF), but at least it meets all the requirements and gets the job done.

    You, a professional programmer, took this guys code and transformed it into a platform specific function that dumps 250 lines of notices out every execution. The point is you're not equivalent to him. He doesn't know what he's doing, while you do... but even he managed to get that part right.



  • @mann_jess said:

    You're totally missing the point. I'm not even completely sure you're trying to understand what I'm writing, so this is really getting nowhere.

    I know exactly what you're saying, and you're just wrong.  I'm not gloating about anything.  His code is not "about right".  It's shitty and awful and you need to stop trying to make excuses for it.  Seriously, get over the platform-specific thing.  It's not part of the requirements and nobody gives a shit.  As I said, any interviewer who wouldn't accept it or at least ask me to write my own factoring function real quick just to "show you can do it" is a dumbass and I don't want to be there.  The notices are your fault for using moronic settings with PHP.  As I said, it's a lazily written script and I'm sure as fuck not going to do all the little checks to stop the notices.  I wouldn't do it with anything else I wrote, either, but for a function written in a forum editor in less than 60 seconds answering an interview question on a web forum for a job I could give a shit about, I'm really not going to bother with the isset() nonsense.  Either turn off notices or STFU, seriously.



  •  Morbius -- you are arguing about things he is not saying. He said the code is pure crap and "about right" for what he expects a non programmer to write:

    @mann_jess said:

    This guys code sucked. It sucked just about as badly as it could possibly suck. There are only a few things I could think of that could make it suck any more than it already does. It shows that he's sloppy and inexperienced, and very clearly not a professional programmer.


    Are you purposefully misinterpreting what he is writing, or just skimming his posts too quickly?  Where is he "making excuses for it?"



  • Ren, you kick ass. Most everyone else who provided samples here, of course, has issues.

    Note that the problem *may* actually make perfect sense. There are applications for primes; it's just that *most* of us don't deal with them. If the job was in a niche area where primes are important, it could be a very useful reference problem.

    (For what' it's worth, I'd have incremented by 180, and not included $max. And, I'd have made a couple of other minor changes that would've resulted in me getting a slightly wrong answer, because like many of the prior posters, I also suck - my code returned 116396280.)



  • @tgape said:

    Ren, you kick ass. Most everyone else who provided samples here, of course, has issues.

    What's wrong with ammoQ's 2nd example above?  Or mine, for that matter?

     

    @tgape said:

    Note that the problem *may* actually make perfect sense.

    It makes perfect fucking sense.  It's 3rd or 4th grade math.

     

    @tgape said:

    There are applications for primes; it's just that *most* of us don't deal with them. If the job was in a niche area where primes are important, it could be a very useful reference problem.

    There are plenty of uses for primality in computer science, but it's true that most business apps don't need that kind of functionality.  However, this is not a reference problem for anyone, it's just simple basic math that anyone with a high school diploma should know.



  • @The Vicar said:

    Since the factors start at 1, though, it's vastly, vastly more efficient to build a list of the necessary prime factors and create the result by multiplying through the list.
     

    So basically a generalized function of the pencil & paper solution, fed with a parameter of 20?



  • @Ren said:

    Personally I don't think much of problems like this, especially if what you're looking for is magic with prime numbers. I can honestly say that in our product group we do not have a single application of prime numbers [...]

    I'd be interested in hearing the rest of the 20 questions, and how many of those involved prime numbers. And, of course, what applications prime numbers have in the position he was being interviewed.

     

    Hear hear.

    What is it with interviewers and primes?



  • @wybl said:

    @Howi said:

    this is my javascript solution.

    Looks nice. Doesn't really work, though.

    Woops, you're right, the second half of one line and the first half of the next seemed to have been removed... I have no idea why but is still looked right at a glance lol

    function findProduct( maxFactor )
    {
        for ( var n = maxFactor; ; n += maxFactor )
            for ( var i = 2; i <= maxFactor; i++ )
                if ( n % i > 0 ) break;
                else if ( i == maxFactor ) return n;
    }
    
    print( findProduct( 20 ));
    

    print is just an alias for document.write :) and yeah, I don't really agree that it looks nice :) As I said I just felt like condensing it.



    UPDATE: GOD DAMN it removed a line again! I can see it in the edit window but not on the page!



    UPDATE 2: Fuck it, here's the unformated version:


    function findProduct( maxFactor )

    {

    for ( var n = maxFactor; ; n += maxFactor )

    for ( var i = 2; i <= maxFactor; i++ )

    if ( n % i > 0 ) break;

    else if ( i == maxFactor ) return n;

    }

    print( findProduct( 20 ));




    Moderator's note: Fixed the "<" signs for you. ammoQ



  • @morbiuswilters said:

    What part of "lazily done" did you not understand?


    You called it the "right solution". It isn't.

    Your point about larger numbers is pretty arbitrary as well, since this is PHP and it natively only handles signed 32-bit ints.

    Sure. The algorithm I presented is thought for a larger scale, to be implemented in a more suitable language. Given the limits of PHP, it's not very difficult to precompute the results up to the limit where the return value of the function cannot be expressed by a signed 32-bit int.
    Oh, and it's great to be lectured on optimization by a guy who checks "isprime()" for every single number instead skipping all the even numbers.

    I've deliberately left out that part to keep the pseudocode short. In terms of O() notation, it's meaningless anyway.


  •  @Ren said:

    @seconddevil said:

    [14]> (find-seq-lcd 1 5)
    60
    [15]> (find-seq-lcd 4 5)
    20
    [16]> (find-seq-lcd 4 7)
    420
    [17]> (find-seq-lcd 1 10)
    2520
    [18]> (find-seq-lcd 1 20)
    15519504

     

     

    Um... are you missing something? 1..10 seems to be right, but something ending with a '4' doesn't seem to be divisible by 20 to me...

     

    You are quite right. I re-wrote it using the built-in lcm and got the right answer (but thats cheating)...

    [mossda@localhost:~]$ cat test.lisp
    (defun find-seq-lcd (start end)
        (loop for m from start to end with r = 1
            do (setf r (lcm r m))
            finally (return r)))

    [mossda@localhost:~]$ clisp -q
    [1]> (load "test.lisp")
    ;; Loading file test.lisp ...
    ;; Loaded file test.lisp
    T
    [2]> (find-seq-lcd 1 20)
    232792560
    [3]> (find-seq-lcd 1 10)
    2520
    [4]> (time (find-seq-lcd 1 20000))
    Real time: 1.609 sec.
    Run time: 1.61 sec.
    Space: 68659024 Bytes
    GC: 126, GC time: 1.206 sec.
    487932562728827051853192251818304... (this goes on several thousand digits)... 7411295098112000000
    [5]>




  • @ammoQ said:

    In terms of O() notation, it's meaningless anyway.
    Man, it'd be sweet if life worked like Big-O.  If you drive n miles at 60 miles an hour, it'll take n/60 hours.  If you drive 120 miles an hour, it'll take n/120 hours.  So, to summarize, it always takes n hours to drive n miles.



  • @ammoQ said:

    You called it the "right solution". It isn't.

    Sure it is.  My approach was more simplistic than yours, but I was partially trying to illustrate how simple this should be to anyone with a 4th grade education and I partially didn't give enough of a shit to do more than the bare minimum.

     

    @ammoQ said:

    Sure. The algorithm I presented is thought for a larger scale, to be implemented in a more suitable language. Given the limits of PHP, it's not very difficult to precompute the results up to the limit where the return value of the function cannot be expressed by a signed 32-bit int.

    Once again, the point is to demonstrate familiarity with the concept.  Yours did that quite well, as did mine.  The interviewer asked for it to be writen in PHP which was a requirement.  If you ignore that, you might as well have written it in ASM for the sake of optimization.

     

    @ammoQ said:

    I've deliberately left out that part to keep the pseudocode short. In terms of O() notation, it's meaningless anyway.

    Obviously.  I was just pointing out that your little "not completely optimized" comment wasn't correct about your own code, either, and that your nit-picking was pointless. 



  • Okay, I had a "duh" moment. Here's a more general solution using number theory, again in Perl:

    print lcm( 1..20 ) . "\n";
    
    sub lcm
    {
    	if ( ( scalar @_ ) == 0 )
    	{
    		return 0;
    	}
    	elsif ( ( scalar @_ ) == 1 )
    	{
    		return int( shift( ) );
    	}
    	else
    	{
    		my $a = int( shift( ) );
    		while ( scalar @_)
    		{
    			my $b = int( shift( ) );
    			my( $c, $d ) = ( $b, $a );
    			while ( $c > 1 )
    			{
    				( $c, $d ) = ( $d % $c, $c );
    			}
    			if ( $c == 0 )
    			{
    				$a = ( $b * $a ) / $d;
    			}
    			else
    			{
    				$a = ( $b * $a );
    			}
    		}
    		return $a;
    	}
    }

    An explanation:

    Using gcd(a,b) to mean "the greatest common divisor of a and b" and lcm(a,b) to mean "the least common multiple of a and b", it is fairly obvious (if you think about it) that:

    • lcm(a,b,c) = lcm(lcm(a,b),c)
    • lcm(a,b) = (a * b)/gcd(a,b)
    • if a % b = 0, then gcd(a,b) = b
    • if a % b = 1, then gcd(a,b) = 1
    • if gcd(a,b+ka) = x for some integer k, then gcd(a,b) = x
    • (and, trivially: lcm(a,b) = lcm(b,a), and gcd(a,b) = gcd(b,a).)

    So: given two integers a and b, we can directly calculate the least common multiple given the greatest common divisor. To find the least common divisor, we can just keep using modular arithmetic back and forth until the result is 0 (in which case the gcd is the modulus) or the result is 1 (in which case the gcd is 1). We can then do this process over and over again using every number in the list.

    The up side is that if the integers are arbitrary (say 123456789, 3457892345, and 7434 instead of the integers from 1 to 20) this is likely to be faster than looking for the prime factors.

    The down side is that if you use arbitrary-precision math, which is necessary for all but the smallest examples, this isn't much faster than the "find the prime factors" method on "integers from 1 to x", and might even be slower. I'm not bothering to test directly, but I suspect it may be marginally slower on the integers from 1 to 20. It's definitely slower on the integers from 1 to 100000 -- I tried the other algorithm on that case yesterday, just for grins, and it took ~5 minutes to spit out the list of prime factors and an "inf" as their product because the answer was too big for non-BigInt math (I'm not actually sure of the time because I switched it into the background and didn't see exactly when it finished). This method, in a version which uses Math::BigInt, seems to be slower, and is fairly pointless because Math::BigInt can (as I pointed out above) has a built-in procedure to do this, which is almost certainly faster than doing the calls manually.

    And if anyone is interested, the least common multiple of the integers from 1 to 100000 is (in one line, because it's 43453 digits long and when wrapped to the window width takes up 3 or 4 times as much vertical space in a window that fills a 1680 by 1050 screen than the entire rest of this post; if you actually care, look at the page source):

    695283836241707197000307586526418388339874291768035113536027537561504144217502123750625798682860204776361287769787645489273366008105870757535968316298519927347209547516689789186138157883056062709938348338270956051626062862418050487468112737231970593946909993998632095154576354703583591294006509140049222683856604706619543595539738978438402143818888509753615804927722779184258615850774595336527867683530147771511517004812429073661582449730940750881684470454082428780784796451406500566730458589565355624608452836674577364123506442443050384444950440591525653918188010327017919410649819332355233989875921895543234344756650897945336056048937263455478734947014964455332915278197351856425777694467952543534429814021764674841817817161841615468965733858490434493043049587815635728171520976388154083920645840383646197592999320498412533493933462231323522502253595236111647340227927290593902410439600751178904259123473863098682290495062334603653129364848319915760867976237629923761510079376685883657628176483037787875183127396254643067113182841283987928992241130413403614454974674479550648225442804389387651030795693118603838122235846136488158673376237619572764694464201691552662309365201096770815931063567208882210049569123207123501181530771069372829593616867255715894684389476472387451571753876847921309599044631299127208575674182311692313126883524414820245461199740107772781706777251206711938365819229725942752719680997884110757762965118646167092557560498081378211038335954175919076013330391034327615765605560609445394168200295549832518389657568041723508844664281122945475345177336844694244288930759822277072734904977452473983500729637225340547747136518100026931854109850944739609167758018592400599935626967631255594920161546189386008628013586072070212849531454804109603696846227313116395887829731466005434182275298064307682895830754156081351040357785559192928046033126005647075995166956520745296214045654304733333215884428392677585853875505289339481082827192972047587617232180330998995523723892511453567261695838123300795834091436300600984655272564566621836043862207179301199072159367205337601357634575317804741146350580066150962775402020085425021072135947923793580486522695421309008747928562439884232026857513567068286230821965660252871941991920120182534072329717562498396293800463821267586385689179335814400643809261463729053343592367592471407345268125388797630505815275778646969440520171561331285666196758419107485039496470620903410094289053875602470289179766046360465837588751842598402728465776590521960050511640747650105247956263408500660159529031715148068076489684916964744609811164322236311906488761072426620289373604127291977547542255224341182590028978979504306120656271511117687682561347267739742244861356517008168756805136890601189509382531188036444849627782142271444136184578208341772831985323982945983426707064018262493409027706644083604612638538444770553482864354857532175735901584469977954700864116870402944558282968388469597925326290569846134772175519994193017421262766852378807128654058511205505327616487504372461280833501328030139655859076825031527750879787650593811933666610372169608056343387183187463300531163009147256474192432496720618234706123466128181726122755793708242245637936679644556241489655726696944238718444076170670492219611699964779100011363000728502299733526093806871197434062940736515618126862199416658811119407438908278384060844018535334910915021102705339634799762923146856949792421423220577184579466344154564326083093506999739675587876288841525909576052001203813643104175050224398268367262315867195203388881669387973672301797492060650637576020785740374332392718196606186480131290392991597756415298082900612808007506833088014607803098186664144435765395702280653916630059322295414489926390811587985535129699320386240501950082260187407332044095433006071896107869853626368728219185793298416565590409621082439650280245296975757373226326892568011020137111161383639372716527929960483086716397904856190853783305856877994809428726957926684036774895820175327194747836934950428677816511211815209932168146607461920549171600768916832320557255287244720050090112002987105226460983278773594074515557421596583561236402717524039324421342151587657372339469306119044607823792729845531863033720837410650611522937887037689817151083661043414976439296049038703486603284891172245111125619551990542030023282464527748755099113225168910287844242571695230079944793220827727337650683267683703461457931193445885838725055304031068324200944573591990010463015851613991507105805164132882724538156095127080926290617976733134458892534584643294445082941400710020130181746010408634016978504878691727298059806128450751117218155602198372641819040267913685081000508928941423257419914312357288229875906626544013928354562665921092612647162554411428897939432539917951788672728696784270182259473457128597561895444789422482376921752620769781560655545128321263673742581579114846837218843909695315127264641175804666742804016336526951358270123585272729448402136256620143022837321319559849048205592768553345729988287307131737295854445640389305699157140483257355083759687952296382863169197626982213068286280693942741442852487916889918802011103414970938970378960702444939225002134922474657777602772956447341253211704803335769100327187557661938567653207365681647148627077184249044636427499113158646392975760279286905016928065743683662543411442990223796042060740065459137757675034698473107234720956636074588497302370085356420509810387547159208526826384578122969752401342095475632400485168606431430079052672808122457978424708555231890746850971139226971635456982512724600475056917102128704959747583697444216354272893414940971242150828839854894049484699352898147349866102672062279177786328044588350154233628633439278283864993321904463082062245683267100308284180406791690392040676575964967852154226857814126169153021908725728220470857569734517806606558688953565705780895504670849054977784193043318331804987404645677828145487521555026121721771963805692967727723270065787219047935618417430174899937683054131189730170655358370110056310834758410032928807905353434509613948594641476759314398743567763749354971597160037608658857945905154767395067009968282149723909972298114581272667668498519351610274350988822400153797602995636728509555823147124962638068520827331932390830421362721578629409584173951765577289849039920711414054427619562965709441222139795379235883011580763331382578803757768848294317638726621025292487502239996190182268209979972341892743745060294743187993787853011938685017770142879963749997496221787346192296625867358034046966231061735131882891696206915804243394215519249981170986062844340738122204690060562165670807477277124701948450121862324254566018413832550946654194979633891449956373513954408804002285259255869946461318808837843226719177725005584623008159766625694305683506582694915214588177038874526467287130207197676000651614977204894653678704047969151060532987853212238634393909336976281243691712759264633030206533256480966637185039764838474581876020947948659854160094618631681776204180745971084638504599834845077601007739853756263815889251339655474929492025640062041551309593461781378517038738843995800392675850652745272988225527496191092977066421188099853539467878709760203282481935154025282794571814746619303783653148775276401783647891806665839872426414898400944761602371235655036393078258212668992784101500820828833808937931279450542679153800667505804662157755429300595394168103682100256172377757850603956868118851509115472475095150725301373419829099900449180347385307403166104802070056810974866779882204719492543384175166595603766138169814585596198930771188815195406889509539127045670928914873445153281692111143022718215105481804081592034225972798218242526721928143169032869559174536144305350543057146065454479309901556038072642938321750176896318729793364527114684719573821361626844203464236945077908524787506487307018118760149029215050005439942575170465277534355817320689024474978831736199568100933487214469753588096903875691580944356935936253765560996344641697807495783966139277520941302173856523482471866689572630503918202477870053230184508268359967428105055235200677093198987040800966049099243978167926899744570228646517224553772011508080996769483524872795381365099980733696246336760347120728174260032370946990837662872921747190181836972776159929491422708793959611187322560677612601061052491550577519776015166148592112858773972581120562417543300461265851625037486142939895283417269595961801833905075931401625731180047160080862746428149703173636291937459186295947836988045439115277354245028305466335883064492585959477175816186236091627852320816219494931065149537299470210899780708977783823133625946656638116047276538786433667198191081105812577074275463900042176589145798085784894672688276017012908472571144264636241995873432851425850132528301074230655022602044548758942312513102773143874390672004800231948893301355106935164890005594487899522487115935041281188482389967128000191136955424753209385904670934763022789465107924446694028623076474228105621897571790288050981062876964044522630556636537219499366317454398298478750744673923709514528232372585321889051307798381788681175175144674416250431123164512302995590559625662032808383247493268940368949288913560293173641973477875658394732293054567211351603580472854559898852046354969746759522044548167812477374806023828408935400452424817780017423514605673509117494383425388195118979533009053406977409702617655220667639318196429963305131622427935175969993926416495319185287700560158832240043880325461227348199393985824251401395155252229350380912343049074902798601872081244824678440769086723896043948158539295096884692403769353016001183625943503187745218379464531308066597541597287674770509328263179255929821629278190540914120567007645068814358110945508737752278422327347191622755313473948443564529814184219848607718449837172214169347580252626396176767937125265209998158535426114706118096251790346193763856102877282572883840662028356822364862776781807635995985049520057741409124559548044385221440180864588483732912070267316654612368343624119475004654063266426875491918735351804762746187455354605497718485513930695909458730193731018886081242801496866295221061369687844969707975586532835588021940201328352736506852379940999449650917098824968858265516671042359813606142753496406759470021405308440681937981500097016375682481019724750495147057552135477877821586982501549461809755714082946422157944099080629464758279276314185738614989213409707454712095717786979829529943362566054257715335525419423793710541961753703400093946544038165344913761921283058785830499176775223631604316977971635363411071873470043972748626903693794436437492697029290377018388067109320655250073917429227073303433320923645349977212845187473642304066885958646424453433753372545670085437606051159766549101444387799953988786669291157072632993491981306173061443393902398714502127835861677974502242214659226089488100732005560654606888643718840365251636989700588862484147349379505760191889387764446888371722507543492366167063726639447541945108605206405050233887509419740735295163648089539319902262544218805585830280992147499650156048354752815966390433850617771588473748380231963657043879592734955020995065887907419223302561593735301716900680970377443489331444875655073255588806765941638581136076405079645532335756902221215790487826463019832104166118509481336095902514437070532611355703021039476776371087104727354403836363892632062355172727710565012081863832315654573301918269625190257376430682858975074765430219420990230205882439397112646783927131083487488712088811703192583874759442819045936506559246864165293410498576275478803253546426076815835996999149694990063765074850502521340199714367731514796890475114318082339847986786410994405840603272196378362464438785787407820828972060570064397810535350095650412236779205668358927270737855882902307805749723752130036895546440167014352210793186146230174060632789629778586940432623604846653783542840624563076775594290190053018466992969838270417996059073654825638483394534661354471738116485849180005550341860061457954238464447541676976432688974534445835678400223586030162262503966389008867734661861944652396148738140607505342809299084251135452792626551142341477906867058164323306734047460498770295503948405981243887458864933488994678951920703279220053019653332539001723008008268021167624721977286918785430755436690715626786933838323837402043546228321621914607592881064294544867687715509021245919857086268199095033833634865087853195566201104680003750444845870429373926727966781426088770464071816361654428328125007088047384304390017941364202879974825153846939900675933685729694856558164532196674449783034536916291328016150338105441548604900397770816773843846134771517461358516720341310797985451044915196812172201602742124081140227872950393187810257394710242368781528725519743103986119983167638041839393519320332454252451916623654420139728487658632501495121604002154916745906902873153087941302905752667373572486851454074689596288579933217135104623325258643302849023458470126521050119744597337878377020057443247503293725393170354416072891548314777585613068240224613318799047547369447476253273089526253155341905473586040654180389046131050270896000142718436048629917289115210034883503375251718687495184308152755752221542474217994533175181695373212235195435758555767593798218002793567207174760821814434369430272651620347212770648202708625902952522836868149748373456910716836860021859925227311405609907617196787445854970570872855745071816907435667718391817029984342617723540464040042176427208990016089505404758419922630017540302531409103942447395342480073495721629580733343252727817878787975949342036501260504635055104952126559969665329567881418913574721496000684040630678522619283974045121327731762450781941720596909131540684785162306342556425262951436859895152673294301611562051237535429016733012733963737477001027236140249547703033721485189960991759008300734937304220415078552062745120555923313008810810014322989567008745594888543030293061142515466385891575416648083631166331101774461488271396968659112376087106830481010905850680202907016741399608865196990847581938542042780972153163865176445582468989019112848269937337518585497953831386473450053339489829011277630664638661898705564144384938029250125019532227291062155804700533768682379209689308216461806403257933075466603521573143251761654220923777197449317049187967876239547493078165191788281525441790477039341434295181855787053714463909020490105487721287360630997660858412584335796411275807411113044774101776530426933559520858388113456529652381538492887194779317779110241410057096092408487371766436301740698399012412507360345164027722873148575437718697358343886978281712176321064550740675886408962030968710262035728907801532026686795468989777631290916627240790045700750816828608794076164263766864770796993800167806983936806066402035300219932981788525365250412827854602261756865064396169560139041326888665377194929979005950452587442954965729769807613821376480960748823076538276085362185435615217148451629508579627856993160205145441047995368430505801309397656758707804878733943943215742399710989941295214914375285165608726053891644342171598741040696014537339955431084844744176674809067760179863790213325440855384251638148899526690789556709377185469969172771743818828157135670428019275588821021066448685213662113434803681058395869963843504885004479576296070882444139272945605951954232319146270853695188022017549520006765298923786702441485390728623538179625892852066073358442504450947248741275472403900014784020784832665368177487582966695974815727541837701719563144174345198785007047781254062790090785894672314379611443994551563979221457064162420472188086659955990567364080723299317603966462598649622865959691067988790228819331019722514871272752724019834222880710640644388008245301379608408543745931826197391970679801722152694734405667805440253587033109783037900759738160763075308622827341308109773937184002669130927118445275270747806755877505722352754486511922486175602162566687252085322927874285844852201559785886528024081324995266653822994597224484665671859248735097683262280010588079578659831738448471171842453802345087695129695501101754485300863095888394647749387750830328995134288626975702723556438719076093653222900091524008837731687197160505450854204046149141325726289678672499641660462432279355265585207772131993527422270387276899131878537672150302813478431933991046624703639917626174775341885040264031081115997853009773640534975152847454808171391043285184969079233010648837567507237551187533953213270193343253646455858317764778475317088258618880252141526010708765850407080062722591129671100088998520559367900439366093575285877546959809324542289667857455471135800114558790117443286055508246143645618805486304117920332679966143730209998804698219370557163920398005745639582255886796792871964448324913579893136565237326240260493924359650934538341661610209753327026996299592742536677076681996451153488396893306721741240599453302567940243699203387687393606087167078407976719925878835949860690253494853879824837207924748840700792833990489051120330787757068134213586391993818783632108985305835070636969307302973199082209165279087125188180273258004148924391287166155571239651463697486558185916263916918483140201124257415426398237314663373175339220685254222178094350945357713665257283618100588316945403356967470119552599184754234968200860283467336388368386737473942973375875843358435281787191042511120818623932015190826759707095952829381347879767115681019096582681069234017480404062451314953927925715405410909200947417831771772957726590410883741754399948635463716084205098854759721052377533654156768026964842356480884428605147246626919442421526356395656590487508840298812136476797671578845187742804381804959757330737639651528047684361700935250904225182850137372958169610365704646470579484410848326050559194303363188374013321732657012004644159653980036623075384857932710405424984795573027039819118835204459348359648862378650696932247055952052056517743901856009556583625038872056511741975994932469653520310297592638562199263229581340515772219662217266346298083883846898336060101459363870342772878333146022959349908933568812466907612231395771541317973663406620679208909864428670876632891092296054844536920023415459560690182535264784516476546174597922951822475835877838213464032585594380010525207040363518424116516545566772129732177892748911134665165343442196528714559350585689445710622746240087402537998148191771137020854462155446519645971615981777241911494170519017296750159295460420602669026251788198729368639185503998822145397275820406227456171065213244082758438508116272273217108556725990319551146546569224810678238893675736906091493679932556721030620351429281848998282717857908518433266040917220399623147954558034904355983313427934959440032851616782429945980238596490994929018057733509176901585667603599837271566977706328724362846237020750101329254978269430651404145686375440427692179715751295158512102079048420665073914419402983527932706812063058679372561392503374319467320040496687746674572537790906807378881639526477986087921249328197726906474433645466956171691048140224291947034774607596563590979361239564809565689844197955876219157514984845211920754929145660497597056219615008194670883071925989444815402754551739867432864575854743711142613789995304716503136414180095114654055969969625657076743826064396752965293458169105044797118861778649070125161978688320230070542783354636832774621368567251502659365158629540817653798698806196275823831228396147989983543397400402938351172044367278639558130073276936813724615602324937085894038563453910853246531005164715821440946323290632666102064560016357442772262459626368210677373366047284818289919594466904628147676010538484360725428227022854110220910707547145928049109604586423849326694787543599739158267422373505998256494928994089265754297379192135091814702549126486011370557228951283205884336138896090527444623669208004073256539352472515044866303712906794670363283774034834330554210008992395514727509194198313119552690444770583034433170217889801894510048899783145112824313365853946764689736843055450073101189441312790351590709566306224270700781550212381493788524698104708858111274563423939321161491906214667733248219006346373004792564532431624834293704377298105605503332392308922565956465657947208291254511037843267696250594254711061383604056690007436316656929908439581659662540669889990260876907132811871717560808343836973172179605211489282561647087007077659468375586128466166600547256170272423969881894380300391913077297608012763453394925862276731542650194823787851840955115230093975231235809671028401955889191780971565459723453602956086037329577659118309195491322988758761795414186939912865112120215709124308025873775081511476561414208386706996324267134268635754776031760247853743223108062302699485791185724873809538566851484047108020217211588860982330142974771066779499203713055607226400486484177807136652518335990534753939169577250819112320978166191214040623743753433169754210016983659190416117352105439057111413728519122338293745415193725671284735372673724903627368909408037368487907988684299241914870768448908166980258315603348721527480222829523818536731734911161552411853658833823491176216695779739031719196783633741666089771693931305209066129036949800734919551139850178756277595299697428614194333620978496844261804097074322118920217033265613155751401856655057485020828702472956954117200419355194793587348665304829444976546046325548091709552999193105418631734298512320768558892970736201835980749889059717612895297300531121228508286467690184386720206956817576887484749988440602995210294267906409727528676077626798800475171239369053733635493216586263997939934359798037583789723742940921746258399645093372146429599507937429121161109386461862518479730492884916736459404022395524677337439390924591106071350723736195210257192980963898593622771400096005443376844367549077533216116009757089930756927221392819032128511742171093614137746217080834143953903359460226155823538732419357585881508632227858562924694575822239126830843690823902369594655011090783595159170087080919544343864858593089023939358967623148085751082677274508381970396946328247524623234564477235121352283179985745426276626536003991523029753895328360793757597976766873317818723524126284665333559430718577486849629547133943556233171807639495511833797799905457325200924971103929012986565710556291113300865645278133391288093247210109592151775207344417172767038009551281541500240419643480063821532436113422674254506740549415737198552575214199466599231396665492642412489277040495484088760988672802406146468118179619040706094751146650204563762549313376913461360522573825654055714448407380198696674663061985741606661210135270731777455957105244749645858927850886392036550451784514346767739080374499134372676739839595493199136800680323418567054974273809776617535506264229345134454993982966062178773666655927492286372960449318049932256515173554196472699960280477900186598049061162170090387032040488072511342646743780848279785019577111987701868952730282706529547795201779272669688541468295069369339096808131778221832269937090485957297171014447935641935730678543909549896937534928050022866644066879508047211363771274519404167515536528876216147164053969804582777711554473912371330014642409434229942679910925471280767977786034269460639663331933246836998582623542068615018982783444137971712272105939181526111458174045713934174848116119213406521250957482711759979635569454497729299981608373935474476850518350855852315358306251478764607659331647259114987588410147849753921451129614725287953695598921439262565647146373804155514167157220732431724127712734925869374344047417179685419693921719970233446618582684748050235295680311115452394482502286401722960561305451864395090697310293243605776381337214453428399004606569563196365614280075786940069347400496999634488980954603280303746401507676990141183224563277131661746008880243209040293131523413837110979622920164171270464667137226400016722827264727232405998115090576629445860039880071315886572910714986572600601081204134189898961626457668445490639926148769653311544353574807558765496751824725212014654834945376776808342374304921260887364139503998729181135545350923682894054476956982125412149000590004692131869349891298665456468242082895476076517595399733133099892710313775258920722635814917124776967097072087190182989212644326602669445495556487006108141126249232358975083002594690551285534720162915804246178673816878708640417954654126598777276800854486847898905565404234171555985881441208557274821182646073686942988081328364638802053684143680082755450217571193024196797664539533122512156627923447953842858259812797592997690301596677067838340495278566009262282302375865049370850894875224897541143129431172986984620367588058693550472512375014285862963909808742969725004107566616620309345376105956511871045685775289115299307561313119529772672843677828907892238418321725890164031643702093570282607309462329592900984008720350930993246016648387996924830346879119153675582099786357290102938830003767046118154342545178567309104132508355229232973665328930166459263273315991282542323080102838901772999736067542559639715354155168540503995708124241698347041171483210164857493709602114842986566561011735083866023642286230064914057732762872489058118322911285707873686159718864027021646290641581222315474764391030909840398160603258648967759296165055290998209615210553625726777784504673875806520631442445173750349606664024188379672321402416374289162778708703535787926924888825449524617869668765132446901802794485014454372923283451728387310336459795690531802032714254785331271614707847623477280564146725154762194324251017235785314923194242665992050658889369589969159823851934813910405081166386288359207802404860144984628294498892801404867251539295617780539213586229378092378433987524442863225864416974577951900797420803328397301327798273630454120611805441089929381666133313045816038798386865234466142472667322691127854766127616343590323287199952143510872085484443706710066069076244052611778180935251714113875906395998524440071330299799753386321960294402606575362001256032585187612944338830147838197422722518904818886807198600027026044884025290572550928941654345354955195427208859506198109965192797861771902585668801002229846151761388544357462953888996141866404926735492246903538398837270262606809279695169708284705602075547160568980349761659509619718226433090212730501560045368573500779298879170693434445268594975330708648625906148051198325557441214548093572575263464001076830137015593644798293447729668824337898234975128084456841622581175010773359647539829916791075307809380656814441288797305713019663877843488356892100269750893431250063832743444841912644686075011090719194492191100521731505150084928790412847843084819816323971170421946658020055678834187618879600144357870214297980220688883457679344138720375251276402018495016993714313175309086511804680847922133337410352979354846229619481235168591950798425999526243800137862740896945081973132452819570371346938053496312777717738794824566692154498972725997945886662177030927327197018795966525450071317233624105654512207954576936989798105685645349589461423834532395607075581304149051880195953672097914599166138867496698954697696200507197580649371867594636274512512498925466022232431540144408588402774947617508237750149803635913225104298190216642203769709165381156240959231332934202320732374705605818443625363724642645603767786784467316875065153084225115935675364693956326821643799616727448172953787612065350579352437526121319813212822876515761975282129249825817756817922580330912675494957815590637157647487589349716936828515214499095420210151598055909037373206677517035782671967361937145474588055948955609916839535685211309034331233187937837399945404705405389535996857919838479964406063749150198110618780579112515809776422948893386027507062142729104266836826423135363372984050898200494734197247026234909088938436234787050590293121333886602172226363186673477629581140905830742073851563286806472807409755050835364102305205516288691778862576137065027987625430033653158472213128186850469783372602272733003944677958535317865067436660946136220522278231553288894013705241812598087983076609773617460358395389865020476372084639930713058777683249710746438311336056855631913171821450254619830528266949221391256588920277798890059486347529972845228824955716810043182633264293715117625279744375221763203127627014292041638330980871011394654626270102843285445830345927591056060390861259821120831606402832362551027305594476038044059035821721542121791527685602434114874683284574660504459640882157426167304893516144613647100981430457920088223944409042859820449660541558661443110679696230590671105597702880333339134187396539149995234216710127585656716137208108352355480155210269212663145585628635536400496159081103155404815213194456416332029753103842057121377983915926713441079026954380627952077499061713667319449572264440773383987585609003491550642799720497474945936789378661322825002480250957730105725099148448315262956497129094657308507677867566029015540492373607017101716939864011987550852417251245078490507900768724606888058652654964598932990765141924011787981933205995081148900324345898172906334651619065044573265404685655051132466820735299077792473163523376073223050412450262213460222987849479692865419904976961016662922496670296101651467337063593083133837001921462755596425760688762985672242527563216076981280050780891676756636833900503106643866662913791699671946337073415260831443421315723382920381759605365133978729516083400215048711886508809771263165324181191119584427381502497796745896408098819816875825968683266918652904131289788427137768566720846037512999299315776488461018778801022333102672439677841772285416432847743959616505372182783195379381138863210658341767042118638113496147139460950775730541466459469614722586181186834573899050373707553913168280999404489889959473058760589334813955151296635990557824608255914929816843914191930167827785267232809245499408233555860588400739905992416229453147471988252507539117780830548454153201330825248771004528095137590863655279155178727940612511590602964599288073320471890999310434813081019724606165927539554606194178560810833833657847976891762181875727962506761490316428455793203539690189193658132267663833067225618374712870322649877083628375099087042372645987555382696943888318039220474658322591779927231062436248861950044722471929989202137712280238638296640685519561670212133109282807974773926276792365990414623362027930715383009527847048449486765609578722697291062087338077191338253058684074745926427622335124090364531041433104218075202358158447979385739344561971345472381423994112834169924624975074716546531438694847379827072776661195478201343978936861793133666637490235661396198859294862754848781790355291773591466631076756044767536957717047585287118960399892607594082198028357582460549296584977979116596705446615193926067008215029984627518589077355326037121200014347941609693240109168653013844160111283754065593680942153134715922741646964147116616467210134576112596778551716742180873557217473872574154236426986636819617823998580939860116303102994123769053182737049677506414713846558918484605770486262082417838399522988714402823490453478786754967000346591850322569242455766920138548010450111612070042254636029724543384966432382017547378709594789749113963095145126052280384010685695616350032083673603591779783963043400327320998257259058385740952257087064493105999968153922719584894751550758294397097826996174348316470225240521762853240084959315097267555560064019115669651132531917030985903439929747844639396739690879207749082409847991430028359398358082791856812036864238040512452566220986194554017760668613831842682407691226980266180275726307931685636533161006049352197605352210051030458684118593992251445679716367237525622403217385707682378883955889372313489034335242729397139004693584031631354111179972422805380861847378798875625857252817610471619388508628910501976567839603244056517808384830139354219598765060129433414377594482112681117637926408103183721858056453805544494382472485338052982902162326354940451186022068753535018638094691002537145226410581898453206708239273267566178841554060698657723379209287677753996684373239696131944776011258793634952493326673022620398435933177500268315853783742317645121339056209563756907993443730310378511210259840261035182285513159364947912074205346037457320090876547588411664573986983723167575258846665314330098443594661484450400130381723568684697345935257904574040960263547184664497536470426745160014407976424103852208410019396463842638585666742660622037343693145864934544126264426844807712597957727803486717524576619417206130494947632284413583128180244260481557885374911248244301961909202693701146133793175424021502003728056197665693986649530840836847640128031742523757464510877566612455819182699582096249248518850118109235132294658821746092511923114546770426011134283607570839992612325704703560259682714936704095150185383335556490905731729458153583935702800556479259116185021772901505348854619112399952069192117913529900997612938927576508601728143621438202697141800679833209367602043054313430599851226313531426864118855284176830447524691696315295384333984815213227487829447744186520430532405349149709746225995622649462246812441515593088736877740341204909850005075230523372636756300455806139990080096779965306111903919424482659876588448364028365524808722775882414277067013268353499708407688935240658313519423995644367364540041645507761175694720584367950076315202963057020213418013704595153193840272460823352281219694422199698285480130582001780967034010002265383282794593188508843998972112994813125527880423013914720894433659825962538957048048810501155024995083203793822913357525303705201142502868955486545739527631282000968834613617801733190874624888455466402373262413284156168758685775377697815992669196704476716462450381397351809414208806093855786471216253788772773743961997075274428327303534845414051487155773422945553404515337861083847516342666778171556690805431251408370907155651825628549536785653941501912840122928484418792913135452389866810592700477253023157411760221979793580436797738950636639304101810579634914140634381334447188124789772252204477518163904463026698794196700283867291599037315816101133045141784803856511016332693708231056729691919339934270660249833516229820350518296100556567837343567109965443039570750810299986143128231806894999208057364044633707256201160020753924381626958586651170081548956962337751498233252031122748079336996898366834713334375201143240858292992463291285255514679145238634681655674569940138345575658360039355449029280109811425144469300488346697718902368320270828783891108681578187838117379071037052675357487027863319531262984170241124576960805627462013249257675674538808435732031839161245487119302984925802160005328113582253086626104650821280526659275216031943738295898890645520061020567799573778596126250932410024967928366105275604719535023570242770324640768227806731082368445333315453778938149923609692030242455784250520760645216698846546802055762278694868182593066799566564517159204052211973484474929671081274886310696548211868041069260711690670112261971831580804868092379069004736637509500131968766692019850637908668502560896147018215218638093792272196249403602460933309988666512290637280710077807888922588122993380574340992025682315349543732484227954127876551037962636150056919078135577452697253476641822120848770412618576753319684180217401289203549418663322957200006245316273166853181335761105089178461754035102974719174454968867704831638900419119415913268745870041893283284169080603997109421586815035735066648653957753261802165532444926935431960121883111169603099456276566017032499524912037452136833406748500502454443395819802976134535717705833157399770404730901753918599867164526996496374834892337328313462970310582113687919202653825384764292265903246710259973347177212262422786063201436932552617591581470702955891681501260880582367499060822827646778763849061415139578230642254265023250678959539034096276393188470170138876322398889020687760993326973342349289797644733713893785177330127935912088101706840706408045587653361398744103604798309600031858421999969917782995407335692553251882320133366209686427396735938123110290670576513740288892070279401379800341712576973298006353763937483972826092613971487926614352413104354996870181559676545327192480615112268991246371258256073244928213138350453060796433649663021850026957115364815285696862977630435707314406413444969472021036118628966695505044439499213635811930317975844020279068930134515673651326931429801503824779704382105091280266598108782921649503108163647343348119604598722291429882478906396064715146654782445489426118121011913694668381665651043763907076514692911047795777999341035325092576326574004170662042808083978510060153452005679758831477397553770512606750832120673310121101791356377133944751158851087420520681772306053607110368224468089243895721614714025139205172684386917883694565182472986679615987565107147368745588726934387388073559138884857320981367112834244935847275550280578235967248268321691374719264387862418796125970779848713040795937410484542187617982208327005875513588161163292226397097694867495329977492197130619134993318666966242113969263667716559333750482403277515765258228204018821793692477571636681717988192586410158553242664960483151452715326491704027502016805954508066521215532792422511921417686726509616466755794433783335938128370156020300441117366493100653151636010411522214968651921305896424108782623141700213677422090621092454911434370373931239262822492855984017488251669498070088065353747916307686094714226125826116601843441979015852132996749021031999767342504959656753047883092261318790014463121777751879468706054879390977467720796262924427255592807531935826707211765140974947567802662251013190436822037706792050161466136112115845188566876167230314382459610833283100735955165146473217795421066448916106131791212482704578240199682201298917383132339074380290178225547366291891598174409787244260804347777128530364195805006785061961467551078315795705876903119126477644977436846531049133097764096349505454036145973116984452731709865162701412344993025786481617663415813827581063331137229975369532047732205272343795266417211164164230879420364985707846127854460884558354706564672469644031565287781771080799117302591350143775676613956324663814659536109753755004412721853070745320538168776929828700337772891850724013932327611987090661829668116591212170036822724666051488009997452088979651979691447511961296212073020290362287888279657140114753773197090181070187025893984428063869335570490155679324291575019175755391879986465373970705203716973024143000529040567153503732572716243184221841491074953776452337363134215619297776820949366394458561013070737901924013571708277469169033087610730665742992286193167881329593151706140674991694847909699286627546764196028170336725187323312494916237925112510377363009075244678092071487132807282157695827296554681638811752149656665994539859000037048594651657130398702285529025128796367981131531039443638255956019734419809577313442346064028633505212498125586083908430197243933130474748630679927782114508719452059271821672233887863242469857835642273946632060272285724874109323900625779822315938294666852456792630470079357863218680765534452947652968859729390098994705318387725151780366570651569350701733498243788616439820066505327890070895830359533539714492827880144312947137789178281370320954244804222746096219122015962796993343375944185372678446183915048645246261450336667849594702876947996911302607112632264094633064469119173439362353668653490857717528353770368644885780855277144970605418837435873040651524928301337625641009910889223616249941593304451895714996186807167339657942302532259214755234035082652970931537184728830649764208116612147496193194170045269354674742931491967140792835657433951020621583448495078879842642406673515113130809560046972455018180526570171385492987634977458053463386381730952116793299409621560188732263550514460869810720392050414571001093814410356855113118139743997476896501616706562692819251086153751499682883274547607600251178035766158718327368278903103175952861933664072970774903122668311873264973423491649970679971666181584606268108663173984821586494627906157907055708070488751203312885214748133578360850881079122349646605115146046711487266061585674193288904007529449866656852678833105956116160448377435874739332452972600637079256043144666987969688994986063123140621043400855751495975197384085491219066412680628405540326227555840888434202963196871063488074623120557950689750891771178701800167009155275650149320655781522244563404560210488639133823502122319902659396980678520090903552652625076459020334002622280400090087048977514297718505135603652777372665152759191534039649415288475594831124376652480490908322006663105025713199522260236215399786339561675402970867284815938770634554099849899084902241909630896251527406641558307373176942084767322588698662950673642044695481183673701460041473933001674666105491453248727769842562145351456520653258647597659574128566650294048551167548539288713121944018727024221545263462660428709096081580291598404172031519119403925318012889307619515010521879095307050610600591978466288340554594370690310945670598276931762154418306550115086448392956515173645365641327715183756012485731850111828560296160157312786938336578795079530019222829887303466764217774356545817068498201887350230313407862021581679378554118491777904059314777550445619491043769838016204897538098636502760630153037746047698823759079077775699297526557112533854684844843934297166760171736012539747988880855386830922004484991918203351251151726835652137321538128086595758742533060151182561674020698317129645175942725533426524239008123107279070880065804350753027857241351156677977777000654081895775660536698449902877096219342907006443298368545318984907649975302647515583745691086281076300064304550686096002742228397902958927860184495555723714283307596278802386598985969321279323887373198006505931813404993057954524290553608140332474225067474071100540562545499585125100417979224768091508985978304696767870748201880558212995306407643168159270320489329544473519343272566575284475060537388377340163387144376042743420671298553705578224385581545707306020013057345103322310128025038937084819090509254382903479148050381315101489928285301684641860480603597395770986147223463465179492868936335014944406522063972957740744733560037104079009110667758008000721978128304450794127461895260214198897612837703830279997928630716165577124074361162267198625362162667593868515174351308678434674840020483387372775284442798522208671926320603772238736940279721240279251748973672296112664891216352670617652005897790320561236637653438203069437102542327403043164026199122316882299753920436395952984593369618040371322983933864388794934199286200323367164924332951302087485764727519526582256389529551689969291494457230843242956180691643232149832977239970020217531467809757166763532805378607530705069490983418916227018391156256185693653136592148313590863478570947235745080660881971250814933772687692929113594616639021840994126792625618218228807622320498606630385423718502816813461773143670753396963485320645542989008847515717047510521609151658351771413354989877498491946611454995525028233596322187534739632073722727751852776708536314867976547545524413919475786666018316690345505314954140132199114066688518793628079384740620779301753443291618542217733838224785735772793578219195089556612913761211923102632005505156904639675687216520939610244972455041282777477952108413549913205633578449701233544115619466622879624705435178849193171404261186749556288890201230495218045032693028889594495101029669712637770196408838972904746679105762467439493425928483944744756228203446737668767220878014543427602563477149901152188797556071681323477425443151422293912488960000000


  • @seconddevil said:

    You are quite right. I re-wrote it using the built-in lcm and got the right answer (but thats cheating)...

    [mossda@localhost:~]$ cat test.lisp
    (defun find-seq-lcd (start end)
        (loop for m from start to end with r = 1
            do (setf r (lcm r m))
            finally (return r)))

    [mossda@localhost:~]$ clisp -q
    [1]> (load "test.lisp")
    ;; Loading file test.lisp ...
    ;; Loaded file test.lisp
    T
    [2]> (find-seq-lcd 1 20)
    232792560
    [3]> (find-seq-lcd 1 10)
    2520
    [4]> (time (find-seq-lcd 1 20000))
    Real time: 1.609 sec.
    Run time: 1.61 sec.
    Space: 68659024 Bytes
    GC: 126, GC time: 1.206 sec.
    487932562728827051853192251818304... (this goes on several thousand digits)... 7411295098112000000
    [5]>

     

    So first it was wrong and now it's just slow?  Compare my Python version, with a non-built-in lcm function:

    #! /usr/bin/env python
    def gcd(a,b):
    if b == 0: return a
    return gcd(b, a % b)
    def lcm(a,b):
            return a * b / gcd(a, b)
    num = 1
    for x in xrange(20000, 1, -1):
    if num % x != 0:
            num = lcm(num, x)
    print num

     It takes 0.918s to run and display its answer, and removing the print statement takes it down to 0.874s.  There's nothing particularly optimized about it, either, although it does run faster than using reduce(lcm, xrange(1,20001)) (or with the counting-down xrange() above) for some reason.  Sure, maybe you can do it faster in C, but my implementation is five lines long.

    On an unrelated note, I had seen people bitching about the editor, but I didn't realize how bad it could be.  Jesus titty-fucking Christ it's bad. Please, turn off TinyMCE and let me just edit the HTML.



  • @notUsingMyRealName said:

    On an unrelated note, I had seen people bitching about the editor, but I didn't realize how bad it could be.  Jesus titty-fucking Christ it's bad. Please, turn off TinyMCE and let me just edit the HTML.

    You can turn it off in your profile options.



  • @cablecar said:

    You can turn it off in your profile options.

    Thanks, that's much better.

    On an only pseudo-related note: I made a better-still implementation, but it's slightly larger... 50 lines or so. If you take my word that I have a divisorcount(x) function that tells you the factors of x and how many times they occur (example: divisorcount(150) => {2: 1, 3: 1, 5: 2} since 150 = 2 * 3 * 5 * 5), though, it's still short:

    from euler_lib import divisorcount
    import operator
    nums = divisorcount(1)
    for x in range(1,20000):
            d = divisorcount(x)
            for p in d:
                    nums[p] = max(nums.get(p, 0), d[p])
    num = reduce(operator.mul, reduce(operator.add, [[k] * v for (k, v) in nums.iteritems()]))

    Interestingly (or perhaps not) about a fifth of the time is spent in the final line, multiplying the factors of the answer to get the actual answer. I think if reduce() were smarter (didn't always evaluate LTR, for example) it could do a better job.

    This being the case, I think it's time to expand the scope of this e-penis waving contest a bit. The largest number divisible by all integers <= a hundred thousand? A mere 3.692 seconds. Going up to a million takes 3m8.146s. Anyone have faster for a million in an interpreted language?



  • @notUsingMyRealName said:

    This being the case, I think it's time to expand the scope of this e-penis waving contest a bit. The largest number divisible by all integers <= a hundred thousand? A mere 3.692 seconds. Going up to a million takes 3m8.146s. Anyone have faster for a million in an interpreted language?

    Why bother? Unless we trust somebody to run all the entries on the same hardware, it will be absolutely meaningless, and even if we had a single person doing it all it would still be too easy to contest the results. Quite aside from the fact that a specific target like that is an invitation to waste a lot of time optimizing for a single case; for example, you could speed up my factor-based version above by pre-computing a list of primes up to 1000 and encoding it in a single-line data string read in via unpack. It wouldn't make it even slightly more useful in the general case (not that finding least common multiples is really all that useful) but it would definitely speed up the "1 to 1000000" evaluation.



  • @The Vicar said:

    @notUsingMyRealName said:

    This being the case, I think it's time to expand the scope of this e-penis waving contest a bit. The largest number divisible by all integers <= a hundred thousand? A mere 3.692 seconds. Going up to a million takes 3m8.146s. Anyone have faster for a million in an interpreted language?

    Why bother? Unless we trust somebody to run all the entries on the same hardware, it will be absolutely meaningless, and even if we had a single person doing it all it would still be too easy to contest the results. Quite aside from the fact that a specific target like that is an invitation to waste a lot of time optimizing for a single case; for example, you could speed up my factor-based version above by pre-computing a list of primes up to 1000 and encoding it in a single-line data string read in via unpack. It wouldn't make it even slightly more useful in the general case (not that finding least common multiples is really all that useful) but it would definitely speed up the "1 to 1000000" evaluation.

     

    Agreed. Also, if you just want '1 to x' factors, why not go one step further and pre-calculate all of those and store them? If you actually need those in an application and it's time-critical, storing a few dozen (or hundred) integers isn't really a problem.



  • @cablecar said:

    Here's another one he did for me from Euler:

    What is the largest prime factor of the number 600851475143?

    (retarded code snipped...)

    The code timed out after 30 seconds. I'm pretty sure he copied his function from here: http://www.geekpedia.com/code14_Check-for-prime-numbers.html. What got me was that in this one he shows that he knows how to use $i+=, and yet still did it wrong.

    I know I said above that I'm happy for people to use any language, but I can't help but wonder why he didn't write it in C++ or something similar (he professed to having five years of experience with C++ on his resume) which would have been way faster than looping 30,042,573,571 times in PHP. I know it's been said a lot of times before on these forums, but it never ceases to amaze me that these people never stop and think, "hang on, there must be a better way of doing this".



    His code for calculating the Fibonnaci sequence didn't work either - it printed '2' 40,000,000 times. I can't help but conclude that his CV was a complete fabrication.

     

    That's a pretty reasonable conclusion.  This one's even easier than the other one....

     

    int largestPrime(int number)

    {

      // What do you mean I can't use tabs in this fucking window???

      // If number == x * y, then x <= sqrt(number) and y >= sqrt(number) (or vice versa)

      // So lets start dividing by the numbers up to and including sqrt(number) until we can't anymore, and our largest prime is whatever's left.

      int divisorLimit = ((int)sqrt(number)) + 1;

      int i;

      int result = number;

      for ( i = divisorLimit; i >1; i--)
      {

        while ( result % i == 0 && result > i )

        {

          result /= i;

        }

      }

      return result;

    }



  •  Even better, the while should be followed by:

     

    i = min(i, result);



  •  Never mind, that only works if the largest prime >= sqrt(number)...

     


Log in to reply