Short & Sweet Math Challenge #11: Who's Next ? « Next Oldest | Next Newest »

Hi all,

After several months' leave of absence, here you are, a new S&SMC challenge to
brighten up your HP programming spirit. After challenges #1, #2, ...,
#9, and #10, "who's next" ? #11, you say ? And how on earth did you came to
that bold conclusion ?

Well, that's exactly the purpose of this S&SMC#11, to substantiate that
very conclusion of yours with hard facts ... well, more like 'soft'(ware) facts, actually. Enter

## The challenge

Try and write a program for any HP model that will accept a sequence of numbers, then produce
its prediction for the next element of the sequence.

For instance:
• Given the sequence 1,2,3,4,5,6,7,8,9,10, your program should
produce the value 11.

• Given the sequence 11,13,15,17,19, your program should
produce the value 21.

• Given the sequence -9,-16,-25,-36, your program should
produce the value -49.

Your program must accept any number of elements (at least 2), then produce
the simplest reasonable prediction for the next element. No provisions
should be taken to predict further elements, just the next one.

Of course, mathematically speaking there's always a choice in selecting the
next element of an arbitrary sequence, as an infinite number of sequences are possible initially having the very same elements. Thus, for instance, the sequence:

```       0, 1
```
might continue like this:
```       0, 1 ->  2, 3, 4, 5, ...
```
or like this:
```       0, 1 ->  0, 1, 0, 1, ...
```

among infinite other possibilities. In this particular example, choosing
2 for the next element is simplest because in the given sequence, going
from 0 to 1 entails a (+1) increment and lacking any more information it
seems simpler to stay with it than unexpectedly reverse it to (-1) for
no apparent reason. So, given the sequence above (0,1), your program is
expected to predict 2 as the next element, not 0 or any other value.

Put your program to the test

Use your program to produce the next element for the following 11 test cases:

1. : 11, 13, 15, 17, 19, ?

2. : -9, -16, -25, -36, ?

3. : 8, 27, 64, 125, 216, ?

4. : 0, 0.01, 0.32, 2.43, 10.24, 31.25, ?

5. : 2, -3, -4, -1, 6, ?

6. : (in radians) sin(0), sin(0.1), sin(0.2), sin(0.3), sin(0.4), ?

7. : Ln(1), Ln(1.1), Ln(1.2), Ln(1.3), Ln(1.4), ?

8. : Pieces of pancake (i.e: flat, 2D) obtained by N cuts: 1, 2, 4, 7, 11, ?

9. : Maximum number of electrons in layer N: 0, 2, 8, 18, 32, 50, ?

10. : Maximum number of pieces of (3D) cake we get with N cuts: 1, 2, 4, 8, 16, ?

11. : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, ?

Midway next week I'll post my solution (plus comments) for the HP-71B (which is
a simple, 3-line program) and I'll also provide an HP-15C version. You might want to try your hand at it this next weekend.

Caveat computat:

Absolutely refrain from using a PC, laptop, or PDA (unless running some HP calc emulator/simulator) to solve the challenge. A Mathematica, Visual Basic, C++, or Java solution is useless to the intended purposes of this challenge, in fact actually defeats them, and submitting one is to be considered unpolite behavior.

And who knows, you might find using your program a useful training for some outdated 'intelligence tests' ... :-)

Best regards from V.

Edited: 13 Oct 2005, 8:27 a.m.

```
>run
Next N? 1
Next N? 2
Next N? 3
Next N?
OK, what comes next? 4
Seq1=1
Seq2=2
Seq3=3
Next:4! Q.E.D. Baby!
>list
10 DIM N1(100) @ ON ERROR GOTO 20 @ INPUT "Next N? ";N @ C=C+1 @ N1(C)=N @ GOTO 10
20 IF C<2 THEN 10 ELSE INPUT "OK, what comes next? ";N
WRN:Line Too Long
30 FOR I=1 TO C @ DISP "Seq"&STR\$(I)&"="&STR\$(N1(I)) @ NEXT I @ DISP "Next:"&STR\$(N)&"! Q.E.D. Baby!"
```

I knew guys like me in college computer lab, in fact, I was a guy like me, who would look for the loophole in every computing problem they saw. The problem statement for this challenge is :

Quote:
"Try and write a program for any HP model that will accept a sequence of numbers, then produce its prediction for the next element of the sequence.

Then follows a list of sequences to try, ranging from the trivial to the Pretty Tricky(tm). None of that really engaged my "inner prankster," but this line did:

Quote:
Midway next week I'll post my solution (plus comments) for the HP-71B (which is a simple, 3-line program)

Impossible! Well, not quite. 8)

To belabor the possibly obvious point, the problem statement could have said "Try and write a program for any HP model that will accept only a sequence of numbers, then produce its prediction for the next element of the sequence." I would then have had less fun with this example. Also, the word "prediction" in the problem statement is obviously a euphemism. Computers don't make predictions, people do, sometimes based on the output of a computer. Given that ambiguity, I feel my usage in the above program fits the stated problem. 8)

I'll bet I can predict what comes next. haha.

Valentin,

I have a pretty good idea how to do that. There's actually an in built function that solves such issues. May we use any function of the 71B or 15C, or should we concentrate on primary functions ?

May I also kindly suggest you to propsoe solution on, say, 41C or 42S modes, as it is the easiest to transpose to any HP non cumputer calculator ?

Hi, Thibaut:

Thibaut posted:

"May we use any function of the 71B or 15C, or should we
concentrate on primary functions ?"

You may use whatever functions are available on any HP model, be they
built-in or in ROMs or whatever. If there are different
ways of doing it depending on the available functions you're
welcome to list them as well. The more, the merrier.

"May I also kindly suggest you to propsoe solution on, say, 41C or 42S modes, as it is the easiest to transpose to any HP non cumputer calculator ?"

If by "propsoe" you mean "propose" and by "modes" you mean "models", my proposal
is for each and every HP model and that of course includes both
the 41C and 42S. Perhaps you were mislead by my explicitly mentioning the HP-71B and HP-15C, but I was merely saying that I'll provide solutions for these particular models, not that only these models could be used.

Obviously, I can't provide a solution tailored for each specific model, so I chose these particular ones, the HP-71B because routines written for it are easiest to understand and thus convert to other machines, and the HP-15C as a worthy representation of the RPN programming paradigm. But other contributors are both welcome and expected to provide their solutions for other HP models.

Waiting for your clever inputs,

Best regards from V.

Hi,

Doesn't this just involve implementing Lagrange Interpolation?

http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html

.

That was my idea.

Sorry for the typos Valentin.

Here is a solution in UserRPL, tested on a 49G+ but should work fine on a 28S, too:

I decided to arrange the values as a function f(x) where x are integers ranging from 0 to n-1 for the given values, with f(0) (or f0 for short) being the last given value and f(n-1) the first. The extrapolated value to be computed is therefore f(-1) or fp for short. This an arbitrary decision but it is workable, as you can see.

My solution fits a polynomial of degree n-1 fo n given values:

```f(x) = a + b*x + c*x^2 + d*x^3 + ...
f(0) = a
f(1) = a +  b +  c +   d + ...
f(2) = a + 2b + 4c +  8d + ...
f(3) = a + 3b + 9c + 27d + ...
```

This has to solved for [ (a = f0) b c d ... ] and can be transformed into a matrix equation (here for degree 3, with 4 values given):

```[ 1  1  1  0 ] [ b  ]   [ f1 - f0 ]
[ 2  4  8  0 ] [ c  ] = [ f2 - f0 ]
[ 3  9 27  0 ] [ d  ]   [ f3 - f0 ]
[ 1 -1  1  1 ] [ fp ]   [ f0      ]
```

This is for the sequence { f3, f2, f1, f0, ? } with ? = fp.

The solution comes in two parts:

MKMAT: Create the matrix

```<< -> n
<< 1 n 1 -
FOR r               row counter
r
IF n 2 > THEN
2 n 1 -
FOR c           column counter
DUP r *
NEXT
END
0
NEXT
1                   last row
IF n 2 > THEN
2 n 1 -
FOR c
DUP NEG
NEXT
END
1                   very last element of matrix
{ n n } >ARRY       creates matrix
>>
>>
'MKMAT' STO>
```

SSMC11: Compute the solution.

Input is a {list} of values, like {11 13 15 17 19}.
The solution is appended to the list.

```<< DUP                   make a copy of the list,
OBJ> -> f0 n          expand to stack and save dimension n
and last element f0 in local variables
<< CASE n 2 <         Do nothing if list too short
THEN n 1 - DROPN
END
n 1 - >LIST        convert back to list (without f0)
-> f               save the list as local variable f
<< n MKMAT INV     create and invert the matrix
n 1 - 1
FOR i           backwards loop to reverse the list
f i GET f0 -  compute f(k)-f0 and leave on stack
-1 STEP
f0              last element of right hand side
{ n 1 } >ARRY   create column vector
*               solve the equation by matrix multiplication
n GET           pick fp (the predicted value) from result
+               append to original list (still on stack)
>>
END                end of CASE statement
>>
>>
'SSMC11' STO>
```

Solutions for test sequences #1 to #6 seem to be accurate.

