Short & Sweet Math Challenge #17: The Feast ! - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: Short & Sweet Math Challenge #17: The Feast ! (/thread-99685.html) |
Short & Sweet Math Challenge #17: The Feast ! - Valentin Albillo - 09-13-2006 Hi all,
now it's as good time as any to post my brand-new Short & Sweet Math Challenge #17: The Feast!, arranged meal-like, so to say. Dust off once more what's left of your HP-calc programming skills (if any) and enjoy ... Bon appetit !
Appetizer: More power to you
"Write a program to find the first exact power of 2 (up to 22500, say) that begins with a given
should output 10, as 210 = 1024. You can either give just the required exponent (10), or also output the power itself (1024), for extra élan.
Use your program to find (and output) the first exact power of 2 which begins with
I'll give both a fast 3-line HP-71B program for the easier case, and a still simple, fairly fast program for the more elaborate second case.
Main course: Le petit homage to the 41 !
"Find a 41-digit number consisting solely of the digits 4,1 which can Important note:
The description above and below has been duly amended to correct the original wording which erroneously said "precisely 41 times"
times. For instance, 100 can be halved 2 times: (1) 100/2 = 50, (2) 50/2 = 25, as 25 can't be halved any further to yield an integer result.
Despite its looks it's actually fairly easy, and to prove it I'll give a very short, 7-line
Le Dessert: Pi & other delights
Pi/4 = 1 -1/3 +1/5 -1/7 + 1/9 - 1/11 + 1/13 - ...Now this infinite series though convergent, if slowly, is a typical case of what's known as an alternating series, because its terms steadily alternate between positive and negative. Furthermore, infinite alternating series like this one, even if convergent, are only conditionally convergent, which means that their value depends on the exact order in which its terms are summed up.
So by varying their order, and even though you're still adding up each and every term exactly once and
This understood, "you must write a program which, given an arbitrary value, will output the exact
As all the terms have "1" as numerator, your program needs to Pi/4, [A] -> 1 -> -3 -> 5 -> -7 -> 9 -> -11 -> ...where the program can continue indefinitely, if desired, to produce as many terms as the user cares for. In this example, the output are the denominators, so the order is: Pi/4 = 1/1 -1/3 + 1/5 -1/7 +1/9 -1/11 ...as expected. Use your program with the following cases, outputting a few dozen terms or so: Sum = Pi/4, Pi/5, e/4, Sin(1), Cos(1), 1, 0, 1-1/3+1/5, .71, .41I'll give both my original solutions, namely a 3-line program for the HP-71B and a 30-step version of it for the HP-15C, both taking negligible time.
That's all. I'll post my original solutions next week, so you've got plenty of time
Edited: 18 Sept 2006, 8:52 a.m. after one or more responses were posted
Re: Short & Sweet Math Challenge #17: The Feast ! - Bruce Horrocks - 09-13-2006 Quote:It's not such a good time - we're all off to HHC2006. You won't hear anything here except the wind whistling through the tumbleweed!! Re: Short & Sweet Math Challenge #17: The Feast ! - Valentin Albillo - 09-13-2006 Hi, Bruce: Bruce posted:
I'll delete my post immediately so please hold your breath while I'm at it, it'll take just a moment ...
Best regards from V.
Re: Short & Sweet Math Challenge #17: The Feast ! - Namir - 09-13-2006 Ditto Bruce .... the only pi HHC2006 attendee will have are ones served by San Jose cantinas (aka restaurants).
Namir
Re: Short & Sweet Math Challenge #17: The Feast ! - Paul Dale - 09-14-2006 I've got an inelegant solution to the first part on the HP49g+:
<< 512 DO 2 * DUP ->STR 1 4 SUB OBJ-> UNTIL 3 PICK == END >> The output is the power itself rather than the exponent. Runtime for the smallest case beginning 2006... is under a minute. The largest case beginning 1000... takes about three minutes to solve. I'm guessing that this is faster than attacking the problem mathematically :-) Converting to get the exponent as asked for is left as an exercise for the reader :-) Either figure it out from the number (beware the limited real exponenet range) or add a counter to the program.
Re: Short & Sweet Math Challenge #17: The Feast ! - Bram - 09-14-2006
So you cooked some bits for a nice bite, Valentin.
LBL V
Not really brilliant, but it will do, although you'll need something like an HP-32SII because of the very large numbers. Yet only 3 tasks can be computed, the other 2 give an overflow.
Re: Short & Sweet Math Challenge #17: The Feast ! - GE - 09-14-2006 My first try at a SSMC, while all were interesting and sometimes mind-bending !!
Challenge 3. Re: Short & Sweet Math Challenge #17: The Feast ! - Kiyoshi Akima - 09-14-2006 Brute force and ignorance on part one (exponent only).
102 => 2^10And some boundary cases (not absolutely sure about the last two, but they're what these programs give) (I know these go beyond the specs): 1 => 2^0 1542 is a somewhat interesting case.
For the HP25 (minor and obvious changes for almost any RPN machine(?)): 01 STO 1
HP-48GX (and most RPL machines(?)): <<
HP-71B: 10 INPUT N @ L=IP(LOG10(N)) @ I=-1 @ T=LOG10(2) Edited: 14 Sept 2006, 7:11 p.m.
Re: Short & Sweet Math Challenge #17: The Feast ! - Paul Dale - 09-14-2006 The third challenge. I'm aware of the approch mentioned in this paper (PDF file). I'm reasonably confident that something similar could be done in this case. Since following that path would be no fun, I present a *twenty-one* step HP-12c program that achieves the goal in a different manner:
01 STO 0 The basic premesis is that if the running sum is greater than the target, we add a negative term and if it is less, we add a positive one. I think a proof of convergence should be fairly straightforward but I'll leave that (or proof that this is wrong) as an exercise... I always start with a positive 1 term because that made the code a little shorter.
Edited: 14 Sept 2006, 8:46 p.m.
Re: Short & Sweet Math Challenge #17: The Feast ! - GE - 09-15-2006 Hello, some more news : Magnificent, but ... - Valentin Albillo - 09-15-2006 Hi, GE: GE boldly posted:
"Just for fun here is the 67-digit number containing only digits 6 and 7 which is exactly 67 times halvable :
I can't comment on your 41-digit result or your multi-precision program capable of computing it as you provided neither. Perhaps a little rechecking is in order ? :-) All in good humor, of course, no offence whatsoever intended :-) :-). "Waiting for SSMC 18 !!"
Thanks for your interest and extremely kind comments, much appreciated.
Edited: 15 Sept 2006, 6:10 a.m.
Re: Short & Sweet Math Challenge #17: The Feast ! - Fernando del Rey - 09-15-2006 This is just another RPN version to the first challenge, but I think it may be faster than others posted earlier. I have tried it on the 42S, but it's very easily adaptable to other models.
01 LBL AB Now it's time to try to tackle the other two challenges.
Thanks, Valentin, for keeping us entertained over the weekend !
You're welcome, thanks for participating ! :-) [NT] - Valentin Albillo - 09-15-2006
Best regards from V.
Re: Magnificent, but ... - GE - 09-15-2006 Aaargh, you are right !!!!!! Time to search for my PI button... Re: Short & Sweet Math Challenge #17: The Feast ! - Marcus von Cube, Germany - 09-15-2006 Hi Valentin, Here is an RPL solution to the main course: Le petit homage to the 41! I didn't read any of the other postings before in order not to get spoiled by someone elses genius ;-) I did it on my new 50g in exact mode because it can easily cope with 41 digit integers. But first a little theory how it works: If you want to decide whether a number is divisible by 2, just check the last digit: If it is divisible by 2, the whole number is. If you want to decide whether a number is divisible by 4, just check the last two digits: If they (as a number) are divisible by 4, the whole number is. More general: If you want to decide whether a number is divisible by 2n, just check the last n digits: If they (as a number) are divisible by 2n, tho whole number is. Now I start building the number from back to front. Since the digits can only be 1 or 4, the goal is to prepend one of these to the result found so far and check for divisibility by the proper power of 2. The result is unique because exactly one of the digits one or four yields to a number which is evenly divisible (the difference between the two possible results is 3*10n-1 which is not divisible by 2n.) To ease the algorithm, the program starts with n=2 and result=4. It takes the number of places (and hence the power of 2) from the stack. Minimum input is 2, smaller numbers are treated as 2.
Here is the code: %%HP: T(3)A(R)F(.);
The result for 41 is: 44111111411444111411141441444411441414144 The computing time is within seconds. [Edited: The given result is not exactly but at least n times halvable. Valentin is about to correct his original posting to match this request.] Marcus
Edited: 18 Sept 2006, 4:34 p.m. after one or more responses were posted
Problem 3 - Crawl - 09-15-2006 Problem 3 seems to be the easiest. The principle here is just to add a term if the sum is less than the desired value, subtract if it's greater, and go to the next term (whichever the case may be) if they're equal. You put the desired value on the stack, and select "okay" from the choose boxes as long as you want more terms. Selecting "cancel" will end the program, with the desired value on level 2, and the approximation using the sum, for comparison, on level 1.
Edited: 15 Sept 2006, 2:58 p.m.
Re: Short & Sweet Math Challenge #17: The Feast ! - Paul Dale - 09-16-2006 Quote: Pauli or Paul please :-) Valentin's HP-15C program is some thirty steps which is quite a bit longer than my HP-12C progam (twenty one) or a naive conversion of this to the HP-15C (twenty four). Even skipping the hard coded initial '1' term doesn't bloat the program enough. I wouldn't be at all surprised if Valentin is attacking this problem differently.
Re: Short & Sweet Math Challenge #17: The Feast ! - Marcus von Cube, Germany - 09-16-2006 Here is my attempt at the appetizer.
It's another RPL program but the logic should be portable to almost any programming language. The algorithm does not test all powers of 2 against the given number x but it computes the matching exponent r of two directly (r = "result"): r := CEIL( log2( x * 10n ) )It then checks, if 2rn is a shift factor that is increased in a loop until a match is found.
In fact, all formulas are converted to logarithmic form. This avoids large numbers: r := CEIL( log2x + n * log210 )On the 50g, extended precision integer arithmetic allows to display the exact power of two together with the final result. The results are exactly the same as already posted by Kiyoshi Akima. And I must agree that 1542 is an interesting case :-)
Here is the code: %%HP: T(3)A(R)F(.); Running times are about 20 seconds for the greater results.
Marcus
Re: Short & Sweet Math Challenge #17: The Feast ! - Valentin Albillo - 09-16-2006 Hi, Paul: Paul posted: "Valentin's HP-15C program is some thirty steps which is quite a bit longer than my HP-12C progam (twenty one) [...] I wouldn't be at all surprised if Valentin is attacking this problem differently."
Thanks for your interest and
Best regards from V.
Re: Short & Sweet Math Challenge #17: The Feast ! - Paul Dale - 09-17-2006 Although not for a calculator, here is the same algorithm written in C:
#include <stdio.h> Run time is rather small :-) Using this, I've verified that all five digit or fewer leading sequences can be found. For each length, here is a table of the last sequence to be found and the power of two where it occurs.
len digit(s) power There might be some merit to the earlier suggestion that any integer could be found in the leading digits of a power of two.
Re: Magnificent, but ... - GE - 09-18-2006 Hello again. Re: Short & Sweet Math Challenge #17: The Feast ! - GE - 09-18-2006 Sorry Marcus, this number is 42-halvable... Ouch! You proved me wrong! - Marcus von Cube, Germany - 09-18-2006 Hi GE, I should have checked my own solution better! The number my program gave is exactly the one you posted here and it is 42 time halvable. :-( Back to the drawing board!
Marcus
Re: Short & Sweet Math Challenge #17: The Feast ! - Marcus von Cube, Germany - 09-18-2006 GE, our postings crossed eachother, I've just found it out! I have to go back to my ideas.
Marcus
Re: Short & Sweet Math Challenge #17: The Feast ! - Marcus von Cube, Germany - 09-18-2006 Replying to myself... (thinking aloud) The problem with my "solution" is that the last digit is a 4 and hence divisible by 22. Now following the algorithm, I always get numbers which are divisible by another power of two. The result is that all numbers my program produces are divisible by 2n+1 where n is the number of digits. Does this mean, there is no solution or is my algorithm wrong?
Marcus
My fault. - Valentin Albillo - 09-18-2006 Hi, Marcus & GE: Marcus posted: "I should have checked my own solution better! The number my program gave is exactly the one you posted here and it is 42 time halvable."
Matter of fact, there would be no solution if the number had to be divisible by 2 exactly 41 times, as there's but a single choice for the digit, 4 or 1, at each step. If putting a 4 makes the number divisible 42 times, putting a 1 instead would make it divisible just 40 times, and there are no other possibilities. Sorry for the inexact wording, I'll correct my original posting when the thread's finished for good, so that it doesn't get archived with the error in place, with an explanation for the need of the correction and full credit to you.
Thanks and best regards from V.
Please read message #14 above. [NT] - Valentin Albillo - 09-18-2006 Best regards from V.
Please read message #14 above. [NT] - Valentin Albillo - 09-18-2006 Best regards from V.
Re: Please read message #14 above. [NT] - Marcus von Cube, Germany - 09-18-2006 Valentin, I've edited my posting again to refer to your correction.
Marcus
Re: Short & Sweet Math Challenge #17: The Feast ! - GE - 09-18-2006 > The problem with my "solution" is that the last digit is a 4 Re: Short & Sweet Math Challenge #17: The Feast ! - Valentin Albillo - 09-18-2006 Hi, GE:
"Actually, EVERY N-digit number divisible by 2^N containing only digits 4 and 1 and whose first digit is 1 is divisible by NO MORE than 2^N."
Yet it is divisible by 2^(3+1), as 144 = 16 * 9. "Hopefully my mother has no Internet access."
Best regards from V.
S&SMC#17: My Original Solutions & Comments [LOOONG] - Valentin Albillo - 09-19-2006 Hi all,
much appreciated. I must say that it's becoming increasingly difficult to come up with a worthy challenge capable of resisting your combined efforts even for a few days. I dread the day when my S&SMCs will be completely solved within a few hours after posting ! This only goes to show the tremendous amount of programming & math ingenuity displayed by this forum's gentle contributors.
That said, these are my original solutions to all three parts of S&SMC#17, plus
Appetizer: More power to you
"Write a program to find the first exact power of 2 (up to 22500, say) that begins by a given
an exact power of 2 that begins with the sequence of digits which represents the number M in the decimal notation. Which is more, this is also true not only for 2 but for any positive integer A other than an exact power of 10, so for example, you can find N such that 3141592654N begins with 2718281828, say.
Once we know that the feat is indeed possible for any given M, we can proceed to implement the 1 INPUT M @ X=FP(LGT(M)) @ Y=FP(LGT(M+1)) @ P=LGT(2) @ FOR I=1 TO 2500which will accept an integer M, then will find out and print the required exponent and the corresponding power of 2 (which begins with M) in exponential notation, using decimal logarithms throughout to keep the numbers within range. Upon running it for the given cases, we construct the following table: Beginning N 2^Nand we also try out Kiyoshi Akima's suggestion: 1542 1542 1.54259995373E464which is indeed rather nice, as the required exponent equals the given beginning sequence, namely 1542, so that we have: 21542 = 1542.59995373 * 10461For the longer case, outputting the resulting power of 2 in full, it suffices to append a routine to compute the exact value of 2N using some multiprecision algorithm. I'll simply use the one I already posted as part of my "Spring Special Challenge" (aka "April's Fool Challenge"), where it was used to efficiently compute 265536-3, and which is readily customizable for an arbitrary power of 2. The resulting program is thus the following 426-byte quick concoction: 10 DESTROY ALL @ OPTION BASE 0 @ INPUT MLet's try a couple of cases: >RUNwhich takes just 0.43 seconds in Emu71 (some 2 min. in an actual HP-71B). Another interesting case is Kiyoshi Akima's 1542: >RUNwhich takes only 1.64 seconds in Emu71 and some 8 min. in a real HP-71B.
Main course: Le petit homage to the 41 !
"Find a 41-digit number consisting solely of the digits 4,1 which can
divisible by 21 and go on adding digits leftwards one at a time, chosing 1 or 4 so that the resulting number is divisible by 22, 23, etc. This is almost trivial up to 10-12 digits (depending on your chosen calc model), for instance this would be one of the simplest HP-71B implementations, valid for up to 12 digits: 1 DESTROY ALL @ U=4 @ V=1 @ N=U @ P=4 @ T=10
and afterwards, for more than 12 digits, you only need a multiprecision modulus operator, 1 DESTROY ALL @ INPUT U,V @ D=U+1 @ DIM N(D),B(D) @ N(1)=U @ L=10^11Running it for all 20 possible cases, you'll get the following table: Digits NumberThe solution for the (4,1) case is thus this 41-digit number, obtained after 4 min. in a physical HP-71B (less than 1 second in Emu71): 44111111411444111411141441444411441414144which indeed is the only 41-digit long number consisting solely of the digits (4,1), and which can be halved at least 41 consecutive times (actually, 42!). Also, the correct solution for the digits (6,7) is: 6677767667676666776766667777767666677766776777777777777666766667776which is 67-digits long, consisting of just the digits (6,7), and can be halved at least 67 consecutive times. Running time is 15 min. in a real HP-71B (less than 4 seconds in Emu71).
By the way, before departing let's have a look at these nice 'cousins' of our number which I've generated for your viewing pleasure, also 41-digit long 44144444111441144114411411444444411441441 = 12009881291601907477 * 3675676972953081511133 (both prime)and these are two equally handsome 'cousins' I've generated for the 67-digit (6,7) number: 6777766776766667676667667777777667667776766667766766666767676677677Who knows, they might come handy to test your favorite factoring or primality test algorithms, or even your multiprecision multiplication routines at the very least. Or, if you're in a little sadistic mood and you've got some students the right age, have them multiply both factors by hand and keep betting whether the next digit in the result is going to be a 6 or a 7 ! ... :-)
Le Dessert: Pi & other delights
"Write a program which, given an arbitrary value, will output the exact
for the HP-71B, which is anything but optimized (pessimized more like!) and will output up to 100 terms, then it will display both the given value and the sum after 100 terms: 1 DESTROY ALL @ INPUT E @ K=100 @ P=1 @ N=2 @ S=0 @ FOR I=1 TO KLet's run it for a few cases: I think you get the idea: though we're adding up each and every term of the series once and only once, we can get any result we want by simply chosing their order in the addition process, which is probably rather unexpected at first sight and nicely shows what conditional convergence of alternating series actually means.
As for the 30-step HP-15C version, it was a direct translation of the
That's all. I hope you enjoyed it all and, again, thanks for your interest and stay tuned for
Edited: 19 Sept 2006, 5:52 a.m.
Re: S&SMC#17: My Original Solutions & Comments [LOOONG] - GE - 09-20-2006 Thank you again Valentin, this SSMC was very interesting. I can't wait to see the next, it must actually be difficult to find interesting subjects.
|