Threaded Mode | Linear Mode

Valentin Albillo · 03-29-2019, 01:55 AM

Hi, all:

Let's continue with my original solutions, today it's time for:

Tier 3 - The Challenge:

Those positive real numbers that are either powers or sums of distinct powers of an arbitrary real number P form an increasing sequence whose first term is 1 (i.e.: P⁰). Write a program which accepts as input both P and an index k and returns the corresponding k^th term in the sequence.

Use your program to find the 1,000,000^th term and the 3,141,593^th term when P = e as well as the 1,234,567^th term and the 2,718,282^th term when P = Pi.

My original solutions:

Though the concept used in this challenge will work for powers of any number P >= 2, whether integer or real, I purposefully used a sequence of real numbers which were either powers or sums of distinct powers of e instead of powers of an integer to avoid giving as examples some integer sequences that people would immediately search for in OEIS.

For instance, my preliminary (not posted) examples where based on the integer sequences for P = 3 and P = 61, namely:

       1 3 4 9 10 12 13 27 28 30 31 36 37 39 40 81 ...

       1 61 62 3721 3722 3782 3783 226981 226982 227042 ...

but I decided to use instead P = e and P = Pi , which generate sequences of reals not present in OEIS. That said, the key fact is that the elements which are either powers or sum of distinct powers of a base P naturally map to the elements which are either powers or sum of distinct powers of base 2, which of course are all the integers 1, 2, 3... , i.e. precisely the indexes for the elements in the base-P sequence. Thus we only need to find the base-2 expression for a given index and then interpret that base-2 expression as a number in base P, which we then convert to the usual base 10. For example:

       - to find the 6^th element in the sequence for P = 61:

              the index 6 in base 2 = 110₂ -> 110₆₁ = 61² + 61¹ = 3721 + 61 = 3782 in base 10

My original solution for the HP-71B is this 68-byte 1-liner:

       1  DEF FNE(N,K) @ M=0 @ P=1 @ REPEAT @ M=M+P*MOD(N,2) @ P=P*K @ N=N DIV 2 @ UNTIL NOT N @ FNE=M

and to compute the particular elements asked for in the challenge, simply:

       >FNE(1000000,EXP(1))

              278394444.173 { = e⁶ + e⁹ + e¹⁴ + e¹⁶ + e¹⁷ + e¹⁸ + e¹⁹ }

       >FNE(3141593,EXP(1))

              1601007663.31

       >FNE(1234567,PI)

               9091632437.43 { = Pi⁰ + Pi¹ + Pi² + Pi⁷ + Pi⁹ + Pi¹⁰ + Pi¹² + Pi¹⁴ + Pi¹⁵ + Pi¹⁷ + Pi²⁰ }

       >FNE(2718282,PI)

               30446503139.5

It's worth mentioning that for P = 8 and P = 16 there's an even simpler solution for the HP-71B right from the command line. For instance, to find the 123^th element in the sequence of powers or sum of distinct powers of 8, simply execute this from the command line:

              >BVAL(BSTR$(123,2),8)

                     299529

which of course agrees with the 1-liner:    FNE(123,8) -> 299529.

Also worth mentioning is the fact that my solution also works for P < 2, even for P = 1, P = 0 and P < 0 but then the resulting sequence is no longer in increasing order as is the case for P >= 2. For instance:

       P = 2       1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...           increasing, Ok

       P = 1.9     1, 1.9, 2.9, 3.61, ..., 13.369, 13.0321, ... not increasing
       P = Phi     1, 1.6180, 2.6180, 2.6180, 3.6180, ...       not increasing, repetitions
       P = 1       1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, ...      ditto
       P = 0       1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...      ditto
       P = -1      1, -1, 0, 1, 2, 0, 1, -1, 0, -2, -1, ...     ditto
       P = -2      1, -2, -1, 4, 5, 2, 3, -8, -7, -10, ...      ditto

Last but not least, this is my original solution for the HP-25, a simple 24-step affair:

       01  STO 0     13   *
       02  STO 1     14   RCL 1
       03  STO/ 1    15   *
       04  CLX       16   +
       05  X<>Y      17   RCL 0
       06  2         18   STO* 1
       07  /         19   Rv
       08  INT       20   X<>Y
       09  X<>Y      21   X#0
       10  LASTX     22   GTO 06
       11  FRAC      23   X<>Y
       12  2         24   GTO 00

For instance:

       FIX 0
       26, ENTER, 3, R/S -> 111
       61, ENTER, 3, R/S -> 361
       1000000, ENTER, 3, R/S -> 1726672221

So much for Tier 3, thanks a lot to Paul Dale for his interest in this particular tier and for taking the time to create a nice 24-step solution for the HP-25 as well. In the next days I'll post my solutions for the subsequent tiers.

V.