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

[brickviking]

(05-15-2018 05:42 PM)Maximilian Hohmann Wrote:  ... (The last time I wrote the word "PEEK" before this reply must have been ca. 1983 when I did some machine language programming on my Sinclair ZX81). ...

PEEK and POKE have interesting results on a SHARP PC-1247. I got several somewhat unexpected results by poking instruction codes directly into program memory, as that was within the range of program listings. I don't have that calculator any more, I suspect I lost it in a move along with the dual-trace 1MHz oscilloscope.

As the 1247 only had 3328 bytes of addressable memory, it wasn't considered "big iron" enough for what I thought I wanted out of a programmable calculator. It certainly wasn't in the same league as the 71B or 75C/D (but was probably considerably cheaper).

(Post 220)

[Valentin Albillo]

.
Hi, Jeff O, Maximilian Hohmann and brickviking:

Jeff O Wrote:Upon further review, Step the 6th is the kind of number manipulation challenge that I have enjoyed attempting on various models [...] With that said, reading that Egan put 3 hours and one sleepless night into it, and it will continue to haunt him, kind of scares me off a bit.

No need to be afraid, Egan was probably trying to scare would-be solvers, actually it's not that difficult. On hindsight, I probably goofed badly when I put this lovely problem last after a row of essentially 71B-only, tricky ones, so people failed to notice its generality (more or less solvable in every machine) and classic nature. My bad.

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

Please do. I haven't created a solution for the DM42 but I guesstimate that with correct programming it can solve the 11-digit version in 5 min. to 1 hour running time.

Quote:In any case, thanks for your challenges, please don’t be put off by a lower than hoped-for response. Next time I’ll be sure to read through more carefully!

Thank you very much, you'll be welcome to try. I feel better now. :-D

Maximilian Hohmann Wrote:Although I [...] would not have been able to solve a single one of these challenges. Especially the ones which require PEEKing the digits of mathematical constants out of the ROM... (The last time I wrote the word "PEEK" before this reply must have been ca. 1983 when I did some machine language programming on my Sinclair ZX81).

He he, same here ! I also had a Sinclair ZX81 back then and also did Z80A machine language programming, most especially video games and graphics routines. I got many books dealing with the matter (which I still keep to this day), most of them truly excellent, and learned a lot. I remember writing my Bombardier game utterly by hand, with no compilers or any other tools, painstakingly computing the offsets for the jumps by sheer byte-counting, etc., and being ecstatic when it run fine the first time I tried it, not even a single bug or miscalculation. Those were the days ... !

Quote:Nonetheless these challenges and the answers are a pleasure to read and think about!

Thank you very much for your kind words, much appreciated. See below for something on PEEK ... :-)

brickviking Wrote:PEEK and POKE have interesting results on a SHARP PC-1247. I got several somewhat unexpected results by poking instruction codes directly into program memory, as that was within the range of program listings.

It's quite similar to the way we HP calc fans initially discovered synthetics in the HP-41C. We would enter data in storage registers and thanks to Bug 2 it would appear in program memory as various synthetic functions, most notably STO M, N, and such. My first HP-41C was a very early model with all the bugs. Regrettably, I eventually sold it and the next HP-41C I got didn't have Bug 2 anymore.

Quote:As the 1247 only had 3328 bytes of addressable memory, it wasn't considered "big iron" enough for what I thought I wanted out of a programmable calculator. It certainly wasn't in the same league as the 71B or 75C/D (but was probably considerably cheaper).

Much cheaper. And the 71B was also much cheaper (and 5 times slower !) than the 75CD (which I never liked, too bulky, bad keyboard layout, mediocre BASIC).

Best regards to all.
V.
.

[J-F Garnier]

(05-17-2018 09:12 PM)Valentin Albillo Wrote:  ... the 71B was also much cheaper (and 5 times slower !) than the 75CD (which I never liked, too bulky, bad keyboard layout, mediocre BASIC).

I do also prefer the HP71, but the HP75 is an interesting machine, too.
Especially the 16kB Math module is very good, much more powerful than the HP80 series Matrix ROM. It has matrix functions, complex number support (although not as nicely integrated than on the HP71), various utility math functions, the PROOT polynomial root finder, the Fourier Transform and more important the FNROOT and INTEGRAL functions.