#6 reveals a value of SIN(0.499989) (I used ASIN to convert back from the numeric value).

I didn' check #7 yet.

#8 reveals 16, #9 reveals 72 but I can't comment on the accuracy.

#10 dosn't work out correctly, the result is 31 instead of 32. The polynomial cannot correctly approximate an exponential function.

#11 reveals 11; obviously the polynomial is heavily oscillating.

Marcus

Hi, Marcus:

Marcus posted:

"Here is a solution in UserRPL, tested on a 49G+ but should work fine on a 28S, too [...] My solution fits a polynomial of degree n-1 fo n given values"

Thanks for your interesting contribution, but that's really overkill ! :-) The goal asked by the challenge, namely to produce the next element of the sequence, can be met by a simple 19-step RPN program for the HP-15C or a one-line program for the HP-71B, which, apart from being much shorter and faster than constructing and then solving a whole system of linear equations to find the coefficients of a polynomial which is then evaluated, they also do not use the large amounts of RAM that your approach requires.

"#10 dosn't work out correctly, the result is 31 instead of 32. The polynomial cannot correctly approximate an exponential function."

Here you are, a new challenge just for you: to try and get more than 31 pieces ouf of a 3D-cake with the next cut. You'll find it impossible, 31 is the correct solution and there's no exponential to be seen here.

Thanks again for contributing and

Best regards from V.

The original author edited out one minor typo

Edited: 17 Oct 2005, 8:55 a.m. after one or more responses were posted

Quote:
Maximum number of pieces of (3D) cake we get with N cuts: 1, 2, 4, 8, 16, ?

Quote:
Here you are, a new challenge just for you: to try and get more than 31 pieces ouf of a 3D-cake with the next cut. You'll find it impossible, 31 is the correct solution and there's no exponential to be seen here.

Valentin,

I don't get the meaning of "cutting a 3D cake". If you simply look at the numbers, the next number is twice its predecessor. For me, this is just the exponential function 2^(n-1), n=1,2,... Computers don't cut cakes, they just deal with the numbers. For *me*, 31 is wrong and 32 should be the result.

Bram's solution seems to give the same results as mine. He must have looked up the resulting coefficients in a text book. Mathemtically, both solutions should be equivalent. But I must admit that, from a programmers standpoint, solving the equation each time is overkill...

What do you think is the best possible solution for case #11? I would say, a linear approximation (least squares) whould give a much more reasonable result than the polynomial.

Marcus

Hi again, Marcus:

Marcus posted:
"I don't get the meaning of "cutting a 3D cake".

You get a typical cake, any 3D-shape as long as it's convex;
a regular, cylindrical one will do. You then get some suitably
planar cutting object, say a knife, and give the cake a planar cut
along any plane that you like. You'll get 2 pieces. You then
proceed to administer the poor cake yet another cut, trying to
maximize the number of pieces you get. Lo and behold, you'll get
four pieces. And so on ... by the time you've administered five
such cuts, you'll be in posession of 31 pieces, not 32. Try it.

"If you simply look at the numbers, the next number is twice its predecessor."

That's a 'fortunate' coincidence and nobody told you to 'simply look at the numbers'. The exact wording
of test case #10 is:

```    10.: Maximum number of pieces of (3D) cake we get with N cuts: 1, 2, 4, 8, 16, ?
```
and it's very clearly stated from the start that said numbers represent maximum number of pieces of 3D cake we get with N cuts.
I don't see why you decide to ignore the challenge's terms and decide that you'll simply 'look at the numbers' instead. Of course, you're entitled to do that, if you feel like it, but then you're not entitled to be surprised when you fail to get the correct result.

"For me, this is just the exponential
function 2^(n-1), n=1,2,...

For me, as I clearly stated in the problem, this is a case of
cake-cutting, which happens to return a polynomial number of pieces, not an exponential one. You ignore the stated conditions at your own peril.

"Computers don't cut cakes, they just deal with the numbers. "

Computers don't 'just deal with numbers', they deal with complex electronic interactions between particles and fields and such. That you decide to interpret them as numbers, text, images, or sounds, is up to you.

"For *me*, 31 is wrong and 32 should be the result."

Fine with me. I'm not going to get into a quarrel with you for this, couldn't care less, actually. Your problem is, IMHO, that you don't read and/or understand what I stated in the challenge: there is an infinite number of functions f(x) that happen to include any given sequence of datapoints. Among them, you were asked to select the simplest, and mathematically, polynomials are far simpler than exponential functions.

To further eliminate ambiguities, I specifically stated that said values represented the number of pieces you get when administering planar cuts to a 3D cake. This narrows it all to polynomials, once again.

Of course, it goes without saying that I selected this example to make people intuitively fall for 32, an thus be annoyed that their programs were producing 31 instead. They would search for a bug, find none, search the web or experiment a little, and eventually be pleasantly surprised to discover there was no bug after all and their program was smarter than themselves because in real life, contrary to intuition, you do get 31 pieces of cake, not 32. Seems you haven't reached to that point yet.

(your reply to Bram) It's one way to compute the
next number, but who decides what is really meant with the given sequence?"

That would be *me*, because I am the one issuing the original challenge, and I clearly state that these numbers are pieces of cake, etc. So that's the meaning of the given sequence for this particular sequence in this
particular challenge that I, in particular, issued. :-)

Stop the weeping at having miserably fallen for #10 and have a look at these URLs: this one and this one, too

"What do you think is the best possible solution for case #11?"

Under the conditions given and clearly stated in the challenge, the best possible solution for case #11 is 11.

Thanks again for your interest and

Best regards from V.

Edited: 17 Oct 2005, 7:41 a.m.

Hi Valentin

I appreciated your challenge, as usual!

One question:
To further eliminate ambiguities, I specifically stated that said values represented the number of pieces you get when administering planar cuts to a 3D cake. This narrows it all to polynomials, once again.

How do you know (or demonstrate) that the number of pieces is given by a polynomial?

J-F

Hi, Jean-François:

Jean-François posted:

"How do you know (or demonstrate) that the number of pieces is given by a polynomial?"

It's a simple problem of combinatorics. I first read about it decades ago in some Martin Gardner's book about recreational mathematics.

You can find a lot of good references here:

Best regards from V.

Hi Valentin!

Quote:
They would search for a bug, find none, search the web or experiment a little, and eventually be pleasantly surprised to discover there was no bug after all and their program was smarter than themselves because in real life, contrary to intuition, you do get 31 pieces of cake, not 32. Seems you haven't reached to that point yet.

:-)

In the meantime I wasn't searching the internet but busily cutting a spherical "cake" with an imaginary knife in my head and I started to discover what the callenge meant. I had just been "looking at the numbers" before...

All your test cases were deliberately choosen to be represented by polynomials either excatly or with reasonable accuracy (ln, sin); therefore a polynomial fit would always produce the desired result.

Why is my program so overly complicated? I simply didn't remember any suitable formula, so I started from scratch and tried to figure one out for myself. On my 49g+ it just worked the way it was intended. Bram's solution (and yours will be too) is much more elegant, programming wise. From a mathematical standpoint, they are equivalent.

Hi Valentin,

I must admit that I didn't find the mathematical approach myself, but no problem: the challenge is in the programming.

So I wrote a program for my HP-48G:

```<< DUP OBJ-> 0 -> N S
<< 1 N
FOR I
-1 I 1 - ^ N I COMB * * 'S' STO+
NEXT
S + >>
>>
```
It reads a list with the series in it from the stack and adds the next element to the tail of this list. So {8 27 64 125 216} becomes {8 27 64 125 216 343}, ready for the next run (that will add 512).

```The program gives the following answers:
1.	21
2.	-49 (-(7^2))
3.	343 (7^3)
4.	77.76
5.	17
6.	0.479.. (=SIN(0.5))
7.	0.405.. (=LN(1.5))
8.	16
9.	72
10.	31
11.	11
and {0 1} => {0 1 2} as required
```

I wonder. Does #4 have a special "meaning"? I notice that the second decimal is increasing and that after 5 runs the prediction comes out (exactly?) 1000. That's kind of special, isn't it?

By the way, is it a coincidence that you came up with 11 test cases for this S&SMC#11 and that the answer of the 11th case is 11? I guess you did this on purpose ...

groeten,

Bram

Bram,

your results are the same as mine but your solution is way shorter! You admit that you didn't work out the math yourself but can you at least explain what your FOR loop is doing?

With pleasure, Marcus,

```1.	At first I didn't have a clue how to compute the next element.
It has something to do with curve fitting was all I could come up with.
2.	Someone posted a link
3.	I read and tried to understand the article
4.	I took formula (4), expanded it to a 4 point situation and
filled in all x's and y's for the "function" (1,a), (2,b), (3,c) and (4,d)
that I defined for my list of {a b c d} in order to compute (5,e)
5.	it appears that P(5)=e=-1.a+4.b-6.c+4.d
6.	I happen to spot Pascal's triangle in the "coefficients"
7.	I concluded that the general formula is the sum of (sign . binomial . element)
8.	sign = (-1)^(I-1), binomial = COMB(N,I), element = element from stack after OBJ->
9.	I tried the sigma-function on the HP-48G, but I couldn't figure out
how to get an indexed array or list element into the formula.
Fortunately the OBJ-> command converts a list into about the ideal format to process.
I need to know the length first to enter the FOR loop and
then one by one the elements are fed into the algorithm.
```

I was very surprised to achieve such a short program.

Bram,

your answer has just crossed my response to Valentin where I assumed you had the solution looked up in a text book. But you obviously did a lot of thinking yourself :-)

What I think can be easily proven (haven't it tried yet) is that both solutions are simply the same. Solving the matrix equation for the next element (named fp or f(-1) in my post) symbolically should reveal the very same coefficients.

Your solution is quite elegant! But I'm still not convinced that the polynomial approach is always the best solution. It's one way to compute the next number, but who decides what is really meant with the given sequence? (See me argument with Valentin about cutting a cake.)

Marcus

Quote:
(...) But I'm still not convinced that the polynomial approach is always the best solution. It's one way to compute the next number, but who decides what is really meant with the given sequence?

Initially I thought that my program would stock 19 as the next number into the list {21 22 25 27 29}, but polynomically you'll have to opt for 36. Apparently real life doesn't always chooses the simplest solution .... ;-)

Hi, Bram:

Bram posted:
"I must admit that I didn't find the mathematical approach myself, but no problem: the challenge is in the programming."

First of all, thanks for your continued interest in my S&SMCs and your kind contributions. I did find the mathematical approach myself, it's actually quite easy, but once you do, the programming is simple and the challenge, at least for me, is to optimize it as much as possible for program size, memory requirements and speed.

"So I wrote a program for my HP-48G:"

My original solutions (a 19-step RPN program for the HP-15C and a one-line program for the HP-71B) are quite similar to yours, except they're even simpler, making no use of the COMB functionality (which the HP-15C has but the HP-71B lacks), and thus can be easily
adapted to most any HP model, including the HP-25C, HP-10C, or
HP-12C, in 25 steps or so, say, with absolutely minimal memory requirements as no datapoints need be stored.

"The program gives the following answers:"

```      1.      21
2.      -49 (-(7^2))
3.      343 (7^3)
4.      77.76
5.      17
6.      0.479.. (=SIN(0.5))
7.      0.405.. (=LN(1.5))
8.      16
9.      72
10.     31
11.     11
and {0 1} => {0 1 2} as required
```

All of them absolutely correct, of course, except #6 and #7 return approximations to sin(0.5) and ln(1.5), not the exact values. Most people would think that #10 should be 32, but it isn't, you can't get more than 31 pieces by giving that number of planar cuts to a convex 3D-cake, here human intuition guesses 32 and flunks out.

"I wonder. Does #4 have a special "meaning"? I notice that the second decimal is increasing and that after 5 runs the prediction comes out (exactly?) 1000. That's kind of special, isn't it?"

Yes, the values for #4 were generated by y = x^5/100, for x from 0 to 5, so the next value is 6^5/100 = 7776/100 = 77.76, and you eventually get to 10^5/100 = 100000/100 = 1000, exactly. It was an attempt to obfuscate things a little by adding decimals, probably quite successful. Without the decimals (i.e.: 0, 1, 32, 243, 1024, 3125) the generating function is probably easier to guess (y = x^5).

"By the way, is it a coincidence that you came up with 11 test cases for this S&SMC#11 and that the answer of the 11th case is 11? I guess you did this on purpose ..."

Yes, that's no coincidence at all. :-) I thought it would be fun for smart readers like yourself to see S&SMC#11 include a test case #11 which features an 11-element sequence whose next element is precisely 11. :-) The nice touch is to make sure that this 11-element sequence looks interesting and its next element is far from obvious, so it comes as a nice surprise when you realize its value is exactly 11.

Best regards from V.

Hi, all:

Thanks to all of you interested in my S&SMC#11, most specially to those who contributed
their own solutions and comments.

S&SMC#11 asked for a program to compute the next element of a given
sequence. As some
of you observed, this could be considered a case of polynomial fitting,
where we first
compute the coefficients of a polynomial which includes all values in the sequence,
then we evaluate the polynomial to get the next value.

However, though workable, this is simply overkill as we're not interested
in making
further predictions or interpolations, just getting the very next element,
so we can
do without the complexity, time, and memory resources necessary for a full-fledged
polynomial fit. We'll use a much simpler mechanism, based in
finite differences.

The details are better understood with an example. Imagine we're asked to predict
the next element of the sequence which begins (8, 27, 64, 125). We then form the
following disposition, where the first row contains the sequence's elements and each
number in the rows below is computed as the difference of the two above it, like this:

```                      n1    n2    n3   n4
---------------------
original sequence:   8    27    64   125
1st differences:     19   37    61       (19 = 27- 8, 37 = 64-27, 61 = 125-64)
2nd differences:        18   24          (18 = 37-19, 24 = 61-37)
3rd differences:           6             ( 6 = 24-18)
```
where we stop as soon as there's a single value in the last row. Now,
to predict the
next element, lacking futher information we simply assume that the last, Nth differences
are constant, and proceed to compute the next entries adding upwards,
row by row, like this:
```                      n1     n2    n3   n4      n5
-------------------------------
original sequence:   8     27    64   125 ..  216   (predicted next element = 125 + 91)
1st differences:     19    37    61 ..   91       (91 = 61 + 30
2nd differences:        18    24 ..  30           (30 = 24 + 6)
3rd differences:           6  ..  6               (3rd differences are constant = 6)
```
and so we get 216 as the predicted value for the next element.
In this particular case,
the original elements were 2^3, 3^3, 4^3 and 5^3, so we would expect 6^3 to
be the next element, which it is (6^3 = 216).

Given this simple, finite-difference algorithm, we could write a short program to
input the original sequence, then compute the finite differences to form a triangular
disposition as seen above, and use it to obtain the predicted next value. But we can
proceed more economically by having a closer look at how the predicted value
is computed. In the example above, the predicted value (216) is computed like this:

```   216 = 125 + 91
= 125 + 61 + 30
= 125 + 61 + 24 + 6
= 125 + (125-64) + 24 + 6
= 125 + (125-64) + (125-64)-(64-27) + 6
= 125 + (125-64) + (125-64)-(64-27) + [(125-64)-(64-27)]-[(64-27)-(27-8)]
= 125 + 125 - 64 + 125 - 64 - 64 + 27 + 125 - 64 - 64 + 27 - 64 + 27 + 27 -8
= 125*4 - 64*6 + 27*4 - 8
```
this is, in the notation above:
```    n5 = n4*4 - n3*6 + n2*4 - n1
```
Doing likewise with 5- and 6-point sequences, we similarly get:
```    n6 = n5*5 - n4*10 + n3*10 - n2*5 + n1
```
and
```    n7 = n6*6 - n5*15 + n4*20 - n3*15 + n2*6 - n1
```
and the coefficients which multiply the n's immediately reminds us of
Pascal's triangle:
```             1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5   10  10  5   1
1  6   15  20  15  6   1
```
where each number is the sum of the two above it. But every element
in each row of
Pascal's triangle is given by a binomial coefficient C(m,n)
(number of combinations
of m elements taken n at a time
), so, for the last row above we have:
```    n7 = n6*C(6,5) - n5*C(6,4) + n4*C(6,3) - n3*C(6,2) + n2*C(6,1) - n1*C(6,0)
```
and similarly for the general case. This can be readily implemented in any HP model,
no matter how small (say HP-10C, HP-12C, HP-25), because:
• no elements need to be stored: each is used only once, so they can
be input one
at a time, interactively, to be immediately used.

• no need to compute each C(m,n) = m!/n!/(m-n)!, because each binomial coefficient
can be computed from the preceding one by performing just one
integer multiplication and one integer division.
Here's the resulting 19-step RPN program for the HP-15C:
```   LBL A
STO I     store the number of elements
1       initialize an auxiliar counter
CHS
STO 0
STO 1     initialize running binomial coefficient
CLX      initialize running sum
*LBL 0
R/S      accept input from the user
RCL 1     update binomial coefficient
RCL* I
RCL/ 0
STO 1
*       update running sum
+
DSE 0     update auxiliar counter
*LBL 0
DSE I     update primary counter
GTO 0     if not done, go for another input
done, stop with next element in display
```
which uses no allocatable registers (just the permanent registers R0, R1, RI) and
works very fast for any number of elements. The sequence's elements are introduced
one at a time, in reverse order (this saves a few extra steps at no cost since you
press exactly the same keystrokes as you would if entering them in order). Here's
a couple of trial runs:
```Sequence 8, 27, 64, 125, ?
FIX 2
4  [A]  125 [R/S]  64 [R/S]  27 [R/S]  8 [R/S] -> 216.00
Sequence 0, 0.01, 0.32, 2.43, 10.24, 31.25, ?
6  [A]  31.25 [R/S] 10.24 [R/S]  2.43 [R/S]
0.32 [R/S]  0.01 [R/S]     0 [R/S] ->  77.76
```
This program can be very easily translated to most any HP model, an HP-25 version
or HP-12C version are about 25 steps long. It can also be converted straight
away to an HP-71B version, namely the following one-liner
(78 bytes):
```1 INPUT "N=";I @ A=I+1 @ B=1 @ S=0 @ FOR I=-I TO -1 @ INPUT "X=";X @ B=B*I/(A+I) @ S=S-X*B @ NEXT I @ DISP S
```
Trial run, test 4: 0, 0.01, 0.32,2.43, 10.24, 31.25, ?
```>RUN
N=6      [ENTER]
X=31.25  [ENTER]
X=10.24  [ENTER]
X=2.43   [ENTER]
X=0.32   [ENTER]
X=0.01   [ENTER]
X=0      [ENTER]
77.76
```
That's all. Thanks again for your interest and

