 The Museum of HP Calculators

HP Forum Archive 18

Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special "Oh So Simple !..."
Message #1 Posted by Valentin Albillo on 1 Apr 2008, 10:11 p.m.

Hi all,

Spring visits us once more and there you are, a brand-new Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special "Oh So Simple !..." for you to tame with the invaluable help of the trusty HP calc model of your choice, whether vintage or cutting-edge, plain-vanilla RPN, powerful graphical RPL, or the HP-71B.

This time the focus is on simplicity. As usual, the challenge is subdivided into five sub-challenges to allow for variety and gradability, roughly ordered from "simplest" to "least simple", where "simplicity" in this context means the particular problem is either simple to enunciate, simple to solve, or both.

Also, to make it even simpler for you (should that be possible), before the Challenge proper I'm giving you three simple training-style samples of what lies ahead, to warm you up. So flex your math-programming muscles, finish them up in a breeze, and then you're fully ready to go berserk ramming against the real Challenge tasks.

Notes:

• Any HP model of your choice may be used but I'll suggest a Minimum Reasonable Model (MRM) for each problem, which is the minimum model capable of solving said problem more or less comfortably, IMO. Obviously, using a more powerful model will make life even easier, and using a lesser model might be possible or not, but a real pain in the neck in any case.

• If you use an HP-41C, you can also use any of these: Math ROM, Advantage ROM, Card Reader ROM, Printer ROM. No other ROMs or extra routines allowed. If you use an HP-71B, you can also use any of these: Math ROM, HP-IL ROM, STRNGLEX. No other ROMs or LEX files allowed.

• Using a PC or any device other than a calculator is strictly forbidden and will only result in showing off your incompetence. You can write your programs in any language supported in any HP calc and your program must run in that calc (e.g., RPN, PRL, 71B-BASIC, 71B-FORTH, GCC for RPL models, etc). Emulators are also welcome. Googling for the solutions is as lame as can be, you're undeserving of entering any challenge if you do and bring nothing but shame to this forum.

The three-pronged pre-Challenge training:

1: Simplest

Given an arbitrary 4x4 real matrix, write a program to compute and output the sum of its four eigenvalues, real and/or complex.

For instance, given the 4x4 matrix:

0.983142345  0.283197300 -4.115518475 -1.660698552
-0.421961836  1.757520105 -3.012345502 -1.674587499
-3.970397996 -1.332130133  3.166741493 -0.294702519
4.881668095 -3.221150835  2.73305616  -0.108431778

your program must compute and output the value 5.798972165, because its four eigenvalues happen to be:

e1 =  2.00989376355
e2 = -1.55106880361 - 2.09930635319 i
e3 = -1.55106880361 + 2.09930635319 i
e4 =  6.89121600867

and
e1 + e2 + e3 + e4 = 5.798972165

MRM (Minimum Recommended Model) = HP-10C.

I'll post my original RPN solution for both the HP-10C (3 steps) and another more powerful Voyager model.

2: Simpler

Write a program to compute and output in one go all real roots of:

1x + 19x + 20x + 51x + 57x + 80x + 82x = 2x + 12x + 31x + 40x + 69x + 71x + 85x

accurate to at least 100 decimal places.

MRM: HP-42S. I'll post my original short solution for the HP-71B

3: Simple

Write a program to output all machine-representable real roots of the equation:

(x+1)2 - (x+2)2 - (x+3)2 + (x+4)2 - (x+5)2 + (x+6)2 + (x+7)2 - (x+8)2 = 0

where machine-representable means that the numerical value in question can be represented exactly in the finite precision of your particular model. For instance, 1E300 and 1.23456789012E-320 are machine-representable numbers in the HP-71B but they aren't in the HP-10C or HP-41CV, say. Your program must not ask for any input from the user and must output all the roots in ascending numerical order.

MRM: HP-11C. I'll post my original 2-line solution for the HP-71B.

The Challenge:

1: Simplest

Write a program to split the set of integers [ 0,1, ... ,15] into two sets with the same number of elements such that the respective sums of the elements, the squares of the elements, and the cubes of the elements of each set are equal.

For instance, we can form the sets [ 0,1,2,3,12,13,14,15 ] and [ 4,5,6,7,8,9,10,11 ] and indeed both have the same number of elements (eight) and the same sums of the elements (60) but the sums of the squares are unequal (748 and 492), let alone the sums of the cubes, so this is hardly a solution.

MRM = HP-10C. I'll post my short, generalized RPN solution for the HP-10C as well as an even shorter generalized RPN solution (9-step) for a more powerful Voyager model

2: Simpler

The first notch of the recent "Valentine's Day 2008 Mini-Challenge" asked for a program to find five numbers when given their pairwise sums and it was stated there that for the general case of N numbers there's always a unique solution except when N is a power of 2, where multiple distinct solutions can be found. So you're asked to

Write a program to find two distinct non-negative sequences of 2N elements which have the same set of pairwise sums

MRM = HP-10C. Again, I'll post my original RPN solutions for the HP-10C and a more powerful Voyager model, as well as a bonus version for the HP-71B.

3: Simple

Ms. Germain selects two integers between 1 and 100 (both excluded) and tells their sum only to Susan and their product only to Peter, both assumed to be ideally intelligent and honest students. She then asks if they can figure out what the original numbers are, and their dialogue goes as follows:

Peter:  I'm sorry Ms. Germain but I can't figure out the numbers right now ...
Susan:  Of course, I knew that you couldn't. Anyway, right now I can't either ...
Peter:  Thanks, Susan, because now I know them !
Susan:  You're welcome, Peter, for now I know them too !!

If they could, your HP can too, so:

Write a program to find the two original numbers.

MRM: HP-15C. I'll post my original solution for the HP-71B

4: Less Simple

Write a program to, given a set of integers, find a nonzero integer constant such that if you multiply each element by it, the set is now entirely composed of perfect powers.

The set may have up to five arbitrary (but distinct) nonzero elements, and an exact representation of the computed constant must be output.

For instance, if the given set is [ 3,4 ], a possible exact solution is represented by the the constant 9, because multiplying each element by it gives the set [ 27,36 ] and both 27 (=33) and 36 (=62) happen to be perfect powers.

Once written, use your program to find such a constant for these sets:

- The Generations set    :  [ 41, 67 ]
- The USA set            :  [ 1776, 2008 ]
- The Then & Now set     :  [ 2007, 2008 ]
- The Halphacentaury set :  [ 1958, 2008, 50 ]
- The Progressions sets  :  [ 2, 3, 4] , [ 3, 4, 5 ] , [ 2, 3, 4, 5 ] and [ 2, 3, 4, 5, 6]
- The Voyager set        :  [ 10, 11, 12, 15, 16 ]
- The Excelsior set      :  [ 71, 42, 15 ]

MRM: HP-41CV. I'll post my original solution for the HP-71B

5: Least Simple

The sequence defined by:

(n+1)*xn+1 = n*xn + xnk

when k = 2 and x1 = 3 continues with

x2 = 6, x3 = 16, x4 = 76, x5 = 1216, and x6 = 247456,

all of which are nicely integer. Regrettably, x7 = 8747993810.2857, which is not. That said, you're asked to

Write a program which, given k and x1, both integer and > 1 , finds and outputs both the index of the first element of the sequence which fails to be an integer, if any, as well as its nonzero fractional part.

For example, for the value x1 = 3 above, your program should output 7 (index of the first non-integer element) and 2/7 = 0.285714285714 (nonzero fractional part of the first non-integer element).

Once written, use your program with k = 2 and the starting values x1 = 15, 41, 42, 50, 67, 71, 1958, 1992, and 2008 to find and output the corresponding indexes and fractional parts of the respective first noninteger elements. And if you succeed, see if your program can cope with the cases k = 2, x1 = 99 or the simpler-looking (!) k = 3, x1 = 2.

MRM: HP42S. I'll post my generalized original solution for the HP-71B

That's all. I think you'll heartedly agree with me that this time everything's really simple, so don't hesitate to take your favorite HP calc and spend an enjoyable time solving each and every one of them. Within a week or so I'll post my original solutions plus comments, as usual.

And remember: Do-Not-Cheat. No googling, no computer programs in C# or Excel, no bending of the rules. That would be lame. You don't need that. You can do it on your own, in spades. I trust you ! Enjoy !

Best regards from V.

 Ad. 1- SimplestMessage #2 Posted by Nenad (Croatia) on 2 Apr 2008, 5:30 a.m.,in response to message #1 by Valentin Albillo The result (sum of eigenvalues) is the sum of main diagonal elements of the original matrix, as I recall from Linear Algebra courses (though I do not remember why). 3 steps solution: + + +

 Re: Ad. 1- SimplestMessage #3 Posted by John Keith on 2 Apr 2008, 9:11 p.m.,in response to message #2 by Nenad (Croatia) On the 48GX and later, only one step: << TRACE >> ;-)

 Re: Pre-Challenges #2-3Message #4 Posted by Steve Perkins on 2 Apr 2008, 3:58 p.m.,in response to message #1 by Valentin Albillo Pre-Challenge #2 I believe I have determined what the real roots of the equation are. I just wish I could prove mathematically that these are the only roots. Here is a program for the HP-25 to output them: 01 6 02 f pause 03 g x=0? 04 R/S 05 1 06 - 07 GTO 02 Pre-Challenge #3 I'm not so great with calculators anymore, but I can (usually) do some algebra. I noticed quickly that the X^2 terms would cancel out giving a linear equation. So I expanded the terms. I ended up concluding that the equation is satisfied for ALL real numbers. This leaves me with a puzzle. How to write a program to satisfy the letter of the problem statement. "Write a program to output all machine-representable real roots of the equation:" Can a program be written to (theoretically) output ALL machine-representable values?

 Re: Challenges #4Message #5 Posted by Steve Perkins on 3 Apr 2008, 10:59 a.m.,in response to message #4 by Steve Perkins >2 DESTROY ALL @ DIM A(5) @ INPUT "HOW MANY (2-5)";C >4 DIM P(5) @ P(1)=1155 @ P(2)=770 @ P(3)=924 @ P(4)=1980 @ P(5)=2100 >6 FOR I=1 TO C @ DISP "A(";I;")"; @ INPUT A(I) @ NEXT I >8 FOR I=1 TO C @ PRINT A(I);"^";P(I); @ IF I10 NEXT I @ PRINT @ END This is brute force (but simple). I started with the 2 number case (call them A,B). I soon found that a multiplier of A^2 * B^3 always worked. When you multiply by A you got a perfect cube. When multiplied by B a perfect square. Extending to 3 numbers (A,B,C) I needed A^15 * B^20 * C^24 to assure even 2nd, 3rd and 5th powers. Of course this often isn't the smallest possible multiplier that satisfies, but it does seem to work. The output for the sets given is kind of boring (and not optimal): 41 ^ 1115 * 67 ^ 770 1776 ^ 1115 * 2008 ^ 770 2007 ^ 1115 * 2008 ^ 770 1958 ^ 1115 * 2008 ^ 770 * 50 ^ 924 2 ^ 1115 * 3 ^ 770 * 4 ^ 924 3 ^ 1115 * 4 ^ 770 * 5 ^ 924 2 ^ 1115 * 3 ^ 770 * 4 ^ 924 * 5 ^ 1980 2 ^ 1115 * 3 ^ 770 * 4 ^ 924 * 5 ^ 1980 * 6 ^ 2100 10 ^ 1115 * 11 ^ 770 * 12 ^ 924 * 15 ^ 1980 * 16 ^ 2100 71 ^ 1115 * 42 ^ 770 * 15 ^ 924 Edited: 3 Apr 2008, 11:23 a.m.

 Re: Challenges #4Message #6 Posted by Valentin Albillo on 3 Apr 2008, 11:49 a.m.,in response to message #5 by Steve Perkins Hi, Steve: Steve posted: "The output for the sets given is kind of boring (and not optimal)" First of all, thanks for your interest and for your very nice posted solution. At first glance, it seems to be correct but I agree with you that the output is certainly boring and calling it "not optimal" is a vaaaaast understatement and could easily win a dozen prizes for "political correctness" :-) For instance, for the sample set [3,4], where I stated that the single-digit constant 9 would do the work, your solution produces instead: 31155 * 4770 = 458397799047057184133972645862312531389 7498430194984804661997443099931507025681 7798964112514664567132257458888454306897 0026190856789656804779577071665305560139 9439403155880275072768601734309995802818 4520322465253381395703159995401741401736 6415417903497193562630878146675362718325 8276641723148858355635909508452980585820 9123585165154734962811349670872215934010 8958539200483759984890688859774167223597 9693459338657601468950703066379137055086 3915368027365530693128867281560637524807 2226133870590389364244752199362460752999 1090434186669799791341281905539526411735 3742928817934644335097288261600412805538 0676812261364454626098243479923850627181 3261947308737780205819640303201318473252 0645919638419607491890339252868846722906 0278437601589417584474744024781066878990 3044846282795871395522812107253913512313 0879958677258586602301016784867415278319 2671755248861308275282811073899411891547 2116799137036398413309711236546910379821 4874545869436763742826250051290255694699 2106935168238391718445225699447748748175 1030068183826432 which certainly could use a little "optimization". For the challenge sets the situation is much, much worse. So, congratulations for giving such a short, clever solution (which I assume is fully correct, can't run right now), you've certainly done your part and fully deserve the credit, but this certainly wasn't what I had in mind. I'm not asking for the smallest possible constant (though that would be nice) but at least something not very far from it, say a few orders of magnitude at most. Got what it takes ? :-) Best regards from V.

 Re: Challenges #4Message #7 Posted by Egan Ford on 3 Apr 2008, 11:58 a.m.,in response to message #6 by Valentin Albillo The original problem states "exact representation". What does that mean exactly? Is a^x * b^y * ... allowed? My solution (still working on it) provides the smallest constant. Some of the constants are 11 digits long. This would make the MRM of a 41CV a bit challenging. Edited: 3 Apr 2008, 12:02 p.m.

 Re: Challenges #4Message #8 Posted by Valentin Albillo on 3 Apr 2008, 12:06 p.m.,in response to message #7 by Egan Ford Hi, Egan: Egan asked: "The original problem states "exact representation". Is a^x * b^y * ... allowed?" Yes, it is allowed. That's precisely why I used the wording "exact representation". The expression used by Steve is an explicit, mathematically exact representation of the constant, even if it can't be evaluated in the particular machine's finite precision. Though I would recommend that if said representation can be exactly evaluated without precision loss, it should be for the user's benefit. Best regards from V.

 Re: Challenges #4Message #9 Posted by Steve Perkins on 10 Apr 2008, 7:43 p.m.,in response to message #6 by Valentin Albillo I haven't made as much headway as I hoped to on this problem. But it's not too hard to do better than I did. 10 DESTROY ALL @ DIM A(5) @ DIM P(5) @ INPUT "HOW MANY (2-5)";C 12 IF C=2 THEN P(1)=2 @ P(2)=3 14 IF C=3 THEN P(1)=15 @ P(2)=20 @ P(3)=24 16 IF C=4 THEN P(1)=105 @ P(2)=140 @ P(3)=84 @ P(4)=90 18 IF C=5 THEN P(1)=1115 @ P(2)=770 @ P(3)=924 @ P(4)=1980 @ P(5)=2100 20 FOR I=1 TO C @ DISP "A(";I;")"; @ INPUT A(I) @ NEXT I 30 FOR I=1 TO C @ PRINT A(I);"^";P(I); @ IF I

 Re: Exercices 2&3Message #10 Posted by J-F Garnier on 2 Apr 2008, 4:02 p.m.,in response to message #1 by Valentin Albillo As for the exercices 2&3, with the help of my HP-71B: #2 20 FOR X=0 TO 259 30 L=1^X+19^X+20^X+51^X+57^X+80^X+82^X 40 R=2^X+12^X+31^X+40^X+69^X+71^X+85^X 50 IF R=L THEN DISP X 60 NEXT X >RUN 0 1 2 3 4 5 6 #3 Thanks to my 49G+ that showed me that the equation is identical to 0=0: 130 FOR E=499 TO -499 STEP -1 140 FOR M=9.99999999999 TO 1 STEP -1.E-11 150 DISP -M*10^E 160 NEXT M 170 NEXT E 180 DISP 0 190 FOR E=-499 TO 499 200 FOR M=1 TO 9.99999999999 STEP 1.E-11 210 DISP M*10^E 220 NEXT M 230 NEXT E Or even simpler with the Math ROM (HP-71B specific): 260 X=-MAXREAL 270 DISP X @ X=NEIGHBOR(X,MAXREAL) @ GOTO 270

 Re: Exercices 2&3Message #11 Posted by Steve Perkins on 10 Apr 2008, 7:56 p.m.,in response to message #10 by J-F Garnier I like your solutions to these! My question is, can we know that there are no more than 7 real roots to the equation given? In the general case, it seems we can't even know that all real roots are integers, as I originally assumed. Consider this simpler example: 2^x + 32^x = 8^x + 18^x How many real roots are there? What are they? I have resisted searching the internet looking for the mathematical basis behind these types of equations. It does have me thinking, and that can't be a bad thing. :-)

 SSMC20 Challenge 1.Message #12 Posted by Egan Ford on 2 Apr 2008, 4:54 p.m.,in response to message #1 by Valentin Albillo Quote: Write a program to split the set of integers [ 0,1, ... ,15] into two sets with the same number of elements such that the respective sums of the elements, the squares of the elements, and the cubes of the elements of each set are equal. For instance, we can form the sets [ 0,1,2,3,12,13,14,15 ] and [ 4,5,6,7,8,9,10,11 ] and indeed both have the same number of elements (eight) and the same sums of the elements (60) but the sums of the squares are unequal (748 and 492), let alone the sums of the cubes, so this is hardly a solution. MRM = HP-10C. I'll post my short, generalized RPN solution for the HP-10C as well as an even shorter generalized RPN solution (9-step) for a more powerful Voyager model I have two solutions for this problem. The first is brute force. The 2nd solution is based on my observations of the first solution. Brute force HPGCC solution: I started with the following identities that I obtained from one of my text books (Excursions in Number Theory, Pg 19): Sum of sequential digits: n*(n+1)/2 Sum of squared sequential digits: n(n+1)(2n+1)/6 Sum of cubes sequential digits: (n*(n+1)/2)^2 One of the sets would have a zero, so I only had to find 7 numbers out of 15 (6435 combinations total) that when summed all 3 different ways equaled 1/2 of the above equations with n = 15. Output from my HPGCC/50g program (source at end of this post): gotit! iter=5279 0 3 5 6 9 10 12 15 and 1 2 4 7 8 11 13 14 Time to solution: 0 seconds The first sequence of numbers all have an even number of 1s (base 2) and the second sequence all have an odd number of 1s. My 16C program to calculate the sets: 001 - 42 34 CLEAR REG 002 - 24 DEC 003 - 43,22, 0 LBL 0 004 - 45 32 RCL I 005 - 43 7 #B 006 - 2 2 007 - 42 9 RMD 008 - 43 48 x!=0 009 - 22 1 GTO 1 010 - 45 32 RCL I 011 - 43 34 PSE 012 - 43,22, 1 LBL 1 013 - 43 24 ISZ 014 - 22 0 GTO 0 015 - 43 21 RTN Toggling line 008 from x!=0 to x=0 will determine which set. After 8 numbers just kill the program. I find this relationship astounding, but I have not had time to explore it much today. Perhaps this weekend. I did modify my brute force program to find more sets that meet the original problem criteria and discovered a few more things of interest: The total number of elements must be k*8 where k > 1, i.e. 16, 24, 32, 40, etc... The sets can be array base 0 or base 1, i.e., 0-15, 1-16, 0-31, 1-32, etc... all have solutions. The solution for 1-16 is the same as 0-15 except that each element is one greater. Here are the sets for k=3, 4, and 5 (array base 0): k=3 gotit! iter=619310 0 1 6 8 10 11 12 13 15 17 22 23 and 2 3 4 5 7 9 14 16 18 19 20 21 k=4 gotit! iter=124340872 0 1 4 9 10 11 13 15 16 18 20 21 22 27 30 31 and 2 3 5 6 7 8 12 14 17 19 23 24 25 26 28 29 k=5 gotit! iter=676322564 0 1 2 5 13 14 16 17 18 19 20 21 22 23 25 26 34 37 38 39 and 3 4 6 7 8 9 10 11 12 15 24 27 28 29 30 31 32 33 35 36 HPGCC Program: #include #define N 15 int a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; int Y1 = N * (N + 1) / 2 / 2; int Y2 = N * (N + 1) * (2 * N + 1) / 6 / 2; int Y3 = N * N * (N + 1) * (N + 1) / 4 / 2; int done = 0; int iter = 0; void combos(int v[], int start, int n, int k, int maxk) { int i, j; int x1, x2, x3; if (done) return; x1 = x2 = x3 = 0; if (k >= maxk) { iter++; for (i = 0; i < maxk; i++) { x1 += v[i]; x2 += v[i] * v[i]; x3 += v[i] * v[i] * v[i]; } if (x1 == Y1 && x2 == Y2 && x3 == Y3) { printf("gotit!\niter=%d\n", iter); printf("0 "); for (i = 0; i < maxk; i++) { printf("%i ", v[i]); } printf("\nand\n"); for (i = 0; i < n; i++) { int ok = 1; for (j = 0; j < maxk; j++) if (a[i] == v[j]) { ok = 0; break; } if (ok) { printf("%i ", a[i]); } } printf("\n"); done = 1; } return; } for (i = start; i < n; i++) { v[k] = a[i]; combos(v, i + 1, n, k + 1, maxk); } } int main() { int v, start; clear_screen(); cpu_setspeed(192 * 1000000); // 192Mhz start = sys_RTC_seconds(); combos(v, 0, 15, 0, 7); printf("Time to solution: %d seconds", sys_RTC_seconds() - start); SLOW_WAIT_CANCEL; return (0); }

 SSMC20 Challenge 2.Message #13 Posted by Egan Ford on 2 Apr 2008, 5:19 p.m.,in response to message #1 by Valentin Albillo Quote: The first notch of the recent "Valentine's Day 2008 Mini-Challenge" asked for a program to find five numbers when given their pairwise sums and it was stated there that for the general case of N numbers there's always a unique solution except when N is a power of 2, where multiple distinct solutions can be found. So you're asked to Write a program to find two distinct non-negative sequences of 2N elements which have the same set of pairwise sums MRM = HP-10C. Again, I'll post my original RPN solutions for the HP-10C and a more powerful Voyager model, as well as a bonus version for the HP-71B. Hmmm... Same as challenge #1: 16C: 001 - 42 34 CLEAR REG 002 - 24 DEC 003 - 43,22, 0 LBL 0 004 - 45 32 RCL I 005 - 43 7 #B 006 - 2 2 007 - 42 9 RMD 008 - 43 48 x!=0 009 - 22 1 GTO 1 010 - 45 32 RCL I 011 - 43 34 PSE 012 - 43,22, 1 LBL 1 013 - 43 24 ISZ 014 - 22 0 GTO 0 015 - 43 21 RTN Just kill after getting 2^N digits, then change 008 to x=0 and rerun to get the other set.

 Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special "Oh So Simple !..."Message #15 Posted by Valentin Albillo on 7 Apr 2008, 5:47 a.m.,in response to message #14 by PeterP Hi, PeterP: PeterP wrote: "I don�t know how I missed this over the last couple of days! Thanks for a wonderful exercise again Valentin!" You're welcome, and let me thank you for your interest and kind words towards my humble efforts, much appreciated. "I have refrained from reading the existing posts so please forgive me if there is already a tip/solution for below. The headers make believe there is not, but who knows" Your intuition is correct. Not only isn't this subchallenge already solved but no one dare touch it with a ten feet pole, you're the very first to have the guts. "Looking at the last problem, it seems that (at least for 41's) the main problem would be how to handle the very quickly very large numbers." Correct. That's the one and only problem because computing the terms is an extremely simple exercise in basic arithmetic. However, it isn't just the 41C the one model to be affected by this circumstance but *any* HP model. Having an arbitrary-size multiprecision library won't automatically save the day with this one. "Okay, and here is where I am stuck [...] How can I get the prime-factorization of and number y+1 if I know the prime factorization of y?"[/italic] Your approach is quite ingenious, congratulations, but regrettably, though knowing the factorization of N+1 or N-1 (even if partial) can be of great help to factorize N, it is by no means easy to implement. Matter of fact, it is much more complicated than the simple procedure required to solve this subchallenge, which can be implemented in a few dozen lines of HP-71B code and probably in less than one line worth of HP50g RPL statements. For instance, in the simplest case of x1 = 15, we find that the subsequent terms are x2 = 120, x3 = 4880, ... but by the time we reach x7 we already have: x7 = 10071474279560550942943268913985959275648738701120 and the factorizations of x7, x7 + 1, and x7 - 1 are, respectively: x7 = 2 * 2 * 2 * 2 * 2 * 2 * 5 * 19 * 61 * 199 * 257 * 1871 * 562673 * 4204807 * 119949240928703736556753 x7 - 1 = 3 * 7 * 7 * 11 * 17 * 37 * 41 * 53 * 733 * 1193 * 14033 * 397151 * 60709531 * 15401576400636983 x7 + 1 = 33433783 * 301236455341010945215002110708978379014087 which, as you can see, do involve very large factors and have very, very little in common. Thus, unless you can deal with these large values and factors, I think another approach will prove more fruitful. Thanks again and Best regards from V. Edited: 7 Apr 2008, 8:25 a.m.

 Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special "Oh So Simple !..."Message #16 Posted by PeterP on 7 Apr 2008, 4:01 p.m.,in response to message #15 by Valentin Albillo thanks for your kind words and hints Valentin, I'll keep working at it... Cheers Peter

 Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special "Oh So Simple !..."Message #17 Posted by Egan Ford on 8 Apr 2008, 12:12 p.m.,in response to message #15 by Valentin Albillo Quote: Not only isn't this subchallenge already solved but no one dare touch it with a ten feet pole, you're the very first to have the guts. I made a lazy attempt last week before I left on vacation. Knowing that it would be impossible I still wrote an arbitrary precision version. And, yes it failed, but you already knew that. But, all was not lost. I did discover that: x1 = 3,10 index = 7 remainder = 2 x1 = 4,6,7,9 index = 17 remainder = 4 The 3 and 10 cases didn't need arbitrary precision, but 4,6,7,9 needed more than 17000 digits. This data provides me with multiple test cases for my analytical solution. I'll try to have something this week or next.

 Problem #5Message #18 Posted by Eamonn on 9 Apr 2008, 2:47 a.m.,in response to message #17 by Egan Ford Hi Valentin, Thanks once again for yet another great S&SMC. I don't know where you come up with the challenges, but it can't be easy to make them so that they have just the right amount of difficulty that a pocket calculator is a good tool to help solve them. Anyway, I see that there have not been a lot of responses to the more difficult challenges so far. This is most likely due to the difficulty level and not due to a lack of trying on the behalf of the MoHPC audience. At least it gives slowpokes like me a chance to work on a solution before one is posted. I believe that I have a solution to problem 5. It seems to work on paper, but I haven't had time yet to write a calculator program that automates it. I plan to do this in the next 24 to 48 hours and post it when I do so. I'm hoping that you will postpone posting your solution until I (and others that I am sure are working on this problem) get a chance to finalize and post my solution. The basic idea is to calculate x(n) mod b and use that to calculate x(n+1) mod b. If x(b) mod b is not 0 then the solution is that the index is b and the remainder is x(b) mod b. Working with x(n) mod b keeps the figures very manageable. The problem was really how to calculate x(n+1) mod b from x(n) mod b, which is easier to state than to do. Once I figured out how to do that, the rest was straightforward. As I said, I have only tried this on paper, but it seems to work so far. Best regards, Eamonn

 Re: Problem #5Message #19 Posted by Egan Ford on 9 Apr 2008, 3:28 a.m.,in response to message #18 by Eamonn Quote: The problem was really how to calculate x(n+1) mod b from x(n) mod b, which is easier to state than to do. If you are trying to solve ax = b mod m, just set x = 1, and increment x until ax mod m = b.

 Re: Problem #5Message #20 Posted by Eamonn on 9 Apr 2008, 12:01 p.m.,in response to message #19 by Egan Ford Thanks Egan. That's basically what I ended up doing, except I started with x=0. It should give the same results I believe. Best Regards, Eamonn

 Re: Problem #5Message #21 Posted by Valentin Albillo on 9 Apr 2008, 7:28 a.m.,in response to message #18 by Eamonn Hi, Eamonn: Eamonn posted: "Thanks once again for yet another great S&SMC. I don't know where you come up with the challenges, but it can't be easy to make them so that they have just the right amount of difficulty that a pocket calculator is a good tool to help solve them." Thanks a lot for your interest, really appreciated. And no, it isn't easy to come up with them challenges. Tuning them up for difficulty is particularly troublesome so that's why I usually include several subchallenges of various difficulties, expecting that everybody will find some suitable for their perceived abilities. "Anyway, I see that there have not been a lot of responses to the more difficult challenges so far. This is most likely due to the difficulty level and not due to a lack of trying on the behalf of the MoHPC audience." I'm not so sure. Certainly, sub #4 and sub #5 are designed to offer a good fight to the likes of Egan, J-F, or yourself among others, but the rest are much more affordable, they basically require only ingenuity, interest, and some research and trial effort. Regrettably, people seem nowadays to be too busy, or too lazy, or both, or they simply aren't that interested in the programming, the algorithms, or even the underlying math anymore. Perhaps they prefer to lurk and just see the efforts of others or even just browse through my final solutions and comments, without bothering to work them out for themselves or even post some comments of their own. I can't be sure this is the case, but I think it is a pretty educated guess. Happens the same with fan publications: people subscribe and then expect to receive a magazine choke-full with interesting information ... created by others; they aren't interested in making the effort to create and submit something interesting themselves, they simply lurk and leech. It is less tiring. Then they're surprised and upset when said publication hits the deck for lack of contributions. "At least it gives slowpokes like me a chance to work on a solution before one is posted [...] I plan to do this in the next 24 to 48 hours and post it when I do so. I'm hoping that you will postpone posting your solution until I (and others that I am sure are working on this problem) get a chance to finalize and post my solution." Certainly. I'll postpone my posting the original solutions and comments till next Monday so you all will have a chance at it. That's about 120 extra hours. This is the last S&SMC for the foreseeable future, the series ends its run here, so try and make the most of it. Again, thanks for your efforts, for your appreciation, and for taking the trouble to post so that I would know. Best regards from V.

 Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special "Oh So Simple !..."Message #22 Posted by Valentin Albillo on 9 Apr 2008, 7:01 a.m.,in response to message #17 by Egan Ford Hi, Egan: Egan posted: "Knowing that it would be impossible I still wrote an arbitrary precision version. And, yes it failed, but you already knew that." Thanks for your interest and willingness to contribute, much appreciated. This and subchallenge #4 are the kind of teasers explicitly concocted to offer some resistance to people with your considerable abilities, all easier tasks having been met quite successfully by you in the past. And yes, I knew. "But, all was not lost. I did discover that [...] The 3 and 10 cases didn't need arbitrary precision, but 4,6,7,9 needed more than 17000 digits." Your results are correct so far, though none of them included any of the asked cases. Remember that the last one is for k=3, not k=2 like all the rest, so your program should ideally cope with general integer k > 1 as well. "This data provides me with multiple test cases for my analytical solution. I'll try to have something this week or next." And I'll be eager to see what you come up with. I will extend the period before I post my original solutions to next Monday so that enough time is available for you to try and solve them. Anyway, I must say that it's a pity that this S&SMC#20 has apparently failed to arouse the same kind of interest as the recent ones did: more than a week has elapsed and the three best subchallenges (#3, #4, #5) remain essentially unsolved, including #3 which hasn't even been mentioned by anyone. The interest for the others hasn't been that high either. I was under the impression that, since a full year has elapsed since the previous S&SMC#19, challenge-loving, math-loving people would be eager to try their wits against my newest production, which is carefully crafted to be both suitably difficult (but not unassailable, mind you) as well as aesthetically pleasing, with some amazing identities, unexpected numeric relationships, and awesome results and algorithms being brought up for public discussion and examination. Regrettably it seems that either I missed the mark with the difficulty or else people are simply too busy and/or too lazy to allocate time and effort to study and solve them. Previous challenges would see a large number of varied solutions for all kinds of models, from large hand-crafted RPN programs to short, mysterious RPL routines, as well as some BASIC, C, or even FORTH implementations. Now we haven't seen more than a line of RPL code in all (that TRACE command) and no one has tried to create their own version after seeing other solutions, or even optimize the ones given (as could have been the case for training-#3 and subchallenge-#4). I take this as a strong signal that my S&SMC's have overstayed their welcome and have now been relegated to the status of minimally interesting topic only appreciated by a very tiny minority (perhaps less than a handful people) while the vast majority of forum regulars and visitors aren't that interested anymore, if at all. Since these challenges do take a lot of time and effort to concoct (research suitable topics, long-list and short-list the most awesome and better suited, create original solutions for them, format and post the very long challenge message, format and post the very long solutions & comments, etc), this is a book case of 'diminishing returns' in which I've reached the point where the small participation does not justify the large effort so this will be the last S&SMC. After all, 20 is a nice round number so we can adequately call it quits after this one, don't you think ? :-) Best regards from V.

 Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special "Oh So Simple !..."Message #23 Posted by Maximilian Hohmann on 9 Apr 2008, 7:22 a.m.,in response to message #22 by Valentin Albillo Hello! Although it was not addressed at me, I MUST answer this one: Quote:After all, 20 is a nice round number so we can adequately call it quits after this one, don't you think ? :-) No, no, no! 20 is not a nice round number. I am far too dumb to come up with a solution for even the "simplest" of your challenges (seriously considering of having my academic grade erased from my passport now :-( ) but as long as you keep coming up with new ones there is always hope! I would suggest 314 as a nice round number for the final challenge :-) Greetings, Max (looking forward to your solutions - even got myself a MATH ROM for my 71B since the last challenge, so that I can, at least, type them into the calculator myself)

 Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special "Oh So Simple !..."Message #24 Posted by Valentin Albillo on 21 Apr 2008, 10:42 a.m.,in response to message #23 by Maximilian Hohmann Hi, Max: Max posted: "No, no, no! 20 is not a nice round number" Yes it is. It's been a number of years since I issued S&SMC#1 and the difficulty has been steadily increasing because of the incredible abilities of interested people like yourself, who quickly solved every challenge no matter how fiendishly tricky. Logically, the time required to concoct, create original solutions, and format and post them has likewise increased, while at the same time participation has decreased to the point that only a handful of people dare to attack them, even when they actually aren't that difficult really. See for example the training problem which essentially asked for a program to output every machine-representable number. This was allegedly interesting and challenging and not difficult at all; Jean-Fran�ois provided a solution which could be easily ported to every machine out there and not specially difficult to discover from scratch. Yet apart from him, no one posted a thing. This being so, I think it's time to end the series because of diminishing returns, and will stick instead to simpler mini-challenges for a while. "Greetings, Max (looking forward to your solutions - even got myself a MATH ROM for my 71B since the last challenge, so that I can, at least, type them into the calculator myself)" Thank you very much for your interest, first part of solutions posted; anyway, I would suggest that it's actually much easier and a better investment of time to use Emu71 instead and simply copy-paste the text from my solutions post to it, thus avoiding boring and error-prone tasks such as entering and checking out by hand a long listing. Best regards from V.

 Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special "Oh So Simple !..."Message #25 Posted by J-F Garnier on 9 Apr 2008, 7:33 a.m.,in response to message #22 by Valentin Albillo Hi Valentin, You wrote: ...this S&SMC#20 has apparently failed to arouse the same kind of interest as the recent ones did... I can only speak for myself, but I always had an high interest in your S&SMC. But maybe this time my math skills are not good enough to solve your last "Oh So Simple !..." challenges. I found the problems #3 and #4 quite interesting for me and thought a lot about them, but was unable to devise a suitable program to solve them. I found some particular solutions "by hand" for #4, but nothing general. However, as you allow us a few days more, I may spend some more time on it. Thanks for your efforts in preparing these S&SMC and best regards, J-F

 Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special "Oh So Simple !..."Message #26 Posted by Valentin Albillo on 21 Apr 2008, 10:44 a.m.,in response to message #25 by J-F Garnier Hi, Jean-Fran�ois: You've done more than your share, and I appreciate it very much. I look forward to see you participate in future mini-challenges, which will probably be centered around the HP-15C and the HP-71B, my two favorite models since ever. Thanks for your continued interest and appreciation, and Best regards from V.

 Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special "Oh So Simple !..."Message #28 Posted by Valentin Albillo on 9 Apr 2008, 4:34 p.m.,in response to message #27 by Egan Ford Hi, Egan: Good advices, all of them. The reason why I've been refraining from palindromic squares and such is that, frankly, they seem quite trivial to me and do not have much mathematical meat, so to say. The fact that certain 12-digit number is the only palindromic square, say, it's a nice curiosity but nothing else. It goes nowhere and teaches you nothing mathematically speaking, though it can be a good programming exercise. On the other hand, the fact that some apparently integer sequence fails to produce an integer after 600 terms have been generated is not only fascinating but discovering why can teach you a lot about divisibility, congruences, and working in modular arithmetic to avoid having to deal with numbers so large that no computer would ever be able to even store them, let alone perform operations on them. Nevertheless you're probably right. The former kind of challenge attracts a larger number of people than the latter, despite its irrelevancy so I might heed your advice and stick to simple mini-challenges for the HP-15C and such for now. As for your 'challenge', I've read the same AMM issue as you did and know as much about the problem as you do, including that one possible solution is A = -2634, B = 955, C = 1770, and D = 5400, as can easily be checked: > A^4+B^4+C^4+D^4 , (A+B+C+D)^4 909087685468561 909087685468561 Writing an elliptic-curve-based program to find some of the infinite solutions is hardly appealing to me right now. I'd rather use the elliptic curve approach to try and write a good factoring program instead. Thanks and best regards from V.

 Re: Challenge 1Message #33 Posted by PeterP on 7 Apr 2008, 4:01 p.m.,in response to message #1 by Valentin Albillo First problem � the below is a solution to the first problem for the 41CV. It is not completely brute force but clearly uses a lot more brawn than brain (of the 41 that is. the small build user has neither in sufficient quantity�) It uses two ideas. First, to get the sum of the two octets to match we shall create pairs of equal sum and can resort to only creating quartets of those pairs and look for those that have equal sum of their squares and cubes. This is similar to the idea that Gauss used to derive the formula for the sum of n integers. Second, it is obvious that the sum of squares and sum of cubes we are looking for in our octet is exactly halve of the sum of the squares/cubes of all integers. The structure of the behemoth below is as follows (1) Pre-fill the registers with the sum of the squares and cubes of the pairs in a convenient fashion so that indirect register polling can grab the right contents (2) It then uses flags to keep track of which pairs it has selected (3) It has 4 nested loops to run through all unique combinations roughly starting with the highest possible sum. When it finds a sum that is equal to � of the total, it goes to check also the cubes, which, as it turns out, also match at this point. I shall think more about this �coincidence�� However, if they were not to match, it would keep on going down the list if possible combinations. Lastly, it does not take advantage of the fact that after a certain point all options will be < than � the total and we could jump directly to �No solution possible� (4) Regs 0 � 7 hold the sum of the square of the relevant pair. (0 for (15,0), 1 for (14,2), etc (5) Regs 10 � 17 hold the sum of the cubes of the relevant pair (6) Reg 08 is the general loop reg for loops over the 8 paris (7) Reg 20, N,O,M are the loop regs for the search loop over unique combinations (8) Reg 18 (:=0.007), 09 (:=10), 23(:=sum of all cubes), 24(:=7), 25(:=sum of all squares) are just placeholders as the slowest instructions on the 41 are numbers so you want to store them in registers if you use them often Run-time is actually not bad at about 55sec on a physical standard speed hp41, including all the feedback that is built into the code. Its not pretty, but it works� BTW - I wish Egan had finished his article about the 41c emulators before the challenge! If his excellent article about the Voyager is any hint on its quality, I would have saved myself a lot of time typing the code into here (Just trying to say that I thought it to be an excellent article and I am very much looking forward to the version about the 41!) LBL �Loop� XEQ �STOSQ� �Start Search� AVIEW CLX X<>F CLA RCL 18 (:=0.007) STO 20 LBL �20 RCL 20 1+ STO N LBL �N RCL N 1+ STO O LBL �O RCL 24 (:=7) RCL O 1+ X>Y? GTO �NS STO M LBL M CLX X<>F SF IND 20 SF IND N SF IND O SF IND M XEQ C VIEW X RCL 25 X=Y? GTO E ISG M GTO M LBL �NS ISG O GTO O ISG N GTO N �No Solution TONE 0 AVIEW RTN GTO �LOOP LBL C �calculate the sum of squares for quartet RCL IND 20 RCL IND N + RCL IND O + RCL IND M + RTN LBL E �check if sum of cubes also matching TONE 5 TONE 9 TONE 5 CLX STO 26 RCL 18 (:=0.007) STO 08 LBL 12 FS? IND 08 XEQ F ISG 08 GTO 12 CLX X<>26 VIEW X RCL 23 X=Y? GTO 99 RTN LBL F �get the right sum of cubes RCL 08 RCL 09 (:=10) + RCL IND X ST+ 26 RTN LBL 99 �great, we found it! BEEP �FOUND AVIEW CLA RCL 18 (:=0.007) STO 08 LBL 14 FS? IND 08 XEQ 15 ISG 08 GTO 14 AVIEW STOP GTO �Loop LBL 15 �create result string in display XEQ IND 08 ARCLI �k, k = append sign RDN ARCLI �k, RTN LBL �STOSQ �fill the registers with sum of squares, cubes etc �Fill Regs� AVIEW CLX STO23 STO 25 STO 26 7 STO 24 10 STO 09 0.007 STO 08 STO 18 LBL 10 XEQ IND 08 XEQ 23 STO IND 08 ST+25 CLX RCL08 10 + X<>Y STO IND Y ST+ 23 ISG 08 GTO 10 2 ST/ 25 ST/ 23 RTN LBL 23 �calc x^2 + y^2 (into X) and x^3+y^3(into y) Enter X^2 St* Y RCL Z X^2 ST* T + RDN + R^ RTN LBL 00 15 0 RTN LBL 01 14 1 RTN LBL 02 13 2 RTN etc� LBL 07 8 7 RTN Edited: 7 Apr 2008, 4:13 p.m.

 Re: Challenge 1Message #34 Posted by Egan Ford on 8 Apr 2008, 11:47 a.m.,in response to message #33 by PeterP Quote: BTW - I wish Egan had finished his article about the 41c emulators before the challenge! If his excellent article about the Voyager is any hint on its quality, I would have saved myself a lot of time typing the code into here (Just trying to say that I thought it to be an excellent article and I am very much looking forward to the version about the 41!) I have been swamped with professional and personal obligations. My goal for all 4 parts to be complete by 4/1 slipped. My 41CX article briefly discusses HP41UC for compiling and printing. The proper HP41UC documentation is here: http://www.hpmuseum.org/software/41uc.htm. The latest version can be obtained from http://hp41.claughan.com/files/hp41uc.zip . It is a DOS program. If you are a Mac or Linux user then you can install DOSBox to run the utility. This is covered in my article. As for emulators, so far I have only documented V41 and EMU41. EMU41 is DOS-based, so if you got HP41UC working you have EMU41 working too. That is the easy part. The hard part is documenting all the different methods of getting code to and from a physical 41 for Windows, Mac, and Linux. I've already done a lot of the research, but there is still so much more to do. Perhaps I'll just skip that part.

 Re: Challenge 1Message #35 Posted by PeterP on 8 Apr 2008, 12:09 p.m.,in response to message #34 by Egan Ford Egan, Thanks for the kind info. I have been looking into SDK41 and I am working on converting the original txt based documentation into a nicer formatted pdf document and maybe some extra info. Also, though I am lightyears behind your level of understanding, I'd be happy to collaborate and write up/research some parts so that you might have some basis to work with rather than having to start from scratch. Just a thought, you know how to reach me :-) Cheers Peter

 Re: Challenge 1Message #36 Posted by Egan Ford on 8 Apr 2008, 12:29 p.m.,in response to message #35 by PeterP Quote: Also, though I am lightyears behind your level of understanding I wouldn't say that. I've been a 41CX user for less than a year. As I discover things that are not well documented or fragmented in too many places I try to make a point of documenting it for other 41 n00bs. Kind of a cookbook, start to end. Quote: I'd be happy to collaborate and write up/research some parts so that you might have some basis to work with rather than having to start from scratch. Just a thought, you know how to reach me :-) Thanks, that'd be great. I'll send you a draft in a few weeks for your review.

 Challenge 2Message #37 Posted by PeterP on 8 Apr 2008, 12:18 p.m.,in response to message #1 by Valentin Albillo First, let me admit that I did read the thread for the recent Valentine�s day challenge and shamelessly used some information left there by Valentin. I hope that I can get a �by� for this cheating from the kind author� I started this second challenge by looking at known solution to see if there is anything to learn from them For n = 2 we have (posted by Valentin in the Valentine Day�s challenge) and n = 3 (from my solution for the first challenge of SSMC20) |1 2 4 7| |0 3 5 6| |1 2 4 7 8 11 13 14| |0 3 5 6 9 10 12 15| Two observations: The first 4 numbers are the same for n=2 and n=3The absolute distance between elements of the first sequence and the second sequence at the same place is always 1. Based on the above observation I thought about creating the solution for n=4 by trial and error and while doing so I made a third observation There seems to be a reversing pattern in how the sequence is created. Let me explain what I mean by this. Lets only look at pairs of numbers at position x for the two sequences and lets call it (u,l) for upper and lower sequence. Additionally, lets denote with a �1� if the upper sequence has the higher number and with a �0� if the lower sequence as the higher number. This representation yields the following string of 1s and 0s for n=2,3,4 where I have taken the liberty to delineate blocks of length n-1. |10|01| |1001|0110| |10010110|01101001| This is a neat reversing patter where we can write an explicit formula for the 1�s and 0�s as a not() function of previous 1�s and 0�s as per below with x(i) being the value at position i i = 1 to N; x(2i-1+1 to 2i) = NOT(x(1 to 2i-1) So lets just start with u(1) = 1 and l(1) = 0. This means that x(1) = 1 as the upper sequence has the higher number. Recursively using the above formula we get x(2) = not(x(1)) = 0 x(3-4) = not(x(1-2) = 01 x(5-8) = not(x(1-4) = 0110 x(9-16) = not(x(1-8) = 01101001 which in turn delivers the recipe and solutions for n = 1,2,3,4 as |1 0| => |1 2| |0 3| |1 0 0 1| => |1 2 4 7| |0 3 5 6| |1 0 0 1|0 1 1 0| =>|1 2 4 7 8 11 13 14| |0 3 5 6 9 10 12 15| |1 0 0 1|0 1 1 0|0 1 1 0|1 0 0 1| =>|1 2 4 7 8 11 13 14 17 18 20 23 24 27 29 30| |0 3 5 6 9 10 12 15 16 19 21 22 25 26 28 31| From here it is relatively straight forward to write a program, however from a quick glance at the manual, it seems that the HP16c (which I have never used) would be most suited given his extensive capabilities with binary numbers. The below code is an implementation for the 41 and is generally very inefficient as it uses 1 reg per position so it maxes out at about n=7. If one would want to make it work for larger numbers, one could devise a space saving mechanism to store up to 31 positions in each register and use the Bit? function of the AdvModule (or somewhat more convenient functions of the CCDmodule). However, I would assume that someone familiar with the HP16c can write a much shorter and faster program� The code below creates first the sequence of 1�s and 0�s by a simple double loop flipping each bit separately before it proceeds to use the bit-pattern to create the sequence. Output is in the form of (u,l) and sequential. Keep pressing r/s for each new pair to appear. As usually there is a bunch of STO functions at the start for repeatedly used numbers as they are so sloooow on the HP41. LBL �C2 CLRG �N? PROMPT STO 00 2 STO 05 X<>Y Y^x 12 + PSIZE -1 STO 03 ABS STO 04 10 STO 06 + STO 07 RCL 00 0.001 STO 01 * RCL 04 (=1) + STO M LBL 00 �loop over i = 1 to N RCL 05 (=2) RCL M INT RCL 04 (=1) - Y^X STO O RCL 04 (=1) + RCL 06 (=10) + RCL 05 (=2) RCL M INT Y^X RCL 06 (=10) + RCL 01 (=0.001) * + STO N LBL 01 �inner loop over all elements 2^(i-1) +1 to 2^i RCL N RCL O - RCL IND X RCL 03 (= -1) + ABS STO IND N ISG N GTO 01 ISG M GTO 00 LBL 02 �display loop RCL 04 (1) STO 11 RCL 07 (=11) RCL 05 (=2) RCL 00 (=N) Y^X RCL 06 (=10) + RCL 01 (=0.001) * + STO 02 CLx Enter RCL 04 (=1) LBL 03 �loop to display one pair RCL IND 02 X=0? XEQ 05 RDN �< ARCLI �k, X<>Y ARCLI �k> AVIEW STOP X>Y? X<>Y RCL 05 (=2) + RCL 04 (=1) X<>Y + LastX ISG 02 GTO 03 BEEP STOP GTO �C2 LBL 05 RTN X<>Y R^ RTN

 SSMC20 Challenge 5. (answers w/ question)Message #38 Posted by Egan Ford on 9 Apr 2008, 3:08 a.m.,in response to message #1 by Valentin Albillo Valentin, can you confirm if the following is correct: x1: 3 k: 2 index: 7 fractional part: 0.285714285714 x1: 15 k: 2 index: 67 fractional part: 0.268656716418 x1: 41 k: 2 index: 17 fractional part: 0.235294117647 x1: 42 k: 2 index: 59 fractional part: 0.559322033898 x1: 50 k: 2 index: 67 fractional part: 0.268656716418 x1: 67 k: 2 index: 109 fractional part: 0.238532110092 x1: 71 k: 2 index: 17 fractional part: 0.235294117647 x1: 1958 k: 2 index: 17 fractional part: 0.235294117647 x1: 1992 k: 2 index: 17 fractional part: 0.235294117647 x1: 2008 k: 2 index: 61 fractional part: 0.983606557377 x1: 99 k: 2 index: 103 fractional part: 0.650485436893 x1: 2 k: 3 index: 89 fractional part: 0.460674157303 Thanks.

 Re: SSMC20 Challenge 5. (answers w/ question)Message #39 Posted by Valentin Albillo on 9 Apr 2008, 6:31 a.m.,in response to message #38 by Egan Ford Hi, Egan: Egan posted: "can you confirm if the following is correct:" I'll try. I can't confirm the fractional parts right now (will do tonight) but as for the indexes let's see: x1: 3 k: 2 index: 7 OK x1: 15 k: 2 index: 67 OK x1: 41 k: 2 index: 17 OK x1: 42 k: 2 index: 59 OK x1: 50 k: 2 index: 67 No, 34 x1: 67 k: 2 index: 109 No, 51 x1: 71 k: 2 index: 17 OK x1: 1958 k: 2 index: 17 OK x1: 1992 k: 2 index: 17 OK x1: 2008 k: 2 index: 61 OK x1: 99 k: 2 index: 103 OK x1: 2 k: 3 index: 89 OK It's strange that your results differ from mine in two cases about the middle of the table. I've tried my algorithm in two different implementations, one written in HP-71B's BASIC, the other written in a math software package's language, and both absolutely agree for the 200+ cases I've tried, which include values of x1 from 2 to 15 plus 41, 42, 50, 67, 71, 1958, 1992, 2008 and assorted others, and for values of k ranging from 2 to 10. This doesn't preclude the possibility of an error on my part, of course, so please check your own implementation for the cases in disagreement (50 and 67) and if you find nothing wrong with your code e-mail me at the address given in my calc web page (don't forget to include "HP CALCS" somewhere) and we can probably sort it out. Also, if you need more test results for other values of x1 or other values of k, let me know and I'll provide them to you ASAP. Thanks for your interest and Best regards from V.

 Re: SSMC20 Challenge 5. (answers w/ question)Message #40 Posted by Eamonn on 9 Apr 2008, 8:12 p.m.,in response to message #39 by Valentin Albillo Hi Valentin, Egan, I have implemented my solution on a PC with Python and I get the same results as Egan for all the test cases x1 = 3, k = 2, n = 7, Fractional Part = 2/7 x1 = 15, k = 2, n = 67, Fractional Part = 18/67 x1 = 41, k = 2, n = 17, Fractional Part = 4/17 x1 = 42, k = 2, n = 59, Fractional Part = 33/59 x1 = 50, k = 2, n = 67, Fractional Part = 18/67 x1 = 67, k = 2, n = 109, Fractional Part = 26/109 x1 = 71, k = 2, n = 17, Fractional Part = 4/17 x1 = 1958, k = 2, n = 17, Fractional Part = 4/17 x1 = 1992, k = 2, n = 17, Fractional Part = 4/17 x1 = 2008, k = 2, n = 61, Fractional Part = 60/61 x1 = 99, k = 2, n = 103, Fractional Part = 67/103 x1 = 2, k = 3, n = 89, Fractional Part = 41/89 One of the things I noticed is that I needed to be careful where I applied the modulo operation. To recap, I am trying to determine if x(b) is divisible by b. I find x(n) mod b for all n < b. I use x(n) mod b to calculate x(n+1) mod b, all the way to x(b) mod b. My first effort applied the modulo operator after calculating n*x(n) + x(n)^k. This gives (((n+1) * x(n+1)) mod b). I then used this to calculate (x(n+1) mod b) by adding multiples of b to (((n+1) * x(n+1)) mod b) until it was divisible by (n+1). I divided this by n+1 and took the result modulo b. However, in some cases, this leads to ambiguities. For example in the case of x(1)=67 and k=3, when testing x(54) for divisibility by 54, I start off by calculating x(2) mod 54, x(3) mod 54, etc. Using the above approach, I get: (2 * x(2)) mod 54 = (67 + 67*67) mod 54 = 20 x(2) mod 54 = 10 On to x(3) (3 * x(3)) mod 54 = (20 + 10*10) mod 54 = 12 So far so good. Now, what is x(3) mod 54? It can actually be one of three values: 4, 22 or 40. My algorithm would find the first answer, 4 and use that in subsequent calculations. However, if I multiply everything out, I find that x(3) = 1,731,280, and x(3) mod 54 is actually 40. I got around this by calculating (n+1) * x(n+1) from the previous values for (( n * x(n) )mod b) and (x(n) mod b) and using this to calculate x(n+1) mod 54 using the same approach as above. For x(3), the calculation is: 3 * x(3) = 120 dividing both sides by 3 gives x(3) = 40, and x(3) mod 54 = 40. Next, I calculate (3*x(3)) mod 54, which is 12 as before. In this case, it correctly calculates x(n+1) mod 54 as 40. Problem is, I don't know if the new approach gives the actual value for x(n+1) mod b in all cases. It gives a value that satisfies the equation, but in some cases, there may be multiple such values and I am not sure that this is the correct answer in all cases. If anyone is interested, let me know and I can post the python code. (Any calculators out there that can run python?) Best Regards, Eamonn.

 Re: SSMC20 Challenge 5. (answers w/ question)Message #41 Posted by Egan Ford on 10 Apr 2008, 1:27 a.m.,in response to message #40 by Eamonn Quote: I have implemented my solution on a PC with Python and I get the same results as Egan for all the test cases This is a great case of two wrongs don't make it right. I think we are using the same methods and getting the same wrong answers for 2 of the cases. Quote: If anyone is interested, let me know and I can post the python code. I used Perl. But will convert to 71B or 42S when satisfied with my solution. BTW, if you like Python and math you may want to check out Sage. I have a Sage server at home, but there are free ones online (https://www.sagenb.org/).

 Re: SSMC20 Challenge 5. (answers w/ question)Message #42 Posted by Valentin Albillo on 10 Apr 2008, 8:05 a.m.,in response to message #41 by Egan Ford Hi, Egan: Just a few assorted results for various values of X1 and K as produced by my algorithm, to help you and Eamonn check yours: X1 K=2 K=3 K=4 K=6 K=8 K=10 ------------------------------------------- 15 67 197 173 37 37 31 41 17 79 17 83 23 23 42 59 151 23 37 17 31 50 34 193 13 37 23 41 67 51 89 97 37 23 83 71 17 79 17 13 46 89 1958 17 158 13 13 149 41 2008 61 229 167 13 37 31 Keep in mind that I can't be 100% sure these are fully correct as my algorithm and/or implementations might be buggy and this is original research, never-before-seen results as far as I know, so there's no published results that I'm aware to refer to. However, though not 100%, I'm reasonably sure of their correctness as my algorithm is simple enough (for the HP-71B implementation it's a mere 5-line looping construction involving just 6 arithmetic operations inside), and I've implemented it in two very different languages and architectures, with both implementations fully agreeing in each and everyone of the 200+ assorted cases tested, which gives me a fair confidence that there's no great chance of there being an error. But it can happen, caveat emptor. Best regards from V. Edited: 10 Apr 2008, 8:15 a.m.

 Re: SSMC20 Challenge 5. (answers w/ question)Message #43 Posted by Egan Ford on 10 Apr 2008, 10:37 a.m.,in response to message #42 by Valentin Albillo Thanks. My output (differences in bold): x1 k=2 k=3 k=4 k=6 k=8 k=10 ---------------------------------------------- 15 67 197 173 37 37 31 41 17 79 17 83 23 23 42 59 151 23 37 17 31 50 67 193 13 37 23 41 67 109 89 97 37 23 83 71 17 79 17 13 67 89 1958 17 193 13 7 5 53 2008 61 229 167 3 5 89 I'm 100% sure its on my end. I confirmed with arbitrary precision code that x1=2008, k=6 is not 3. For 50,2 and 67,2 if you could tell me what modulo you used? Is it 17^2 and 2*17^2 respectively? That may help me find my bug. Thanks. Edited: 10 Apr 2008, 11:08 a.m.

 Re: SSMC20 Challenge 5. (answers w/ question)Message #44 Posted by Valentin Albillo on 10 Apr 2008, 11:18 a.m.,in response to message #43 by Egan Ford Hi again, Egan: Egan posted: "Thanks. [...] I'm 100% sure its on my end." You're welcome. And yes, I'm afraid something's wrong in your algorithm because, just for instance, for K = 6 and X1 = 2008 you're getting 3 as the index of the first non-integer element, while in fact we have: X1 = 2008, X2 = 32775721083076740076, integer, and finally X3 = 413230412070500434091017858379218242685361747527131392695857693393246688375057739098922315422691000940697924992949576, which is also integer. X4 = 124478...4462326 is integer as well, so 3 can't possibly be the correct index of the first non-integer element. Same with indexes 5 and 7 in your results, which can also be checked directly (if laboriously). Good luck finding the (possibly very subtle) error, and Best regards from V.

 Re: SSMC20 Challenge 5. (answers w/ question)Message #45 Posted by Valentin Albillo on 10 Apr 2008, 11:34 a.m.,in response to message #43 by Egan Ford Hi, Egan: I see you edited your post while I was "in transit" composing my reply, to add the (6,2008) comment and the question, so I didn't see both edits till I clicked the submit button and the thread refreshed. As for the question, I'm afraid I can't help. It seems my algorithm and yours are sufficiently dissimilar that your question doesn't apply to mine. I do several modular operations with different modulus in a single loop iteration, and it doesn't seem easy to discuss the details without disclosing the whole algorithm as it is implemented with so few basic arithmetic operations (just 6 per cycle). Best regards from V.

 Re: SSMC20 Challenge 5. (answers w/ question)Message #46 Posted by Eamonn on 10 Apr 2008, 1:05 p.m.,in response to message #43 by Egan Ford Egan, Valentin, Here is the output of my algorithm for the test cases above: x1 k= 2 k= 3 k= 4 k= 6 k= 8 k=10 --------------------------------------------- 15 67 197 173 37 37 31 41 17 79 17 83 23 23 42 59 151 23 37 17 31 50 67 193 13 37 23 41 67 109 89 97 37 23 83 71 17 79 17 13 67 89 1958 17 193 13 13 -1 41 2008 61 229 167 13 37 31 The -1 in the result for x1=1958, k=8 is because in one of the loops, my algorithm doesn't find a solution to xn mod b when given n*xn mod b. So it would appear that my algorithm still needs some refinement. Of course the results I get don't fully match either of your sets of results. Here are the cases in which the three algorithms yield different results: x1 k Valentin Egan Eamonn ---------------------------------- 50 2 34 67 67 67 2 51 109 109 71 8 46 67 67 1958 3 158 193 193 1958 6 13 7 13 1958 8 149 5 1958 10 41 53 41 2008 6 13 3 13 2008 8 37 5 37 2008 10 31 89 31 We all get the same results for all the other cases. Based on the previous messages, I was thinking my algorithm would match Egans results in all cases - but sometimes it agrees with Valentins results. Clearly we are all doing something slightly different. I'll see if I can figure out why my routine fails in the (1958,8) case. Best Regards, Eamonn.

 Re: SSMC20 Challenge 5. (answers w/ question)Message #47 Posted by Egan Ford on 19 Apr 2008, 7:30 a.m.,in response to message #43 by Egan Ford Getting closer: Expected: X1 K=2 K=3 K=4 K=6 K=8 K=10 ------------------------------------------- 15 67 197 173 37 37 31 41 17 79 17 83 23 23 42 59 151 23 37 17 31 50 34 193 13 37 23 41 67 51 89 97 37 23 83 71 17 79 17 13 46 89 1958 17 158 13 13 149 41 2008 61 229 167 13 37 31 Obtained: x1 k=2 k=3 k=4 k=6 k=8 k=10 ---------------------------------------------- 15 67 197 173 37 37 31 41 17 79 17 83 23 23 42 59 151 23 37 17 31 50 67 193 13 37 23 41 67 109 89 97 37 23 83 71 17 79 17 13 67 89 1958 17 193 13 13 149 41 2008 61 229 167 13 37 31 I found some time early this AM (jet lagged) to look at this again. Although my Perl code and Eamonn's Python code follow the same principal, Python has the benefit of arbitrary precision integers, whereas my Perl prototype does not. This explains most of the discrepancies in the lower right corner of my previous post. The differences are now limited to those solutions with composite index numbers. Edited: 19 Apr 2008, 8:53 a.m.

 Re: SSMC20 Challenge 5. (answers w/ question)Message #48 Posted by Eamonn on 10 Apr 2008, 1:14 p.m.,in response to message #41 by Egan Ford Hi Egan, Thanks for the tip about Sage - I have not come across it before. I will investigate some more. For my day job, I do quite a bit of numerical processing with Python, using Numpy and Scipy to simulate wireless communications systems. I used to use Matlab, which is great for scripting small stuff, but it's not an ideal language for large projects. I have never used Perl. When I was looking around for a good general purpose scripting language, Python won out with its clean syntax and libraries for numerical computations. They both appear to be equally capable though. Best Regards, Eamonn.

 Re: SSMC20 Challenge 5. (answers w/ question)Message #49 Posted by Egan Ford on 11 Apr 2008, 3:59 p.m.,in response to message #40 by Eamonn Quote: If anyone is interested, let me know and I can post the python code. Please do.

 Re: SSMC20 Challenge 5. (answers w/ question)Message #50 Posted by Eamonn on 11 Apr 2008, 10:07 p.m.,in response to message #49 by Egan Ford Hi Egan, Here it is. The function findit takes x1 and k as the input parameters and returns the index and the remainder. I have not had time to figure out why it fails for the (1958,8) test case since my last post. If you wouldn't mind posting your perl code for comparison that would be great. A couple of tips for anyone trying to follow the code that hasn't seen python before: - Python doesn't use { and } as in c to group lines of code into a block. Instead, it treats lines of code at the same indentation as a single block of code. - % is the python modulo operator (eg. 17 % 5 = 2) - ** is the python power operator (eg. 2 ** 5 = 32) - # is the python comment indicator Best Regards, Eamonn def findit(x1, k): a = 1 done = False while done == False: d = 0 xn = x1 nxn = xn a += 1 for n in range(1, a): # c equivalent is: for ( n=1 ; n<(a-1) ; n++ ) np1xnp1 = nxn + xn ** k d = 0 if a != n+1: # search below will fail if a == n+1 while (d*a + np1xnp1) % (n+1) != 0 and done == False: d+=1 if d > n+1: # Failed to find a solution to the modulo problem done = True a = -1 xn = ( ( d * a + np1xnp1 ) / (n+1) ) % a np1xnp1 = np1xnp1 % a nxn = np1xnp1 if nxn != 0: done = True return (a, nxn) Edited to fix small cut/paste error in original posted code Edited: 12 Apr 2008, 12:38 a.m.

 Re: SSMC20 Challenge 5. (answers w/ question)Message #51 Posted by Eamonn on 14 Apr 2008, 1:41 a.m.,in response to message #50 by Eamonn Egan, Valentin, My intention was to port the above algorithm or a slightly modified version to the HP-71B. After examining some more cases however, it is clear that the problem of multiple solutions to xn mod a, when (n * xn) mod a is known, is the root of the problem with this approach. I made an attempt at trying to decide between the possible solutions by making use of the previously calculated and stored solution to xn mod (a-1). However there are cases where this approach also fails to find a unique solution for xn mod a. This is certainly an interesting problem to work on. I now know a lot more about modular arithmetic that before, having now come across the linear congruence theorem, the extended Euclidean algorithm and the Chinese remainder theorem. Still not quite there yet with a solution. From your previous posts Valentin, it appears that you are using perhaps a different approach. I look forward to when you publish your solution, or to Egan's or anyone else's solution also. Best regards, Eamonn.

 Re: SSMC20 Challenge 5. (answers w/ question)Message #52 Posted by PeterP on 14 Apr 2008, 11:04 p.m.,in response to message #51 by Eamonn Eamonn, Sorry to bug you, but would you possibly be so kind and post (or email) me the key pieces you found to learn about the items you mentioned about modular arithmetic? I never learned it in school yet found it very interesting. Thanks for your and Egan's ongoing posting on this problem, I'm a silent follower... Cheers Peter

 Re: SSMC20 Challenge 5. (answers w/ question)Message #53 Posted by Eamonn on 15 Apr 2008, 11:46 p.m.,in response to message #52 by PeterP Hi Peter, No problem - I found most of the information searching for "modulo arithmetic". The most straightforward explanations that I found are on Wikipedia at the links below. I hope you find them useful. By the way, I was reading through your solution to Problem #4. I see that you have some modular arithmetic in there, so you seem to know a thing or two about it :-) I'll have to study your solution a bit more to fully understand it, but it looks pretty impressive. Best Regards, Eamonn

 Re: Challenge 3Message #55 Posted by J-F Garnier on 10 Apr 2008, 7:18 a.m.,in response to message #54 by PeterP Hi Peter, I'm still working on my program (not yet running), but I think your result is correct. Let's try to verify how Susan and Peter were thinking: P=52, so Peter can't determine if the numbers are (2,26) or (4,13). S=17, so Susan can't determine if the numbers are: (2,15), (3,14), (4,13), (5,12), (6,11), (7,10) or (8,9) and she is sure that in any case Peter can't determine the numbers because none of her candidate number pairs is made of 2 prime numbers. As Peter now knows that, he can think like this: His (2,26), (4,13) candidate number pair makes the following possible sum: 28 and 17. If the sum would be 28, would Susan be able to be sure that Peter can't determine the numbers? No, because with a sum of 28 the Susan's candidate number would be: (2,26), (3,25), (4,24), (5,23), (6,22), (7,21) ... and (5,23) is made of 2 prime numbers. So now, Peter KNOWS that the sum is 17, and thus knows the numbers are 4 and 13. Is now Susan able to find the numbers? Her candidate numbers are (2,15), (3,14), (4,13), (5,12), (6,11), (7,10) or (8,9), so the possible products are: 30, 42, 52, 60, 66, 70 and 72. If Peter was able to find the number in only one case, then it would tell Susan the solution. Would Peter have been able to find the numbers in another case than the correct P=52? If the product would be 30, the possible candidates of Peter would have been (2,15) and (3,10), (6,5) and Peter sum's candidate would be 17, 13, 11. With all these odd sums, Susan would be sure because no odd number is the sum of 2 prime numbers, So in this case, Peter would not have find the numbers. If the product would be 42, the possible candidates of Peter would have been (2,21) and (3,14), (6,7) and Peter sum's candidate would be 23, 17, 13. With all these odd sums, Susan would be sure because no odd number is the sum of 2 prime numbers, So in this case, Peter would not have find the numbers. If the product would be 52, the possible candidates of Peter would have been (2,26) and (4,13) and Peter sum's candidate would be 28, 17. With 28, Susan would not be sure because 28 may be = 5+23 (prime numbers), With 17, Susan would be sure because no odd number is the sum of 2 prime numbers, So in this case, Peter would have find the numbers (4,13) [that he actually did]. If the product would be 60, the possible candidates of Peter would have been (2,30) and (3,20), (4,15), (5,12), (6,10) and Peter sum's candidate would be 32, 23, 19, 17 and 16. With 32, Susan would not be sure because 32 may be = 3+29 (prime numbers), With 16, Susan would not be sure because 16 may be = 3+13 (prime numbers). With the other odd sums, Susan would be sure because no odd number is the sum of 2 prime numbers, So in this case, Peter would not have find the numbers. If the product would be 66, the possible candidates of Peter would have been (3,22) and (6,11) and Peter sum's candidate would be 25, 17. With it, Susan would be sure because no odd number is the sum of 2 prime numbers, So in this case, Peter would have find the numbers. If the product would be 70, the possible candidates of Peter would have been (5,14) and (7,10) and Peter sum's candidate would be 19, 17. With it, Susan would be sure because no odd number is the sum of 2 prime numbers, So in this case, Peter would have find the numbers. So there is only one case where Susan can find the numbers knowing that Peter did it. The numbers are 4 and 13, if I'm correct. Valentin, can you confirm if this is correct? Edited: 10 Apr 2008, 7:23 a.m.

 Re: Challenge 3Message #56 Posted by Valentin Albillo on 10 Apr 2008, 7:28 a.m.,in response to message #55 by J-F Garnier Hi, J-F: Jean-Fran�ois posted: "The numbers are 4 and 13, if I'm correct. Valentin, can you confirm if this is correct ?" Yes I can and yes, they are correct. Congratulations both to PeterP for his insight and clever RPN program and to you for your accurate logic and detailed explanation. See to it that an HP-71B program is created to find the solution, nothing less is to be expected from Emu71's creator. :-) Best regards from V.

 Re: Challenge 3Message #57 Posted by PeterP on 10 Apr 2008, 12:05 p.m.,in response to message #55 by J-F Garnier wow, this is a brilliantly clear explanation, J-F. I wish I had had you as a teacher J-F, I'm very impressed. Attention, potential spoiler - having finished the challenge I did allow myself to google for Mrs Germain and found this link to learn that she is actually quite famous and has a very moving and impressive live. And her first name is Sophie... Cheers Peter

 Re: Challenge 3Message #58 Posted by J-F Garnier on 10 Apr 2008, 3:21 p.m.,in response to message #55 by J-F Garnier Below is my program for the HP-71B. I used an idea from Peter, i.e. a even number is always the sum of 2 prime numbers, this avoids to explicitly test for prime numbers. I found the same solution than Peter: (4,13) but the surprise is that my program finds three other possible solutions. I checked the (13,16) pair by hand in a similar way than I checked the (4,13) pair above, and it seems OK. Can somebody confirm it with another method, or did I something wrong? J-F 10 ! --- S&SMC 20 --- 20 ! JFG tentative solution 30 FOR S1=7 TO 100 STEP 2 ! for all plausible sums 40 C2=0 50 ! consider all possible pairs (A1,B1) for the given sum S1 60 FOR A1=2 TO S1/2 70 B1=S1-A1 80 P1=A1*B1 ! tentative product 90 ! consider all the pairs for the tentative product P1 100 C=0 110 FOR A2=MAX(2,INT(P1/99)) TO SQRT(P1) 120 IF MOD(P1,A2)#0 THEN 180 130 B2=P1/A2 140 S2=A2+B2 150 IF MOD(S2,2)=0 THEN 180 160 C=C+1 ! count the odd sums 170 IF C=1 THEN A8=A2 @ B8=B2 ! store possible solution 180 NEXT A2 190 IF C=1 THEN A9=A8 @ B9=B8 @ C2=C2+1 ! one possible solution 200 NEXT A1 210 IF C2=1 THEN DISP A9,B9 ! this is a solution 220 NEXT S1 >RUN 4 13 13 16 4 37 16 37 Edited: 10 Apr 2008, 3:35 p.m.

 Re: Challenge 3Message #59 Posted by Valentin Albillo on 10 Apr 2008, 7:46 p.m.,in response to message #58 by J-F Garnier Hi, J-F: Jean-Fran�ois wrote: "I checked the (13,16) pair [...] and it seems OK. Can somebody confirm it with another method, or did I something wrong ?" Sorry, J-F but (13,16) isn't another solution, your program is nice but slightly simpler than needed here. The pair (13,16) has sum 29. With that sum the first three dialogs would be fulfilled but not the fourth, i.e, Peter, given the product of 13*16 = 208 would be able to deduce the correct pair after Susan's first comment. But the fourth dialog cannot be fulfilled: Susan has no way to know if the correct sum, 29, came as 2+27 or 13+16. Think about it. Thanks for your interest and Best regards from V.

 Re: Challenge 3 - correctedMessage #60 Posted by J-F Garnier on 11 Apr 2008, 8:15 a.m.,in response to message #59 by Valentin Albillo OK, I see my mistake, my assumption "no odd number is the sum of 2 prime numbers" is obviously false... Here is my corrected program, a bit less simple as I had to explicitly test for some prime numbers. J-F 10 ! --- S&SMC 20 --- 20 ! JFG corrected solution 30 FOR S1=5 TO 195 STEP 2 ! for all plausible sums 35 IF FNP(S1-2) THEN 220 40 C2=0 50 ! consider all possible pairs (A1,B1) for the given sum S1 60 FOR A1=2 TO S1/2 70 B1=S1-A1 80 P1=A1*B1 ! tentative product 90 ! consider all the pairs for the tentative product P1 100 C=0 110 FOR A2=MAX(2,INT(P1/99)) TO SQRT(P1) 120 IF MOD(P1,A2)#0 THEN 180 130 B2=P1/A2 135 IF B2>99 THEN 180 140 S2=A2+B2 150 IF MOD(S2,2)=0 THEN 180 155 IF FNP(S2-2) THEN 180 160 C=C+1 ! count the items not a sum of 2 prime numbers 170 A8=A2 @ B8=B2 ! store possible solution 180 NEXT A2 190 IF C=1 THEN A9=A8 @ B9=B8 @ C2=C2+1 ! one possible solution 200 NEXT A1 210 IF C2=1 THEN DISP A9,B9 ! this is a solution 220 NEXT S1 230 END 240 DEF FNP(X) ! test if X is prime (X odd, X<200) 250 FNP=0 260 IF X=3 OR X=5 OR X=7 OR X=11 OR X=13 THEN FNP=1 270 IF MOD(X,3) AND MOD(X,5) AND MOD(X,7) AND MOD(X,11) AND MOD(X,13) THEN FNP=1 280 END DEF >RUN 4 13 Edited: 12 Apr 2008, 10:43 a.m.

 Challenge 4Message #61 Posted by PeterP on 12 Apr 2008, 9:52 p.m.,in response to message #1 by Valentin Albillo I approached the 4th challenge first with paper and pencil. Soon I was back to prime-factorizations and developed a matrix representation scheme that proved quite useful. Lets call our input numbers ni with i=1,2,...NMax. NMax := 5 for the stated problems and we'll generaly use super-scripts for our input-numbers Let P = (p1,p2,...,pnp) be a vector which holds all prime-factors that appear at least in one of the input numbers ni So each ni = product(p1k1i,p2k2i,...,pnpknpi) We can now arrange the prime-factorization of our input numbers in a neat matrix PFM (PrimeFactorizationMatrix) with np rows and NMax columns. with pfm(row,column) = krowcolumn so for example for the set (50,1958,2008) we would have P = (2,5,11,89,251) |1 1 3| |2 0 0| PFM = |0 1 0| |0 1 0| |0 0 1| as 50 = 21*52*110*890*2510 1958 = 21*50*111*891*2510 2008 = 23*50*110*890*2511 Next I decided to respresent the constant we are asked to find C(n1,n2,...,nNMax) in its prime factorization form using the elements of P. This means we have to find a seperate ci for each row of PFM. Sounds like it has gotten worse, now we are looking for np constants... To generate perfect powers, there needs to be a value ppi for each number ni for which kji MOD ppi = 0 for all j=1,2,...,np The following algorithm does most likely not find the smallest constat C = product(p1c1,p2c2,...,pnpcnp) as I have arbitrarily assigned pp1 = 2,pp2 = 3,pp3 = 5, etc. I believe this to be not a horrible choice but I'm sure one can find smaller C in certain cases. Basically, depending on the relationship between the kji there is an optimal set of ppi but I could not figure out an easy way to find that set. From here we can build a relatively fast and straight forward code which, however, I implemented in the 71b (learning a lesson from the last challenge). Get the number of input numbers N1 and the input numbers N() Store the pp in R() with R1=2,R2=3etc Calculate the prime factorization of each number, storing the set of appearing prime-factors in P() and the PFM matrix in P1() Loop over all rows j Calculate the first possible integer T = [RN1 - k1N1 Mod RN1] Mod RN1. I'm sure there is a prettier calculation but this one works at least... Check if the sum of all the (T+kji) Mod Rj = 0 If not, increase T by RN1. This is similar to the Sieve of Eratosthenes Next row j Two comments to the code below. First, I am very inexperienced with using the 71b so please forgive the cluncky code. Second, I used the math-rom and the JPC rom which made the code easier to write, hoping that the kind author of the challenge will overlook this. The code produces the following answers C(41,67) = 413 * 672 C(1776,2008) = 33 * 373 * 2512 C(2007,2008) = 2233 * 2512 C(50,1958,2008) = 217 * 1120 * 8920 * 25124 C(2,3,4) = 23 * 320 C(3,4,5) = 315 * 210 * 524 C(2,3,4,5) = 263 * 3140 * 590 C(2,3,4,5,6) = 2483 * 3560 * 51980 C(10,11,12,15,16) = 22163 * 5825 * 11770 * 3594 C(71,42,15) = 7115 * 220 * 314 * 720 * 524 Listing (mod typos) 10 Option Base 1 @ Destroy All 20 Input "Nr of Integers: ";N1 30 Dim R(6) @ R(1)=2 @ R(2)=3 @ R(3)=5 @ R(4)=7 @ R(5)=11 @ R(6)=13 40 Dim N(N1) @ Dim P(20) @ Dim P1(20,N1) @ Dim R(N1) 50 Mat Input N @ k = 0 55 REM Calculate all primfactors P and matrix PFM (:=P1) 60 For i = 1 To N1 70 X = PRIM(N(i)) @ If X = 0 Then X = N(i) 80 While N(i) <> 1 90 k = k+1 @ P(k) = X 100 For j = 1 To N1 @ P1(k,j) = FNC(N(j),X) @ N(j) = N(j)/X^P1(k,j) @ Next j 110 X = PRIM(N(i)) @ If X = 0 Then X = N(i) 120 End While 130 Next i @ Dim P1(K,N1) @ Dim P(K) 135 REM Calculate constant, prime-factor by prime-factor 140 For L = 1 to K 150 X = Mod(P1(L,N1),R(N1)) 160 T = Mod(R(N1)-X,R(N1)) 170 S = 0 @ For j = 1 to N1 @ S = S + Mod(T+P1(L,j),R(j)) @ Next j 180 While S <> 0 190 T = T + R(N1) 200 S = 0 @ For j = 1 to N1 @ S = S + Mod(T+P1(L,j),R(j)) @ Next j 210 End While 220 Disp P(L);"^";T;" * " 230 Next L 240 Disp "1. Done!" @ Beep 500 Def FNC(N,F) @ C=0 @ While FP(N/F) = 0 @ C=C+1 @ N=N/F @ End While @ FNC=C @ End Def Edited: 16 Apr 2008, 10:22 a.m. after one or more responses were posted

 Re: Challenge 4Message #62 Posted by J-F Garnier on 14 Apr 2008, 7:28 a.m.,in response to message #61 by PeterP Hi Peter, I can't make your program running, probably some typos... J-F

 Re: Challenge 4Message #63 Posted by PeterP on 14 Apr 2008, 9:44 a.m.,in response to message #62 by J-F Garnier J-F, Thanks, yes there was a typo in line 100 (* instead of @). It should work now but I can't check (in the office and don't have the calc with me or your simulator...) Thanks for letting me know!! Cheers Peter

 Re: Challenge 4Message #64 Posted by Steve Perkins on 14 Apr 2008, 1:14 p.m.,in response to message #62 by J-F Garnier Is there an "easy" or at least straight-forward way to cut and paste code like this into the simulator? I'd like to try it myself, but don't have time to retype it just now. Thanks for the wonderful EMU71 by the way, and any help you (or others) can give!

 Re: Challenge 4Message #65 Posted by Valentin Albillo on 14 Apr 2008, 2:04 p.m.,in response to message #64 by Steve Perkins Hi, Steve: Steve posted: "Is there an "easy" or at least straight-forward way to cut and paste code like this into the simulator?" Well, yes ... as "easy" as copying the text listing from the web page and pasting it into Emu71 in a newly created, empty program file. Or are you saying you don't know how to copy and paste text between a Windows GUI application and a console-style one ? Also, there's some controversy on whether to call this kind software "emulator" or "simulator". My own criterium is to call it "emulator" when it's actually using the original ROM assembler code which gets executed by an emulated CPU (Saturn for the HP-71B), and "simulator" otherwise (i.e., doesn't use the original ROMs nor does it execute original assembler code). Using this criterium, Emu71 is an "emulator" for me, not a "simulator". And a pretty good one at that. Best regards from V.

 Re: Challenge 4Message #66 Posted by Steve Perkins on 14 Apr 2008, 8:13 p.m.,in response to message #65 by Valentin Albillo You're right, of course. I should have used the term "emulator" for the excellent EMU71. As for the copying and pasting, I should have explained my problem. I assumed the same thing afflicted everyone. When I try to paste a copied line, most of the text gets missed. Only a few characters get entered. It seems the emulator is looking for keystrokes and missing some when the come to quickly for the original ROM code to copy with perhaps? This is in a Windows XP cmd.exe window. Does anyone else have this problem? Or does it work better in another environment? For instance, trying to paste (from the above code) line 240, instead of 240 Disp "1. Done!" @ Beep I get 24d1N"E

 Re: Challenge 4Message #68 Posted by J-F Garnier on 15 Apr 2008, 6:43 a.m.,in response to message #66 by Steve Perkins Hi Steve, Valentin explained all (Thanks, Valentin!) Please have a look here and let me know if you still have problems. J-F

 Re: Challenge 4Message #69 Posted by Steve Perkins on 15 Apr 2008, 12:34 p.m.,in response to message #68 by J-F Garnier Thanks, I'll install the latest right away. I feel silly that this wasn't an obvious thing for me to try. Update: works as advertised! Thanks for the advice, and especially for the fantastic software!

 Re: Challenge 4Message #70 Posted by Steve Perkins on 15 Apr 2008, 2:33 p.m.,in response to message #61 by PeterP Nicely done Peter! I did have to make a correction to line 220. It seemed you meant to display entries from the P() array. And a small improvement: 220 If T>0 Then Disp P(L);"^";T;" * " Other than that, I double checked most of the outputs and it ran as you specified. I'm getting more fond of the math and JPC roms too! I wish I had some good documentation for the math rom, since I finally got one with an HP-71B I acquired. Very nicely analyzed and programmed. Edited: 15 Apr 2008, 2:55 p.m.

 Re: Challenge 4Message #71 Posted by PeterP on 15 Apr 2008, 4:57 p.m.,in response to message #70 by Steve Perkins Steve, thanks for your kind words, improvement and identification of Typo! I was too elated & spent at that point to improve :-) As for the math rom documentation, you can find it on the fantastic DVD that Dave hicks sells here on the museum (aside from all sorts of other goodies). Check out this link And for the JPC rom, J-F has put together a great resource including manuals. Check out this link Cheers Peter

 Last chance (Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special) Message #72 Posted by Valentin Albillo on 15 Apr 2008, 7:52 a.m.,in response to message #1 by Valentin Albillo Hi, all: Within the next day or two I'll post my original solutions to the current S&SMC#20 so if you want to post yours before I do, this is your last chance. It depends of my workload and free time availability but I'd say you still have some 24 to 72 hours before the deadline. As requested, I've extended it past the one-week usual length to allow Egan, Eamonn, and all others to refine or correct their solutions, but it seems all's said and done by now. Thanks to all for your interest and willingness to share and Best regards from V.

 Re: Last chance (Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special) Message #73 Posted by Egan Ford on 15 Apr 2008, 5:32 p.m.,in response to message #72 by Valentin Albillo Hola Valentin, Sadly, I've been swamped with work and travel for the last 5 days with no outlook of enough downtime to revisit #5 or #4. (Not far from you actually, in Sevilla now.) That said I have not given up, but fear I will run out of time.

 Re: Last chance (Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special) Message #74 Posted by Valentin Albillo on 21 Apr 2008, 11:23 a.m.,in response to message #73 by Egan Ford Hi, Egan: I've posted my original solutions and comments for all problems except the last three, which include the ones you've been working on. Within 24 hours I'll post the remaining solutions, so I sincerely hope you'll be able to make it. It's already some 21 days since I posted the challenge and the start of the thread risks disappearing on its way towards the Archives, which would render it incomplete ... :-) Best regards from V.

 Re: Last chance (Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special) Message #75 Posted by Egan Ford on 21 Apr 2008, 5:43 p.m.,in response to message #74 by Valentin Albillo Thanks for the extra time. Unless an Ah-ha! strikes before I sleep I am afraid all I have is a solution that will correctly find the index only if it is prime. The composite indexes still elude me. Incomplete 71B entry (bold are wrong): K= 2 X1= 15 INDEX= 67 REM= .268656716418 K= 2 X1= 41 INDEX= 17 REM= .235294117647 K= 2 X1= 42 INDEX= 59 REM= .559322033898 K= 2 X1= 50 INDEX= 67 REM= .268656716418 K= 2 X1= 67 INDEX=109 REM= .238532110092 K= 2 X1= 71 INDEX= 17 REM= .235294117647 K= 2 X1=1958 INDEX= 17 REM= .235294117647 K= 2 X1=1992 INDEX= 17 REM= .235294117647 K= 2 X1=2008 INDEX= 61 REM= .983606557377 K= 2 X1= 99 INDEX=103 REM= .650485436893 K= 3 X1= 2 INDEX= 89 REM= .460674157303 Code: 10 DESTROY ALL @ OPTION BASE 0 20 ! INPUT "k=";K @ INPUT "x1=";X1 @ CALL DOIT(K,X1,I,R) 30 FOR J=1 TO 11 @ READ K @ READ X1 @ CALL DOIT(K,X1,I,R) 40 DISP "K=";K;" X1="; 50 DISP USING "4D,7A,3D,5A,D.12D";X1," INDEX=",I," REM=",R/I 60 NEXT J 70 END 80 DATA 2,15,2,41,2,42,2,50,2,67,2,71,2,1958,2,1992,2,2008,2,99,3,2 90 SUB DOIT(K,X1,I,R) 100 DIM P(100) @ P(0)=2 @ L=1 @ Q=2 110 'START': X=X1 @ CALL NPRIME(Q,P(),L) 120 FOR N=1 TO Q 130 X=MOD(X,Q) @ T=X 140 FOR J=1 TO K-2 @ T=T*X @ T=MOD(T,Q) @ NEXT J 150 Y=MOD(X*(T+N),Q) 160 IF Y=0 THEN GOTO 'START' 170 FOR Z=1 TO Q 180 IF MOD(Z*(N+1),Q)=Y THEN X=Z @ GOTO 210 190 NEXT Z 200 I=N+1 @ R=Y @ GOTO 220 210 NEXT N 220 END SUB 230 SUB NPRIME(Q,P(),L) 240 J=P(L-1) 250 J=J+1 260 FOR I=0 TO L-1 270 IF MOD(J,P(I))=0 THEN 250 280 NEXT I 290 Q=J @ L=L+1 @ P(L-1)=Q 300 END SUB Edited: 21 Apr 2008, 6:33 p.m.

 Re: Last chance (Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special) Message #76 Posted by Eamonn on 22 Apr 2008, 2:18 a.m.,in response to message #75 by Egan Ford Nice Work Egan. I am in more or less the same boat as you - I have an algorithm that works for the cases where the index is prime. Kudos to you though for submitting an actual solution for a programmable calc. Having spent quite a bit of time on this problem over the past few weeks, I am really looking forward to seeing Valentin's solution. I am pretty sure that I will learn a lot from it, as usual. Best regards, Eamonn.

 Re: Last chance (Re: Short & Sweet Math Challenge #20: April 1st, 2008 Spring Special) Message #77 Posted by Egan Ford on 22 Apr 2008, 9:45 a.m.,in response to message #76 by Eamonn Thanks. Here's more stuff. If you replace lines 10-80 with: 5 DESTROY ALL @ OPTION BASE 0 @ DIM X(6) @ DIM Y(8) @ DIM Z(6) 10 DISP " x1"; 15 FOR J=1 TO 6 @ READ X(J) @ IF X(J)<10 THEN DISP " "; 20 DISP " k=";STR\$(X(J)); @ NEXT J 25 DISP @ FOR J=1 TO 40 @ DISP "-"; @ NEXT J @ DISP 30 FOR J=1 TO 8 @ READ Y(J) @ NEXT J 35 T=TIME 40 FOR J=1 TO 8 @ FOR L=1 TO 6 @ CALL DOIT(X(L),Y(J),I,R) 45 Z(L)=I @ NEXT L 50 DISP USING "4D,6D,6D,6D,6D,6D,6D";Y(J),Z(1),Z(2),Z(3),Z(4),Z(5),Z(6) 55 NEXT J 60 DISP "TIME:";TIME-T 65 END 70 DATA 2,3,4,6,8,10 75 DATA 15,41,42,50,67,71,1958,2008 You can generate the following table (errors in bold): x1 k=2 k=3 k=4 k=6 k=8 k=10 ---------------------------------------- 15 67 197 173 37 37 31 41 17 79 17 83 23 23 42 59 151 23 37 17 31 50 67 193 13 37 23 41 67 109 89 97 37 23 83 71 17 79 17 13 67 89 1958 17 193 13 13 149 41 2008 61 229 167 13 37 31 TIME: 122.06 2 minutes with EMU71. I didn't have time to test a physical 71B. I am guessing that it would have taken hours. If any are interested I have qbasic versions as well. The above code runs in less than a second compiled with FreeBASIC. Edited: 22 Apr 2008, 9:52 a.m.

 Re: My Original Solutions and Comments - Part 1 (Re: S&SMC#20)Message #79 Posted by Fernando del Rey on 21 Apr 2008, 1:48 p.m.,in response to message #78 by Valentin Albillo Dear Valent�n, Just a couple of lines from someone who has dedicated some time to work on the S&SMC#20 challenges (though admittedly not enough time), without reaching anything that would be worth posting on the Forum. I�m pretty sure there are many others anonymous readers like me, who have enjoyed the challenges and the ingenious responses from the clever people in this Forum. Even though I have not contributed back, I still fully appreciate your efforts and those of the other contributors, and wish to publicly thank you for it. And if I may ask for a wish: why don�t you make the S&SMC a once-per-year event, always on April 1st. It would make a nice tradition in this Forum. Still, if you call it quits on #20, I must say you�ve done more than enough. I will look forward to your mini-challenges. Regards, Fernando

 Re: My Original Solutions and Comments - Part 1 (Re: S&SMC#20)Message #80 Posted by Valentin Albillo on 21 Apr 2008, 5:18 p.m.,in response to message #79 by Fernando del Rey Hi, Fernando: Thanks for your kind & friendly comments. Re making S&SMC's a once-per-year affair, it's actually what I've been doing for the past three years (save for the Valentine's Day Special, which was intended as training for the April's Fool one). However, taking this last S&SMC#20 as an example, I began to research materials for it as early as January. Making a long list of suitable problems, refining it to a short list, then programming my own original solutions to the problems (including lots of test cases, optimizing, and debugging) took the remaining time till I posted the result last April 1st. In other words, a lot of free time used for this and a lot of work. Even if once a year. And the participation, however high-level it might be, just doesn't warrant it. Thinking otherwise amounts to delusion, which I'm not prone to. So I'll stick to mini-challenges for now. Thanks a lot for your interest and kind words, it's a pity I never got to see your solutions (or even attempts at solving my challenges). I know you are fully capable to solve them all hands down if given just a tiny amount of free time, which regrettably I also know you simply don't have. Very Best regards from V.

 Re: My Original Solutions and Comments - Part 1 (Re: S&SMC#20)Message #81 Posted by Marcus von Cube, Germany on 30 Apr 2008, 3:52 a.m.,in response to message #79 by Fernando del Rey Hi Valentin, I was hoping to find the time to tackle some of the problems you posted in S&SMC#20 but my job simply didn't leave enough time. :( My HP-50g happily solved the prechallenge #2 and I found out about the identity in prechallenge #3. But that was it. (My knowledge about eigenvalues has faded away in the last 24 years.) What I still don't get is the reasoning behind challenges #1 and #2. What has the number of bits to do with the sum of powers or the pairwise sums? Is this an incident you need to know about or can it be deducted in an understandable way? Thanks again for your efforts which make me feel like an (April's) fool in most of the cases. Marcus

My Original Solutions and Comments - Part 3 (Re: S&SMC#20) [LONG and I mean it]
Message #84 Posted by Valentin Albillo on 26 Apr 2008, 10:47 p.m.,
in response to message #78 by Valentin Albillo

Hi, all:

This is Part 3 of "S&SMC#20: My Original Solutions & Comments" which at long last concludes with my solution for the very last (and most difficult) subchallenge #5. Several of you bravely attempted to conquer it with various degrees of success: both Eamonn and Egan Ford posted actual results and finally Egan posted HP-71B code. However, their results do not fully agree with mine in all cases for whatever reasons. That said, let's proceed:

The Challenge (concluded)

5 - Least Simple

"The sequence defined by

(n + 1) * xn+1 =  n*xnk + xn

with k = 2 and x1 = 3, continues with x2 = 6, x3 = 16, x4 = 76, x5 = 1216, and x6 = 247456, all of which are nicely integer. Regrettably, x7 = 8747993810.2857..., which is not. Write a program which, given k and x1, both integer and > 1 , finds and outputs both the index of the first element of the sequence which fails to be an integer, if any, as well as its nonzero fractional part."

The fun factor here is that the task would be absolutely trivial were it not for the fact that the terms of the sequence grow unbelievably enormous extremely quickly for most values of k and x1. Just for instance, for the "simplest" case k=2 and x1=2, the sequence merrily goes:

x2 = 3, x3 = 5, x4 = 10, x5 = 28, x6 = 154, x7 = 3520, x8 = 1551880, x9 = 267593772160, x10 = 7160642690122633501504, ...

and so on till the last integer element at index 42, which has about 89,288,343,500 digits !!. The next element, x43, is *not* integer and, using the asymptotic formula:

xn = ( n + 2 - 1/n + 4/n2 - 21/n3 + 138/n4 - 1091/n5 + ...) * C2n

where C = 1.04783144758..., approximately evaluates to:

x43 = 5.41 * 10 178,485,291,567

but a number more than 178 billion digits long isn't something that any current computer can handle, let alone handheld programmable calculators, not even HP's. Now, if this is the case for the quite modest k=2, x1=2, and x43, just try to imagine the humongous size of x601 (!!), the first non-integer element for k=3, x1=11. Even merely computing its exact size is far from trivial, let alone the element itself !

Consider also the extremely disconcerting mathematical nature of what's happening here: a simple recurrence which unfailingly produces a sequence of integer elements for the first 600 cases suddenly and most unexpectedly results in a non-integer one for case 601, and the same goes for other values of the parameters.

What to do ? Well, I see three possible approaches. On one extreme you could try using the full multiprecision route and proceed to compute each element till the first non-integer one is found. This may succeed for a few values of k and x1 (k=2, x1=3 or k=8, x1=10, for instance) but for the most part, as seen in the case of k=2, x1=2, it's a totally hopeless dead end, now and in the foreseeable technological future.

The other extreme would be using as little multiprecision as possible or even none at all and try to cope using modular arithmetic and solving congruences to go forward seeking for the elusive non-integer element. This is mostly the route Eamonn and Egan followed, but though they succeeded in the majority of cases at minimal computing cost, they found some recalcitrant ones which, at the time of writing this, they haven't completely succeeded in ironing out.

My original solution is an intermediate one. I don't use the full multiprecision approach, as I quickly saw the task was impossible, but I'm using modular arithmetic to a sufficiently high precision (up to 500 digits for the version I'm posting here) that the algorithm is straightforward and no ambiguities arise at any point, just a very simple loop till either the first non-integer element is found, or the maximum precision is reached, or time becomes excessive, whichever comes first.

The only problem for me is that I wanted to implement my solution for the HP-71B which, regrettably, lacks the multiprecision integer features of advanced RPL models. However, this only means that besides the simple code to implement the main algorithm (6 lines), I needed to implement a multiprecision "library" which would allow calls from the main program to perform the requested multiprecision operations on demand.

This isn't particularly easy, most specially as it must both run fast and be as small and compact as possible since this is a simple S&S Math Challenge, not a full-fledged article on how to implement multiprecision libraries in the HP-71B. With that in mind, I created the following original solution for the HP-71B:

Main program (just 6 lines of HP-71B BASIC code implementing the base algorithm):

10 DESTROY ALL @ OPTION BASE 1 @ D=200 DIV 6+1 @ DIM F(D),X(D),Y(D),Z(D) 20 INPUT "K,X1=";K,X1 @ SETTIME 0 @ FOR N=10 TO 2000 STEP 10 @ CALL MFAC(N,F) 30 DISP N; @ CALL N2M(X1,Y) @ FOR I=2 TO N @ MAT Z=Y @ CALL MDIVK(Z,I-1) 40 CALL MPOW(Z,K,X) @ CALL MSUM(Y,X,Z) @ CALL MMOD(Z,F,Y) @ CALL MMODK(Y,I,M) 50 IF M THEN DISP @ DISP I;M/I;TIME @ END ALL 60 NEXT I @ NEXT N

As HP-71B's BASIC lacks any multiprecision operations, integer or otherwise, the main program simply calls the relevant library functions (you'll find a reasonably detailed description of the library in Apendix A below). The main program is executing the equivalent of the following pseudo-code:

dimension multiprecision variables F, X, Y, and Z to hold a certain number of digits (200 above) ask the user for K and X1 for values of N from 10 to 2000 (both included) and counting in steps of 10, do: assign the factorial of N to F assign the value of X1 to Y for values of I from 2 to N, both included, do assign the value of Y to Z integer-divide Z by I-1 assign the value of Z raised to the kth power to X assign the value of X + Y to Z assign the value of Z Modulus F to Y assign the value of Y Modulus I to M If M is not zero, then we've found the first non-integer element, so output index and fractional part and terminate loop to process the next value of I loop to process the next value of N

My original program is an implementation extensively relying in full multiprecision modular arithmetic, and taking into account the ideas discussed in the book "Mainly Natural Numbers" which you can freely download in PDF format from here. This particular problem is featured in Chapter IV: "Some Sequences of Large Integers", pp. 32-37., though the notation there differs slightly from mine; for instance my case k=2, x1=2, appears there as m=1, x1=2, etc. You're advised to read it for the rigorous analysis and relevant details, as space (and notational difficulty inherent to text-based HTML) does not permit to discuss the subject at lenght here.

Now this is a sample run for the case k=2, x1=41:

>RUN

k,x1=2,41

10 20 ... -> 17 .235294117647 1.53

where the running index is shown at steps of 10 while the computation is in progress, then the index of the first non-integer element is output (17), as well as its fractional part (0.235294117647) and the time it took to find it (1.53 seconds under Emu71, a little over 6 min. in a physical HP-71B).

Note:

The default precision listed above in line 10 is 200 digits, which is more than enough for all the cases I asked except the two final, extra ones which require about 360 and 415 digits, respectively. If you get an error (normally "Subscript") while checking some case, just increase the precision from 200 to some suitable higher value less than 500 in line 10 above.

Running my program for the asked values, one gets the following results and times (for Emu71 @ 2.4 Ghz, single Pentium 4 CPU with 512 Mb RAM under Windows XP Home Edition 2002; for a physical HP-71B, multiply the given times by roughly 250):

k x1 index #digits fractional part time ----------------------------------------------------- 2 2 43 200 0.558139534884 19.10 2 3 7 200 0.285714285714 0.26

2 15 67 200 0.268656716418 77.60 2 41 17 200 0.235294117647 1.53 2 42 59 200 0.559322033898 44.40 2 50 34 200 0.117647058824 10.33 2 67 51 200 0.411764705882 41.56 2 71 17 200 0.235294117647 1.58

2 1958 17 200 0.235294117647 1.64 2 1992 17 0.235294117647 1.64 2 2008 61 200 0.983606557377 77.10

2 99 103 360 0.650485436893 593.41 3 2 89 415 0.460674157303 686.60

and further this is a short table of extra results for comparison purposes with the book and/or your own programs (140 digits are more than enough so edit line 10 accordingly):

k x1 index #digits fractional part time ----------------------------------------------------

3 6 31 140 0.645161290323 16.40 4 7 13 140 0.692307692308 2.02 6 11 19 140 0.263157894737 5.19 8 3 7 140 0.285714285714 0.60 8 8 17 140 0.588235294118 6.01

Finally, this is an extensive table of results obtained with a different version of my ad-hoc library, which allows for much greater number of digits but takes at least one order of magnitude longer (the posted version can only handle slightly less than 500 digits, being limited by the exponent range of the built-in REAL precision, but it's smaller and much faster, and thus better suited for the cases asked in this subchallenge).

For each assorted x1 and k, two numbers are given: the index of the first non-integer element, and the approximate number of digits necessary to carry out the computations, which will appear as "?" if the program could not reach far enough before I gave up due to timing considerations. Some of these results appear in the book I mentioned (and fully coincide with them), but the rest I've never seen published before so this can be considered original research publicly appearing for the first time in the World Wide Web and so independent corroboration would be most welcome.

x1 K=2 K=3 K=4 K=5 K=6 K=7 K=8 K=9 K=10 ---------------------------------------------------------------------------------------------------------- 2 43 103 89 395 97 598 214 2024 19 95 239 ? 37 331 79 1036 83 1222 3 7 6 89 403 17 54 43 255 83 733 191 2464 7 20 127 1901 31 323 4 17 27 89 403 23 84 139 1182 13 52 359 ? 23 167 158 2502 41 469 5 34 74 89 402 97 599 107 845 19 95 419 ? 37 331 79 1030 83 1224 6 17 27 31 97 149 1032 269 ? 13 47 127 1477 23 169 103 1449 71 1000 7 17 26 151 788 13 35 107 849 37 250 127 1475 37 332 103 1457 83 1226 8 51 128 79 343 13 35 214 2025 13 50 239 ? 17 107 163 ? 71 1000 9 17 25 89 402 83 491 139 1180 37 247 191 2464 23 167 103 1453 23 211 10 7 6 79 343 23 84 251 2460 347 ? 239 ? 7 19 163 ? 41 476 11 34 73 601 ? 13 34 107 848 19 88 461 ? 37 329 79 1035 31 323 12 17 27 197 1095 97 600 ? ? 37 248 191 2436 17 102 79 1034 41 478 13 17 26 151 788 23 85 ? ? 37 248 127 1480 37 327 158 2495 31 323 14 43 103 158 834 67 369 139 1184 37 245 191 2462 23 161 158 2503 41 473 15 67 186 197 1097 173 1244 139 1182 37 249 ? ? 37 332 127 1902 31 322

41 17 25 79 346 17 52 107 851 83 736 127 1479 23 168 79 1026 23 209 42 59 157 151 789 23 79 251 2462 37 244 191 2463 17 105 ? ? 31 324 50 34 74 193 1070 13 35 107 848 37 248 191 2463 23 169 79 1028 41 478 67 51 129 89 401 97 599 251 2463 37 250 191 2462 23 164 79 1031 83 1227 71 17 26 79 344 17 53 107 850 13 52 127 1477 46 446 ? ? 89 1342 99 103 324 31 97 13 34 139 1182 13 44 ? ? 37 332 151 2355 41 465

1958 17 27 158 834 13 34 251 2461 13 47 ? ? 149 2066 ? ? 41 474 1992 17 27 197 1098 17 53 107 850 109 1040 ? ? 23 168 103 1456 89 1342 2008 61 164 229 1321 167 1191 ? ? 13 52 191 2462 37 327 ? ? 31 322

That's all. This "Short & Sweet Math Challenges" series exclusive to the MoHP ends its run now. The very first S&SMC#1 was posted in May, 27th 2002 at 9:59 a.m., so it's been nearly six years sharing what I hope has been interesting and rarely-seen math ideas and highly creative programming techniques for an incredible variety of HP (and non-HP) calc (and non-calc) models.

Thanks to all of you for your unfailing interest and for your extremely worthy contributions, it's been a pleasure and a continued source of learning and awe to me.

Very Best Regards From V.

Appendix A: The multiprecision library

I'll briefly discuss here the small (just 32 lines of code) "Ad-hoc multiprecision library" I've implemented specifically for this particular subchallenge (the following listing is numbered as if to be included in the same file as the main program without line numbers conflicting, but could reside in a separate program file in RAM as well, if intended to be used by other programs).

70 !
80 SUB MMUL(A(),B(),C()) @ MAT C=ZER @ CALL MTOP(A,U) @ CALL MTOP(B,V)
90 K=1000000 @ FOR I=1 TO V @ M=B(I) @ IF NOT M THEN 120 ELSE L=I
100 FOR J=1 TO U @ N=A(J) @ IF N THEN P=C(L)+M*N @ C(L)=RMD(P,K) @ C(L+1)=C(L+1)+P DIV K
110 L=L+1 @ NEXT J
120 NEXT I
130 SUB MPOW(A(),N,C()) @ IF NOT N THEN MAT C=ZER @ C(1)=1 @ END ELSE MAT C=A
140 IF N=1 THEN END ELSE DIM B(UBND(C,1)) @ U=LOG2(N) @ IF FP(U) THEN 160
150 FOR I=1 TO U @ MAT B=C @ CALL MMUL(B,B,C) @ NEXT I @ END
160 FOR I=2 TO N @ MAT B=C @ CALL MMUL(B,A,C) @ NEXT I
170 SUB MSUM(A(),B(),C()) @ MAT C=A+B @ CALL MNOR(C)
180 SUB MSBI(A(),B()) @ MAT A=A-B @ CALL MNOR(A)
190 SUB MMODK(A(),K,M) @ DIM B(UBND(A,1)) @ MAT B=A @ M=K @ CALL MDIVK(B,M)
200 SUB MDIVK(A(),K) @ FOR I=UBND(A,1) TO 2 STEP -1 @ P=A(I) @ IF P=0 THEN 220
210 A(I)=P DIV K @ A(I-1)=A(I-1)+MOD(P,K)*1000000
220 NEXT I @ P=A(1) @ A(1)=P DIV K @ K=MOD(P,K)
230 SUB MNOR(A()) @ FOR I=1 TO UBND(A,1) @ P=A(I)
240 IF P>999999 THEN A(I)=RMD(P,1000000) @ A(I+1)=A(I+1)+P DIV 1000000
250 IF P<0 THEN A(I)=P+1000000 @ A(I+1)=A(I+1)-1
260 NEXT I
270 SUB MTOP(A(),U) @ FOR U=UBND(A,1) TO 2 STEP -1 @ IF A(U) THEN END
280 NEXT U
290 SUB M2N(A(),N) @ N=0 @ FOR I=UBND(A,1) TO 1 STEP -1 @ N=N*1000000+A(I)
300 IF N>1E12 THEN N=SCALE10(N,6*I-6) @ END
310 NEXT I
320 SUB N2M(N,A()) @ MAT A=ZER @ I=0 @ M=N
330 IF M THEN I=I+1 @ A(I)=MOD(M,1000000) @ M=M DIV 1000000 @ GOTO 330
340 SUB MMOD(A(),B(),C()) @ U=UBND(A,1) @ DIM X(U),Z(U) @ CALL M2N(B,V) @ MAT C=A
350 CALL M2N(C,U) @ IF U<V THEN END
360 CALL N2M(MAX(INT(NEIGHBOR(NEIGHBOR(NEIGHBOR(NEIGHBOR(NEIGHBOR(U,0),0),0),0),0)/V),1),X)
370 CALL MMUL(X,B,Z) @ CALL MSBI(C,Z) @ GOTO 350
380 SUB MFAC(N,A()) @ CALL N2M(FACT(MIN(N,17)),A) @ IF N<18 THEN END
390 FOR I=18 TO N @ MAT A=(I)*A @ CALL MNOR(A) @ NEXT I

"Ad-hoc library" in this context means that it's tailored to do what the main program needs to do and absolutely nothing more, so it's mainly useful for the present purpose and not general-purpose by any stretch of the imagination. Thus, it has the following disclaimer attached:

• the function set it's not complete or symmetric: only the indispensable functionality for the task at hand is included so many unneeded operations aren't implemented at all such as integer division of two multiprecision arguments, for instance, while others are implemented only for a multiprecision argument and a single precision one. Also, some of the operations return the result in a variable different from the arguments while others are done in place. Note in particular that no routines to input or output the multiprecision values are provided.

• it's not optimized: all arguments are operated upon at maximum precision (say 200-digit precision), even if the actual value stored in the multiprecision variable is only 10 digits long.

• it has no error checking at all: most errors will result in a hard, untrapped error which will stop program execution. Also, debugging and checking hasn't been exhaustive so errors may have crept in.

• only positive integers are supported: any negative intermediate or final results arising will result in a hard (untrapped) error.

Most of these shortcomings are the result of designing it to run fast, be small in size, and most importantly, take as little of my scarce free time as possible to develop and debug. On the positive side, you'll find that:

• most operations are optimized for speed by using assembly-language matrix operations, as well as one or two neat tricks.

• as many as a full dozen routines are provided, all of them callable from your own programs (use them at your own risk).

Available calls reference:

Note: In what follows,

• Multiprecision variables can hold multiprecision positive integer values up to slightly less than 500 digits long (approximately), depending on the DIMension of the underlying arrays. Each of them should be DIMensioned (with OPTION BASE 1 in effect) as a REAL precision array with (N DIV 6)+1 elements where N is the maximum number of digits, as each array element will hold up to 6 digits.

• Single-precision variables can hold positive integers up to 6 digits long.

• REAL variables can hold any positive integer value within the range of built-in REAL precision.

SUB MMUL(A(),B(),C())  { Multiprecision MULtiplication }

Takes two multiprecision variables A and B and returns their product in the multiprecision variable C. A and B are unaffected.

SUB MPOW(A(),N,C())  { Multiprecision POWer }

Takes a multiprecision variable A and a single-precision value N and returns the value of the power AN in the multiprecision variable C. A and N are unaffected.

SUB MSUM(A(),B(),C())   { Multiprecision SUM }

Takes two multiprecision variables A and B and returns their sum in the multiprecision variable C. A and B are unaffected.

SUB MSBI(A(),B())   { Multiprecision SuBtraction In-place }

Takes two multiprecision variables A and B and returns their difference in the multiprecision variable A (subtraction in place). B is unaffected.

SUB MMODK(A(),K,M)   { Multiprecision MODulus single-precision }

Takes a multiprecision variable A and a single-precision value K and returns the single-precision value of A modulus K in the single-precision variable M, which must be passed by reference (or else won't return a thing in it). A and K are unaffected.

SUB MDIVK(A(),K)    { Multiprecision DIV (and modulus) single-precision }

Takes a multiprecision variable A and a single-precision variable K and returns the multiprecision value of the integer division operation A DIV K in the multiprecision variable A (i.e., in place) as well as the single-precision value of A modulus K in the single-precision variable K itself, which must be passed by reference. If you don't want or need the modulus and want K to remain unaffected you can simply pass K by value instead.

SUB MNOR(A())   { Multiprecision NORmalization }

Internal use only. Normalizes a multiprecision variable A in place

SUB MTOP(A(),U)  { Multiprecision TOP }

Internal use only, though it can be useful for printing multiprecision variables, etc. Returns in the single-precision variable U the index of the topmost non-zero element of the multiprecision variable A. Variable U must be passed by reference. Variable A is unaffected.

SUB M2N(A(),N)  { Multiprecision to real-precision Numeric variable }

Returns in the REAL precision variable N the approximate value of the multiprecision variable A (up to 12-digit mantissa and exponent up to 499). Variable N must be passed by reference. Variable A is unaffected.

SUB N2M(N,A())  { Numeric Real-precision variable to Multiprecision }

Assigns the value of the REAL precision variable N to the multiprecision variable A. Variable N is unaffected.

SUB MMOD(A(),B(),C()) { Multiprecision MODulus }

Takes two multiprecision variables A and B and returns the multiprecision value of A modulus B in the multiprecision variable C. A and B are unaffected.

SUB MFAC(N,A())  { Multiprecision FACtorial }

Takes the single-precision value N and returns its factorial in the multiprecision variable A. N is unaffected.

Sample use:

Let's say we need to compute the following:

69! MOD 1368 = 161707119156747337147933149666645422128978599226831537632782504385470771962

This is how we would proceed (from the keyboard in this case):

1) DIMension several multiprecision variables capable of holding up to 100 digits (actually 102):

> DESTROY ALL @ OPTION BASE 1 @ P=100 DIV 6+1 @ DIM F(P),A(P),B(P)

2) Make the necessary calls to the multiprecision library in order to perform the computation:

> CALL MFAC(69,F) { compute the factorial of 69 } @ CALL N2M(13,A) { assign the value 13 to multiprecision variable A } @ CALL MPOW(A,68,B) { raise A (13) to the 68th power and assign the result to B } @ CALL MMOD(F,B,A) { compute the modulus operation and assign the result to A }

3) Output the multiprecision result (watch your WIDTH setting):
> FOR I=P TO 1 STEP -1 @ DISP A(I); @ NEXT I @ DISP

0 0 0 0 161 707119 156747 337147 933149 666645 422128 978599 226831 537632 782504 385470 771962

which is the correct result as shown above, disregarding the non-significant 0's at the beginning.

 Re: My Original Solutions and Comments - Part 3 (Re: S&SMC#20) [LONG and I mean it]Message #85 Posted by Egan Ford on 29 Apr 2008, 3:10 p.m.,in response to message #84 by Valentin Albillo Valentin, et al, I have not given up on finding a solution without the use of multiprecision libraries or methods. Hopefully in time I will find one, but this thread will be long archived, so I'll post my summary now. I've written about 20 different programs in 4 different languages with various levels of success, but no single program finds all cases. To show that a calculator can solve even the most difficult case presented (k=3, x1=11) I created an HPGCC2 version of Valentin's method for the 50g with the following results:  k=2,x1=99 and k=3,x1=2 on my 50g outperform EMU71+PC by a wide margin. :-) Animation for the k=3,x1=11 case (replays every 10 seconds):  The f,x,y,z,m labels display the length in digits. The HPGCC2 source based on Valentin's algorithm is located at the end of this post. If any want the binary please email me. If any want to compile this or any of my C code for themselves, then read my HOWTO at: http://sense.net/~egan/hpgcc/. Two multiprecision libraries are included with this HOWTO. My best 71B BASIC program is only capable of finding prime indexes, but it is significantly faster than using multiprecision. EMU71 results: >RUN k=3 x1=2 k= 3 x1= 2 INDEX= 89 FRAC= .460674157303 TIME(S): 1.75 >RUN k=2 x1=99 k= 2 x1= 99 INDEX=103 FRAC= .650485436893 TIME(S): 1.47 >RUN k=3 x1=11 k= 3 x1= 11 INDEX=601 FRAC= .672212978369 TIME(S): 451.12 My BASIC program compiled with FreeBASIC can find k=25,x1=9 (index=1451, special case (prime)) in seconds, but on the same PC with compiled C using Valentin's multiprecision method it takes about 1/2 a day. I must find a non-multiprecision method that works for all cases if one exists. :-) Valentin, Thank you for all your time and effort taken to create your many challenges. They do challenge me and I am sorry to see them go. I can only hope that the interest in your mini-challenges will encourage you to grant this community another SSMC next April Fools Day. Code: 71B BASIC version (fails with composite indexes): 10 DESTROY ALL @ OPTION BASE 0 20 INPUT "k=";K @ INPUT "x1=";X1 @ T=TIME @ CALL DOIT(K,X1,I,R) 30 DISP "k=";K;" x1="; 40 DISP USING "4d,7a,3d,6a,d.12d";X1," INDEX=",I," FRAC=",R/I 50 DISP "TIME(S):";TIME-T 60 SUB DOIT(K,X1,I,R) 70 DIM P(1000) @ P(0)=2 @ L=1 @ Q=2 80 'START': X=X1 @ CALL NPRIME(Q,P(),L) 90 FOR N=1 TO Q 100 X=MOD(X,Q) @ T=X 110 FOR J=1 TO K-2 @ T=T*X @ T=MOD(T,Q) @ NEXT J 120 Y=MOD(X*(T+N),Q) 130 IF Y=0 THEN GOTO 'START' 140 FOR Z=1 TO Q 150 IF MOD(Z*(N+1),Q)=Y THEN X=Z @ GOTO 180 160 NEXT Z 170 I=N+1 @ R=Y @ GOTO 190 180 NEXT N 190 END SUB 200 SUB NPRIME(Q,P(),L) 210 J=P(L-1) 220 J=J+1 230 FOR I=0 TO L-1 240 IF MOD(J,P(I))=0 THEN 220 250 NEXT I 260 Q=J @ L=L+1 @ P(L-1)=Q 270 END SUB Valentin's Method in HPGCC2: #include #include int main() { mp_int f,x,y,z,a,m,t; char *buf; int i, j, n = 0, k, x1, start, g=0; sys_slowOff(); clear_screen(); printf("running..."); x1 = sat_pop_zint_llong(); k = sat_pop_zint_llong(); mp_init(&f); mp_init(&x); mp_init(&y); mp_init(&z); mp_init(&a); mp_init(&m); mp_init(&t); start = sys_RTC_seconds(); while(n+=10) { printf("%d ",n); mp_set_int(&f,1); for(i=2;i<=n;i++) mp_mul_d(&f,i,&f); // f = n! mp_set_int(&y,x1); // y = x1 for(i=2;i<=n;i++) { mp_set_int(&t,i-1); mp_div(&y,&t,&z,&a); // z = floor(y/(i-1)) mp_expt_d(&z,k,&x); // x = z^k; mp_add(&x,&y,&z); // z = x + y mp_div(&z,&f,&a,&y); // y = z mod f mp_set_int(&t,i); mp_div(&y,&t,&a,&m); // m = y mod i if(!mp_iszero(&m)) { buf = malloc((int)((log10(256.0)*mp_unsigned_bin_size(&m)) + 10) * sizeof(char)); mp_toradix(&m, buf, 10); j = atoi(buf); printf("\n\nk:%d x1:%d index: %d\nremainder: %.12f\n",k,x1,i,(double)j/i); printf("f: %d\nx: %d\ny: %d\nz: %d\nm: %d\n", (int)(log10(256.0)*mp_unsigned_bin_size(&f)), (int)(log10(256.0)*mp_unsigned_bin_size(&x)), (int)(log10(256.0)*mp_unsigned_bin_size(&y)), (int)(log10(256.0)*mp_unsigned_bin_size(&z)), (int)(log10(256.0)*mp_unsigned_bin_size(&m))); printf("time(s): %d",sys_RTC_seconds()-start); WAIT_CANCEL; return(0); } } } } Edited: 29 Apr 2008, 9:21 p.m.

 Re: My Original Solutions and Comments - Part 3 (Re: S&SMC#20) [LONG and I mean it]Message #86 Posted by Valentin Albillo on 1 May 2008, 2:50 p.m.,in response to message #85 by Egan Ford Hi, Egan: I'm truly wordless at your magnificent achievements with this and any other challenges you've taken on. As you know, I don't specially like RPL models and that's the reason why I have none (save for a NIB HP28S) and further I've never been interested in them or produced programs for them, but I must confess that the way you use them, what with HPGCC, is truly amazing and fully shows their incredible capabilities to the best. Just for instance, the mere fact you can solve the k=3, x1=11 case is frankly awesome in the extreme, as it demands 4300-digit arithmetic at the very least, yet everything's concluded within a mere half and hour in a handheld calculator. Even sticking to the HP-71B, your non-fully multiprecision method is also outstanding, despite the fact that it doesn't solve all cases. The timing for that same case is also fantastic at 450+ seconds under Emu71. In short, I've been as enthralled with your productions as you might have been with mine, if not more, and (said in good humor, mind you) you're the main culprit of my S&SMC series being ended: you've forced me to raise the level to such heights, in order to actually provide a credible challenge that could hold your attacks even for a few days or hours, that most anyone else couldn't follow at all and quickly lost interest finding them completely over the top !! :-) Last, thank you very much for everything: your interest, your dedication, your insights, your amazing solutions. You've certainly been one of the main reasons for me enjoying it all and the best justification for my (considerable) efforts. Best regards from V.

 Re: My Original Solutions and Comments - Part 3 (Re: S&SMC#20) [LONG and I mean it]Message #87 Posted by PeterP on 30 Apr 2008, 12:35 a.m.,in response to message #84 by Valentin Albillo Valentin, Thanks for all the time you stole away from other endeavors of your live to bring yet another challenge to us. As usually I enjoyed it a great deal, learned a lot and even allow myself a tinge of happiness in having gotten farther in this challenge than in most of my other attempts (although your gracious allowance to my deviation from some rules was most appreciated). And your free providing of a multi-precision library is a special goodie to end this sequence of challenges on a high note! I'll have to study the library carefully to understand it (maybe it even gives me some tips on how to write efficient multiplication and division routines in HP41 MCODE, something I am currently trying to learn and find info about) Thanks again and I can only second Egans hope that around April 1st you will allow me again to make a fool of myself by attempting your 'simple' challenge. Seriously, though, a very heartfelt Thank You! from your Austrian participant for all your kind work and advice you so freely give. Cheers Peter

 Re: My Original Solutions and Comments - Part 3 (Re: S&SMC#20) [LONG and I mean it]Message #88 Posted by Valentin Albillo on 1 May 2008, 3:18 p.m.,in response to message #87 by PeterP Hi, PeterP: You've certainly done great things with this last challenge, I'm pretty amazed at your incresing capabilities over the months and the accelerated rate of prowess you've continually been showing. I've read your outputs with interest and admiration, and want to thank you for them and for taking the time to produce them. As for my ad-hoc multiprecision library, it's very ad-hoc, concocted in as little time as possible and with the minimum functionality needed, as stated in the disclaimer. If you're gonna develop multiprecision routines in HP41C's MCODE, better starting code and algorithms would be needed. A minimum reasonable effort would consider these improvements as mandatory: A complete, symmetric set, which would include addition, subtraction, multiplication, and division, also including in-place versions and single-precision operands, plus modulus and powers Extra operations: fast multiplication/division by powers of ten (shift left and right), boolean comparisons (less than, greater than, equal, equal to zero) Provision to deal with negative arguments and, eventually, floating point arguments. Provision to exceed the 500-digit limit by not making it dependent on the built-in REAL range. Fully checked for implementation errors, and all argument or range errors fully trapped and duly reported in a controlled manner. As you see, that's a lot of work, and implementing it all in MCODE can be a daunting task indeed, but with the potential to be very enjoyable and ultimately useful as well. Thanks again, I'm keen to learn of your MCODE experiences, and Best regards from V. Go back to the main exhibit hall