How to find Margic numbers

[valleymorning]

Dear all,

Could anyone help me on finding all magic numbers using JAVA with 1000 iterations or less?
Magic numbers are 6 digit numbers that have the property that they are equal to the square of the sum of two 3-digit numbers when it's high-order and low-order digits are separated.

For example:
123789 is not a magic number because:
123+789 = 912 and 912^2 = 831744, which is not the original number 123789.

998001 is a magic number because:
998+1 = 999 and 999^2 = 998001, which is the original number.

Thank you in advance for your help.
Valleymorning

[freelancelote]

So, where's your problem? finding the algorithm or coding it?

[valleymorning]

So, where's your problem? finding the algorithm or coding it?

Hi freelancelote,

Thanks very much for your response.
I'm seeking for both, and with the algorithm
which the best Java APIs I should use.

For algorithm, my thought is to store the original number, and store the numbers as a string of characters, convert each of them to number, and sum the first three digits, then sum the last three digits, adding the two sums, and square the resulted value , and finally compare it to the original value. However, my algorithm is kinda cumbersome, I wish you can help me to improve it if you could.

Thanks,
VM

is

[freelancelote]

hi valleymorning.
Perhaps an idea would be:
1. split the 6 digit number in two: divide the number by 1000 and put the result as an int into a variable (say firstPart). Find the modulo 1000 of the 6 figure number and that'll be the other variable you need (say secondPart).
2. the rest then, you said it: sum the two of them, square the result and compare the result with the original 6 digit number.

As for the API, if you plan to just run the program from command line, I don't think you'll have to import anything.
If you'd like to put it nicely on a window, with graphics and all, then you'll have to use java.awt and javax.swing.
Besides, if you'd like to store this 1000 numbers on a file then use the java.io.

But wait and see what a more senior member would like to say; they normally come up with pretty sneaky algorithms.

I hope it helped.

[VernonDozier]

Could anyone help me on finding all magic numbers using JAVA with 1000 iterations or less?

You may need to elaborate on what precisely this restriction means, including the word "iterate". I imagine it means that this brute-force method is no good:

for (int i = 100000; i < 999999; i++)
{
    check whether i is a magic number
}

That would be 900,000 checks, which is well over 1,000. Generally I see the word "iteration" applied to methods like calculating PI. Each iteration gets you closer and closer, but it's an estimate. That would not apply here. So find out what that 1000 iteration rule means. Perhaps you aren't allowed to TEST each number but rather have to GENERATE each number. It's too completely different approaches. The "dumb", brute-force method above is a checking method. freelancelote's idea is a checking method.

By the way, when I say "dumb" method, I don't mean that it is necessarily a dumb method to use. Often they are the fastest to program and the right way to do it. But they don't involve any mathematics and they aren't elegant (or "sneaky" as freelancelote puts it).

One thing to notice mathematically right away is that a number like 564182 is definitely not a magic number since it ends in 2. Any number whose last digit is 2, 3, 7, or 8 cannot be a magic number since no number squared has a last digit of 2, 3, 7, or 8, so cross those off your list right away. But you can cross way more of them off right away.

The approach should be this: Don't test numbers that are not squares of three digit numbers. any number that is not a square of a number is immediately off the list with no testing required, no adding, no modulus calculation. Generate all of the squares and test them. Take the square root of 100,000 and round up. The square-root of 1,000,000 is easy: 1000. 1000 squared is 1,000,000, which is too big. So use 999.

int lowestPossible = /* square root of 100,000, rounded up */
int highestPossible = 999;

for (int i = lowestPossible; i <= highestPossible; i++)
{
    int possibleMagicNumber = i * i;

    // test whether possibleMagicNumber is a magic number
}

That solves your 1,000 max iterations problem, I imagine, since you're only testing fewer than 700 numbers as opposed to testing 900,000 numbers.

Using Strings is completely unnecessary. This is an arithmetic problem. The nice part is that the squaring is unnecessary since you've already done it. For example, take 400:

Square 400. You get 160,000. Split 160,000 into 160 and 000. Add them up. You get 160. It is completely unnecessary to square 160 and see if you get 160,000. You already know that you won't since you know that 400 squared is 160,000. Just compare 160 to 400. They aren't equal, so 160,000 isn't a magic number.

[valleymorning]

Hi frelancelote,

Thanks so much for your help.
I also listen to other ideas from this community.
It's a great community to be with.

Best,
VM

[valleymorning]

Hi VernonDozier,

I truly appreciate your thought. It's a great idea to eliminate the numbers ending with 2, 3, 7, 8 and take the approach to GENERATE rather than TEST each number.