Best regards from V.

Thanks, and as usual it all looks so simple now.
I will try to find time to get it working on my 55.

However, I have always been reluctant to use interpoling beyond the interval where I have data as it usually produces rubbish (unless you know which "physics" law to follow. Anyone knows of rules validating the use of interpolation beyond the interval?

Thanks,

Arnaud

Edited: 18 Oct 2005, 10:52 a.m.

Hi Valentin,

Thank you for your explanations and your programs, which are very compact indeed. The first one runs on my HP-32SII apart from the duplicate label. The 32SII doesn't allow this. As it is a dummy line to ignore a skip of the DSE 0, it can of course be replaced with another label.

All in all it was nice exercising.

Valentin --

Thanks for posting a clever and interesting exercise. The method and HP-15C program you provided seems fairly clever; I'll try the HP-71B version when I get more proficient with it.

Curiously, while the program (adapted just slightly for the HP-41C and HP-42S) works as advertised for the examples you provided, it does not give the correct results for the simple Fibonacci sequence:

an+1 = an + an-1

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

I get either 0 or twice the correct value as the next term (depending upon how many terms were specified).

I have not analyzed the technique to explain why this is so. Would you have some mathematical insights about this?

Thanks,

-- KS

The Fibonacci sequence isn't a polynomial sequence.

The nth term can be given in closed form

Fn = ((1 + sqr(5))^n - (1 - sqr(5))^n)/(sqr(5)*2^n)

I posted,

Quote:
Curiously, while the program (adapted just slightly for the HP-41C and HP-42S) works as advertised for the examples you provided, it does not give the correct results for the simple Fibonacci sequence:

an+1 = an + an-1

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

I get either 0 or twice the correct value as the next term an+1(depending upon how many terms were specified).

The program gives 0 as the next term an+1 for odd n > 1; it gives double the correct value of the next term for even n > 1. So, if an+1 represents the correct value of the next term,

an+1 * [1 + (-1)n] is returned.

It's somewhat correct... ;-)

-- KS

That was my concern, see message 21 above. However I didn't have time to find an example. I didn't have time to think about the challenge either but I wouldn't have found the answer, exactly because of this.

Arnaud

Hi, Karl:

Karl posted:

Yes, the finite difference algorithm my solution implements will produce the 'correct' next element (in the sense given) for any sequence generated by evaluating polynomials of any degree at equally spaced data points.

The Fibonacci sequence you give is usually defined as a linear recurrence, in which the Nth term depends on a linear combination of preceding terms. These kind of recurrences usually result in sequences generated by either exponentials or trigonometrics (which are nothing more than exponentials for complex arguments), but not polynomials except in degenerate cases.

Your sequence is 1,1,2,3,5,8,13,21,..., where each term is computed from the preceding ones like this:

```      an+2 = an+1 + an
```
i.e., each term is the sum of the two preceding ones. Thus, its nth-term can be expressed as a function of n in this way:
```      a(n) = C1.x1n + C2.x2n
```
where C1,C2 are suitable constants and x1,x2 are the two roots of the equation associated to the recurrence, namely (notice how closely it mimics the form of the recurrence itself):
```      x2 = x + 1
```
so x1 and x2 are, respectively, (1+sqr(5))/2 and (1-sqr(5))/2,
and you can determine C1,C2 by making use of the initial
conditions:
```     a(1) = 1
a(2) = 1
```
resulting in the values:
```     C1 = 1/sqr(5)
C2 = -1/sqr(5)
```
so you finally get:
```     a(n) = (((1+SQR(5))/2)^n-((1-SQR(5))/2)^n)/SQR(5)
```
which, certainly, it's *not* a polynomial.

If the roots of the associated equation turned out to be complex, then the general term would involve trigonometrics, but the details are fairly similar. Which is more, you can leave everything the same, with exponentials of imaginary values, and if your HP model allows you to compute them, it would work perfectly Ok.

After all, who needs a sin(x) function when you can compute it as (e^(i*x) - e^(-i*x))/(2*i) ? :-)

Best regards from V.

Thank you, Valentin -- an excellent and informative explanation, as usual.

The test case 4 sequence:

0, 0.01, 0.32, 2.43, 10.24, 31.25

I could ask what its definition is, but I expect that I could find out by running your recently-posted HP-71B polynomial curve-fitting routine. Could the HP-41C Stat Pac PC-F routine also find it (maximum order = 3)?

-- KS

Hi, Karl:

Karl posted:

"Thank you, Valentin -- an excellent and informative explanation, as usual."

You're welcome, I'm really fortunate to have such kind, keen, and appreciative 'readers'. :-)

"The test case 4 sequence: 0, 0.01, 0.32, 2.43, 10.24, 31.25
I could ask what its definition is, but I expect that I could find out by running your recently-posted HP-71B polynomial curve-fitting routine. Could the HP-41C Stat Pac PC-F routine also find it (maximum order = 3)?"
.

It is:

```     P(x) = (x^5)/100
```
for x= 0,1,...,5 and yes, any curve-fitting routine worth its salt can find it, provided it copes with degrees up to 5, so perhaps the PC-F routine will be unable to find this one (the best a 3rd-degree polynomial can achieve with these data is to have an absolute maximum error H=0.52, see below). Next element is, of course, (6^5)/100 = 7776/100 = 77.76.

My HP-71B Minimax Polynomial program that you mention can (of course!!) find this, but it's absolutely overkill ! We have an idiom in Spanish for this, namely "Matar moscas a cañonazos" which literally means " To kill flies with a canon" but properly translates in English as "To crack a nut with a sledgehammer". Nevertheless, a sample run of my program goes as follows:

```   >CAT
MINIMAXP   BASIC  3018 07/09/04 06:14
>RUN
Verbose ? (Y/N):  N
[K]bd,[D]ef,[F]ile=  K
# Points=  6
#1: X,Y=  0,0
#2: X,Y=  1,0.01
#3: X,Y=  2,0.32
#4: X,Y=  3,2.43
#5: X,Y=  4,10.24
#6: X,Y=  5,31.25
Store in  *
Degree=
Max. error=  0
Degree 1 ... H= 8.16000000000   (max. error for a 1st-degree polynomial)
Degree 2 ... H= 2.76666666690   (max. error for a 2nd-degree polynomial)
Degree 3 ... H= 0.52000000000   (max. error for a 3rd-degree polynomial)
Degree 4 ... H= 0.03750000000   (max. error for a 4th-degree polynomial)
Degree 5 ... H= 0.00000000000   (max. error for a 5th-degree polynomial)
A0= 0.00000000000
A1= 0.00000000000
A2= 0.00000000000
A3= 0.00000000000
A4= 0.00000000000
A5= 0.01000000000
```
Thus, it has found that these datapoints are perfectly represented (absolute maximum error H = 0.00000000000) by the 5th-degree polynomial:
```       P(x) = A5*x^5 = 0.01*x^5 = (x^5)/100
```

Thanks again for your interest and kind words and

Best regards from V.

Edited: 21 Oct 2005, 4:34 a.m.

 Possibly Related Threads... Thread Author Replies Views Last Post Need help understanding math.... cyrille de Brébisson 9 1,048 12-13-2013, 02:23 AM Last Post: Didier Lachieze HP Prime - Short "learning" modules CR Haeger 1 382 11-27-2013, 02:13 PM Last Post: Jonathan Cameron I have written a short introduction to the HP Prime Michael Carey 7 869 11-18-2013, 08:04 PM Last Post: Michael Carey HP-65 short circuit Ignacio Sánchez 2 451 10-22-2013, 08:27 AM Last Post: Ignacio Sánchez Reig OT: a math competition site Pier Aiello 0 278 09-16-2013, 06:03 AM Last Post: Pier Aiello OT: Simulating a TI calculator with crazy 11-bit opcodes Egan Ford 8 815 08-13-2013, 12:06 AM Last Post: Paul Dale Simple Math Question Namir 2 401 08-09-2013, 06:13 PM Last Post: Eddie W. Shore Cool math clock Bruce Bergman 28 2,068 04-10-2013, 03:13 AM Last Post: Siegfried (Austria) FRAM71 for HP-71B, short update #3 Hans Brueggemann 15 1,158 01-20-2013, 10:22 AM Last Post: Jerry Raia Math Challenge I could not solve Meindert Kuipers 22 1,700 01-05-2013, 04:43 PM Last Post: Thomas Klemm

Forum Jump:
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
Short & Sweet Math Challenge #11: Who's Next ? « Next Oldest | Next Newest »

Hi all,

