Short & Sweet Math Challenge #21: Powers that be

[Valentin Albillo]

 
Hi, J-F:

(11-10-2016 05:47 PM)J-F Garnier Wrote:  I have two comments:

1) It seems that your program doesn't explore all the polynomials. [...] However, I was able to hack your program to display all the tested polynomials, and indeed some are missing: [...] For instance, the polynomials x^2+x+1 and x^2+x-1 are not tested, as well as the x^3+x^2... polynomials.

I made use of mathematical equivalences and polynomial theory to prune the number of polynomials to be tested to the barest minimum necessary. For instance, your polynomial:

        x^2+x+1

doesn't have any real roots, just two conjugate complex roots. For polynomials with real coefficients, all complex roots come out in conjugate pairs which of course have the same absolute value and thus can't be unique, i.e., even if their absolute value were >1 there are two of them, not just one as required.

Your other polynomial, namely:

        x^2+x-1

is equivalent to x^2-x-1 if you simply change the variable from x to -x, which of course doesn't alter its absolute value at all, so you only need to generate and check x^2-x-1, which I did. In short, I choose the coefficients in such a way that those redundant polynomials aren't generated while searching.

Quote:2) my second comment is what I already mentioned in my previous message: the value 1.75487766625, root of x^4-x^3-x^2-1, is not found by this algorithm, although its powers clearly tend to an integer (quite quickly actually)

Your number 1.75487766625 is indeed a bona-fide Pisot number (which is the proper mathematical name for the numbers which have this almost-integer powers property) as can be readily checked like you did.

However, although it's indeed a root of the 4th-degree polynomial you mention, namely:

        x^4-x^3-x^2-1

this is not its minimal polynomial. Your number is a root of infinite polynomials with integer coefficients but only one of them has the minimum degree possible, and in this case it is the 3rd-degree polynomial:

        x^3-2*x^2+x-1

which neither your second program nor my original solution generates or checks because it is not a -1,0,+1 polynomial as per the challenge requirements because it does have a -2 coefficient. That's why neither your program nor mine should have found it and that's correct, the -2 coefficient places it squarely out of the specified requirements.

Quote:Thanks again for this challenge!

You're welcome, I'm glad you enjoyed it and thank you very much for your interest, your kind comments and, above all, the time you took to deal with it, much appreciated. Hope to see you back in S&SMC#22 due next month or so.

Best regards.
V.