Programming math challenge gives wrong answer

Joined
Aug 6, 2023
Messages
1
Reaction score
0
I have the equation x^2 - y^2 - z^2 = n, where x, y, z and n are all positive integers. x, y and z must follow the same arithmetic progression (e.g. z is 7 less than y which is 7 less than x). The goal is to calculate the number of n less than one million which have exactly ten such solutions.
I parametrised the equation as
x = a
y = a - b
z = a - 2b

This transforms the equation into
(5b - a)(a - b) = n.
Since z is positive, a > 2b.
This means a > 0.
Since n is positive, this implies that a - b > 0 since a - b == 0 would imply n == 0.
Since x is positive, a > 0.
For any b, the smallest value of (5b - a)(a - b) such that n is positive is (5b - (2b+1))((2b+1) - b) = (3b-1)(b+1).

Here is my code:

C++:
#include <iostream>

using namespace std;

int main() {
    vector<int> numbers(1000000, 0);
    
    for(int b=1;(b+1)*(3*b-1)<1000000;b++) {
        for(int a=2*b+1;a<5*b&&(5*b - a)*(a - b)<1000000;a++) {
            numbers[(5*b - a)*(a - b)]++;
        }
    }
    
    int num_of_values = 0;
    
    for(int i=0;i<1000000;i++) {
        if(numbers[i] == 10) {
            num_of_values++;
        }
    }
    
    cout<<num_of_values<<endl;
    
    return 0;
}
 
Joined
Sep 21, 2022
Messages
134
Reaction score
17
For any b, the smallest value of (5b - a)(a - b) such that n is positive is (5b - (2b+1))((2b+1) - b) = (3b-1)(b+1).
b=3
(3b-1)(b+1)=32
a=7
(5b-a)(a-b)=32

32 is not the smallest

b=3
a=14
(5b-a)(a-b)=11

b=3
a=12
(5b-a)(a-b)=27

b=3
a=13
(5b-a)(a-b)=20
 
Joined
Sep 21, 2022
Messages
134
Reaction score
17
This looks like a project Euler problem.

I'd put the b loop inside the a loop.

2 < a < (5/4)*10^6

a/5 < b < a/2

Just my opinion.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,821
Messages
2,569,749
Members
45,733
Latest member
MariaQch13

Latest Threads

Top