After several months' leave of absence, here you are, a new S&SMC challenge to
brighten up your HP programming spirit. After challenges #1, #2, ...,
#9, and #10, "who's next" ? #11, you say ? And how on earth did you came to
that bold conclusion ?

Well, that's exactly the purpose of this S&SMC#11, to substantiate that
very conclusion of yours with hard facts ... well, more like 'soft'(ware) facts, actually. Enter

## The challenge

Try and write a program for any HP model that will accept a sequence of numbers, then produce
its prediction for the next element of the sequence.

For instance:
• Given the sequence 1,2,3,4,5,6,7,8,9,10, your program should
produce the value 11.

• Given the sequence 11,13,15,17,19, your program should
produce the value 21.

• Given the sequence -9,-16,-25,-36, your program should
produce the value -49.

Your program must accept any number of elements (at least 2), then produce
the simplest reasonable prediction for the next element. No provisions
should be taken to predict further elements, just the next one.

Of course, mathematically speaking there's always a choice in selecting the
next element of an arbitrary sequence, as an infinite number of sequences are possible initially having the very same elements. Thus, for instance, the sequence:

```       0, 1
```
might continue like this:
```       0, 1 ->  2, 3, 4, 5, ...
```
or like this:
```       0, 1 ->  0, 1, 0, 1, ...
```

among infinite other possibilities. In this particular example, choosing
2 for the next element is simplest because in the given sequence, going
from 0 to 1 entails a (+1) increment and lacking any more information it
seems simpler to stay with it than unexpectedly reverse it to (-1) for
no apparent reason. So, given the sequence above (0,1), your program is
expected to predict 2 as the next element, not 0 or any other value.

Put your program to the test

Use your program to produce the next element for the following 11 test cases:

1. : 11, 13, 15, 17, 19, ?

2. : -9, -16, -25, -36, ?

3. : 8, 27, 64, 125, 216, ?

4. : 0, 0.01, 0.32, 2.43, 10.24, 31.25, ?

5. : 2, -3, -4, -1, 6, ?

6. : (in radians) sin(0), sin(0.1), sin(0.2), sin(0.3), sin(0.4), ?

7. : Ln(1), Ln(1.1), Ln(1.2), Ln(1.3), Ln(1.4), ?

8. : Pieces of pancake (i.e: flat, 2D) obtained by N cuts: 1, 2, 4, 7, 11, ?

9. : Maximum number of electrons in layer N: 0, 2, 8, 18, 32, 50, ?

10. : Maximum number of pieces of (3D) cake we get with N cuts: 1, 2, 4, 8, 16, ?

11. : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, ?

Midway next week I'll post my solution (plus comments) for the HP-71B (which is
a simple, 3-line program) and I'll also provide an HP-15C version. You might want to try your hand at it this next weekend.

Caveat computat:

Absolutely refrain from using a PC, laptop, or PDA (unless running some HP calc emulator/simulator) to solve the challenge. A Mathematica, Visual Basic, C++, or Java solution is useless to the intended purposes of this challenge, in fact actually defeats them, and submitting one is to be considered unpolite behavior.

And who knows, you might find using your program a useful training for some outdated 'intelligence tests' ... :-)

Best regards from V.

Edited: 13 Oct 2005, 8:27 a.m.

```
>run
Next N? 1
Next N? 2
Next N? 3
Next N?
OK, what comes next? 4
Seq1=1
Seq2=2
Seq3=3
Next:4! Q.E.D. Baby!
>list
10 DIM N1(100) @ ON ERROR GOTO 20 @ INPUT "Next N? ";N @ C=C+1 @ N1(C)=N @ GOTO 10
20 IF C<2 THEN 10 ELSE INPUT "OK, what comes next? ";N
WRN:Line Too Long
30 FOR I=1 TO C @ DISP "Seq"&STR\$(I)&"="&STR\$(N1(I)) @ NEXT I @ DISP "Next:"&STR\$(N)&"! Q.E.D. Baby!"
```

I knew guys like me in college computer lab, in fact, I was a guy like me, who would look for the loophole in every computing problem they saw. The problem statement for this challenge is :

Quote:
"Try and write a program for any HP model that will accept a sequence of numbers, then produce its prediction for the next element of the sequence.

Then follows a list of sequences to try, ranging from the trivial to the Pretty Tricky(tm). None of that really engaged my "inner prankster," but this line did:

Quote:
Midway next week I'll post my solution (plus comments) for the HP-71B (which is a simple, 3-line program)

Impossible! Well, not quite. 8)

To belabor the possibly obvious point, the problem statement could have said "Try and write a program for any HP model that will accept only a sequence of numbers, then produce its prediction for the next element of the sequence." I would then have had less fun with this example. Also, the word "prediction" in the problem statement is obviously a euphemism. Computers don't make predictions, people do, sometimes based on the output of a computer. Given that ambiguity, I feel my usage in the above program fits the stated problem. 8)

I'll bet I can predict what comes next. haha.

Valentin,

I have a pretty good idea how to do that. There's actually an in built function that solves such issues. May we use any function of the 71B or 15C, or should we concentrate on primary functions ?

May I also kindly suggest you to propsoe solution on, say, 41C or 42S modes, as it is the easiest to transpose to any HP non cumputer calculator ?

Hi, Thibaut:

Thibaut posted:

"May we use any function of the 71B or 15C, or should we
concentrate on primary functions ?"

You may use whatever functions are available on any HP model, be they
built-in or in ROMs or whatever. If there are different
ways of doing it depending on the available functions you're
welcome to list them as well. The more, the merrier.

"May I also kindly suggest you to propsoe solution on, say, 41C or 42S modes, as it is the easiest to transpose to any HP non cumputer calculator ?"

If by "propsoe" you mean "propose" and by "modes" you mean "models", my proposal
is for each and every HP model and that of course includes both
the 41C and 42S. Perhaps you were mislead by my explicitly mentioning the HP-71B and HP-15C, but I was merely saying that I'll provide solutions for these particular models, not that only these models could be used.

Obviously, I can't provide a solution tailored for each specific model, so I chose these particular ones, the HP-71B because routines written for it are easiest to understand and thus convert to other machines, and the HP-15C as a worthy representation of the RPN programming paradigm. But other contributors are both welcome and expected to provide their solutions for other HP models.

Waiting for your clever inputs,

Best regards from V.

Hi,

Doesn't this just involve implementing Lagrange Interpolation?

http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html

.

That was my idea.

Sorry for the typos Valentin.

Here is a solution in UserRPL, tested on a 49G+ but should work fine on a 28S, too:

I decided to arrange the values as a function f(x) where x are integers ranging from 0 to n-1 for the given values, with f(0) (or f0 for short) being the last given value and f(n-1) the first. The extrapolated value to be computed is therefore f(-1) or fp for short. This an arbitrary decision but it is workable, as you can see.

My solution fits a polynomial of degree n-1 fo n given values:

```f(x) = a + b*x + c*x^2 + d*x^3 + ...
f(0) = a
f(1) = a +  b +  c +   d + ...
f(2) = a + 2b + 4c +  8d + ...
f(3) = a + 3b + 9c + 27d + ...
```

This has to solved for [ (a = f0) b c d ... ] and can be transformed into a matrix equation (here for degree 3, with 4 values given):

```[ 1  1  1  0 ] [ b  ]   [ f1 - f0 ]
[ 2  4  8  0 ] [ c  ] = [ f2 - f0 ]
[ 3  9 27  0 ] [ d  ]   [ f3 - f0 ]
[ 1 -1  1  1 ] [ fp ]   [ f0      ]
```

This is for the sequence { f3, f2, f1, f0, ? } with ? = fp.

The solution comes in two parts:

MKMAT: Create the matrix

```<< -> n
<< 1 n 1 -
FOR r               row counter
r
IF n 2 > THEN
2 n 1 -
FOR c           column counter
DUP r *
NEXT
END
0
NEXT
1                   last row
IF n 2 > THEN
2 n 1 -
FOR c
DUP NEG
NEXT
END
1                   very last element of matrix
{ n n } >ARRY       creates matrix
>>
>>
'MKMAT' STO>
```

SSMC11: Compute the solution.

Input is a {list} of values, like {11 13 15 17 19}.
The solution is appended to the list.

```<< DUP                   make a copy of the list,
OBJ> -> f0 n          expand to stack and save dimension n
and last element f0 in local variables
<< CASE n 2 <         Do nothing if list too short
THEN n 1 - DROPN
END
n 1 - >LIST        convert back to list (without f0)
-> f               save the list as local variable f
<< n MKMAT INV     create and invert the matrix
n 1 - 1
FOR i           backwards loop to reverse the list
f i GET f0 -  compute f(k)-f0 and leave on stack
-1 STEP
f0              last element of right hand side
{ n 1 } >ARRY   create column vector
*               solve the equation by matrix multiplication
n GET           pick fp (the predicted value) from result
+               append to original list (still on stack)
>>
END                end of CASE statement
>>
>>
'SSMC11' STO>
```

Solutions for test sequences #1 to #6 seem to be accurate.

#6 reveals a value of SIN(0.499989) (I used ASIN to convert back from the numeric value).

I didn' check #7 yet.

