[VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" Special

05242018, 05:10 PM
(This post was last modified: 06022018 06:07 PM by Jeff O..)
Post: #31




RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
(05172018 09:12 PM)Valentin Albillo Wrote:Jeff O Wrote:My usual inclination with such problems is to just go ahead and try for a brute force method, then try to optimize. The DM42 is fast, I would like to see how many digits it could handle in a reasonable time by brute force, so if I get the time I may have a go at it. (05242018 06:14 AM)PeterP Wrote: ...but I wanted to ask for your opinion about posting it or not given that it is indeed past your suggested deadline. Peter, Based on Valentin's "please do" stated above, I'm going on the assumption that it is OK to post. If interested, see below, which details my "clumsy" solution. As a start, I went ahead and created a bruteforce program with which I identified the 30 selfies from 1 to 10 digits: 1 2 3 4 5 6 7 8 9 173 351 704 4361 4749 8028 48039 72729 84745 438845 5136299 5271471 7180089 8180124 15087642 77439588 351589219 579533274 638494435 802115641 4777039764 For the sake of completeness, here are the 11digit selfies, determined using a revised program as described in my post below: 15 694 046 123 52 249 382 004 30 609 287 624 97 653 680 744 60 605 588 394 87 561 939 628 41 919 540 249 I implemented this program on Free42 with the intent to download to my DM42 to see how fast it might go on that machine. The above results were obtained running Free42 on my desktop PC. Output was to the virtual printer. It produces the first 19 (i.e., 6digit or fewer selfies) nearly instantaneously, then slows down considerably. Takes about maybe 2.5 minutes to get the 7digit, then maybe 25 minutes for the 8digit, and awhile for the 9digit. I let the program run most of yesterday and then overnight, and this morning was rewarded with the lone 10digit selfie. It looks like finding the seven 11digit selfies would take about 20 days, so I think I’ll probably wait until I figure out some optimized method to find those rather than continuing to run my program. My brute force method does not look directly for selfies, it looks for numbers which have the property that if you sum its N digits raised to the Nth power you get the original number back (let’s call them inverse selfies), then it simply reverses those to create the selfie. I quickly found that not all inverse selfies will be a selfie when reversed. Specifically those that end in zero will not, since when an N digit number ending in zero is reversed, it becomes an N1 digit number. I thought that perhaps filtering out numbers ending in zero, i.e., not summing their digits to the Nth power to see if they were inverse selfies and so reducing the quantity of numbers to be checked by 10%, might speed things up. Unfortunately, performing that check on every number seemed to take longer, or at least was no quicker, than summing the digits to the Nth power for all numbers and then checking only inverse selfies to see if they end in zero. (I found two such numbers, 370 and 24678050, before I revised the program to eliminate them.) In any case, a 10fold or more increase in speed is really needed to make this practical. I can see some ways to determine that some numbers need not be checked, for example, no 10digit number with three or more nines need be checked since all those will sum to an 11 digit number, no 10 digit number with six as the largest digit can be a selfie since thoese will not sum to a 10 digit number. I’ll keep thinking about the problem to see if I can develop a method that will be much quicker  hopefully it won’t keep me awake at night. Here is the brute force program listing: 00 { 90Byte Prgm } 01▸LBL "VA6_6" 02 CLA 03 CF 29 04 FIX 00 05 RCL 02 06 ARCL ST X 07 ALENG 08 STO 00 09 0 10▸LBL 04 11 ATOX 12 X=0? 13 GTO 05 14 48 15  16 RCL 00 17 Y↑X 18 + 19 GTO 04 20▸LBL 05 21 CLX 22 RCL 02 23 X≠Y? 24 GTO 08 25 10 26 ÷ 27 FP 28 X=0? 29 GTO 08 30 ARCL ST Y 31 0 32 STO 01 33▸LBL 06 34 ATOX 35 X=0? 36 GTO 07 37 48 38  39 RCL 01 40 10↑X 41 ISG 01 42 DEG 43 × 44 + 45 GTO 06 46▸LBL 07 47 R↓ 48 PRX 49▸LBL 08 50 ISG 02 51 DEG 52 GTO "VA6_6" 53 END edited to correct typo and add clarity to one item edit no. 2  added the 11digit selfies to the list Dave  My mind is going  I can feel it. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)