PE 75 primitive Pythagorean triples

  • Thread starter Thread starter Arman777
  • Start date Start date
  • Tags Tags
    Primitive
Click For Summary

Discussion Overview

The discussion revolves around the problem of finding primitive Pythagorean triples (a, b, c) such that the sum S = a + b + c is less than 15 × 10^5. Participants explore various coding approaches and mathematical properties related to generating these triples, including the use of parameters m and n.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant shares a Python code snippet aimed at generating primitive Pythagorean triples using the conditions gcd(m, n) = 1 and the parity of m and n.
  • Some participants question the necessity of focusing solely on primitive triples, suggesting that non-primitive triples like (6, 8, 10) are also valid solutions.
  • There is a suggestion to consider the efficiency of different looping strategies, with some arguing that using m and n is preferable to looping over a and b.
  • Another participant proposes a method involving an array to tally occurrences of sums of triples, noting potential performance issues due to the large number of square root calculations.
  • One participant discusses the importance of ensuring that the method used to generate triples is necessary, sufficient, and unique.
  • Another participant reflects on the need to profile code for efficiency, particularly regarding the use of gcd calculations.
  • Several participants express uncertainty about the best approach and indicate they are still in the planning or thinking stages of their coding solutions.

Areas of Agreement / Disagreement

Participants express differing views on the necessity of focusing on primitive triples versus non-primitive ones. There is no consensus on the best coding approach, with multiple strategies being proposed and debated.

Contextual Notes

Some participants note potential inefficiencies in their proposed methods, particularly regarding the computational cost of gcd calculations and the performance of different algorithms. There are also mentions of bugs in the code snippets shared, but these remain unresolved.

Who May Find This Useful

This discussion may be useful for individuals interested in algorithm design, coding efficiency, and mathematical properties of Pythagorean triples, particularly in the context of programming challenges.

  • #31
Arman777 said:
We can optimize now

OK. You know my first question: "where is your program spending its time?"
 
Physics news on Phys.org
  • #32
Vanadium 50 said:
OK. You know my first question: "where is your program spending its time?"
:angel:

Sadly I don't know

Code: 
         277502 function calls in 110.125 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:103(release)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:143(__init__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:147(__enter__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:151(__exit__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:157(_get_module_lock)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:176(cb)
        2    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:211(_call_with_frames_removed)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:222(_verbose_message)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:232(_requires_builtin_wrapper)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:307(__init__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:311(__enter__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:318(__exit__)
        4    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:321(<genexpr>)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:369(__init__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:416(parent)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:424(has_location)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:433(spec_from_loader)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:504(_init_module_attrs)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:576(module_from_spec)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:58(__init__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:663(_load_unlocked)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:719(find_spec)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:740(create_module)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:748(exec_module)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:765(is_package)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:78(acquire)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:855(__enter__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:859(__exit__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:882(_find_spec)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:948(_find_and_load_unlocked)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:978(_find_and_load)
        1  109.993  109.993  110.125  110.125 P75.py:1(<module>)
    13388    0.078    0.000    0.078    0.000 P75.py:23(<setcomp>)
        3    0.000    0.000    0.000    0.000 {built-in method _imp.acquire_lock}
        1    0.000    0.000    0.000    0.000 {built-in method _imp.create_builtin}
        1    0.000    0.000    0.000    0.000 {built-in method _imp.exec_builtin}
        1    0.000    0.000    0.000    0.000 {built-in method _imp.is_builtin}
        3    0.000    0.000    0.000    0.000 {built-in method _imp.release_lock}
        2    0.000    0.000    0.000    0.000 {built-in method _thread.allocate_lock}
        2    0.000    0.000    0.000    0.000 {built-in method _thread.get_ident}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.any}
        1    0.000    0.000  110.125  110.125 {built-in method builtins.exec}
        4    0.000    0.000    0.000    0.000 {built-in method builtins.getattr}
        4    0.000    0.000    0.000    0.000 {built-in method builtins.hasattr}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        2    0.000    0.000    0.000    0.000 {built-in method builtins.print}
   250000    0.052    0.000    0.052    0.000 {built-in method math.gcd}
        2    0.000    0.000    0.000    0.000 {built-in method time.perf_counter}
    14044    0.002    0.000    0.002    0.000 {method 'add' of 'set' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    0.000    0.000    0.000    0.000 {method 'get' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'remove' of 'set' objects}
        2    0.000    0.000    0.000    0.000 {method 'rpartition' of 'str' objects}

What is this represents ?

P75.py:1(<module>)---

I guess just running takes the time and using sets which contains large numbers.
 
  • #33
Is there some other way than "set" to keep track of what lengths have been used and how often?
 
  • #34
Vanadium 50 said:
Is there some other way than "set" to keep track of what lengths have been used and how often?

Well without using set I cannot do my operations. So my algorithm fails. So I don't think there's within the current algorithm structure. But I am thinking.
 
  • #35
Arman777 said:
Well without using set I cannot do my operations.

Nonsense.

What's wrong with a plain old array of 1 to maximum length?
 
  • #36
Vanadium 50 said:
Nonsense.

I mean arrays don't support (|) or (&) operations. Of course, array's can be used. But I have to transform these operations into the loops and that's not so good.

I'll do the same thing but using extra loops to create operations.

I can do the same with set's and only using 2 simple operation symbol. I don't see how using arrays would change the run-time, without changing the algorithm itself. (Also I remember that sets are faster then when searching numbers in it. In my previous question about prime numbers I guess)

I think the problem is in the algorithm itself.

I can try to create a method where at some steps I can reset the num_set_0 so that the length of set does not exceed ten thousand
 
  • #37
OK, you're the boss. Your code runs in an hour, mine in milliseconds. What do I have to teach you. Good luck!
 
  • #38
I am not the boss. I just argued that just changing set to arrays would not make any difference without chaging the algorithm itself.

Because lists do not support -, &, | operations.

I created functions for these oprations and turn my code into the list version. At max_sum = 10 000, my code is 33 times faster then list version.

If there's a faster way then doing these logical operations on lists other then creating functions, maybe things could be different. But I don't know how to do that.
 

Similar threads

Monte Carlo simulation, rejection algorithm
  • · Replies 2 ·
Replies
2
Views
2K
Comp Sci Orbit of the Earth - numerical methods leapfrog
  • · Replies 3 ·
Replies
3
Views
2K
Sum of All Positive Integers n where d+n/d is Prime to 100M
  • · Replies 80 ·
3
Replies
80
Views
10K
Comp Sci Matrix problem in java using bubble sort
  • · Replies 7 ·
Replies
7
Views
2K
Comp Sci Orbit of Earth: Plotting Trajectory
  • · Replies 6 ·
Replies
6
Views
2K
How to Create a Flowchart for Calculating GCD?
  • · Replies 27 ·
Replies
27
Views
5K
Comp Sci RSA to encrypt English Alphabets, any restrictions?
  • · Replies 7 ·
Replies
7
Views
2K
Number theory, primitive pythagorean triples
  • · Replies 6 ·
Replies
6
Views
2K
An array problem involving a recursive binary search
  • · Replies 18 ·
Replies
18
Views
3K
Largest Prime Factor of 600851475143
  • · Replies 39 ·
2
Replies
39
Views
4K