a new challenge! « Next Oldest | Next Newest »

 ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-10-2010, 10:30 PM Write a program for your favorite programmable calculator to determine this. The only prime number p with digits abcde such that p = (a! + b! + c! + d! + e!) + (a + b + c + d + e). For example, if 10343 is prime, then 10343 = (1! + 0! + 3! + 4! + 3!) + (1 + 0 + 3 + 4 + 3). Of course, that's not the one (although 10343 is prime). Don't give away the winning answer for a few days, but post your masterpiece program here for the world to see, or at least us nerds. ▼ Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 07-11-2010, 10:15 AM Don, Thanks for an interesting challenge! Shall we assume from the wording of the question that the answer is 5 digits long? (e.g. maximum search space is primes from 10,000 to 99,999) Cheers, Al ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-11-2010, 11:29 AM yes Glenn Shields Member Posts: 63 Threads: 8 Joined: Dec 2009 07-11-2010, 12:16 PM Great challenge for a Sunday morning. This took 32 minutes on my HP50g - I started with 10007, the first 5 digit prime: << 10007 -> pri << DO ; pri NEXTPRIME DUP 'pri' STO ->STR 0 SWAP 1 5 FOR i HEAD LASTARG TAIL SWAP OBJ-> DUP ! + ROT + SWAP NEXT DROP DUP UNTIL pri == END >> >> The ; is "safedrop" for when the stack is empty. I wish it could be faster -- will watch and wait!! Thanks, Glenn (in West LA). ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-11-2010, 12:49 PM Thanks Glenn. I wish I understood RPL, but I'm too much of an RPN man to take the time to learn it. I'm working on a solution on the 30b, which I believe has the same processor as your 50g. Will post later today. Don Glenn Shields Member Posts: 63 Threads: 8 Joined: Dec 2009 07-11-2010, 01:43 PM Yes, Don, it's hard to be comfortable in both - when I got the 35s, I was doing lots of RPN, last one was a Mastermind program. Now I can't even remember it, but have written a new one for the 50g, which can do more for such a game (like display the history of your guesses and results). But for anyone else into RPL, here is another version of the one just posted, and faster (18 minutes) because I dumped the string manipulation for a loop using FP/IP decomposition of the number (of course we know 10007 is not it): << 10007 -> pri << DO ; pri NEXTPRIME DUP 'pri' STO 0 SWAP 1 5 FOR i 10 / FP LASTARG IP SWAP 10 * DUP ! + ROT + SWAP NEXT DROP DUP UNTIL pri == END >> >> Cheers, Glenn ▼ Glenn Shields Member Posts: 63 Threads: 8 Joined: Dec 2009 07-11-2010, 02:56 PM Sorry, when I ran this program it had real numbers, everything had a decimal point. Apparently this beast handles real numbers faster than integers (I'm sure this was mentioned somewhere in the past), so here is my final entry (Beta-tested): << 10000. -> pri << DO ; pri NEXTPRIME DUP 'pri' STO 0. SWAP 1 5 FOR i 10. / FP LASTARG IP SWAP 10. * DUP ! + ROT + SWAP NEXT DROP DUP UNTIL pri == END >> R->I >> (more like 19 minutes) :-) Mark Storkamp Member Posts: 83 Threads: 5 Joined: Oct 2007 07-11-2010, 03:07 PM 62 minutes on i41CX+ ``` 01 LBL "CHLNG" 02 .009 03 STO 10 04 LBL 01 05 RCL 10 06 INT 07 FACT 08 LASTX 09 + 10 STO IND 10 11 ISG 10 12 GTO 01 13 1 E4 14 STO 10 15 LBL 02 16 RCL 10 17 NEXTPRM 18 STO 10 19 0 20 X<>Y 21 LBL 03 22 10 23 / 24 INT 25 X<>Y 26 LASTX 27 FRC 28 10 29 * 30 X<>Y 31 RCL IND Y 32 + 33 X<>Y 34 RDN 35 X<>Y 36 X>0? 37 GTO 03 38 X<>Y 39 RCL 10 40 X!=Y? 41 GTO 02 42 END ``` ▼ Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 07-12-2010, 01:23 AM Mark, remind me which ROM contains "NEXTPRM" or is it built into the 41c? Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-12-2010, 09:02 AM Thanks for your solution, Mark. Is the NEXTPRM at line 17 a standard feature of the 41 instruction set, or is it in a separate library? I don't really know much about the 41. I know most CAS calculators have an isprime function, and I wonder if the standard vanilla 41 has that too. ▼ Mark Storkamp Member Posts: 83 Threads: 5 Joined: Oct 2007 07-12-2010, 09:22 AM As far as I know it's only available in the i41CX-Math module on the iPod/iPhone. Even if it were available in the regular 41, I don't have the patience (or enough batteries) to wait for it to solve it. Since the answer must contain 7s or 8s, but no 9s, I thought there might be a way to dump out of the inner loop faster if I don't meet that criteria, but it seems the test for that is just as expensive. If I could get to the BCD values, then adding 11111 and masking just the MSB of each nibble would tell me if I had a 7 or 8, but I haven't done MCode programming on the 41 yet. Mark Storkamp Member Posts: 83 Threads: 5 Joined: Oct 2007 07-12-2010, 02:41 PM Now I'm down to 6m 8.47s on the i41CX+. Also took out NEXTPRM so it should run on any 41CX. ``` 01 LBL "CHLNG2"  02 STOPSW  03 0  04 SETSW  05 RUNSW  06 CF 29  07 FIX 00 <- Using the ALPHA reg now, remove all punctuation.  08 48.057 <- pre-compute !+n and store in regs returned by ATOX  09 STO 01  10 LBL 01  11 RCL 01  12 INT  13 48  14 -  15 FACT  16 LASTX  17 +  18 STO IND 01  19 ISG 01  20 GTO 01  21 88779 <- start with largest possible value, decrement by 2  22 STO 01  23 LBL 02  24 RCL 01  25 2  26 -  27 STO 01  28 CLA  29 ARCL X  30 CLST  31 ATOX <- loop is unrolled and repeated 4 more times  32 RCL IND X  33 X<>Y  34 RDN  35 +  36 ATOX  37 RCL IND X  38 X<>Y  39 RDN  40 +  41 ATOX  42 RCL IND X  43 X<>Y  44 RDN  45 +  46 ATOX  47 RCL IND X  48 X<>Y  49 RDN  50 +  51 ATOX  52 RCL IND X  53 X<>Y  54 RDN  55 +  56 RCL 01  57 X!=Y? <- if not done yet, repeat with next value  58 GTO 02  59 STOPSW  60 RCLSW  61 BEEP  62 END ``` ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 07-12-2010, 05:02 PM Since you are using the ALPHA register you can probably use POSA and check for the existence of the number 9 (9! is too large). That will cut your number of tests from 1471 to 953. You also need at least one 8 or two 7's or 7 and 8. Unsure how quickly you can test for that; useless test after you know the answer. If possible you could also count down avoiding numbers that end in 5. E.g. if number mod 5 == 0 then -2 from number. Edited: 12 July 2010, 5:54 p.m. Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-11-2010, 08:54 PM Well, I planned on doing a 30b version but that turned out to be more trouble than I thought, so I did a TI-NSpire CAS Touchpad solution. It found the solution in 1 minute and 23 seconds! Seriously! ```Define prime()= Prgm :Local i,a,b,j :For i,10007,99999,2 : If isPrime(i) Then : a:=i:b:=0 : For j,1,5 : b:=b+mod(a,10)+(mod(a,10))! : a:=iPart(((a)/(10))) : EndFor : If i=b Then : Disp i : Stop : EndIf : EndIf :EndFor :EndPrgm ``` ▼ hpnut Senior Member Posts: 408 Threads: 45 Joined: Oct 2007 07-11-2010, 09:08 PM Programming the HP 30b in RPN is difficult. the fact that current hp calculators also have algebraic and "chain" modes only makes for a muddled instruction manual. ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-11-2010, 10:19 PM I admit that programming the 30b takes some getting used to. Unlike the 12c and other "traditional" RPN calcs, it's not "pure" RPN; it's kind of a hybrid RPL/RPN environment. And the conditional tests don't obey the traditional "do if true" rule, and that REALLY takes some getting used to. But if you can learn its habits you will appreciate its speed and the fact you can assign any command to any key (well, almost any key). Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 07-12-2010, 01:03 AM Here's a basic working versionfor 42s. Starts with 88,777 value and decrements by 2, printing all values that match the "abcde" requirement above. ( as it turns out, there appears to be only 1 so it is not necessary to check for primacy) ```(Assumes display is already set to ALL) 00 { 86-Byte Prgm } 01>LBL 01 'Begin program 02 SIZE 60 ' Set sz to 60 for indirect regs "0" to "8" 03 CLRG ' Clear the numbered registers 04 9 ' Initial value for calculating n! 05 STO 09 06 48 ' set up the indirect registers 48 above the 07 + ' number to correct for ATOX numbering scheme 08 STO 10 ' Setup indirect addresses for the numbers 09>LBL 06 <- ' Loop for calculating n! for 1..9 10 RCL 09 | 11 N! | 12 48 | 13 - | ' subtract 48 for ATOX (will get added back) 14 STO IND 10 | ' initialize values 15 DSE 10 | ' decrement indirect register counter 16 DSE 09 | ' decrement value counter 17 GTO 06 -- ' loop for initial values 18 -47 19 STO 48 ' Only add 1 for 0! (1-48) 20 -44 21 STO 44 ' trap the "," Character from "xx,xxx" 22>LBL 05 23 88777 ' using greedy method 99,999-max(n!) so we 24 STO 09 ' should start at 88777 and decrement by 2 25>LBL 02 <-- ' Main decrementing loop 26 CLA | ' Clear alpha reg 27 ARCL 09 | ' move current counter into alpha 28 CLX | 29>LBL 03 <-- | ' Main summation loop 30 ATOX | | 31 X=0? | | ' if all numbers used, 32 GTO 04 | | ' exit summation loop 33 RCL+ IND ST X | | ' add ATOX value to indirect address val. 34 + | | ' Add to prev. sum 35 GTO 03 -- | 36>LBL 04 | ' Check to see if sum = counter 37 X<>Y | 38 RCL 09 | 39 X=Y? | ' if sum = counter 40 GTO 07 | ' Print the value 41 X<=0? | 42 STOP | ' HALT if negative counter 43 DSE 09 | 44 DSE 09 | ' Otherwise decrement 2 45 GTO 02 -- ' Go back to main decrement loop 46>LBL 07 ' Subroutine to print the counter value 47 PRX 48 CLST ' This CLST will allow the loop to continue 49 GTO 04 ' by decrementing 2 on the next loop ``` Edited: 12 July 2010, 1:04 a.m. ▼ Katie Wasserman Posting Freak Posts: 1,477 Threads: 71 Joined: Jan 2005 07-12-2010, 01:45 AM Here it is for the 12C. On the 12C+ this take about 1 hour, 25 minutes -- that translates to about 10 days on the original 12C. ```01 9 02 9 03 9 04 9 05 STO 0 06 2 07 STO+0 08 RCL 0 09 SQR 10 1 11 + 12 STO 4 13 3 14 STO 1 15 RCL 0 16 RCL 1 17 / 18 FRAC 19 x=0 20 GTO 06 21 2 22 STO+1 23 RCL 4 24 RCL 1 25 x<=y 26 GTO 15 27 0 28 STO 2 29 RCL 0 30 STO 3 31 1 32 0 33 / 34 INTG 35 STO 3 36 LST X 37 FRAC 38 1 39 0 40 x 41 STO+2 42 n! 43 STO+2 44 RCL 3 45 x=0 46 GTO 48 47 GTO 30 48 RCL 2 49 RCL 0 50 - 51 x=0 52 GTO 54 53 GTO 06 54 RCL 0 55 GTO 00 ``` Since most of the time is spent checking for primes using the simplest possibly method. The following code doesn't bother to check for primes and simply tests all odd numbers. It gets the right answer (because there's only one integer between 10001 and 99999 that meets the condition anyway) and runs considerably faster. ```01 9 02 9 03 9 04 9 05 STO 0 06 2 07 STO+0 08 0 09 STO 2 10 RCL 0 11 STO 3 12 1 13 0 14 / 15 INTG 16 STO 3 17 LST X 18 FRAC 19 1 20 0 21 x 22 STO+2 23 n! 24 STO+2 25 RCL 3 26 x=0 27 GTO 29 28 GTO 12 29 RCL 2 30 RCL 0 31 - 32 x=0 33 GTO 35 34 GTO 06 35 RCL 0 36 GTO 00 ``` -Katie ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-12-2010, 03:24 AM Thanks Katie and Allen for those very interesting solutions. Well, I took the primality test out of the NSpire version, and the speed difference was remarkable. IT TOOK LONGER! Much longer, so long that I stopped it after 5 minutes. I used two methods to remove the prime test: comment out the two lines (If...Endif) and physically delete the two lines. It didn't matter, it was still running after 5 minutes. I can't explain it, but unless I'm stupid (which is possible) there seems to be a bug on the NSpire. I'll post something to their forum and see what response I get. ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-12-2010, 03:33 AM I was stupid. If you remove the isprime() check code, it's going to execute all the code in the For loop for every number in the For loop, not just primes. That causes a longer execution time, obviously. Duh. ▼ hugh steers Senior Member Posts: 536 Threads: 56 Joined: Jul 2005 07-12-2010, 07:25 PM unless isPrime is very slow. so, not dumb and worth a try! Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 07-12-2010, 07:35 PM Without the knowledge that the only solution is prime, isPrime at some point is required. ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-12-2010, 08:34 PM Thanks Hugh and Egan. I think isPrime() on the NSpire is very fast, which would explain why eliminating it resulted in a much longer execution time: the time saving by eliminating isPrime() is more than offset by having every number go through the following code. I've tried to find the algorithm that isprime uses on the NSpire, and TI says it uses the trial factor increments for multiples of 2, 3, and 5 up to 1200, and then uses Montecarlo method for higher numbers, but the Montecarlo method sometimes will say that a prime is not prime, or something like that, I probably don't have it exactly right. I'm in a lot of pain today; I had knee surgery to remove a huge infection area and I can barely walk. Gotta go take a pain pill. Don David Hayden Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 07-12-2010, 08:48 AM Here is my solution for the 50g. It takes 20 minutes 51 seconds to find the answer. In the listing "sigmaLIST" is the command to add the elements of a list (capital sigma, followed by "LIST"). I took a slightly different approach and used list processing. After finding the next prime, I break it into a list of the digits, then take the factorial of the list, etc. I haven't compared this to other solutions to see which is faster. ```« 9999 -> PRI « DO PRI NEXTPRIME DUP 'PRI' STO PRI 1. DISP @ 12345 I->R 1. 5. FOR i DUP 10. MOD SWAP 10. / IP NEXT DROP @ 1. 2. 3. 4. 5. 5. ->LIST @ Now you have the digits as a list DUP ! sigmaLIST SWAP sigmaLIST UNTIL + PRI == END PRI » » ``` ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-12-2010, 09:06 AM Nice solution, David. So the 50g can break up a number into its individual digits pretty easily, apparently. That is always harder to do in RPN or BASIC. ▼ David Hayden Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 07-14-2010, 07:37 AM Quote: Nice solution, David. So the 50g can break up a number into its individual digits pretty easily, apparently. That is always harder to do in RPN or BASIC. Don, Breaking numbers into their component digits is actually pretty easy. In pseudo code: ```while number <> 0 begin digit = number MOD 10 ( store the digit somewhere) number = Integer_Part(number / 10) end ``` Dave ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-14-2010, 08:29 AM Yeah, that's pretty straightforward. The problem is with machines that don't have the mod or rmdr function, such as the 12c or 30b. It takes three steps to get the digit on those machines: ```/ 10 fp x 10 ``` I always save the result of step 1 above so I don't have to divide by 10 again later in the loop to adjust the number, just do an ip at that point. Palmer O. Hanson, Jr. Posting Freak Posts: 901 Threads: 113 Joined: Jun 2007 07-14-2010, 09:57 PM Quote: Nice solution, David. So the 50g can break up a number into its individual digits pretty easily, apparently. That is always harder to do in RPN or BASIC. Actually, breaking a number up into its individual digits is easy in BASIC if you use the string commands; for example, on the CC-40 and TI-74 10 INPUT N 20 S = 0 30 A\$ = STR\$(N) 40 FOR I = 1 TO 5 50 S = S + VAL(SEG\$(A\$,I,1)) 60 NEXT I 70 DISPLAY S 80 PAUSE will display the sum of the digits of a five digit number. A similar program on the Sharp PC-1261 requires only that SEG\$ be changed to MID\$. If you store the factorials of the digits in an array F then you can get the sum you are looking for in your challenge by adding the term F(VAL(SEG\$(A\$,I,1))) to line 50. And, if you want to automatically accept different numbers of digits you can change the upper limit of the loop to LEN(A\$). I could go on and on, but you get the idea. Palmer ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-14-2010, 10:42 PM Quote:breaking a number up into its individual digits is easy in BASIC if you use the string commands Agreed, as you have showed. But strings don't exist in most programmable calculators, at least the ones I play with today. If I wanted to use strings I'd get out my 71b, but I hate to think how long that program would run before finding the solution. And, no, I don't believe in emulators. ▼ Miles Willmek Junior Member Posts: 6 Threads: 1 Joined: Nov 2009 07-15-2010, 04:19 AM Quote: ... I'd get out my 71b, but I hate to think how long that program would run before finding the solution. For the record: 40 minutes, 4 seconds using basically the same alogorithm as the TI-NSpire. I couldn't resist trying it out. :-) ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-15-2010, 06:51 AM Thanks Miles. I would have thought it would have taken a bit longer. Don Glenn Shields Member Posts: 63 Threads: 8 Joined: Dec 2009 07-12-2010, 10:21 AM Thanks, David, tried your prgm and loved it, especially the DISP, that's always nice. Been working with this machine for 10 months, which is not long enough to get it all under your belt- like parallel processing with lists, and the use of MOD -- great stuff. But how do these number wizards find these unique numbers - kind of mind-blowing. ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-12-2010, 11:31 AM Glenn, this particular factoid came from this book. ▼ Dave Shaffer (Arizona) Posting Freak Posts: 776 Threads: 25 Joined: Jun 2007 07-12-2010, 01:36 PM Don: What is the plot on the cover of the book? ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-12-2010, 02:58 PM That plot shows the distribution of small Eisenstein primes. This site is associated with that book and briefly discusses this. David Hayden Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 07-13-2010, 06:56 AM Oops! The run time that I listed with without lines to display the progress. So for faster run time, remove "PRI 1. DISP" Dave Alex G Junior Member Posts: 2 Threads: 0 Joined: Jul 2010 07-25-2010, 05:28 PM Hi - I am a newbie to RPL and the HP50g, though I have a smattering of functional programming understanding, and I really like what I've seen so far. Thanks to David and others, who've been useful signposts on the early stages of the road. Here's my approach. I split it up into 3 programs, I'm a great believer in readability and re-use. First the main proggy, FINDSPPR, to find that 'special' prime: « DO NEXTPRIME UNTIL DUP SPECPR END » The above calls the function SPECPR, which returns 1 if the prime is 'special', 0 otherwise. « DUP INT2LIST « DUP ! + » MAP sigmaLIST == » (Lovely to have MAP available, BTW, FILTER is easy to write, too) Finally INT2LIST, which turns the integer to a string of digits. Had a bit of trouble here, but in the end I used David's approach. « DUP SIZE -> N « 1. N FOR J DUP 10. MOD SWAP 10. / IP NEXT DROP N ->LIST REVLIST » » 27 minutes for the above! Too much really, for an ARM machine, but then , I suppose, I should remember it's an ARM emulating a Saturn. It would be nice to have the INT2LIST function built-in, or at least, maybe at SysRPL level. I found out a lot about the calc while writing it, and in a way, it was the biggest time-hog for this program. My initial approach was recursive, using lists, and took about four times as long as "David's", above. I realised iteration would be quicker. I also used STO+ with lists, but this was still too slow. Then I realised that my indefinite WHILE loop was still taking too long. It was worth getting the SIZE and using a FOR (75% speedup). Finally, my intial approach was to use IDIV2 rather than MOD and IP, falsely thinking it would be faster. Wrong. « DUP SIZE -> N « 1. N FOR J 10. IDIV2 SWAP NEXT DROP N ->LIST REVLIST » » Takes almost twice as long as the version finally used. Now, I do realise that there are a whole lot of clever optimizations and/or assumptions available to sped things up, but I was really looking for a simple answer, without such ingenuities. Much as I am liking RPL I think the speed issue is a huge problem, I wrote a similar program to the one above on my PDA using Scheme and SLIB and it ran in seconds! Hmm, I see there is an RPL/2 available out there... (lamp emoticon here) Edited: 25 July 2010, 5:49 p.m. after one or more responses were posted ▼ Alex G Junior Member Posts: 2 Threads: 0 Joined: Jul 2010 07-25-2010, 05:36 PM Oops, sorry for the «s, some problems handling Unicode, I see, the symbols are meant to be << and >>, of course. (PS. Appears fixed now, oh... I dunno) Edited: 25 July 2010, 6:14 p.m. Katie Wasserman Posting Freak Posts: 1,477 Threads: 71 Joined: Jan 2005 07-12-2010, 11:53 AM Curiously enough, there's also only one 6-digit number with this same property, x = (a! + b! + c! + d! + e! + f!) + (a + b + c + d + e + f). However 'x' is a composite number. ▼ Kiyoshi Akima Senior Member Posts: 325 Threads: 18 Joined: Jul 2006 07-13-2010, 01:10 PM Katie, is that a number with a==0? ▼ Kiyoshi Akima Senior Member Posts: 325 Threads: 18 Joined: Jul 2006 07-13-2010, 01:25 PM Never mind. There was a typo in my program that was only showing a five-digit number. Fixing the typo, I found the six-digit number. Program coming soon... Kiyoshi Akima Senior Member Posts: 325 Threads: 18 Joined: Jul 2006 07-13-2010, 01:48 PM Okay, a brute force unoptimized program for six digits on the HP 50g. The program doesn't stop when it finds a solution, but keeps looking for more, leaving each one on the stack. ```<< 1. 9. FOR a 0. 9. FOR b 0. 9. FOR c 0. 9. FOR d 0. 9. FOR e a 10. * b + 10. * c + 10. * d + 10. * e + 10. * a DUP ! + b DUP ! + + c DUP ! + + d DUP ! + + e DUP ! + + 0. 9. FOR f DUP2 f ! + IF == THEN OVER f + UNROT END NEXT DROP2 NEXT NEXT NEXT NEXT NEXT >> ``` I haven't done any timing test to see whether it's quicker to break a number apart or to put it together as I'm doing here. Another possibility might be to use an indexed table instead of a factorial computation. Some combinatorics might be a possibility. We know there are at most two 9s in the number. If there are no 9s then there must be at least three 8s. I have put in one minor optimization, in that I'm checking to see whether the number abcde0 == (a! + b! + c! + d! + e! + f!) + (a + b + c + d + e) [simply subtract f from both sides of Katie's expression]. Estimated runtime is somewhere between three hours and overnight. Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 07-12-2010, 06:42 PM Hmmm... how about: p = +/- a! +/- b! +/- c! +/- d! +/- e! +/- a +/- b +/- c +/- d +/- e There are three solutions (where p is prime). If you completed Don's challenge then you know one of them, but what are the other two? Hint: Don't be quick to rule out 9's. E.g. 39869 -> + 3! + 9! + 8! - 6! - 9! + 3 + 9 + 8 + 6 + 9 and is only off by 228. Edited: 12 July 2010, 7:57 p.m. ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-12-2010, 08:45 PM Egan, I don't understand. Why isn't plus and minus all those numbers zero? ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 07-12-2010, 08:49 PM + or - not + and -. You have 1024 sums to search/number. E.g. in the above example there is a mix of - and +. Edited: 12 July 2010, 8:50 p.m. ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-18-2010, 09:13 AM Quote:+ or - not + and -. You have 1024 sums to search/number Egan, I must be dense because I still don't understand. Suppose you had 2 numbers (1 and 2 let's say) instead of 10. ```+1 +2 = 3 +1 -2 = -1 -1 +2 = +1 -1 -2 = -3 ``` It still adds up to zero. What am I not seeing here? Don ▼ David Hayden Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 07-18-2010, 10:09 AM Don, Let me try to rephrase Egan's challenge. Given the digits of p (a, b, c, d, and e), combine a, b, c, d, e, a!, b!, c! d! and e! using only addition and subtraction to create an expression for p. The original challenge was to use ONLY addition. Egan is saying "can you find other numbers using addition AND subtraction?" ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-18-2010, 10:49 AM Now that I understand! Thanks David. Now to solve it.... Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 07-25-2010, 06:21 PM Yes. Thanks David. I just got back from vacation. So, no takers? ▼ David Hayden Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 07-25-2010, 08:50 PM Please don't give the answer yet, Egan. I may give it a try this week. Han Senior Member Posts: 709 Threads: 104 Joined: Nov 2005 07-13-2010, 10:44 PM You should be able to reduce the runtime by pre-computing a table of factorials for each digit. Also, you can also rule out 9 as a digit as 9! is already too big (more than 5 digits), let alone being added to anything positive. On machines such as the HP50G where exact numbers are handled differently from approximate numbers, it is faster to use the approximate form if you know the result will not overflow. I believe this was already mentioned. In general, though, the commands that take more than one argument (e.g. "+") will always convert to approximate numbers provided at least one of the arguments is as such. The overhead that notice in the runtime is due to this conversion. ▼ Han Senior Member Posts: 709 Threads: 104 Joined: Nov 2005 07-15-2010, 01:36 AM Up late packing for a trip tomorrow; thought I'd share my program. Finds the answer in 12 minutes, 30 seconds. ```<< 40320. 5040. 720. 120. @ 8! 7! 6! 5! 24. 6. 2. 1. 1. @ 4! 3! 2! 1! 0! 9999. -> p @ initial "prime" << DO p @ (fixed a typo) DO NEXTPRIME @ find next prime UNTIL DUP ->STR @ in which 9 is "9" POS NOT @ not a digit END 'p' STO @ save prime 0. p @ sum ; p 1. 5. FOR n DUP 10. MOD @ get digit: d DUP 4. + PICK @ get d! + ROT + @ new total SWAP 10. / IP @ remove LSD NEXT DROP @ unneeded 0. UNTIL p == END 9. DROPN p @ drop !'s; p >> >> ``` Edited: 20 July 2010, 11:55 p.m. after one or more responses were posted ▼ Glenn Shields Member Posts: 63 Threads: 8 Joined: Dec 2009 07-17-2010, 06:49 AM Han, I tried your program, but it seemed to get stuck in a loop of 10007 NEXTPRIME 10009, so with the test loop rewritten like this: DO DO p NEXTPRIME 'p' STO UNTIL p ->STR "9" POS NOT END ... the program ran as expected, it took 13 minutes, 10 seconds for me. Thanks for this "extra" challenge, with all due respect a great approach. Regards, Glenn ▼ Han Senior Member Posts: 709 Threads: 104 Joined: Nov 2005 07-19-2010, 08:32 PM Quote: Han, I tried your program, but it seemed to get stuck in a loop of 10007 NEXTPRIME 10009, so with the test loop rewritten like this: DO DO p NEXTPRIME 'p' STO UNTIL p ->STR "9" POS NOT END ... the program ran as expected, it took 13 minutes, 10 seconds for me. Thanks for this "extra" challenge, with all due respect a great approach. Regards, Glenn Glenn, You are right in that there is a typo. My program has: DO p DO NEXTPRIME UNTIL DUP ->STR "9" POS NOT END 'p' STO (There should be a p between the two DOs, and not after.) ▼ Glenn Shields Member Posts: 63 Threads: 8 Joined: Dec 2009 07-22-2010, 08:50 PM Thanks for that correction, Han. I tried your program again, and it does run in the time you say, about 30 seconds faster than my re-write. Could this be because i call p again, while you leave it in the stack with DUP ? It must be a real but very small difference, to add up to only 30 seconds in many (thousands?) iterations. Can't wait for the next one. Kiyoshi Akima Senior Member Posts: 325 Threads: 18 Joined: Jul 2006 07-16-2010, 05:08 PM Sometimes the amount of that overhead can be staggering. I first unrolled the innermost loop (the factorial lookups) and got the program to run in just under 12 minutes. Then I converted to SysRPL, which forces the programmer to worry about the data types. That almost doubled the speed, to 6.5 minutes. ```:: AtUserStack ( no stack arguments required ) 40320 5040 720 120 24 6 2 ONEONE 9973 FPTR2 ^#>Z ( largest four-digit prime ) BEGIN BEGIN ( reject primes containing nines ) FPTR2 ^Prime+ DUP FPTR2 ^Z>S tok9 ONE POS\$ #0= UNTIL DUP FPTR2 ^Z>S DISPROW1 DUP FPTR2 ^Z>R COERCE DUP TEN #/ SWAP DUP #5+ PICK #+ SWAP TEN #/ SWAP DUP #6+ PICK #+ SWAP TEN #/ SWAP DUP #7+ PICK #+ SWAP TEN #/ SWAP DUP #8+ PICK #+ SWAP DUP #8+ PICK #+ #+ #+ #+ #+ #= UNTIL 10UNROLL 9 NDROP ; ``` PS: Is it too soon to mention that a tremendous speed gain can be achieved by starting from the other end? ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-16-2010, 06:30 PM Quote: Is it too soon to mention that a tremendous speed gain can be achieved by starting from the other end? No, this thread started several days ago and most folks have had time to digest it, I think. Yes, starting at 99999 and going down should reduce the times (since I know that the magic number is obviously >50000). What surprizes me with the run times I have seen so far is that the TI-NSpire, running BASIC, seems to be somewhat faster than the 50g running RPL. I thought the 50g could do almost anything in less than a nano-second. I'm exaggerating, of course. I'm thinking that the NSpire isprime() function must be really optimized or something. Don ▼ Palmer O. Hanson, Jr. Posting Freak Posts: 901 Threads: 113 Joined: Jun 2007 07-16-2010, 10:26 PM Quote: No, this thread started several days ago and most folks have had time to digest it, I think. Yes, starting at 99999 and going down should reduce the times (since I know that the magic number is obviously >50000). Because the solution also can't stand three eights it would be possible to further reduce the time by starting somewhere in the neighborhood of 88800 and going down. To avoid that sort of silliness it would be better to require that the solution scan the entire range. Palmer ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-17-2010, 12:00 AM Quote:To avoid that sort of silliness it would be better to require that the solution scan the entire range. But if someone can make a mathematical case for scanning a smaller range, as some have done in this thread, I think, then more power to them, use the smaller range and tell us why you can do it. For example, several folks mentioned that the number can't have a 9 in it because 9! is larger than a 5 digit number. The number 8 has limitations too. I'd rather see the thought behind these things than just scanning all 5-digit numbers. My NSpire method just did that too, because I was lazy and dumb! But I value and admire smarts. Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 07-17-2010, 09:31 AM Quote: To avoid that sort of silliness it would be better to require that the solution scan the entire range. What's the point? I can prove fully that the number must: ```1) The number is odd 2) The number is less than 88777 ( e.g. greedy algorithm by subtracting the max n! from 99,999) and larger than 10087 3) The sum of digits (SOD) is between 14 and 37 (corollary to 2) 4) There exists at least one digit above 6, but no nines anywhere in the number 5) The SOD is not a multiple of 3 6) The last digit is a 1,3, or 7 ``` By implementing a selection of these rules, you can reduce the naive search by more than 60%. While that might not be important on the range of 99,000, imagine if the problem were expanded to six-digit numbers as Katie suggested? Suddenly a hard problem becomes much easier with a more purposeful algorithm. For any problem like this, searching the entire range is like paying full price at one store despite the half-off sale next door. ▼ Kiyoshi Akima Senior Member Posts: 325 Threads: 18 Joined: Jul 2006 07-17-2010, 03:16 PM 7) There must be an odd number of the digits {0,3,5,7}, which implies that there is an even number (possibly zero) of the digits {1,2,4,6,8}. From #4 above there are no nines. ▼ Glenn Shields Member Posts: 63 Threads: 8 Joined: Dec 2009 07-17-2010, 04:40 PM Thanks, Katie, for this new challenge, and thanks Han for the method of pre-computing the factorials. I modified Han's program to include 9! and to increment by 1. It was hard to guess a range of numbers, but those around 770000 to 880000 seemed likely. But incrementing by ones was taking forever. I have two hp50g's, and set one to go up (using INCR) and one to go down from 775000. Six hours later, no answer, and batteries were getting low. So, deciding to skip by 10, and taking a wild guess that the number ends in 7, the answer popped up in a short while (but far from the initial guess, btw). Also, the answer, I must confess, does have a 9 in it, and the sod is a multiple of 3. Here's the program all in a row: << 362880. 40320. 5040. 720. 120. 24. 6. 2. 1. 1. 100007. -> n << DO 0. n 10 + DUP 'n' STO 1. 6. FOR i DUP 10. MOD DUP 4. + PICK + ROT + SWAP 10. / IP NEXT DROP UNTIL n == END 10. DROPN n >> >> Again, thanks to Katie for this calculator fun! Incidentally, neither this number nor the original challenge number is listed in the "numeropedia" on-line which covers a huge range of numbers (yes I tried to cheat!) Cheers, Glenn ▼ Katie Wasserman Posting Freak Posts: 1,477 Threads: 71 Joined: Jan 2005 07-18-2010, 01:36 AM I cheated too, I found the number using a tiny AWK program on my PC in a couple of seconds. It's a lot of number crunching for a calculator. Han Senior Member Posts: 709 Threads: 104 Joined: Nov 2005 07-20-2010, 04:44 PM Quote: I have two hp50g's, and set one to go up (using INCR) and one to go down from 775000. Six hours later, no answer, and batteries were getting low. Don't forget -- the HP50G can run off of USB power. Just plug it into your laptop or PC when doing heavy calculations for "free" power =) Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 07-23-2010, 05:27 PM Hello Don, Quote: since I know that the magic number is obviously >50000 Since you've given no other hints, we curious people here had to write our own programs or run someone else's program to know what it is. I won't spoil it all by simply listing it here. Instead, I present the following sequence that should work on any 10-digit HP RPN calculator that has Gamma function, like the HP-11C and 15C. I've made some arrangements to make your magic number look like one: 14 (2*7) palindromic lines, some 7s and exactly 7 calls to x! in the fourth line. ``` 7 1 1/x 1 7 + SQRTx SQRTx x! x! x! x! x! x! x! 7 1 1/x 3 SQRTx 3 x! / + 2 * - ``` Of course a simple INT might replace 10 lines (and make it work on 12-digit calculators too), but I like this pattern. Gerson. Edited: 23 July 2010, 5:41 p.m. ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-23-2010, 06:21 PM To borrow a quote from Apollo 13: And you, sir, are a steely-eyed missleman! How clever. thx, Don Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 07-17-2010, 06:59 PM Quote: ... a tremendous speed gain can be achieved by starting from the other end? Indeed! Even my last-hour very inelegant solution on the 50g below finds the solution in less than 73 seconds (Too busy at work last week to give it a try). I tested only odd numbers ending in 7, 3 and 1 (There is no prime number ending in 5 but 5 itself and 9 cannot be in the solution). ```%%HP: T(3)A(R)F(,); DIR PRG \<< 88777 DO DUP ISPRIME? \<< CHK \>> IFT 4 - DUP ISPRIME? \<< CHK \>> IFT 2 - DUP ISPRIME? \<< CHK \>> IFT 4 - DUP 10000 < UNTIL END \>> CHK \<< DUP N2L DUP ! + \GSLIST == \<< KILL \>> IFT \>> N2L \<< DUP \->STR DUP HEAD STR\-> { } + SWAP TAIL DUP HEAD STR\-> ROT + SWAP TAIL DUP HEAD STR\-> ROT + SWAP TAIL DUP HEAD STR\-> ROT + SWAP TAIL STR\-> + \>> END ``` Thomas Klemm Senior Member Posts: 735 Threads: 34 Joined: May 2007 07-20-2010, 09:27 PM First I wanted to have a rough estimate of the number of primes between 10,000 and 88,888. Using the aproximation n/log(n) I got 6,714 while the correct answer is 7,382. The constraint concerning the factorial of the digits seemed to be more rigid than that of beeing a prime. Since the order of the digits doesn't change the sum I wondered how many possibilities I'd have to check. I decided to have the digits ordered descending from left to right. Since we need at least two 7's and at most three 8's I check the following two ranges: ```77000 - 77777: comb(10, 7) = 120 80000 - 88888: comb(12, 8) = 495 ``` Thus I'd have to check only 615 cases. For each case the "magic" sum is calculated. To make it easier to compare the digits I use a representation where the position counts the digits, e.g. 34316 -> 1012010. When they agree the program stops and displays this representation. From this the number can be calculated using the "magic" sum. Now you only have to verify that this number is a prime. Initialization (some may call it cheating): ```10 STO 0 ``` 1st run (77000 - 77777): ```7.007 STO 1 STO 2 0.007 STO 3 GTO 3 R/S ``` There's no solution within this range. 2nd run (80000 - 88888): ```8.008 STO 1 0.008 STO 2 GTO 2 R/S ``` There's exactly one solution: 210101000. So we know we have two 8's, one 7, one 5 and one 3. I'm leaving it up to you to calculate the number. You probably already know it. Here's the program for the HP-15C: ```LBL A STO 1 LBL 1 RCL 1 STO 2 LBL 2 RCL 2 STO 3 LBL 3 RCL 3 STO 4 LBL 4 RCL 4 STO 5 LBL 5 5 STO I CLx ENTER LBL 9 RCL (i) INT ENTER 10^x R-^ + x<>y ENTER x! + R-^ + DSE I GTO 9 0 x<>y LBL 0 RCL / 0 INT x<>y LSTx FRAC RCL * 0 10^x + x<>y TEST 0 GTO 0 R-v TEST 5 R/S ISG 5 GTO 5 ISG 4 GTO 4 ISG 3 GTO 3 ISG 2 GTO 2 ISG 1 GTO 1 RTN ``` This is just a raw version. It could be improved when some of the repeating results were cached in registers. It runs quiet fast in the emulator of my iPhone but I don't know how long it would take on the real calculator. Thanks for the nice challenge and all the other solutions. Best regards Thomas Edited: 20 July 2010, 10:17 p.m. ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-21-2010, 01:20 AM Thomas, what a nice algorithm! I appreciate the fact you could pick this problem apart logically without resorting to the brute-force approach. Well done! Don Shepherd Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 07-21-2010, 10:16 AM Quote: Since we need at least two 7's and at most three 8's Shouldn't it be two 8's at most as 3*8! is a 6-digit number? Anyway, I haven't understood how you set up the range you want to check. Quote: I don't know how long it would take on the real calculator. The second run took about 46 minutes on my 2.2x 15C, which translates to about 1 hour and 40 minutes on a normal 15C (or 1 and a half hour if the speed-up factor is 2 - I don't remember whether I changed it or not). Regards, Gerson. ▼ Thomas Klemm Senior Member Posts: 735 Threads: 34 Joined: May 2007 07-21-2010, 07:05 PM Quote: Shouldn't it be two 8's at most as 3*8! is a 6-digit number? Absolutely correct! Yet three 8's are still a correct upper limit. Quote: Anyway, I haven't understood how you set up the range you want to check. Actually I'd like to check the digits 77000 - 88800. However my program doesn't allow to configure that directly, but it's possible to configure a range as 000 - 777 or 0000 - 8888. So I expanded the range a little and split it into two parts: 77000 - 77777 and 80000 - 88888. In the first case two digits are constant (7) while in the second only one is (8). Many thanks for taking the time to meassure the runtime of my program. I'm surprised it took so long but the calculation in the inner-most loop is quiet complex. It might be possible to use something simpler as the (alternate) sum of the digits. It all depends on how many false positives are produced. Cheers Thomas ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 07-21-2010, 11:49 PM Hello Thomas, Thanks for your explanations. Quote: I'm surprised it took so long but the calculation in the inner-most loop is quiet complex. That's not so long, considering the HP-15C is a slow calculator. At least its power consumption is very low: it's running on a set of batteries that my HP-42S used to exaustion, yet there's some energy left to power up even a sped-up 15C (no blinking star so far). Regards, Gerson. Edited: 22 July 2010, 9:52 a.m. Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-26-2010, 06:47 AM Here is a solution for the HP-30b. It finds the number in 31 seconds. The primacy of the number can be verified in less than 1 second using the code in message# 30 of this thread. I start with 88777, the largest possible 5-digit number based upon 8! and 7!, and decrement by 2 to check only odd numbers. Following is BASIC-like pseudocode and the 30b RPN code that follows the BASIC model. ```for i = 88777 to 1 step -2 a=i b=0 for j = 0 to 4 d = a mod 10 b = b + d + d! a = ip (a/10) next j if b = i then print b/stop next i 88777 sto 0 lbl 10 sto 2 0 sto 3 4 eex 3 +/- sto 1 lbl 11 rcl 2 10 / ans x<->y math up = x sto+3 ! sto+3 rcl 2 10 / math up up = sto 2 isg 1 goto 11 rcl 3 rcl 0 ?= gt 12 2 - sto 0 goto 10 lbl 12 stop ``` Thanks to all who participated in this little endeavor, especially those who offered non-brute-force solutions. The intelligence and creativity of members of this forum are amazing. Edited: 26 July 2010, 7:11 a.m. ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 07-27-2010, 02:30 PM No improvement from what's been posted so far. The number is found in 7 minutes and 48 second on my HP 33s (batteries starting to get low). Four more seconds can be gained if the constant in lines D0004 and D0014 is recalled from a register. Now the number only has to be checked for primality, which shoud take no more than a few seconds. ```B0001 LBL B B0002 4 B0003 STO A B0004 STO C B0005 2 B0006 STO B B0007 88777 B0008 STO N B0009 -1 B0010 STO X F0001 LBL F F0002 1 F0003 STO+ X F0004 RCL X F0005 3 F0006 RMDR F0007 1 F0008 + F0009 STO i F0010 RCL(i) F0011 STO- N F0012 0 F0013 STO S F0014 RCL N D0001 LBL D D0002 ENTER D0003 ENTER D0004 10 D0005 RMDR D0006 8 D0007 x this generates the sequence 4,4,2,4,4,2,... when x=2,3,4,5,6,7,... F0013 STO- N ; which is successively subtracted from n, so that odd numbers ending in 5 or 9 are skipped F0014 0 F0015 STO S ; initialize sum F0016 RCL N D0001 LBL D D0002 ENTER D0003 ENTER D0004 10 D0005 RMDR ; get single digits of n starting from the last significant digit D0006 8 D0007 x

 Possibly Related Threads... Thread Author Replies Views Last Post RE: 35s sorting routine challenge - Gene's Challenge Miguel Toro 4 437 08-01-2007, 08:36 AM Last Post: Miguel Toro

Forum Jump: