a new challenge!



#82

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.


#83

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


#84

yes

#85

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).


#86

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

#87

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


#88

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) :-)

#89

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

#90

Mark, remind me which ROM contains "NEXTPRM" or is it built into the 41c?

#91

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.


#92

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.

#93

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

#94

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.

#95

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


#96

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.


#97

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).

#98

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.


#99

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


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.


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.


unless isPrime is very slow. so, not dumb and worth a try!

Without the knowledge that the only solution is prime, isPrime at some point is required.


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

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
»
»


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.


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


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.

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


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.


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. :-)


Thanks Miles. I would have thought it would have taken a bit longer.

Don

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.


Glenn, this particular factoid came from this book.


Don: What is the plot on the cover of the book?


That plot shows the distribution of small Eisenstein primes.

This site is associated with that book and briefly discusses this.

Oops! The run time that I listed with without lines to display the progress. So for faster run time, remove "PRI 1. DISP"

Dave

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


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.

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.


Katie, is that a number with a==0?


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...

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.

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.


Egan, I don't understand. Why isn't plus and minus all those numbers zero?


+ 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.


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


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?"


Now that I understand! Thanks David.

Now to solve it....

Yes. Thanks David. I just got back from vacation. So, no takers?


Please don't give the answer yet, Egan. I may give it a try this week.

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.


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


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


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.)


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.

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?


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


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


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.

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.


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.


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


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.

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 =)

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.


To borrow a quote from Apollo 13: And you, sir, are a steely-eyed missleman!

How clever.

thx, Don

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

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.


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

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.


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


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.

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.


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<y?
D0008 GTO F
D0009 Rv
D0010 STO+ S
D0011 x!
D0012 STO+ S
D0013 Rv
D0014 10
D0015 INT/
D0016 x#0?
D0017 GTO D
D0018 RCL S
D0019 RCL N
D0020 x=y?
D0021 STOP
D0022 GTO F

length checksum
B 78 0D17
F 90 7D36
D 102 A8D7


Thanks Gerson. I know that many here don't like the 33s because of its chevron keyboard, but that never bothered me, it is a fast little calculator, much faster than its successor, the 35s.

Until HP releases an ARM-based scientific RPN programmable calculator, I do recommend the 30b. It is a bit quirky to program, but it is blazingly fast.


You're welcome, Don. Than YOU for the interesting problems you've been posting.

I prefer the 33s over the 35s for a many reasons. Among them:

- It's faster;

- Checksums work;

- ALL mode works the way I like;

- XEQ works like it should (XEQ label only to execute a program);

- Many functions accessible right from the keyboard.

The 33s keyboard, however, is not good.

Regards,

Gerson.

B0001 LBL B                
B0002 1.009 ; precompute factorial of digits as per Han's suggestion
B0003 STO i
C0001 LBL C
C0002 RCL i
C0003 IP
C0004 1
C0005 -
C0006 x!
C0007 STO(i) ; the factorial of digits 0..8 will be stored in registers A through I
C0008 ISG i
C0009 GTO C
C0010 88781
C0011 STO N
C0012 1
C0013 STO X
F0001 LBL F
F0002 1
F0003 STO+ X
F0004 4
F0005 RCL X
F0006 3
F0007 RMDR
F0008 2
F0009 RMDR
F0010 LASTx
F0011 *
F0012 - ; 4 - 2*mod(mod(x,3),2) -> 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<y?
D0008 GTO F ; abort process when a digit greater than 8 is found
D0009 Rv
D0010 STO+ S ; add digit to sum
D0011 RCL+ A ; increment digit
DOO12 STO i ; and use it as a pointer to table of factorials
D0013 RCL (i) ; get factorial of digit
D0014 STO+ S ; and add it to sum
D0015 Rv
DO016 Rv ; discard digit and factorial
D0017 10
D0018 INT/
D0019 x#0?
D0020 GTO D ; repeat until there is no digit left
D0021 RCL S
D0022 RCL N
D0023 x=y?
D0024 STOP ; stop when n matches sum
D0025 GTO F ; next n

length checksum

B 21 E56B
C 75 E81F
F 108 08CF
D 111 3F33

Running time: 6m 23s

A somewhat faster version:

B0001 LBL B
B0002 1.008
B0003 STO i
C0001 LBL C
C0002 RCL i
C0003 IP
C0004 x!
C0005 STO(i)
C0006 ISG i
C0007 GTO C
C0008 8
C0009 STO I
C0010 10
C0011 STO J
C0012 88781
C0013 STO N
C0014 1
C0015 STO X
F0001 LBL F
F0002 RCL A
F0003 STO+ X
F0004 4
F0005 RCL X
F0006 3
F0007 RMDR
F0008 RCL B
F0009 RMDR
F0010 LASTx
F0011 *
F0012 -
F0013 STO- N
F0014 0
F0015 STO S
F0016 RCL N
D0001 LBL D
D0002 ENTER
D0003 ENTER
D0004 RCL J
D0005 RMDR
D0006 RCL I
D0007 x<y?
D0008 GTO F
D0009 Rv
D0010 STO+ S
D0011 x=0?
D0012 x!
DOO13 STO i
D0014 RCL (i)
D0015 STO+ S
D0016 Rv
DO017 Rv
D0018 RCL J
D0019 INT/
D0020 x#0?
D0021 GTO D
D0022 RCL S
D0023 RCL N
D0024 x=y?
D0025 STOP
D0026 GTO F

length checksum

B 21 71FD
C 93 D48D
F 84 2659
D 78 6BDC

Running time: 6m 11s


Edited: 29 July 2010, 2:40 p.m.


Quote:
Running time: 6m 11s

4m 29s after replacing batteries with brand-new ones. This means it would take about 23 seconds on a 30b running the same algorithm (considering the performance of both calculators on Xerxes's benchmark).


Quote:
This means it would take about 23 seconds on a 30b running the same algorithm

In message #1 in this thread I used a different algorithm, but it took 31 seconds on the 30b. Quite a fast little machine, I wish Office Depot in my town had it, I'd like to get another one. Richard Nelson says August...

Don


23 seconds is just an estimation which may be wrong. The actual timing would be only known by porting the algorithm to the 30b, but I fear this is not so straightforward. Anyway, the half minute running time you have actually obtained is pretty impressive. I don't have a 30b yet (I am reluctant to get another financial calculator - I got rid of one 12C Platinum, one 19BII and one 17BII. Only one 12C and one 12C+ left now, the first because it's a Voyager and the latter because it's its extremely fast version). Still waiting for a new 30s or something like that ...

Gerson.


The algorithm I used on the 30b should be translatable to the 12c+. You'd need to control the loop manually since there's no ISG, but we've been doing that for years on the 12c. The 30b and 12c+ use the same processor, so the timing should be similar.


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: