Project Euler 141:Investigating progressive numbers, n, which are also square.

Problem 141 of Project Euler proved to be just as difficult as the number of people who has actually solved it shows.  The problem reads

A positive integer, n, is divided by d and the quotient and remainder are q and r respectively. In addition dq, and r are consecutive positive integer terms in a geometric sequence, but not necessarily in that order.

For example, 58 divided by 6 has quotient 9 and remainder 4. It can also be seen that 4, 6, 9 are consecutive terms in a geometric sequence (common ratio 3/2).
We will call such numbers, n, progressive.

Some progressive numbers, such as 9 and 10404 = 1022, happen to also be perfect squares.
The sum of all progressive perfect squares below one hundred thousand is 124657.

Find the sum of all progressive perfect squares below one trillion (1012).

I ended up getting the right idea when I was working out. I guess some times it really does help to do something else. In this problem it comes down to some really basic properties and insights so lets start with those

Getting the basics right

First of all we have d,r and q. The first thing that we can note is that by definition of the remaineder we have that r < d. Furthermore we can without loss of generality assume that otherwise we can interchange d and q, and then it will still hold. By that assumption we will end up with

The second thing that we should start looking at is the geometric progression.  A geometric progression is defined as

according to Wikipedia. Such that we have a constant factor c between two terms. There are no requirements for this a except that it has to be different from 0.  However we can see that in our case we can see that we must have

And that c>1 otherwise the first inequality would not hold.

Building on the basics

Furthermore we can conclude that c must be rational, otherwise d and q cannot be integers. And therefore we can write c = a/b. In this case we get that

We can also without loss of generalization say that gcd(a,b) = 1, since otherwise we could just factor out the common factor and get the same result. Furthermore a > b since c > 1.  Looking at q in that light it is clear that must divide r otherwise q is not an integer.  That means we can write for some c.

So by substituting the expression for r into the previous expressions we get

And thus we can write

Transforming this into code

How does this help us? Well we have reordered n to be dependent on three other factors. So that means we can write three loops with bounds

since a is cubed in the expression and a > b, so we have to make it at least 2. Then we can calculate progressive numbers and check if they are square. I can see after solving the problem that none of the numbers in the solution is generated more than once, but I  couldn’t prove that before hand so I decided to put them all in a list knowing there were likely only a few numbers.

The code I have written looks like

long limit = (long)1e12;
List<long> progressiveSquares = new List<long>();

for (long a = 2; a < 10000; a++) {
    for (long b = 1; b < a; b++) {
        if (a * a * a * b * b + b * b >= limit) break;
        if (GCD(a, b) > 1) continue;

        for (long c = 1; ; c++) {
            long n = a * a * a * b * c*c + c * b * b;
            if (n >= limit) break;

            if (IsSquare(n) && !progressiveSquares.Contains(n))
                progressiveSquares.Add(n);

        }
    }
}

long result = progressiveSquares.Sum();

At first I forgot to square c in the calculation of n, in that case it takes forever to get through the loop. After I fixed that it took me 235ms to run the code and get the result.

Wrapping up

This seems almost trivial to me once I solved it. But before I got the insights I had a hard time wrapping my head around it. I am really curious how you solved it.

As always you can find the code here.

Posted by Kristian

22 comments

this is a good problem

I am probably missing something, but where does c come from? You are talking about f, then suddenly c, then f, and then c again.

Thanks for noticing that. It was my mistake. I decided to change f to c after writing most of the post. However, I never proofread this post apparently. There should be not more mentions of the variable f. And if there is then it should have been c.

Ahh. Thanks

To be honest, I thought it was a problem with me missing some crucial part of the mathematics, not a problem with the article!

Thanks for your article, Kristian.
In first part, you said that, we can exchange the role of d & q, imply r<d<q. But i think is not be true. For example: 6 = 4*1 + 2, and both dividend and remainder, 4 and 2, greater than quotient (=1), so we can't say nothing about d and q.

Instead, we still get r q, from given data it followed that: q = r^2/d, so we can rewrite this original function in that form: n^2 = d*r^2/d + r, or n^2 = r^2 + r. But the right side has value between r^2 and (r+1)^2, it can’t be the perfect square, lead to contradict.

Afterthat, we can continue with your analysis.

In the example you supply here we have that d = 4, q = 1 and r = 2.

if we interchange d and q then we will have that
d = 1 and then the quotient becomes q=6 and remainder r=0, and in that case it still holds. It is correct that as soon as I change the divider then other numbers change.

i like the fact that your service provides ways of writing math equations.
can i subscribe to the service [word processing].

I am just using a wordpress plugin that handles it for me. I haven’t investigated what happens inside of it, besides the fact that it uses LaTeX to render it.