That is quite the same feature set than the 71.
Or we may better say that the HP71 Math ROM included all the previous HP75 Math ROM features, adding a better integration with the mainframe (e.g. complex number) and improvements such as the re-entrant FNROOT and INTEGRAL functions.

And with emu75 (very similar to emu71/DOS that you know very well), the first two drawbacks mentioned above are no more relevant :-)

J-F

[Valentin Albillo]

.
Hi, J-F:

(05-20-2018 02:50 PM)J-F Garnier Wrote:  I do also prefer the HP71, but the HP75 is an interesting machine, too.
Especially the 16kB Math module is very good, much more powerful than the HP80 series Matrix ROM.

I'd love to have a look at its Owner's Handbook to ascertain what it does and what it doesn't do. Just for instance, I think comparing it to the HP80 series Matrix ROM is quite unfair. The Matrix ROM does just that, matrix handling, so it's no surprise it doesn't delve with complex suppport, integrals, or root-finding, that's simply out of its scope.

For what it does, matrices, I wonder if the HP-75 16 Kb ROM had even a fraction of its functionality. I don't remember that it did, and that's why I'd love to see its manual. The HP-71B Math ROM is also quite inferior in that regard, having much less functionality in its matrix capabilities as compared to the HP80 series ROM.

Quote:It has matrix functions, complex number support (although not as nicely integrated than on the HP71), [...]

Matter of fact, the complex number support isn't integrated at all. The HP-75 mainframe has no provision whatsoever for complex number support (unlike the HP-71B, which does) and so there's no way to integrate it, nicely or not. I did try those capabilities at the time and found them severely lacking and awkward to use.

Quote:[...]the PROOT polynomial root finder, the Fourier Transform and more important the FNROOT and INTEGRAL functions. That is quite the same feature set than the 71.

I seriously doubt it because the HP-71B's is a 32Kb ROM and the HP-75C's is a 16 Kb one. I don't think that Capricorn assembly language is 2 times more space-efficient than Saturn assembly language so I don't think that it could fit in 16 Kb what it takes 32 Kb in the HP-71B.

Back at the time I had an HP-87XM fitted with the Assembler ROM (among many others) ad 192 Kb RAM and I did tons of Capricorn assembly language BIN files, including a very large one implementing all kinds of matrix functionality (even SORTing), printing utilities to speed raster graphics, CRT manipulation, the works, and I don't think the instruction set was 200% more efficient space-wise.

Quote:Or we may better say that the HP71 Math ROM included all the previous HP75 Math ROM features, adding a better integration with the mainframe (e.g. complex number) and improvements such as the re-entrant FNROOT and INTEGRAL functions.

The Math ROM article in the HP Journal says as much. It also says that it used the best algorithms from the 80 series Matrix ROM and enhanced versions of the HP-15C algorithms.

Quote:And with emu75 (very similar to emu71/DOS that you know very well), the first two drawbacks mentioned above are no more relevant :-)

Thanks for your kind words but I'm pretty sure you do know emu71/DOS better than me ... ;-D

Best regards.
V.
.
Edit to correct a mistake.

[rprosperi]

(05-20-2018 11:01 PM)Valentin Albillo Wrote:  I seriously doubt it because the HP-71B's is a 64 Kb ROM and the HP-75C's is a 16 Kb one. I don't think that Capricorn assembly language is 4 times more space-efficient than Saturn assembly language so I don't think that it could fit in 16 Kb what it takes 64 Kb in the HP-71B.

The 75C/D has 48KB ROM in all, comprised of:

SYSROM - 24K
BASROM - 8K
ALTROM - 8K
MELROM - 8K

This is 'visible' by using the VER$ function which reports 'aaaaaa', 'bbbbbb', or 'dddddd', indicating the version letter for each of the 6 x 8K ROMs.

[Valentin Albillo]

.
Hi, Bob:

(05-21-2018 12:02 AM)rprosperi Wrote:  The 75C/D has 48KB ROM in all, comprised of:[...] This is 'visible' by using the VER$ function which reports 'aaaaaa', 'bbbbbb', or 'dddddd', indicating the version letter for each of the 6 x 8K ROMs.