The range from 100000 <i< 999999 may be to big,
However, with the range 316 <i < 999 (given
int lowestPossible = 316 /* square root of 100,000, rounded up */
int highestPossible = 999)
how can I handle the number 000000 ( 0*0=0) and 000 001 (1*1=1)

Could you explain a little bit on the approach that "Don't test numbers that are not squares of three digit numbers"

Thank you again for your help.
VM

You may need to elaborate on what precisely this restriction means, including the word "iterate". I imagine it means that this brute-force method is no good:

for (int i = 100000; i < 999999; i++)
{
    check whether i is a magic number
}

That would be 900,000 checks, which is well over 1,000. Generally I see the word "iteration" applied to methods like calculating PI. Each iteration gets you closer and closer, but it's an estimate. That would not apply here. So find out what that 1000 iteration rule means. Perhaps you aren't allowed to TEST each number but rather have to GENERATE each number. It's too completely different approaches. The "dumb", brute-force method above is a checking method. freelancelote's idea is a checking method.

By the way, when I say "dumb" method, I don't mean that it is necessarily a dumb method to use. Often they are the fastest to program and the right way to do it. But they don't involve any mathematics and they aren't elegant (or "sneaky" as freelancelote puts it).

One thing to notice mathematically right away is that a number like 564182 is definitely not a magic number since it ends in 2. Any number whose last digit is 2, 3, 7, or 8 cannot be a magic number since no number squared has a last digit of 2, 3, 7, or 8, so cross those off your list right away. But you can cross way more of them off right away.

The approach should be this: Don't test numbers that are not squares of three digit numbers. any number that is not a square of a number is immediately off the list with no testing required, no adding, no modulus calculation. Generate all of the squares and test them. Take the square root of 100,000 and round up. The square-root of 1,000,000 is easy: 1000. 1000 squared is 1,000,000, which is too big. So use 999.

int lowestPossible = /* square root of 100,000, rounded up */
int highestPossible = 999;

for (int i = lowestPossible; i <= highestPossible; i++)
{
    int possibleMagicNumber = i * i;

    // test whether possibleMagicNumber is a magic number
}

That solves your 1,000 max iterations problem, I imagine, since you're only testing fewer than 700 numbers as opposed to testing 900,000 numbers.

Using Strings is completely unnecessary. This is an arithmetic problem. The nice part is that the squaring is unnecessary since you've already done it. For example, take 400:

Square 400. You get 160,000. Split 160,000 into 160 and 000. Add them up. You get 160. It is completely unnecessary to square 160 and see if you get 160,000. You already know that you won't since you know that 400 squared is 160,000. Just compare 160 to 400. They aren't equal, so 160,000 isn't a magic number.

[valleymorning]

Hello VernonDozier,

I see why we don't need to use string because
we calculate it mathematically as freelancelote
mentioned above.

Thanks again,
VM

[valleymorning]

Hello VernonDozier,

I see why we don't need to use string because
we calculate it mathematically as freelancelote
mentioned above.

Thanks again,
VM

However, I'm still thinking that if I don't use string to convert the possible magic number, how can I check if its last digit is 2, 3, 7, or 8
in order to toss that number out?

Thanks,
VM

[VernonDozier]

I assumed "6 digit number" meant 100,000 or more. If it doesn't, just have the range be from 0 to 999 rather than from 317 to 999. That'll be exactly 1000 comparisons, so you're still OK.

Regarding the fact that no square of a number ends in 2, 3, 7 or 8, that's true, but now irrelevant. There is no need to test for that. You already KNOW that any number that you are testing IS a square because you squared a number to GET the number you are testing for "magic-ness".

If you were given a number that you had to TEST for square-ness, you could check that last digit. In this case, again since you already know the number you are testing is a square, it's irrelevant. Your job is simply to split the number in two and add:

for (int i = lowestPossible; i <= highestPossible; i++)
{
    int possibleMagicNumber = i * i;
    int thousandsPart, onesPart;

    // split possibleMagicNumber into onesPart and thousandsPart

    if (onesPart + thousandsPart == i)
    {
        // possibleMagicNumber is "magic"
    }
}

[valleymorning]

I assumed "6 digit number" meant 100,000 or more. If it doesn't, just have the range be from 0 to 999 rather than from 317 to 999. That'll be exactly 1000 comparisons, so you're still OK.

Regarding the fact that no square of a number ends in 2, 3, 7 or 8, that's true, but now irrelevant. There is no need to test for that. You already KNOW that any number that you are testing IS a square because you squared a number to GET the number you are testing for "magic-ness".

Hi VernonDozier,
Great! Got it! Thanks so much for your shedding the light on this problem. Your approach is very smart and elegant. I've learned a lot from you and freelancelote.

Have a Happy Labor Day.
VM