Project Euler 9. Feedback request + need help with terminal condition

I used maths from 2 wiki articles, will blur it in case somebody consider it a spoiler.
Research is part of the challenge I guess

The thing is: my solution is cool for cases, when n is ‘appropriate’ function parameter, meaning:

3 numbers: a, b, c is Pythagorean triple.
a + b + c = n

For cases when n is not fit in the above conditions, my code will loop infinitely :upside_down_face:

I want to implement some terminal condition for outer loop(aka while loop), but I’m so stuck after all this maths, and I need some ideas. Any hint is greatly appreciated.

function specialPythagoreanTriplet(n) {
    //all Pyth. primitive triples can be generated from
    //'root' triple a = 3 b = 4 c = 5
    
    //non-primitive triples can be generated by simple multiplication
    //of primitive ones
    
    //step 1
    //every subarray >>> Pyth. primitive triple
      let storageOfPrimitiveTriples = [[3, 4, 5]];
    

    while (true) {


      
      for (let primitiveTriple of storageOfPrimitiveTriples) {
        const sumOfabc = primitiveTriple.reduce(
            (a, b) => a + b, 0
          );
        
        //if we found primitive triple such as
        //sumOfabc is divisor of n:
        //can get result
        //for non-primitive triple
        //with simple math
        
        if (n % sumOfabc === 0) {
          primitiveTriple = primitiveTriple.map((num) => (num * n / sumOfabc));
          return primitiveTriple.reduce(
            (a, b) => a * b, 1
            );
        }
      }
        //if did not found result >>> need to generate next
        //level of primitive triples, and get rid of current level
        
        let newLevel = [];
        for (let primitiveTriple of storageOfPrimitiveTriples) {
          
          newLevel.push(
            [
            primitiveTriple[0] - primitiveTriple[1] * 2 + primitiveTriple[2] * 2,
            primitiveTriple[0] * 2 - primitiveTriple[1] + primitiveTriple[2] * 2,
            primitiveTriple[0] * 2 - primitiveTriple[1] * 2 + primitiveTriple[2] * 3
            ]
            );
          
          newLevel.push(
            [
            primitiveTriple[0] + primitiveTriple[1] * 2 + primitiveTriple[2] * 2,
            primitiveTriple[0] * 2 + primitiveTriple[1] + primitiveTriple[2] * 2,
            primitiveTriple[0] * 2 + primitiveTriple[1] * 2 + primitiveTriple[2] * 3
            ]
            )
          
          newLevel.push(
            [
            - primitiveTriple[0] + primitiveTriple[1] * 2 + primitiveTriple[2] * 2,
            - primitiveTriple[0] * 2 + primitiveTriple[1] + primitiveTriple[2] * 2,
            - primitiveTriple[0] * 2 + primitiveTriple[1] * 2 + primitiveTriple[2] * 3
            ]
            )
          
        }
        
        storageOfPrimitiveTriples = newLevel;
    }
    
}

console.log(specialPythagoreanTriplet(1000));

Not related to your question but how did you blur the text? I didn’t know that.

Hello. In the post editor, on top panel(where are buttons B, I etc) you need to click the rightmost button. You’ll see blur option there.

Oh that’s amazing. Thank you!

Try logging the sum of the items in the triple. You’ll see they bounce around before finally growing beyond n since it appears you are generating a tree of triples that are not ordered.

The loose constraints on the problem mean that no item in the triple can be more than n and the sum can’t be more than n so those are your candidates for stop conditions. But, they will only work on an ordered set of triples.

1 Like

Yeah, the main issue that the tree itself is not ordered:

for example: in the second generation of triples, there will be

a = 21 b = 20 c =29 >>> a + b + c = 70

in the third gen, however, on of triples:

a = 7 b = 24 c= 25 >>> a + b + c = 56

Simple condition while (a+b+c < n) or anything like that will not work for this algorithm. There is no direct connection between tree generation and growth of a+b+c.

I guess I need to dive in some math once more to build appropriate terminal condition.

First four levels of this tree on wiki

Edit. And, according to math, this tree is infinite, I need to stop while loop somehow somewhere)

Well, for now I see at least something:

even before strarting loop i can set boundary conditions:

if n < 12 i’ll just return “nope”)

a+b+c >>> always even number >>> can do check if (n % 2 !== 0) and deal with that.

MAJOR UPDATE. Well, I guess I found it. There is another way to generate tree levels, and there will be connection between levels and sum(a, b, c).

Need to rewrite big chunk of code, that’s a little annoying. But when it’ll be done, for every n: integer there will be adequate output.

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.