MC: 4th power with no small digits
in [HP48]
|
Prev: (Sorry for the non french speaking peoples) Un logiciel de géométrie dynamique pour HP
Next: Dust inside 50g. How to clean? How to prevent?
From: Han on 29 Mar 2010 16:41 Dave, Here are some slight modifications of your code. Mainly, HEAD and TAIL are slow. Also, there is really no need to take the FLOOR of the upper bound because we're counting by integers. You can additionally add in a filter for the last 2 digits; however, since the numbers in the range 10^[(d+log(5)/4] ... 10^[(d+1)/4] is relatively small even for 14 digit numbers, and the time required to test the last two digits of n (must compare against at most 24 values) is actually higher than just testing all the digits of n^4 (at most 14), we would only include the filter for sufficiently large d. The only problem with the code below is that we are limited to 44- digit integers unless we convert %n_low and %n_high to integers prior to the FOR n statement (which eliminates the need for R->I). This can easily be adjusted; however, computing with integers takes more time than computing with reals. This runs in about 17.58 seconds. << 0. 1. @ n (desired number) and d (digits) WHILE OVER NOT REPEAT .698970004336 @ precompute LOG(5) OVER 1. + 4. / @ lower bound: [d + LOG(5)]/4 < LOG(n) ALOG CEIL @ ensure we start with an even IF DUP 2. MOD @ integer n > THEN 1. + END OVER 1. + 4. / @ upper bound: LOG(n) < (d + 1)/4 ALOG @ stack: 0. %d %n_low %n_high FOR n @ stack: 0. %d n R->I 4 ^ ->STR @ $ = digits of n^4 DUP SIZE @ stack: 0. %d $ %pos DO 1. - @ ok to skip last digit (always a 6) UNTIL DUP2 DUP SUB @ stack: 0. %d $ $digit "4" > OVER AND @ big digit and more to go? NOT @ no, move on to next digit END @ much faster than HEAD/TAIL SWAP DROP @ stack: 0. %d %pos @ if %pos = 0 then all digits @ were big, otherwise small @ digit occured at %pos IF THEN ELSE @ IF THEN ELSE faster than IF NOT THEN n ROT @ stack: 0. %d %n DROP SWAP @ stack: %n %d 1.E499 'n' STO @ stop our loop END 2. @ only check evens STEP 1. + @ digits++ END DROP @ %n %d -> %n >>
From: John H Meyers on 29 Mar 2010 18:58 @ Fourth power of positive integer having no digit less than 5 @ Short (size) program for HP49/50 @ can search until insufficient memory to hold data \<< 0 DO 1 + DUP SQ SQ \->STR { "0" "1" "2" "3" "4" } POS UNTIL \GSLIST NOT END \>> @ Program for HP48G[X], can search up to 2^16-1 \<< 64 STWS DEC #0 DO 1 + DUP DUP * DUP * \->STR { "0" "1" "2" "3" "4" } POS UNTIL \GSLIST NOT END \>> @ [End]
From: John H Meyers on 29 Mar 2010 20:19 On 3/29/2010 5:58 PM: > @ Fourth power of positive integer having no digit less than 5 > > @ Short (size) program for HP49/50 > @ can search until insufficient memory to hold data > \<< 0 DO 1 + DUP SQ SQ \->STR > { "0" "1" "2" "3" "4" } POS > UNTIL \GSLIST NOT END \>> > > @ Program for HP48G[X], can search up to 2^16-1 > \<< 64 STWS DEC #0 DO 1 + DUP DUP * DUP * \->STR > { "0" "1" "2" "3" "4" } POS > UNTIL \GSLIST NOT END \>> > > @ [End] If we accept having proved that all odd 4th powers end in "1" or "25" (and thus would be rejected) then we can change 1 + to 2 + to approximately halve the times of the above. \GSLIST NOT can also be replaced by { 0. 0. 0. 0. 0. } SAME to be a bit faster, at the expense of larger program. [r->] [OFF]
From: Han on 29 Mar 2010 22:47 On Mar 29, 6:19 pm, John H Meyers <jhmey...(a)nomail.invalid> wrote: > On 3/29/2010 5:58 PM: > > > @ Fourth power of positive integer having no digit less than 5 > > > @ Short (size) program for HP49/50 > > @ can search until insufficient memory to hold data > > \<< 0 DO 1 + DUP SQ SQ \->STR > > { "0" "1" "2" "3" "4" } POS > > UNTIL \GSLIST NOT END \>> > > > @ Program for HP48G[X], can search up to 2^16-1 > > \<< 64 STWS DEC #0 DO 1 + DUP DUP * DUP * \->STR > > { "0" "1" "2" "3" "4" } POS > > UNTIL \GSLIST NOT END \>> > > > @ [End] > > If we accept having proved that all odd 4th powers > end in "1" or "25" (and thus would be rejected) > then we can change 1 + to 2 + > to approximately halve the times of the above. > > \GSLIST NOT can also be replaced by { 0. 0. 0. 0. 0. } SAME > to be a bit faster, at the expense of larger program. > > [r->] [OFF] Good call on the SQ SQ in place of 4 ^. Using SQ SQ reduces the time from 17.58s to 13.71s
From: Han on 29 Mar 2010 23:02
On Mar 29, 4:58 pm, John H Meyers <jhmey...(a)nomail.invalid> wrote: > @ Fourth power of positive integer having no digit less than 5 > > @ Short (size) program for HP49/50 > @ can search until insufficient memory to hold data > \<< 0 DO 1 + DUP SQ SQ \->STR > { "0" "1" "2" "3" "4" } POS > UNTIL \GSLIST NOT END \>> > > @ Program for HP48G[X], can search up to 2^16-1 > \<< 64 STWS DEC #0 DO 1 + DUP DUP * DUP * \->STR > { "0" "1" "2" "3" "4" } POS > UNTIL \GSLIST NOT END \>> > > @ [End] A list of 1-chr strings takes up a lot of space due to 5byte headers (5 nibbles for object type, and 5 more nibbles for string length). Here's one slightly shorter which embeds the list as a string: \<< 0 DO 2 + DUP SQ SQ \->STR "{\"0\"\"1\"\"2\"\"3\"\"4" STR\-> POS UNTIL \GSLIST NOT END \>> |