#8 reveals 16, #9 reveals 72 but I can't comment on the accuracy.

#10 dosn't work out correctly, the result is 31 instead of 32. The polynomial cannot correctly approximate an exponential function.

#11 reveals 11; obviously the polynomial is heavily oscillating.

Marcus

Hi, Marcus:

Marcus posted:

"Here is a solution in UserRPL, tested on a 49G+ but should work fine on a 28S, too [...] My solution fits a polynomial of degree n-1 fo n given values"

Thanks for your interesting contribution, but that's really overkill ! :-) The goal asked by the challenge, namely to produce the next element of the sequence, can be met by a simple 19-step RPN program for the HP-15C or a one-line program for the HP-71B, which, apart from being much shorter and faster than constructing and then solving a whole system of linear equations to find the coefficients of a polynomial which is then evaluated, they also do not use the large amounts of RAM that your approach requires.

"#10 dosn't work out correctly, the result is 31 instead of 32. The polynomial cannot correctly approximate an exponential function."

Here you are, a new challenge just for you: to try and get more than 31 pieces ouf of a 3D-cake with the next cut. You'll find it impossible, 31 is the correct solution and there's no exponential to be seen here.

Thanks again for contributing and

Best regards from V.

The original author edited out one minor typo

Edited: 17 Oct 2005, 8:55 a.m. after one or more responses were posted

Quote:
Maximum number of pieces of (3D) cake we get with N cuts: 1, 2, 4, 8, 16, ?

Quote:
Here you are, a new challenge just for you: to try and get more than 31 pieces ouf of a 3D-cake with the next cut. You'll find it impossible, 31 is the correct solution and there's no exponential to be seen here.

Valentin,

I don't get the meaning of "cutting a 3D cake". If you simply look at the numbers, the next number is twice its predecessor. For me, this is just the exponential function 2^(n-1), n=1,2,... Computers don't cut cakes, they just deal with the numbers. For *me*, 31 is wrong and 32 should be the result.

Bram's solution seems to give the same results as mine. He must have looked up the resulting coefficients in a text book. Mathemtically, both solutions should be equivalent. But I must admit that, from a programmers standpoint, solving the equation each time is overkill...

What do you think is the best possible solution for case #11? I would say, a linear approximation (least squares) whould give a much more reasonable result than the polynomial.

Marcus

Hi again, Marcus:

Marcus posted:
"I don't get the meaning of "cutting a 3D cake".

You get a typical cake, any 3D-shape as long as it's convex;
a regular, cylindrical one will do. You then get some suitably
planar cutting object, say a knife, and give the cake a planar cut
along any plane that you like. You'll get 2 pieces. You then
proceed to administer the poor cake yet another cut, trying to
maximize the number of pieces you get. Lo and behold, you'll get
four pieces. And so on ... by the time you've administered five
such cuts, you'll be in posession of 31 pieces, not 32. Try it.

"If you simply look at the numbers, the next number is twice its predecessor."

That's a 'fortunate' coincidence and nobody told you to 'simply look at the numbers'. The exact wording
of test case #10 is:

```    10.: Maximum number of pieces of (3D) cake we get with N cuts: 1, 2, 4, 8, 16, ?
```
and it's very clearly stated from the start that said numbers represent maximum number of pieces of 3D cake we get with N cuts.
I don't see why you decide to ignore the challenge's terms and decide that you'll simply 'look at the numbers' instead. Of course, you're entitled to do that, if you feel like it, but then you're not entitled to be surprised when you fail to get the correct result.

"For me, this is just the exponential
function 2^(n-1), n=1,2,...

For me, as I clearly stated in the problem, this is a case of
cake-cutting, which happens to return a polynomial number of pieces, not an exponential one. You ignore the stated conditions at your own peril.

"Computers don't cut cakes, they just deal with the numbers. "

Computers don't 'just deal with numbers', they deal with complex electronic interactions between particles and fields and such. That you decide to interpret them as numbers, text, images, or sounds, is up to you.

"For *me*, 31 is wrong and 32 should be the result."

Fine with me. I'm not going to get into a quarrel with you for this, couldn't care less, actually. Your problem is, IMHO, that you don't read and/or understand what I stated in the challenge: there is an infinite number of functions f(x) that happen to include any given sequence of datapoints. Among them, you were asked to select the simplest, and mathematically, polynomials are far simpler than exponential functions.

To further eliminate ambiguities, I specifically stated that said values represented the number of pieces you get when administering planar cuts to a 3D cake. This narrows it all to polynomials, once again.

Of course, it goes without saying that I selected this example to make people intuitively fall for 32, an thus be annoyed that their programs were producing 31 instead. They would search for a bug, find none, search the web or experiment a little, and eventually be pleasantly surprised to discover there was no bug after all and their program was smarter than themselves because in real life, contrary to intuition, you do get 31 pieces of cake, not 32. Seems you haven't reached to that point yet.

(your reply to Bram) It's one way to compute the
next number, but who decides what is really meant with the given sequence?"

That would be *me*, because I am the one issuing the original challenge, and I clearly state that these numbers are pieces of cake, etc. So that's the meaning of the given sequence for this particular sequence in this
particular challenge that I, in particular, issued. :-)

Stop the weeping at having miserably fallen for #10 and have a look at these URLs: this one and this one, too

"What do you think is the best possible solution for case #11?"

Under the conditions given and clearly stated in the challenge, the best possible solution for case #11 is 11.

Thanks again for your interest and

Best regards from V.

Edited: 17 Oct 2005, 7:41 a.m.

Hi Valentin

I appreciated your challenge, as usual!

One question:
To further eliminate ambiguities, I specifically stated that said values represented the number of pieces you get when administering planar cuts to a 3D cake. This narrows it all to polynomials, once again.

How do you know (or demonstrate) that the number of pieces is given by a polynomial?

J-F

Hi, Jean-François:

Jean-François posted:

"How do you know (or demonstrate) that the number of pieces is given by a polynomial?"

It's a simple problem of combinatorics. I first read about it decades ago in some Martin Gardner's book about recreational mathematics.

You can find a lot of good references here:

Best regards from V.

Hi Valentin!

Quote:
They would search for a bug, find none, search the web or experiment a little, and eventually be pleasantly surprised to discover there was no bug after all and their program was smarter than themselves because in real life, contrary to intuition, you do get 31 pieces of cake, not 32. Seems you haven't reached to that point yet.

:-)

In the meantime I wasn't searching the internet but busily cutting a spherical "cake" with an imaginary knife in my head and I started to discover what the callenge meant. I had just been "looking at the numbers" before...

All your test cases were deliberately choosen to be represented by polynomials either excatly or with reasonable accuracy (ln, sin); therefore a polynomial fit would always produce the desired result.

Why is my program so overly complicated? I simply didn't remember any suitable formula, so I started from scratch and tried to figure one out for myself. On my 49g+ it just worked the way it was intended. Bram's solution (and yours will be too) is much more elegant, programming wise. From a mathematical standpoint, they are equivalent.

Hi Valentin,

I must admit that I didn't find the mathematical approach myself, but no problem: the challenge is in the programming.

So I wrote a program for my HP-48G:

```<< DUP OBJ-> 0 -> N S
<< 1 N
FOR I
-1 I 1 - ^ N I COMB * * 'S' STO+
NEXT
S + >>
>>
```
It reads a list with the series in it from the stack and adds the next element to the tail of this list. So {8 27 64 125 216} becomes {8 27 64 125 216 343}, ready for the next run (that will add 512).

```The program gives the following answers:
1.	21
2.	-49 (-(7^2))
3.	343 (7^3)
4.	77.76
5.	17
6.	0.479.. (=SIN(0.5))
7.	0.405.. (=LN(1.5))
8.	16
9.	72
10.	31
11.	11
and {0 1} => {0 1 2} as required
```

I wonder. Does #4 have a special "meaning"? I notice that the second decimal is increasing and that after 5 runs the prediction comes out (exactly?) 1000. That's kind of special, isn't it?

By the way, is it a coincidence that you came up with 11 test cases for this S&SMC#11 and that the answer of the 11th case is 11? I guess you did this on purpose ...

groeten,

Bram

Bram,

your results are the same as mine but your solution is way shorter! You admit that you didn't work out the math yourself but can you at least explain what your FOR loop is doing?

With pleasure, Marcus,

```1.	At first I didn't have a clue how to compute the next element.
It has something to do with curve fitting was all I could come up with.
2.	Someone posted a link
3.	I read and tried to understand the article
4.	I took formula (4), expanded it to a 4 point situation and
filled in all x's and y's for the "function" (1,a), (2,b), (3,c) and (4,d)
that I defined for my list of {a b c d} in order to compute (5,e)
5.	it appears that P(5)=e=-1.a+4.b-6.c+4.d
6.	I happen to spot Pascal's triangle in the "coefficients"
7.	I concluded that the general formula is the sum of (sign . binomial . element)
8.	sign = (-1)^(I-1), binomial = COMB(N,I), element = element from stack after OBJ->
9.	I tried the sigma-function on the HP-48G, but I couldn't figure out
how to get an indexed array or list element into the formula.
Fortunately the OBJ-> command converts a list into about the ideal format to process.
I need to know the length first to enter the FOR loop and
then one by one the elements are fed into the algorithm.
```

