Strange Numbers

Here are the properties of "strange numbers" in the problem I'm doing:

1) They have an even number of decimal digits (no leading zeros).

2) Define left half to be the number represented by the most significant half of digits of the original number, and right half to be the one represented by the least significant half. The right h开发者_如何学Calf may have leading zeros. The strange number is the square of the sum of its halves: 81 = (8 + 1)^2

Here are some other examples: 998001 = (998 + 001)^2, 3025 = (30 + 25)^2

How can I write a program that lists all the strange numbers in increasing order that have no more than 18 decimal digits?

I understand how to do this by looking at all the possibilities (numbers with 2 digits, 4 digits, 6 digits, ... , 18 digits), but that would take days to run. Are there any patterns to this, so I can output all the strange numbers in a matter of seconds? I would prefer answers in Java, but pseudo code is okay also.

---

All these 'strange' numbers are perfect squares. So you can start by going through all the numbers and squaring them (until the square has more than 18 digits). And for each square, check to see if it is 'strange'.

Edit I'll also add that the reason this speeds things up so much is that it changes the solution from O(n) to O(√n)

---

Besides @spatulamania's speed-up, you can use modulo arithmetic to further speed up the checks.

To check every perfect square, you'll have to split the number into the two parts, add them, square the sum and compare it with the original number. (I'll name this as "full-check")

Instead, you can first check only the last digits of the two parts (and square their sum). For example, for number 99980001, take digits 8 and 1, take the square of (8+1)^2 = 9^2 = 81 and test that the last digit (1 in this case), is same as the last digit of 99980001 (I'll name this as "small-check"). If yes, then proceed with the full-check.

Since there are only 10x10=100 such combinations, this just needs to be done once. You'll create an array of acceptable combinations, that you can use:

0   0
0   1
8   1
4   4
8   4
0   5
0   6
8   6
4   9
8   9

Using this, you'll need to do only the "small-check" for about 82% of the perfect squares (those that fail the small-check) and both checks for the rest 18% (that pass the small-check, so "full-check" will be needed too). Therefore, if the "small-check" can be done fast enough, you'll gain some speed.

You may find even faster to expand this table for the last 2 digits of the two parts and use it (when n is large enough).

---

class strange_number
{
    int number(int n)
    {
        int x = n;
        String a = Integer.toString(n);
        int d = a.length();
        if(((int)(Math.pow(((x%(int)(Math.pow(10,d/2)))+(x/(int)(Math.pow(10,d/2)))),2))) == x)
        return 1;
        else
        return 0;
    }
}

can try this way. This may help u.