On Monday, July 12, 2021 at 10:01:36 PM UTC+3, Michael S wrote:
> 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.

I didn't do a reasonable thing. Instead, I did this:
$ time ./euler-413-final1 36
1 9 9 4.104
2 20 29 4.166
3 360 389 4.166
4 2701 3090 4.178
5 4096 7186 4.178
6 109466 116652 4.178
7 161022 277674 4.178
8 13068583 13346257 4.178
9 2136960 15483217 4.182
10 0 15483217 4.182
11 71101800 86585017 4.190
12 55121700430 55208285447 4.194
13 1057516028 56265801475 4.223
14 1023436651875 1079702453350 4.268
15 30731637609504 31811340062854 4.268
16 719883432165805 751694772228659 4.268
17 195741994241 751890514222900 4.600
18 2325274798835849 3077165313058749 4.846
19 2253334981970 3079418648040719 6.365
20 14258990353214916495 14262069771862957214 6.365
21 33134685643184 14262102906548600398 10.625
22 5041746922237448246 19303849828786048644 10.625
23 375213413241495 19304225042199290139 26.305
24 13119917959126435648946 13139222184168634939085 26.305
25 1002012764891350262722506 1015151987075518897661591 26.305
26 8701748936645284200857 1023853736012164181862448 55.480
27 66488874235428050 1023853802501038417290498 331.309
28 12244686991286657955227400 13268540793787696372517898 331.309
29 719431039502164172 13268541513218735874682070 1266.840
30 9420183703185916092057240786 9433452244699134827931922856 1266.840
31 7955196982875614557 9433452252654331810807537413 4890.669
32 1044368729348834888241541279499 1053802181601489220052348816912 4890.669
33 109472444039835433842 1053802181710961664092184250754 18955.948
34 37965679725962948820277344022 1091767861436924612912461594776 18955.948
35 148798789390894672890531437539966 149890557252331597503443899134742 18955.948
36 155772981015805981518042643206768 305663538268137579021486542341510 18955.948

real 175m38.573s
user 0m0.000s
sys 0m0.000s

The 4th column is a peak working set size, in MB

Also,
$ time ./euler-413-final1 38 38
38 67735710564427721233072120099477 67735710564427721233072120099477 37213.352

real 116m24.953s
user 0m0.000s
sys 0m0.000s

What about nDigits=37 ?
With this particular implementation it will take 15 times more memory than nDigits=33 and ~20 times more time.
I can find machine time, but not the memory.

Memory consumption can be cut to almost half by spilling intermediate results of each stage to disk.
With good NVMe SSD it wouldn't even be much slower than keeping everything
in memory, because each stage accesses results of the previous stage in sequentially order and only once.
But even after such modification nDigits=37 will need ~150 GB of RAM. Not too much for many people, but too much for me.
Esp. considering that no one will pay me to know the answer and almost no one will look at the number.