I was very surprised to achieve such a short program.

Bram,

your answer has just crossed my response to Valentin where I assumed you had the solution looked up in a text book. But you obviously did a lot of thinking yourself :-)

What I think can be easily proven (haven't it tried yet) is that both solutions are simply the same. Solving the matrix equation for the next element (named fp or f(-1) in my post) symbolically should reveal the very same coefficients.

Your solution is quite elegant! But I'm still not convinced that the polynomial approach is always the best solution. It's one way to compute the next number, but who decides what is really meant with the given sequence? (See me argument with Valentin about cutting a cake.)

Marcus

Quote:
(...) But I'm still not convinced that the polynomial approach is always the best solution. It's one way to compute the next number, but who decides what is really meant with the given sequence?

Initially I thought that my program would stock 19 as the next number into the list {21 22 25 27 29}, but polynomically you'll have to opt for 36. Apparently real life doesn't always chooses the simplest solution .... ;-)

Hi, Bram:

Bram posted:
"I must admit that I didn't find the mathematical approach myself, but no problem: the challenge is in the programming."

First of all, thanks for your continued interest in my S&SMCs and your kind contributions. I did find the mathematical approach myself, it's actually quite easy, but once you do, the programming is simple and the challenge, at least for me, is to optimize it as much as possible for program size, memory requirements and speed.

"So I wrote a program for my HP-48G:"

My original solutions (a 19-step RPN program for the HP-15C and a one-line program for the HP-71B) are quite similar to yours, except they're even simpler, making no use of the COMB functionality (which the HP-15C has but the HP-71B lacks), and thus can be easily
adapted to most any HP model, including the HP-25C, HP-10C, or
HP-12C, in 25 steps or so, say, with absolutely minimal memory requirements as no datapoints need be stored.

"The program gives the following answers:"

```      1.      21
2.      -49 (-(7^2))
3.      343 (7^3)
4.      77.76
5.      17
6.      0.479.. (=SIN(0.5))
7.      0.405.. (=LN(1.5))
8.      16
9.      72
10.     31
11.     11
and {0 1} => {0 1 2} as required
```

All of them absolutely correct, of course, except #6 and #7 return approximations to sin(0.5) and ln(1.5), not the exact values. Most people would think that #10 should be 32, but it isn't, you can't get more than 31 pieces by giving that number of planar cuts to a convex 3D-cake, here human intuition guesses 32 and flunks out.

"I wonder. Does #4 have a special "meaning"? I notice that the second decimal is increasing and that after 5 runs the prediction comes out (exactly?) 1000. That's kind of special, isn't it?"

Yes, the values for #4 were generated by y = x^5/100, for x from 0 to 5, so the next value is 6^5/100 = 7776/100 = 77.76, and you eventually get to 10^5/100 = 100000/100 = 1000, exactly. It was an attempt to obfuscate things a little by adding decimals, probably quite successful. Without the decimals (i.e.: 0, 1, 32, 243, 1024, 3125) the generating function is probably easier to guess (y = x^5).

"By the way, is it a coincidence that you came up with 11 test cases for this S&SMC#11 and that the answer of the 11th case is 11? I guess you did this on purpose ..."

Yes, that's no coincidence at all. :-) I thought it would be fun for smart readers like yourself to see S&SMC#11 include a test case #11 which features an 11-element sequence whose next element is precisely 11. :-) The nice touch is to make sure that this 11-element sequence looks interesting and its next element is far from obvious, so it comes as a nice surprise when you realize its value is exactly 11.

Best regards from V.

Hi, all:

Thanks to all of you interested in my S&SMC#11, most specially to those who contributed
their own solutions and comments.

S&SMC#11 asked for a program to compute the next element of a given
sequence. As some
of you observed, this could be considered a case of polynomial fitting,
where we first
compute the coefficients of a polynomial which includes all values in the sequence,
then we evaluate the polynomial to get the next value.

However, though workable, this is simply overkill as we're not interested
in making
further predictions or interpolations, just getting the very next element,
so we can
do without the complexity, time, and memory resources necessary for a full-fledged
polynomial fit. We'll use a much simpler mechanism, based in
finite differences.

The details are better understood with an example. Imagine we're asked to predict
the next element of the sequence which begins (8, 27, 64, 125). We then form the
following disposition, where the first row contains the sequence's elements and each
number in the rows below is computed as the difference of the two above it, like this:

```                      n1    n2    n3   n4
---------------------
original sequence:   8    27    64   125
1st differences:     19   37    61       (19 = 27- 8, 37 = 64-27, 61 = 125-64)
2nd differences:        18   24          (18 = 37-19, 24 = 61-37)
3rd differences:           6             ( 6 = 24-18)
```
where we stop as soon as there's a single value in the last row. Now,
to predict the
next element, lacking futher information we simply assume that the last, Nth differences
are constant, and proceed to compute the next entries adding upwards,
row by row, like this:
```                      n1     n2    n3   n4      n5
-------------------------------
original sequence:   8     27    64   125 ..  216   (predicted next element = 125 + 91)
1st differences:     19    37    61 ..   91       (91 = 61 + 30
2nd differences:        18    24 ..  30           (30 = 24 + 6)
3rd differences:           6  ..  6               (3rd differences are constant = 6)
```
and so we get 216 as the predicted value for the next element.
In this particular case,
the original elements were 2^3, 3^3, 4^3 and 5^3, so we would expect 6^3 to
be the next element, which it is (6^3 = 216).

Given this simple, finite-difference algorithm, we could write a short program to
input the original sequence, then compute the finite differences to form a triangular
disposition as seen above, and use it to obtain the predicted next value. But we can
proceed more economically by having a closer look at how the predicted value
is computed. In the example above, the predicted value (216) is computed like this:

```   216 = 125 + 91
= 125 + 61 + 30
= 125 + 61 + 24 + 6
= 125 + (125-64) + 24 + 6
= 125 + (125-64) + (125-64)-(64-27) + 6
= 125 + (125-64) + (125-64)-(64-27) + [(125-64)-(64-27)]-[(64-27)-(27-8)]
= 125 + 125 - 64 + 125 - 64 - 64 + 27 + 125 - 64 - 64 + 27 - 64 + 27 + 27 -8
= 125*4 - 64*6 + 27*4 - 8
```
this is, in the notation above:
```    n5 = n4*4 - n3*6 + n2*4 - n1
```
Doing likewise with 5- and 6-point sequences, we similarly get:
```    n6 = n5*5 - n4*10 + n3*10 - n2*5 + n1
```
and
```    n7 = n6*6 - n5*15 + n4*20 - n3*15 + n2*6 - n1
```
and the coefficients which multiply the n's immediately reminds us of
Pascal's triangle:
```             1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5   10  10  5   1
1  6   15  20  15  6   1
```
where each number is the sum of the two above it. But every element
in each row of
Pascal's triangle is given by a binomial coefficient C(m,n)
(number of combinations
of m elements taken n at a time
), so, for the last row above we have:
```    n7 = n6*C(6,5) - n5*C(6,4) + n4*C(6,3) - n3*C(6,2) + n2*C(6,1) - n1*C(6,0)
```
and similarly for the general case. This can be readily implemented in any HP model,
no matter how small (say HP-10C, HP-12C, HP-25), because:
• no elements need to be stored: each is used only once, so they can
be input one
at a time, interactively, to be immediately used.

• no need to compute each C(m,n) = m!/n!/(m-n)!, because each binomial coefficient
can be computed from the preceding one by performing just one
integer multiplication and one integer division.
Here's the resulting 19-step RPN program for the HP-15C:
```   LBL A
STO I     store the number of elements
1       initialize an auxiliar counter
CHS
STO 0
STO 1     initialize running binomial coefficient
CLX      initialize running sum
*LBL 0
R/S      accept input from the user
RCL 1     update binomial coefficient
RCL* I
RCL/ 0
STO 1
*       update running sum
+
DSE 0     update auxiliar counter
*LBL 0
DSE I     update primary counter
GTO 0     if not done, go for another input
done, stop with next element in display
```
which uses no allocatable registers (just the permanent registers R0, R1, RI) and
works very fast for any number of elements. The sequence's elements are introduced
one at a time, in reverse order (this saves a few extra steps at no cost since you
press exactly the same keystrokes as you would if entering them in order). Here's
a couple of trial runs:
```Sequence 8, 27, 64, 125, ?
FIX 2
4  [A]  125 [R/S]  64 [R/S]  27 [R/S]  8 [R/S] -> 216.00
Sequence 0, 0.01, 0.32, 2.43, 10.24, 31.25, ?
6  [A]  31.25 [R/S] 10.24 [R/S]  2.43 [R/S]
0.32 [R/S]  0.01 [R/S]     0 [R/S] ->  77.76
```
This program can be very easily translated to most any HP model, an HP-25 version
or HP-12C version are about 25 steps long. It can also be converted straight
away to an HP-71B version, namely the following one-liner
(78 bytes):
```1 INPUT "N=";I @ A=I+1 @ B=1 @ S=0 @ FOR I=-I TO -1 @ INPUT "X=";X @ B=B*I/(A+I) @ S=S-X*B @ NEXT I @ DISP S
```
Trial run, test 4: 0, 0.01, 0.32,2.43, 10.24, 31.25, ?
```>RUN
N=6      [ENTER]
X=31.25  [ENTER]
X=10.24  [ENTER]
X=2.43   [ENTER]
X=0.32   [ENTER]
X=0.01   [ENTER]
X=0      [ENTER]
77.76
```
That's all. Thanks again for your interest and

