Short & Sweet Math Challenge #21: Powers that be

[Valentin Albillo]

 
Short & Sweet Math Challenge #21: Powers that be

Hi all,

At the end of April 2008 and after 20 releases I concluded my "Short & Sweet Math Challenges" series which allowed you to dust off and show off both your favorite programmable HP calcs and your math/HP-programming skills while introducing and discussing interesting and unusual mathematical topics.

The series was well received and now, some 8 years later, I'm releasing "season 2", so to say, beginning with this brand-new S&SMC #21, in the tradition and style of the preceding ones. Iif this second installment gets a similarly good reception, I intend to eventually post another full 20-strong batch.

Now as for this present new challenge, first a short prelude. Many of you will surely have heard about Phi, the ubiquitous so-called Golden Ratio constant which can be promptly evaluated as (1+Sqrt(5))/2, namely:

       Phi = 1.61803+

Phi is further characterized by being the largest root in absolute value of the polynomial x^2-x-1 (i.e.: Phi^2-Phi-1 = 0), which happens to be the lowest-degree polynomial for which Phi is a root and thus it gets called the "minimal polynomial" of Phi.

As it happens, Phi has a plethora of very interesting, sometimes unique properties, one of them being that its increasing powers are ever nearer to integer values, for instance:

       Phi^20   =   15126.99993+
       Phi^50   =   28143753122.99999999996+
       Phi^100  =   792[...]126.999999999999999999998+
       Phi^200  =   627[...]126.999999999999999999999999999999999999999998+

Alas, while certainly interesting, this quasi-integer property of the powers of Phi is far from unique, there are some other constants that boast this very property, as for instance (let's call it "Hpi" for the time being):

       Hpi = 1.32471+

which happens to be the largest root in absolute value of the polynomial x^3-x-1 (i.e.: Hpi^3-Hpi-1 = 0), which is its minimal polynomial. Indeed, we do have:

       Hpi^20   =   276.992+
       Hpi^50   =   1276942.001+
       Hpi^100  =   163[...]001.9999995+
       Hpi^200  =   265[...]250.000000000001+
       Hpi^500  =   115[...]876.9999999999999999999999999999994+

demonstrating that Hpi's powers also get nearer and nearer to integer values, like Phi's do.

That said, now go and get a programmable HP calc of your choice (say an HP-10C or better, hardware/software based HP-calc emulators also welcomed) and use that calc's language of your choice (say RPN, FOCAL, RPL, BASIC, FORTH, etc.) to try and meet:


The Challenge:

Write a program to find and output the constants that have the aforementioned quasi-integer-powers property, subject to the requirements that your program must:

- find ALL such constants in the range 1 < constant < 2, for minimal polynomials up to degree 8 having all their coefficients equal to either +1, 0, or -1, the leading coefficient in particular being always +1.

- output both each constant AND the minimal polynomial for which it is a root, sorted by increasing numerical value, with a final tally of how many constants were found (hint: more than 30) and, optionally, timing.

Of course, the faster your program runs the better, smaller program sizes being important but secondary. If your chosen HP calc runs too slowly you might consider, in order:

       . using a better algorithm and/or optimizing your solution for speed,
       . coding in a faster language (say FORTH or assembler, if available),
       . using a faster HP calc,
       . using an HP-calc emulator running on a faster platform, or
       . just be patient and have a meal (or two) while it merrily runs.

That's all. Within a few days I'll post and comment my 12-line (60-statement, 585-byte) solution for the HP-71B, which runs like this (no spoilers):

>RUN
       ... some lines of output ...

       1.57367896839    x^8-x^7-x^6+x^2-1
       1.59000537390    x^7-x^5-x^4-x^3-x^2-x-1
       1.60134733379    x^7-x^6-x^4-x^2-1
       1.61803398875    x^2-x-1

       ... more lines of output ...

       (number of constants found)

I'll also comment on the underlying theory and algorithm used as well as trivia and problems I found. Now for the small print:

  - you can use any ROMs, libraries or binary files for your calc as long as they are readily available, preferably for free, as well as extra RAM if needed. For instance, for the HP41 and emulators you can use the Math ROM, Advantage ROM, card reader ROM, printer ROM and many others. My HP-71B solutions typically may use the Math ROM, HP-IL ROM, JPCROM, STRNGLEX binary and additional RAM modules.

  - you can use any hard/soft emulator for a given HP calc model but solutions given for non-HP calcs (say written in Excel, Visual Basic, C#, for vintage SHARP or TI machines, etc) won't be considered to have met the Challenge and in fact may spoil the fun for all.

  - ditto for using the web to search for solutions. You will ruin the fun for yourself and other people attempting the challenge so you'd better try and solve it by your own efforts first, not mercilessly scavenging the web.


Enough said, now let's see your solutions ! (and please do not use CODE sections in your posts, they don't print well).

Best regards.
V.
.