My bad. I was referring to the sizes of the respective Math ROMs, not the System ones but I got the wrong 71B Math ROM size, it's 32 Kb, not 64 Kb, which I'll correct immediately in my post.

Thanks a lot. 4:15 a.m. here. Regards.
V.
.

[rprosperi]

(05-21-2018 02:14 AM)Valentin Albillo Wrote:  .
Hi, Bob:

(05-21-2018 12:02 AM)rprosperi Wrote:  The 75C/D has 48KB ROM in all, comprised of:[...] This is 'visible' by using the VER$ function which reports 'aaaaaa', 'bbbbbb', or 'dddddd', indicating the version letter for each of the 6 x 8K ROMs.

My bad. I was referring to the sizes of the respective Math ROMs, not the System ones but I got the wrong 71B Math ROM size, it's 32 Kb, not 64 Kb, which I'll correct immediately in my post.

Thanks a lot. 4:15 a.m. here. Regards.
V.
.

Happy to chat, and glad if it helped to clarify the discussion.

Though this probably could have waited until 6 or 7 am...

[J-F Garnier]

(05-20-2018 11:01 PM)Valentin Albillo Wrote:  I'd love to have a look at its Owner's Handbook to ascertain what it does and what it doesn't do.

The handbook and QRG are available on the HP75 group (access to files for registered users only), together with the HP75 Math ROM source file!

Quote:For what it does, matrices, I wonder if the HP-75 16 Kb ROM had even a fraction of its functionality. I don't remember that it did, and that's why I'd love to see its manual. The HP-71B Math ROM is also quite inferior in that regard, having much less functionality in its matrix capabilities as compared to the HP80 series ROM.

I dind't remember that the Series 80 Matrix ROM had such more functionalities. Maybe it's time for me to re-start my old HP85...

Quote:Matter of fact, the [HP75] complex number support isn't integrated at all. The HP-75 mainframe has no provision whatsoever for complex number support (unlike the HP-71B, which does) and so there's no way to integrate it, nicely or not. I did try those capabilities at the time and found them severely lacking and awkward to use.

Sure. Complex numbers are managed as 2-element arrays and, for instance, to add two complex numbers you must do something like:
MAT Z = CADD(Z1,Z2)
But at least it exists, if you need complex numbers, you don't have to write your own routines as you have to in the Series 80.

Quote:

Quote:[...]the PROOT polynomial root finder, the Fourier Transform and more important the FNROOT and INTEGRAL functions. That is quite the same feature set than the 71.

I seriously doubt it because the HP-71B's is a 32Kb ROM and the HP-75C's is a 16 Kb one. I don't think that Capricorn assembly language is 2 times more space-efficient than Saturn assembly language so I don't think that it could fit in 16 Kb what it takes 32 Kb in the HP-71B.

This is surprising for me too. Even if the 71 Math LEX is only 27 kB long (the rest of the ROM is filled with 0), it makes a big difference of code size.
I intent to compare the features of the 71 and 75 Math ROM more in details. But it will be the subject of another thread.

Quote:Back at the time I had an HP-87XM fitted with the Assembler ROM (among many others) ad 192 Kb RAM and I did tons of Capricorn assembly language BIN files, including a very large one implementing all kinds of matrix functionality (even SORTing), printing utilities to speed raster graphics, CRT manipulation, the works, and I don't think the instruction set was 200% more efficient space-wise.

If you still have some material of that time, we at the HP Series 80 group would love to see it, and preserve it if you permit.

J-F

[Valentin Albillo]

(05-21-2018 08:24 AM)J-F Garnier Wrote:  (... lotsa lotsa things ...)
J-F

This is deviating too far from my S&SMC#23 so time for another dedicated thread.

I suggest you create it with some adequate Subject (say, "Math ROMs for 71B, 75C and Series 80") and include as its first post what you say in your latest here, then I'll comment on each of your points.

Regards.
V.
.

[PeterP]

