On Monday, July 12, 2021 at 10:56:40 AM UTC+3, Michael S wrote:
> On Sunday, July 11, 2021 at 1:27:26 AM UTC+3, Michael S wrote:
> > On Friday, July 9, 2021 at 5:20:10 PM UTC+3, Michael S wrote:
> > > On Friday, July 9, 2021 at 4:24:57 PM UTC+3, Kent Dickey wrote:
> > > > In article <06a1aff4-365a-4f91...@googlegroups.com>,
> > > > Michael S <already...@yahoo.com> wrote:
> > > > >Solved it, finally.
> > > > >6 seconds of intentionally non-optimized compute + ~30 hours of thinking
> > > > >and trying, 10 of each due to being stubborn.
> > > > >
> > > > > 1 9 9
> > > > > 2 20 29
> > > > > 3 360 389
> > > > > 4 2701 3090
> > > > > 5 4096 7186
> > > > > 6 109466 116652
> > > > > 7 161022 277674
> > > > > 8 13068583 13346257
> > > > > 9 2136960 15483217
> > > > >10 0 15483217
> > > > >11 71101800 86585017
> > > > >12 55121700430 55208285447
> > > > >13 1057516028 56265801475
> > > > >14 1023436651875 1079702453350
> > > > >15 30731637609504 31811340062854
> > > > >16 719883432165805 751694772228659
> > > > >17 195741994241 751890514222900
> > > > >18 2325274798835849 3077165313058749
> > > > >19 2253334981970 3079418648040719
> > > > >
> > > > >But I cheated - did it in C++ with use of STL containers.
> > > > >Of course, I can do it in C, but then bulk of the code will be dealing
> > > > >with infrastructure instead of problem in hand.
> > > > So, what is the "trick"?
> > > Do you really want to know?
> > > I think, it's more interesting to figure it out by yourself. You can see uncommented solution in my github repo.
> > > https://github.com/already5chosen/others/commit/07075aba5bcc3ebbbc45891015f36ac8bd373c71
> > > But I recommend to try to not look for another day or week.
> > > > Does it extend beyond 19 digits (which is what
> > > > fits in a long long)?
> > > >
> > > It would work, if somewhat slower, since all data elements are bigger.
> > > 33-34 digits are almost certainly doable on PC with 16GB of RAM, but not in 1 minute.
> > > I don't know how much more is doable, estimation of the size of data structures could serve as a math challenge all by itself.
> > >
> > >
> > >
> > > > Kent
> > I did the change to counters, extending them to 128 bit, but left the rest of fields, in particular keys, at 64 bit, so this variant can go to 31 digits, but not above.
> > On my old home PC with 8 GB of RAM it chocked at 27 digits.
> > Now I am trying on platform with a bit more RAM.
> >
> > Results so far:
> > 1 9 9
> > 2 20 29
> > 3 360 389
> > 4 2701 3090
> > 5 4096 7186
> > 6 109466 116652
> > 7 161022 277674
> > 8 13068583 13346257
> > 9 2136960 15483217
> > 10 0 15483217
> > 11 71101800 86585017
> > 12 55121700430 55208285447
> > 13 1057516028 56265801475
> > 14 1023436651875 1079702453350
> > 15 30731637609504 31811340062854
> > 16 719883432165805 751694772228659
> > 17 195741994241 751890514222900
> > 18 2325274798835849 3077165313058749
> > 19 2253334981970 3079418648040719
> > 20 14258990353214916495 14262069771862957214
> > 21 33134685643184 14262102906548600398
> > 22 5041746922237448246 19303849828786048644
> > 23 375213413241495 19304225042199290139
> > 24 13119917959126435648946 13139222184168634939085
> > 25 1002012764891350262722506 1015151987075518897661591
> > 26 8701748936645284200857 1023853736012164181862448
> Update:
> Bigger gear easily calculated 27, 28 and 30 digits, but was running out of memory at 29 digits.
> In order to crack it I had to make several changes to data structures. The changes made thing a little
> slower, but brought peak memory consumption down to 48-49GB. The machine in question has 64GB installed
> but it's used simultaneously thorough Windows terminal server by several people, so even when they do not not run their heavy jobs, memory still consumed and at best 56-57 GB were available to my program.
> The full run from 1 to 30 digits took 256m11.022s. This version release majority of memory back to system
> at the beginning of each sub-stage, i.e. 29*28/2=406 times. If I'll by more grabby, the run time can be reduced
> to ~200minutes.
> Results so far:
> 1 9 9
> 2 20 29
> 3 360 389
> 4 2701 3090
> 5 4096 7186
> 6 109466 116652
> 7 161022 277674
> 8 13068583 13346257
> 9 2136960 15483217
> 10 0 15483217
> 11 71101800 86585017
> 12 55121700430 55208285447
> 13 1057516028 56265801475
> 14 1023436651875 1079702453350
> 15 30731637609504 31811340062854
> 16 719883432165805 751694772228659
> 17 195741994241 751890514222900
> 18 2325274798835849 3077165313058749
> 19 2253334981970 3079418648040719
> 20 14258990353214916495 14262069771862957214
> 21 33134685643184 14262102906548600398
> 22 5041746922237448246 19303849828786048644
> 23 375213413241495 19304225042199290139
> 24 13119917959126435648946 13139222184168634939085
> 25 1002012764891350262722506 1015151987075518897661591
> 26 8701748936645284200857 1023853736012164181862448
> 27 66488874235428050 1023853802501038417290498
> 28 12244686991286657955227400 13268540793787696372517898
> 29 719431039502164172 13268541513218735874682070
> 30 9420183703185916092057240786 9433452244699134827931922856
>
>
> With relatively minor changes to data structures I can very likely solve nDigits=32,34,35 and 36.
> But for nDigits=31 I'd need bigger machine (I'd guess, 200GB will do) and ~12 hours of compute
> time. For nDigits=33 - 4 times more than that, both in memory and in time.
> That's unless there exists another algorithmic breakthrough.

