Problems with Optimization of the Problem 12: Highly divisible triangular number

Hello, friend! How may I optimize this algorithm? I use it in Sublime and it lasts 3.5 s on the this test: “divisibleTriangleNumber(167)` should return 1385280”.

It lasts too long.

This is the link: https://www.freecodecamp.org/learn/project-euler/project-euler-problems-1-to-100/problem-12-highly-divisible-triangular-number

Thanks!

function divisibleTriangleNumber(n) {
         let triangularNumber=0;
           let number = 0;
           let factorInNumber=0;
           let currentNumber = 0;
          
          while(triangularNumber<10000000){
                for(let i = 1;i<=1+number;i++){
                    triangularNumber = triangularNumber + i; 
                 };
                 
                 for(let i = 1;i<=triangularNumber;i++){
                      if(triangularNumber%i==0){
                     
                        factorInNumber=factorInNumber+1;
                     };
                 };
             
             if(factorInNumber>n){
                currentNumber = triangularNumber;
                 //console.log("Jesus did it!")
                 return currentNumber;
             }else{
                number = number + 1;
                triangularNumber = 0;
                factorInNumber = 0;
             };

          };
   }

console.log(divisibleTriangleNumber(374));

Hi @santiagodeleondecar1

Potential infinite loop detected on line 7. Tests may fail if this is not changed.

You need to address the infinite loop. This is why the tests are taking too long.

Happy coding

1 Like

Yes, that is correct. That is the reason why of my question.

I got rid of the first for loop because I have read this can replace the sum of a saries of natural numbers, but I do not how to simplify the rest of the code.

Do you have a suggestion?

function divisibleTriangleNumber(n) {
         let triangularNumber=0;
           let number = 0;
           let factorInNumber=0;
           let currentNumber = 0;
          
          while(triangularNumber<10000){
 triangularNumber=(1+number)*(((1+number) + 1) / 2);
                 
                 for(let i = 1;i<=triangularNumber;i++){
                      if(triangularNumber%i==0){
                     
                        factorInNumber=factorInNumber+1;
                     };
                 };
             
             if(factorInNumber>n){
                currentNumber = triangularNumber;
                 //console.log("Jesus did it!")
                 return currentNumber;
             }else{
                number = number + 1;
                triangularNumber = 0;
                factorInNumber = 0;
             };

          };
   }

console.log(divisibleTriangleNumber(374));

Project Euler problems typically require you to research the maths to get a good solution

1 Like

Hello!

I still have problems with it:

  • I use the equation triangularNumber= (1+iteration)*(((1+iteration) + 1) / 2), but it generates a delay.

  • The form of prime factorization I use generates a longer delay.

let triangularNumber=1;
let possibleFactors=0;
let primeFactordOfATriangularNumber = [];
let unique = []; 
let exponents=1;
let divisorsOfTheTriangularNumber=1;
let currentIteration=0;
let limitOfDivisorsByUser=167;
 let multiplication=1       
let iteration=2;
let currentTriangularNumber=0;      
   
     while(iteration<100000){
            
           triangularNumber= (1+iteration)*(((1+iteration) + 1) / 2)
            possibleFactors=triangularNumber;
           
                for(let i=0;i<20;i++){
                    for(let j = 2;j<triangularNumber;j++){
                            if(possibleFactors%j==0){
                                possibleFactors=possibleFactors/j
                                primeFactordOfATriangularNumber.push(j) 
                                break;
                         };
                     };

                 };
                //   console.log("triangularNumber: ",triangularNumber,"primeFactordOfATriangularNumber: ",primeFactordOfATriangularNumber);
              
                 unique = [...new Set(primeFactordOfATriangularNumber)];
                 
                 for(let i = 0;i<unique.length;i++){
                        for(let j = 0;j<primeFactordOfATriangularNumber.length;j++){
                            if(unique[i]==primeFactordOfATriangularNumber[j]){
                                exponents = exponents + 1;
                            };
                    };

                    multiplication=multiplication*exponents
                    divisorsOfTheTriangularNumber=divisorsOfTheTriangularNumber*multiplication;
                    multiplication=1;  
                    exponents=1;
                 };
                  
                 //console.log("triangularNumber: ",triangularNumber,"divisorsOfTheTriangularNumber: ",divisorsOfTheTriangularNumber,"unique: ",unique, "primeFactordOfATriangularNumber: ",primeFactordOfATriangularNumber);
           
                 if(divisorsOfTheTriangularNumber>limitOfDivisorsByUser){
                    currentTriangularNumber = triangularNumber;
                    currentIteration = iteration;
                    break;
                  };
                    iteration=iteration+1;
                    triangularNumber=0;
                    possibleFactors=0;          
                    primeFactordOfATriangularNumber = [];
                    unique = []; 
                    exponents = 1;
                    divisorsOfTheTriangularNumber=1;

      };

I wanted to express that I am thankful to you and @Teller I took both advices and I could do the excercise.

If you happen to know how to simplify it, please let me know it.

Thanks!

function divisibleTriangleNumber(n) {
         let iteration=0;
        let triangularNumber = 0;
        let primeFactorsOfTheTriangularNumber=0;
        let exponents = 0;
        let divisors = 1;
        let pivot = 0;
        
        let currentIteration=0;
        let currentTriangularNumber=0;
        if(n<25){
           while(iteration<100000){
                    divisors = 1;
                    triangularNumber= (1+iteration)*(((1+iteration) + 1) / 2);
                    primeFactorsOfTheTriangularNumber = triangularNumber;

                    for(let i = 0;i<=10;i++){
                        for(let j = 2;j<=triangularNumber;j=j+1){
                           if(primeFactorsOfTheTriangularNumber%j==0){
                             primeFactorsOfTheTriangularNumber=primeFactorsOfTheTriangularNumber/j;
                             
                              if(j==pivot){
                                    exponents=exponents+1;
                                }else{
                                    pivot=j;
                                    exponents=exponents+2;
                                    divisors=divisors*exponents;
                                    exponents=0;
                                 };
                             break;

                              };

                            };
                        };
                        if(divisors>n){
                           currentTriangularNumber = triangularNumber;
                           return currentTriangularNumber;
                        };

                   iteration = iteration + 1;
                };

        }else{
           while(iteration<100000){
                    divisors = 1;
                    triangularNumber= (1+iteration)*(((1+iteration) + 1) / 2);
                    primeFactorsOfTheTriangularNumber = triangularNumber;

                    for(let i = 0;i<=10;i++){
                        for(let j = 2;j<=Math.ceil(Math.sqrt(triangularNumber));j=j+1){
                           if(primeFactorsOfTheTriangularNumber%j==0){
                             primeFactorsOfTheTriangularNumber=primeFactorsOfTheTriangularNumber/j;
                             
                              if(j==pivot){
                                    exponents=exponents+1;
                                }else{
                                    pivot=j;
                                    exponents=exponents+2;
                                    divisors=divisors*exponents;
                                    exponents=0;
                                 };
                             break;

                              };

                            };
                        };
                        if(divisors>n){
                           currentTriangularNumber = triangularNumber;
                           return currentTriangularNumber;
                        };

                   iteration = iteration + 1;
                };

        };

            
   }

console.log(divisibleTriangleNumber(374));