Dear Valentin, thank you for providing yet another of your most wonderful teaching exercises! While it was more focused on 71B but you - thankfully - left one to be tackled by other calculators as well. I had a long flight (actually two) so I tried by luck with it but alas, upon finishing a working code discovered that I had found the original thread after the deadline had past (I did not read the fine print nor any of the comments lest I spoil my pleasure).

My code takes a few minutes to deliver the first 9 digit 'Selfie' on my i41CX, is of course entirely clumsy and could use a true masters hand, but I wanted to ask for your opinion about posting it or not given that it is indeed past your suggested deadline.

In any case, I am very thankful for spending yet again an incredible amount of time and effort in concocting, creating, testing, and then wrapping in a nice story one of your wonderful S&SMC.

Many more you make, I hope.

Cheers

PeterP

[Jeff O.]

(05-17-2018 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.

(05-17-2018 09:12 PM)Valentin Albillo Wrote:  Please do. I haven't created a solution for the DM42 but I guesstimate that with correct programming it can solve the 11-digit version in 5 min. to 1 hour running time.

(05-24-2018 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 brute-force 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 11-digit 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., 6-digit or fewer selfies) nearly instantaneously, then slows down considerably. Takes about maybe 2.5 minutes to get the 7-digit, then maybe 25 minutes for the 8-digit, and awhile for the 9-digit. I let the program run most of yesterday and then overnight, and this morning was rewarded with the lone 10-digit selfie. It looks like finding the seven 11-digit 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 N-1 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 10-fold 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 10-digit 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 { 90-Byte 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 11-digit selfies to the list

[Valentin Albillo]

.
.
Hi, PeterP and Jeff 0.:

(05-24-2018 06:14 AM)PeterP Wrote:  Dear Valentin, thank you for providing yet another of your most wonderful teaching exercises!

Long time no see, PeterP !! I missed you ! ... Glad to see you taking part in one of my recent S&SMC's as you so frequently did in the past.

Quote:While it was more focused on 71B but you - thankfully - left one to be tackled by other calculators as well.

Yes, I was fearing that it was too 71B centric and regrettably the HP-71B seems placed in a no-man's land being the only calc-sized BASIC model, not RPN, not RPL, so it seems it's got very few fans and thus I provided a plan B by including last a challenge that could be solved in most calcs. My fears proved real so I'm glad I did.

Quote:upon finishing a working code discovered that I had found the original thread after the deadline had past (I did not read the fine print nor any of the comments lest I spoil my pleasure).

Actually, there are no hard deadlines, most especially for a challenge that no one posted anything about and thus for which I also posted no solution. In such a case anyone is welcome to post anything at any time.

Quote:My code takes a few minutes to deliver the first 9 digit 'Selfie' on my i41CX, is of course entirely clumsy and could use a true masters hand, but I wanted to ask for your opinion about posting it or not given that it is indeed past your suggested deadline.

See above. I'm eager to see your code so post it here at your earliest convenience, and if possible include timings.

Quote:In any case, I am very thankful for spending yet again an incredible amount of time and effort in concocting, creating, testing, and then wrapping in a nice story one of your wonderful S&SMC. Many more you make, I hope.

You're welcome, thanks a lot for your everlasting appreciation. I have several S&SMC plus assorted Mini-Challenges ready to post at a moment's notice.

Jeff O. Wrote:As a start, I went ahead and created a brute-force program with which I identified the 30 selfies from 1 to 10 digits:

I'm glad that you decided to give it a go, as you say you would. Brute-force or not your results are correct so congratulations, you're the first one (and so far the only one until PeterP posts his code) to solve it so my most sincere congratulations.

Quote:The above results were obtained running Free42 on my desktop PC. It produces the first 19 (i.e., 6-digit or fewer selfies) nearly instantaneously, then slows down considerably. [...] It looks like finding the seven 11-digit 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.

Wise decision. Brute-force usually takes (generic) you so far, then you must think harder in order to beat the exponential curse.

Quote:In any case, a 10-fold or more increase in speed is really needed to make this practical. [...] 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.

Please do. I'll post my original solution at 23:xx (GMT+1) next Sunday so you've got plenty of time to refine and expand your own.

Thanks to both and best regards.
V.
.

[PeterP]

Thank you VA for your kind encouragement to post, it was a pleasure to work on for a flight (and a night) so I'm glad I get to share.

Another way to define the selfie is an n-digit number which is identical to the sum of the n-the power of its digits, but does not end in a 0.

To constrain the search space, I used two features:
(1) One can always rank order the digits of a number in a monotonously falling fashion (each digit is smaller or equal than the prior one
(2) As soon as one has a sum of n-th power of digits which is larger than 10^n, one can stop as all combination of digits to the right will yield unqualified results.

The combined application of the above allows to cut of quite substantial swaths of the search tree.

The implementation is based on the specific limitations of the HP41, namely:
1) It can only deal with at most 6 subroutine levels. This makes a recursive approach unfortunately not possible on the 41, yet I would not be surprised if this is possible, indeed advisable for the 71b
2) The 41 is very very slow in dealing with direct number entries. As such, virtually all numbers are stored in registers for faster processing
3) Akin to the JPC rom, my version uses my beloved Sandbox module, for the use of INCX, DECX, and AINT
4) Once a number has been found with a sum of the n-th powers of its digits between 10^n and 10^(n-1), the number is then checked to see if it is a selfie, aka the sum of its digts raised to the n-th power, using AINT and ATOX.