Best regards from V.

Thanks, and as usual it all looks so simple now.
I will try to find time to get it working on my 55.

However, I have always been reluctant to use interpoling beyond the interval where I have data as it usually produces rubbish (unless you know which "physics" law to follow. Anyone knows of rules validating the use of interpolation beyond the interval?

Thanks,

Arnaud

Edited: 18 Oct 2005, 10:52 a.m.

Hi Valentin,

Thank you for your explanations and your programs, which are very compact indeed. The first one runs on my HP-32SII apart from the duplicate label. The 32SII doesn't allow this. As it is a dummy line to ignore a skip of the DSE 0, it can of course be replaced with another label.

All in all it was nice exercising.

Valentin --

Thanks for posting a clever and interesting exercise. The method and HP-15C program you provided seems fairly clever; I'll try the HP-71B version when I get more proficient with it.

Curiously, while the program (adapted just slightly for the HP-41C and HP-42S) works as advertised for the examples you provided, it does not give the correct results for the simple Fibonacci sequence:

an+1 = an + an-1

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

I get either 0 or twice the correct value as the next term (depending upon how many terms were specified).

I have not analyzed the technique to explain why this is so. Would you have some mathematical insights about this?

Thanks,

-- KS

The Fibonacci sequence isn't a polynomial sequence.

The nth term can be given in closed form

Fn = ((1 + sqr(5))^n - (1 - sqr(5))^n)/(sqr(5)*2^n)

I posted,

Quote:
Curiously, while the program (adapted just slightly for the HP-41C and HP-42S) works as advertised for the examples you provided, it does not give the correct results for the simple Fibonacci sequence:

an+1 = an + an-1

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

I get either 0 or twice the correct value as the next term an+1(depending upon how many terms were specified).

The program gives 0 as the next term an+1 for odd n > 1; it gives double the correct value of the next term for even n > 1. So, if an+1 represents the correct value of the next term,

an+1 * [1 + (-1)n] is returned.

It's somewhat correct... ;-)

-- KS

That was my concern, see message 21 above. However I didn't have time to find an example. I didn't have time to think about the challenge either but I wouldn't have found the answer, exactly because of this.

Arnaud

Hi, Karl:

Karl posted:

Yes, the finite difference algorithm my solution implements will produce the 'correct' next element (in the sense given) for any sequence generated by evaluating polynomials of any degree at equally spaced data points.

The Fibonacci sequence you give is usually defined as a linear recurrence, in which the Nth term depends on a linear combination of preceding terms. These kind of recurrences usually result in sequences generated by either exponentials or trigonometrics (which are nothing more than exponentials for complex arguments), but not polynomials except in degenerate cases.

Your sequence is 1,1,2,3,5,8,13,21,..., where each term is computed from the preceding ones like this:

```      an+2 = an+1 + an
```
i.e., each term is the sum of the two preceding ones. Thus, its nth-term can be expressed as a function of n in this way:
```      a(n) = C1.x1n + C2.x2n
```
where C1,C2 are suitable constants and x1,x2 are the two roots of the equation associated to the recurrence, namely (notice how closely it mimics the form of the recurrence itself):
```      x2 = x + 1
```
so x1 and x2 are, respectively, (1+sqr(5))/2 and (1-sqr(5))/2,
and you can determine C1,C2 by making use of the initial
conditions:
```     a(1) = 1
a(2) = 1
```
resulting in the values:
```     C1 = 1/sqr(5)
C2 = -1/sqr(5)
```
so you finally get:
```     a(n) = (((1+SQR(5))/2)^n-((1-SQR(5))/2)^n)/SQR(5)
```
which, certainly, it's *not* a polynomial.

If the roots of the associated equation turned out to be complex, then the general term would involve trigonometrics, but the details are fairly similar. Which is more, you can leave everything the same, with exponentials of imaginary values, and if your HP model allows you to compute them, it would work perfectly Ok.

After all, who needs a sin(x) function when you can compute it as (e^(i*x) - e^(-i*x))/(2*i) ? :-)

Best regards from V.

Thank you, Valentin -- an excellent and informative explanation, as usual.

The test case 4 sequence:

0, 0.01, 0.32, 2.43, 10.24, 31.25

I could ask what its definition is, but I expect that I could find out by running your recently-posted HP-71B polynomial curve-fitting routine. Could the HP-41C Stat Pac PC-F routine also find it (maximum order = 3)?

-- KS

Hi, Karl:

Karl posted:

"Thank you, Valentin -- an excellent and informative explanation, as usual."

You're welcome, I'm really fortunate to have such kind, keen, and appreciative 'readers'. :-)

"The test case 4 sequence: 0, 0.01, 0.32, 2.43, 10.24, 31.25
I could ask what its definition is, but I expect that I could find out by running your recently-posted HP-71B polynomial curve-fitting routine. Could the HP-41C Stat Pac PC-F routine also find it (maximum order = 3)?"
.

It is:

```     P(x) = (x^5)/100
```
for x= 0,1,...,5 and yes, any curve-fitting routine worth its salt can find it, provided it copes with degrees up to 5, so perhaps the PC-F routine will be unable to find this one (the best a 3rd-degree polynomial can achieve with these data is to have an absolute maximum error H=0.52, see below). Next element is, of course, (6^5)/100 = 7776/100 = 77.76.

My HP-71B Minimax Polynomial program that you mention can (of course!!) find this, but it's absolutely overkill ! We have an idiom in Spanish for this, namely "Matar moscas a cañonazos" which literally means " To kill flies with a canon" but properly translates in English as "To crack a nut with a sledgehammer". Nevertheless, a sample run of my program goes as follows:

```   >CAT
MINIMAXP   BASIC  3018 07/09/04 06:14
>RUN
Verbose ? (Y/N):  N
[K]bd,[D]ef,[F]ile=  K
# Points=  6
#1: X,Y=  0,0
#2: X,Y=  1,0.01
#3: X,Y=  2,0.32
#4: X,Y=  3,2.43
#5: X,Y=  4,10.24
#6: X,Y=  5,31.25
Store in  *
Degree=
Max. error=  0
Degree 1 ... H= 8.16000000000   (max. error for a 1st-degree polynomial)
Degree 2 ... H= 2.76666666690   (max. error for a 2nd-degree polynomial)
Degree 3 ... H= 0.52000000000   (max. error for a 3rd-degree polynomial)
Degree 4 ... H= 0.03750000000   (max. error for a 4th-degree polynomial)
Degree 5 ... H= 0.00000000000   (max. error for a 5th-degree polynomial)
A0= 0.00000000000
A1= 0.00000000000
A2= 0.00000000000
A3= 0.00000000000
A4= 0.00000000000
A5= 0.01000000000
```
Thus, it has found that these datapoints are perfectly represented (absolute maximum error H = 0.00000000000) by the 5th-degree polynomial:
```       P(x) = A5*x^5 = 0.01*x^5 = (x^5)/100
```

Thanks again for your interest and kind words and

Best regards from V.

Edited: 21 Oct 2005, 4:34 a.m.

 Possibly Related Threads... Thread Author Replies Views Last Post Need help understanding math.... cyrille de Brébisson 9 1,048 12-13-2013, 02:23 AM Last Post: Didier Lachieze HP Prime - Short "learning" modules CR Haeger 1 382 11-27-2013, 02:13 PM Last Post: Jonathan Cameron I have written a short introduction to the HP Prime Michael Carey 7 869 11-18-2013, 08:04 PM Last Post: Michael Carey HP-65 short circuit Ignacio Sánchez 2 451 10-22-2013, 08:27 AM Last Post: Ignacio Sánchez Reig OT: a math competition site Pier Aiello 0 278 09-16-2013, 06:03 AM Last Post: Pier Aiello OT: Simulating a TI calculator with crazy 11-bit opcodes Egan Ford 8 815 08-13-2013, 12:06 AM Last Post: Paul Dale Simple Math Question Namir 2 401 08-09-2013, 06:13 PM Last Post: Eddie W. Shore Cool math clock Bruce Bergman 28 2,068 04-10-2013, 03:13 AM Last Post: Siegfried (Austria) FRAM71 for HP-71B, short update #3 Hans Brueggemann 15 1,158 01-20-2013, 10:22 AM Last Post: Jerry Raia Math Challenge I could not solve Meindert Kuipers 22 1,700 01-05-2013, 04:43 PM Last Post: Thomas Klemm

Forum Jump:
user
• HP Museum Forums
• Not affiliated with Hewlett-Packard and does not represent HP in any way. HP® logos are trademarks of Hewlett-Packard. Site rights ©2002-2013 Dave Hicks. All rights reserved. Museum Forum Software by Polarity Software.
• Museum Forum Software by Polarity Software.