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

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

Written by on 23 March 2013

Topics: Project Euler

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.

22 Comments For This Post I'd Love to Hear Yours!

  1. kimera says:

    this is a good problem

  2. DarthCrap says:

    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.

  3. Kristian says:

    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.

  4. DarthCrap says:

    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!

  5. doluong87 says:

    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.

  6. Kristian says:

    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.

  7. kimera says:

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

  8. Kristian says:

    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.

  9. Jean-Marie Hachey says:

    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.

  10. Jean-Marie Hachey says:

    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/

  11. Jean-Marie Hachey says:

    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.

  12. Karl Keller says:

    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
    
  13. Muhammad Junaid says:

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

  14. pasha says:

    >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?

  15. pasha says:

    Seems like my comment has been crippled by unknown reason…

  16. pasha says:

    [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?

  17. pasha says:

    >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?

  18. pasha says:

    [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?

  19. pasha says:

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

  20. Antonio Sanchez says:

    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.

  21. Michael says:

    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 Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.