The code below takes as an entry the number of digits and then runs until all n-digit selfies are found. Adding a loop over all digits would be trivial but was not done for the purpose of easier exploration of the results of the code, timing, etc.

Code:


LBL ‘VASSMC’
CLRG
STO 00        ‘’store n-digit
10^x
STO 40        ‘’store upper limit
10
/
STO 42        ‘’store lower limit
48
STO 48        ‘’store const for fast conversion from ASCII to number
21
STO 20        ‘’start space to store found numbers
19
STO 41        ‘’location for full sum
9
RCL 00
-
INCX
10
STO IND Y
GTO IND Y    ‘’this starts the search loop at the right label for the number of digits
LBL 01
   RCL 01    “digit in first spot, initialized with 10
   STO 02    “max digit for second spot
   DECX
   X<0?        “Are we done?
   GTO ‘DONE
   STO 01    “no, store for next loop
   RCL 00    “number of digits
   Y^X
   STO 11    “temp-sum of first digit to n-th power
   LBL 02    “second digit
      RCL 02    “second digit, initialized in prior code to value of first digit
      STO 03    “max digit for third spot
      DECX
      X<0?    “Are we done?
      GTO 01    “yep, count down one more the first digit
      STO 02    “nope. Calc n-th power
      RCL 00
      RCL 11    “get sum from prior digit
      +
      STO 12    “store sum of this digit
      RCL 40    “10^n, upper limit
      X<=Y?    “Is the current sum smaller than this 10^n?
      GTO 02    “Nope, count down on this level by one
      LBL 03    “yes, tackle next digit. 
         RCL 03    “third digit, initialized in prior code to value of first digit
         STO 04    “max digit for fourth spot
         DECX
         X<0?    “Are we done?
         GTO 02    “yep, count down one more the prior digit
         STO 03    “nope. Calc n-th power
         RCL 00
         RCL 12    “get sum from prior digit
         +
         STO 13    “store sum of this digit
         RCL 40    “10^n, upper limit
         X<=Y?    “Is the current sum smaller than this 10^n?
         GTO 03    “Nope, count down on this level by one
         LBL 04
            RCL 04
            STO 05    
            DECX
            X<0?    
            GTO 03    
            STO 04    
            RCL 00
            RCL 13    
            +
            STO 14    
            RCL 40    
            X<=Y?    
            GTO 03
            LBL 05
               […]
               LBL 06
                  […]
                  LBL 07
                     […]
                     LBL 08
                        […]
                        LBL 09
                           RCL 09
                           DECX
                           X<0?
                           GTO 08
                           STO 09
                           RCL 00
                           Y^X
                           RCL 18
                             +
                           STO 19
                           RCL 40
                           X<=y?
                           GTO 09
                           LBL 11        “we have found a candidate
                              RCL 42    “check for lower limit
                      RCL IND 41   “Final sum
                              X<=Y?
                              GTO 09
                              CLA
                      ARCLI    “arcl integer
                              ALENG
                      LBL 00    “calc sum of n-th power of digits of candidate
                         ATOX
                         RCL 48    “value: 48
                         -
                         RCL 00
                         Y^X
                         ST- Z    “subtract from candidate value
                         RDN
                         DSE X
                    GTO 00
                    RDN        “candidate – sum of n-th power of its digits
                          X=0?        “have we found one?
                    XEQ ‘FND    “yes, we have
                    GTO 09
                    LBL ‘FND
                       RCL IND 41
                       ARCLI
                       10        “check for last digit 0
                       /
                          FRC
                       X=0?    “is last digit 0?
                       RTN    “false alarm…
                       AREV    “reverse number in alpha
                       TONE 9
                       AVIEW
                       STO IND 20    “preserver for after the run (for long unmonitored runs)
                       ISG 20
                       CLA
                       RTN