Jean-Marie Hachey

Table 1
The ten first progressive perfect square numbers.
[Re: Project Euler 141: Investigating progressive numbers, n, which are also square]

http://img713.imageshack.us/img713/5861/pe141tablone.jpg

___

Sources:

1) Project Euler 141
Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem141.cs
2) Microsoft Visual C# 2010 Express
3) Microsoft Office Excel (2007)

___

A great solution to a challenging problem.
Thanks to Kristian.

Jean-Marie Hachey

Some results and comments.
[Re: Project Euler 141].

In the results presented here, we may underline
the following characteristics:
1) d = (k^2)r
2) d = kq
3) q = kr
4) Table 2 shows that: d > n^(1/2):
d:[n^(1/2)]:–> 4:[3]; 144:[102]; 225:[130]; 1058:[312]; 4900:[3465].
5) EN 4 shows a case where k is a fractional number: 11.5=46/4, 46 may be related to the cubic root of 97344 (46,0012602);
also 1058=2x23x23.
6) The remainders correspond to: 1, 8 = (2^3), 25 = (5^2), 36 = (6^2), 1225 = (35^2).

___

Table 2
Progressive perfect square numbers: some results and comments.
[RE: Project Euler 141: Investigating progressive numbers, n, which are also square.]

http://img594.imageshack.us/img594/9523/pe141tabletwo.jpg
___

Sources:
As described in the previous comment.
Additional source:
Quadratic Formula Calculator
http://quadratic-formula-calculator.com/

Jean-Marie Hachey

Results and comments:
[Re: Project Euler 141].
Common prime factor sequences are in brackets.
With some exceptions for factors of remainders (r), common ratios (k) or their multiples are usually part of prime factor sequences.

___

Table 3
Progressive perfect square numbers and prime factors.
[RE: Project Euler 141: Investigating progressive numbers, n, which are also square.]

http://img210.imageshack.us/img210/394/pe141table3.jpg

___

Sources:
As described in the previous comments.

Karl Keller

My early attempts in python were extremely slow.
After learning from your analysis of the problem …
This worked.

from math import *
from fractions import gcd
def is_square(n) :
    return int(sqrt(n)) == sqrt(n)
# r < d < q
# a > b , a/b = c
# because d^2 = q*r
# cb^2 < cab < ca^2
# n = cabca^2 + cb^2 = a^3*c*2*b + b^2*c = a*a*a*c*c*b + b*b*c
L = 10**12
progressiveSquares = set()
sum_progressive_squares = 0
for a in range(2,int(L**(1/3.)+1)) :
    for b in range(1,a) :
        if a*a*a*b*b + b*b >= L : break
        c = 1
        n = a*a*a*c*c*b + b*b*c
        while n < L :
            n = a*a*a*c*c*b + b*b*c
            if is_square(n) and n not in progressiveSquares :
                progressiveSquares.add(n)
                sum_progressive_squares += n
                print n,b*b*c,a*b*c,a*a*c
            c +=1
     
print sorted(progressiveSquares)
print "answer",sum(progressiveSquares)
print "sum_progressive_squares", sum_progressive_squares
Muhammad Junaid

Hi! I found it a very good problem. . . but there is a mistake in this problem of F & c. .

>By that assumption we will end up with r < d 11=2*4+3

In both cases either d or q is less than r.
Can you explain please?

Seems like my comment has been crippled by unknown reason…

[By that assumption we will end up with r < d 11=2*4+3

In both cases either d or q is less than r.
Can you explain please?

>By that assumption we will end up with r < d 11=2*4+3. In both cases either d or q is less than r. Can you explain please?

[By that assumption we will end up with r less than d less than q

I can’t understand this assumption. How did you come up with idea that q has to be greater than d and r. For example:

n=d*q+r : 11=4*2+3 : 11=2*4+3

In both cases either d or q is less than r.
Can you explain please?

Sorry for spam, I was just trying to figure out why my message was screwd up.

Antonio Sanchez

I agree with some of the others here, that we cannot (in general) assume that r is less than q. In the example provided above by doluong87, 6 = 4*1+2, 6 WOULD be considered a progressive number. However, restricting r less than d less than q, the only options are:
6 = 3*2+0
6 = 6*1+0
So 6 would NOT be detected as a progressive number. It turns out we are getting lucky, that the added restriction that n is also a perfect square eliminates these cases.

You have a bug in your code, I think.

if (a * a * a * b * b + b * b >= limit) break;

should be:

if (a * a * a * b + b * b >= limit) break;

Looks like you’re lucky and it didn’t affect the results (and probably sped things up significantly).

Leave a Reply