Observation #4 proved to be rather important.
After I took advantage of it, the size of the data set (for nDigits=28) shrunk by factor of 7.
Execution time also improved. As a result, I managed to calculate result for nDigits=31.
nDigits=32 was easy, as expected.

Results so far:
1 9 9
2 20 29
3 360 389
4 2701 3090
5 4096 7186
6 109466 116652
7 161022 277674
8 13068583 13346257
9 2136960 15483217
10 0 15483217
11 71101800 86585017
12 55121700430 55208285447
13 1057516028 56265801475
14 1023436651875 1079702453350
15 30731637609504 31811340062854
16 719883432165805 751694772228659
17 195741994241 751890514222900
18 2325274798835849 3077165313058749
19 2253334981970 3079418648040719
20 14258990353214916495 14262069771862957214
21 33134685643184 14262102906548600398
22 5041746922237448246 19303849828786048644
23 375213413241495 19304225042199290139
24 13119917959126435648946 13139222184168634939085
25 1002012764891350262722506 1015151987075518897661591
26 8701748936645284200857 1023853736012164181862448
27 66488874235428050 1023853802501038417290498
28 12244686991286657955227400 13268540793787696372517898
29 719431039502164172 13268541513218735874682070
30 9420183703185916092057240786 9433452244699134827931922856
31 7955196982875614557 9433452252654331810807537413
32 1044368729348834888241541279499 1053802181601489220052348816912

Time: 172m45.059s
Peak working set size: 27,182,277,000 bytes

The later number means that the same program when applied to nDigits=33 will need approximately 110 GB of RAM.
Right now I have no access to computer that carries that much.
I do know how to make data structures approximately 1.7 times more compact, but it will come at cost of rather significant
slowdown. Besides 110/1.7 = 64GB so it's borderline and most likely wouldn't fit in physical memory anyway.

So, the most reasonable thing to do would be to declare a victory and stop right there.