LBL ‘DONE
   BEEP
   ‘DONE
   AVIEW
END

Very much looking forward to comments, in particular ways to make it smarter.

[Jeff O.]

(05-24-2018 09:13 PM)Valentin Albillo Wrote:  

Jeff O. Wrote:In any case, a 10-fold or more increase in speed is really needed to make this practical. [...] 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.

Please do. I'll post my original solution at 23:xx (GMT+1) next Sunday so you've got plenty of time to refine and expand your own.

Thanks to both and best regards.
V.

So as to not use anyone else's concepts for the time being, I have not reviewed Peter's work. Should anything I say or present below be a repetition of concepts presented by Peter, I fully acknowledge his priority.

In an effort to reduce execution time, I developed a method which basically checks 10 numbers at a time. I guess a better way to describe it would be to say that it determines if there is a solution between successive numbers that end in zero.

Since it is still basically just brute force, i.e., does not break any ground in attacking the problem in a super-efficient manner, I won't explain the procedure in detail. If anyone wants an explanation, I can provide it.

Since it effectively checks 10 numbers at a time, it seemed like a program based on the procedure should theoretically be up to 10 times faster than the previous program, as it checks all N+1 digit numbers by counting up to N. In practice, it appears that the various manipulations required to implement it eliminate some of the time saving. The speed-up seems to be more like a factor of 4 to 5. But with that improvement, I went ahead and turned it loose to find the 11-digit selfies. After (only) several days (again, on Free42 running on a couple of PCs), it found the seven 11-digit selfies:

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

The new program listing is presented below. Unfortunately, this program does not technically meet the original challenge. It cannot determine the single digit selfies from 1 through 9 since if you start counting at 1, it is checking candidates starting at 10. I could add code to just print out 1 through 9 at the start, but that seems unnecessary.

As noted, this is still essentially just brute force, and would be totally impractical on a DM42. Running on a physical machine in minutes or hours would require a massive speed-up factor. I'll keep trying to think of some other method to attack the problem that would be faster, but there's not much time until Sunday. Then I'll have to decide if I want to admit defeat and review Valentin's solution, or let it haunt me the rest of my days...

00 { 112-Byte Prgm }
01▸LBL "SELF"
02 CLA
03 CF 29
04 FIX 00
05 RCL 02
06 ARCL ST X
07 10
08 ×
09 ALENG
10 1
11 +
12 STO 00
13 R↓
14▸LBL 04
15 ATOX
16 X=0?
17 GTO 05
18 48
19 -
20 RCL 00
21 Y↑X
22 -
23 X<0?
24 GTO 08
25 GTO 04
26▸LBL 05
27 R↓
28 RCL ST X
29 RCL 00
30 1/X
31 Y↑X
32 1
33 +
34 IP
35 STO 11
36 RCL 00
37 Y↑X
38 RCL- 11
39 X≠Y?
40 GTO 08
41 10
42 RCL× 02
43 RCL+ 11
44 ARCL ST X
45 0
46 STO 01
47▸LBL 06
48 ATOX
49 X=0?
50 GTO 07
51 48
52 -
53 RCL 01
54 10↑X
55 ISG 01
56 DEG
57 ×
58 +
59 GTO 06
60▸LBL 07
61 R↓
62 PRX
63▸LBL 08
64 ISG 02
65 DEG
66 GTO "SELF"
67 END

[Valentin Albillo]

.
Hi, Jeff O.:

(06-02-2018 06:01 PM)Jeff O. Wrote:  In an effort to reduce execution time, I developed a method which basically checks 10 numbers at a time. I guess a better way to describe it would be to say that it determines if there is a solution between successive numbers that end in zero. [...] the speed-up seems to be more like a factor of 4 to 5. [...] After (only) several days (again, on Free42 running on a couple of PCs), it found the seven 11-digit selfies:

Congratulations, it's quite an achievement and I thank you for your efforts on this last part of my S&SMC#23. A factor of 400-500% faster over what sheer brute force produces is certainly a remarkable improvement.

Quote:Unfortunately, this program does not technically meet the original challenge. It cannot determine the single digit selfies from 1 through 9 since if you start counting at 1, it is checking candidates starting at 10. I could add code to just print out 1 through 9 at the start, but that seems unnecessary.

It certainly is. The meat of the challenge is to produce the many-digit selfies, not the trivial ones. Insisting on that would be nitpicking on my part, which I don't usually indulge in.

Quote:As noted, this is still essentially just brute force, and would be totally impractical on a DM42. Running on a physical machine in minutes or hours would require a massive speed-up factor

Indeed. As far as I know, there are at least three ways to attack this problem. The first and most obvious is sheer brute force (very brute), but that stumbles at 10 or 11 digits at most and even then it takes excessively long times.

The second and third ways depend on the same idea but implement it differently and both reduce exponentially the required times, to the point that 11 digits can be reached in Emu71 in a few minutes, and using somewhat slow multiprecision software running on a decidedly slow old PC they can still find all the solutions with 10, 20, 30 and more digits in a few hours at most.

Quote:I'll keep trying to think of some other method to attack the problem that would be faster, but there's not much time until Sunday. Then I'll have to decide if I want to admit defeat and review Valentin's solution, or let it haunt me the rest of my days...

Time is not a problem, I'm also no nitpicker with deadlines and such. If you need more time, I'll glady postpone posting my solutions. Also, if you'd accept a hint or two in order to be able to implement the 2nd or 3rd ways, I'll gladly obligue. Perhaps it would spoil somewhat the pleasure of finding the idea by yourself but in the other hand it's also quite pleasurable to create a markedly non-trivial working solution starting from a little hint instead of sorely admitting defeat after so much effort and time.

Your choice ... :-D

Again, thanks for your interest and your great efforts, have a nice weekend.
V.
.

[Warbucks]

The original problem is a BBP problem using PSLQ as a tool (integer relations finding) is it not?

[Jeff O.]

(06-02-2018 10:37 PM)Valentin Albillo Wrote:  Time is not a problem, I'm also no nitpicker with deadlines and such. If you need more time, I'll glady postpone posting my solutions. Also, if you'd accept a hint or two in order to be able to implement the 2nd or 3rd ways, I'll gladly obligue. Perhaps it would spoil somewhat the pleasure of finding the idea by yourself but in the other hand it's also quite pleasurable to create a markedly non-trivial working solution starting from a little hint instead of sorely admitting defeat after so much effort and time.

Your choice ... :-D
Again, thanks for your interest and your great efforts, have a nice weekend.
V.

Thanks for your kind words about my efforts. Sure, I’ll take a little more time and a hint or two. I’ll consider it a learning experience rather than a failing.

[Valentin Albillo]

.
Hi, Jeff O.:

(06-03-2018 04:34 PM)Jeff O. Wrote:  Thanks for your kind words about my efforts. Sure, I’ll take a little more time and a hint or two. I’ll consider it a learning experience rather than a failing.

In 5 minutes, check your Private Messages. :-)

Regards.
V.
.

[Jeff O.]

(06-04-2018 09:19 PM)Valentin Albillo Wrote:  In 5 minutes, check your Private Messages. :-)

Regards.
V.
.

Thank you, message received. I’ll see what I can do with the information.

[Valentin Albillo]

(06-03-2018 04:52 AM)Warbucks Wrote:  The original problem is a BBP problem using PSLQ as a tool (integer relations finding) is it not?

I don't get you. What "original problem" are you referring to ?

V.
.