On Friday, July 9, 2021 at 6:23:44 PM UTC+3, DFS wrote:
> On 7/9/2021 8:52 AM, Michael S wrote:
>
>
> > Solved it, finally.
>
> Good job.
>
>
> FYI: 'triceps' from Japan solved it 00:40:17 after it was posted.
>
> https://projecteuler.net/fastest=413

WOW!

To my defense:
I am programming for too many years. As a result, thinking too much like programmer :(
In order to solve this kind of challenges quickly one has to think like mathematician.
Also, it helps to be half my age.

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

On 09/07/2021 13:52, Michael S wrote:
> On Thursday, July 8, 2021 at 11:03:08 AM UTC+3, Michael S wrote:
>> On Wednesday, July 7, 2021 at 2:02:53 AM UTC+3, Michael S wrote:
>>> On Tuesday, July 6, 2021 at 8:28:02 PM UTC+3, Kent Dickey wrote:
>>>> In article <c7bfb14a-2084-41c3...@googlegroups.com>,
>>>> Michael S <already...@yahoo.com> wrote:
>>>>>
>>>>> Those are still variations of the theme that I outlined in the post from
>>>>> Jul 4, 2021, 1:21:16 PM
>>>>> As proven in the post from Jul 5, 2021, 12:44:48 PM, as far as original
>>>>> 1=19 digits challenge is concerned, it's a dead end.
>>>>> In order to tackle the original challenge, the positive (one-child)
>>>>> results should somehow be discovered and counted in bunches of of at
>>>>> least thousands (preferably 100s of thousands) rather than one-by-one.
>>>>> Just rejecting negatives in bunches is not sufficient.
>>>> I was just posting code I wrote before your posts.
>>>>
>>>> I did not see any "proofs", there was a post with some numbers, with no
>>>> explanation of where they came from or why we should believe it.
>>> There was an explanation: the numbers are estimates found by Monte Carlo method.
>>> For each number of digits I tested 1E7 randomly distributed points and extrapolated.
>>> Later on I repeated the tests with 1E8 point per range and got approximately the same
>>> result. That is, estimates could be off by few per cents, but it wouldn't change the conclusion:
>>> the total number of one-child numbers in range 1:1e19 is too huge for any methods that reject
>>> candidates in bunches but confirm individually.
>>> Why should you believe it? Because I said so and I tend to be reliable in that sort of things.
>>> I didn't post the Monte Carlo code here because
>>> (a) it is trivial, every decent pro has to be able to code something like that in less than 2 hours
>>> (b) it is coded in C++ and the group is about C.
>>> I can save it at my github account if wish to see it.
>>>
>>> BTW, here are full results:
>>> 1: 10 / 10 * 10 = 1.000000000000000e+01
>>> 2: 20 / 90 * 90 = 2.000000000000000e+01
>>> 3: 360 / 900 * 900 = 3.600000000000000e+02
>>> 4: 2701 / 9000 * 9000 = 2.701000000000000e+03
>>> 5: 4096 / 90000 * 90000 = 4.096000000000000e+03
>>> 6: 109466 / 900000 * 900000 = 1.094660000000000e+05
>>> 7: 161022 / 9000000 * 9000000 = 1.610220000000000e+05
>>> 8: 13068583 / 90000000 * 90000000 = 1.306858300000000e+07
>>> 9: 237707 / 100000000 * 900000000 = 2.139363000000000e+06
>>> 10: 0 / 100000000 * 9000000000 = 0.000000000000000e+00
>>> 11: 78609 / 100000000 * 90000000000 = 7.074810000000000e+07
>>> 12: 6126028 / 100000000 * 900000000000 = 5.513425200000000e+10
>>> 13: 11791 / 100000000 * 9000000000000 = 1.061190000000000e+09
>>> 14: 1137562 / 100000000 * 90000000000000 = 1.023805800000000e+12
>>> 15: 3414651 / 100000000 * 900000000000000 = 3.073185900000000e+13
>>> 16: 7992302 / 100000000 * 9000000000000000 = 7.193071800000000e+14
>>> 17: 198 / 100000000 * 90000000000000000 = 1.782000000000000e+11
>>> 18: 258937 / 100000000 * 900000000000000000 = 2.330433000000000e+15
>>> 19: 30 / 100000000 * 9000000000000000000 = 2.700000000000000e+12
>>> Total 3.084430326475721e+15
>>>> I wrote
>>>> some code to get some idea if pruning would work--and for some ranges, it's
>>>> very effective, for other ranges, it's not effective at all. Basically,
>>>> to see the timing differences for different ranges. My pruning code showed:
>>>>
>>>> size runtime factor number of 1-childs
>>>> 10^6: 0.046 secs = = 116652
>>>> 10^7: 0.231 secs = 5.02x = 277674
>>>> 10^8: 5.374 secs = 23.2x = 13346257
>>>> 10^9: 11.463 secs =2.13x = 15483217
>>>>
>>> I have exact results for up to 13 digits.
>>> Ndigits N-one-childs
>>> 1 - 10
>>> 2 - 20
>>> 3 - 360
>>> 4 - 2701
>>> 5 - 4096
>>> 6 - 109466
>>> 7 - 161022
>>> 8 - 13068583
>>> 9 - 2136960
>>> 10 - 0
>>> 11 - 71101800
>>> 12 - 55121700430
>>> 13 - 1057516028
>>> Pay attention, format is slightly different from yours, yours is accumulated, mine is per specific number of digits.
>>> 12 and 13 digits took relatively long compute time to find - 38min and 57min respectively. i.e. much more than the time allowed by informal rules of the challenge.
>> Update:
>> With better code (posted on comp.arch) I managed to brute-force 14 digits.
>> It took almost 4 hours on a single core, far away from timing requirements of the challenge.
>> I expect that 17 digits can be ripped in similar time. May be, 19 digits too, not sure about it.
>> For 15 digits I expect results in 4-5 days.
>> But ripping 16 or 18 digits with this code will take many months of single-core compute time.
>> Current results:
>> 1 - 9
>> 2 - 20
>> 3 - 360
>> 4 - 2701
>> 5 - 4096
>> 6 - 109466
>> 7 - 161022
>> 8 - 13068583
>> 9 - 2136960
>> 10 - 0
>> 11 - 71101800
>> 12 - 55121700430
>> 13 - 1057516028
>> 14 - 1023436651875
>> 15 - ???
>> 16 - ???
>> 17 - ???
>> 18 - ???
>> 19 - ???
>>>> This shows pruning working very effectively for 10^9. But 8-digit numbers
>>>> have so many 1-childs, that pruning the negative just doesn't cut out
>>>> enough work. It needs to do something to count groups of 1-childs positively.
>>>>
>> I am starting to get an idea of how to count in bunches.
>> Still have one algorithmic difficulty to figure out before I start coding.
>>>> It's easy to brute force the digits through 10^9. However, something happens
>>>> when the digits are >= 10. I already reported there are no 1-childs when
>>>> digits == 10.
>>> Yes, when the fact is know that's relatively easy to understand.
>>>> The problem changes for digits >= 11 since individual digits
>>>> can no longer be 1-childs (other than 0). Rather than trying them all, there's
>>>> a way to show what patterns result in 1-childs (and not 2-childs or 0-childs),
>>>> and then just counting those patterns. This is not obvious to me and would
>>>> require a great deal more study, since it seems to revolve around 19-digit
>>>> numbers and factors of 19 (and 18, etc.).
>>>>
>>>> I don't see how to partition this problem easily. Take 18-digit numbers. You
>>>> can try all 9-digit numbers and calculate for all 10^9 combos whether that
>>>> sequence is a 0-child, 1-child, or 2+child. So, all 18-digit numbers of
>>>> 0-child 9-digit numbers and then 1-child 9-digit numbs, or 1-child 9-digit
>>>> numbers then 0-child 9-digit numbers concatenated together would give you a
>>>> 1-child. But that doesn't work: there are new patterns formed which need to
>>>> be accounted for which could generate another 1-child, making the 18-digit
>>>> number no longer a 1-child. I don't see how to detect that without forming
>>>> them.
>>>>
>>> Me too.
>>> And yes, 18 digits are the most problematic by far, but 16 digits would also
>>> took months of single-core compute time with this sort of algorithm.
>>>> I suspect there's a pattern, and that if you take a given divisor (say,
>>>> 18), and form all strings of length 1 through 9, there's a pattern to the
>>>> number of 1-childs for a given length (and we don't see this solving the
>>>> problem directly since the divisor is changing as well as the length). And
>>>> that this pattern results in a formula for 1-childs of 18 digits, something
>>>> like: raw 1-childs for 10^18 - (raw 1-childs for 10^17) - (a few '18' cases
>>>> caused by the extra digit going from 17 to 18 digits).
>>>>
>>>> Kent
>
> 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.

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.

On Sunday, July 11, 2021 at 6:40:14 PM UTC+3, Mike Terry wrote:
> On 09/07/2021 13:52, Michael S wrote:
> > On Thursday, July 8, 2021 at 11:03:08 AM UTC+3, Michael S wrote:
> >> On Wednesday, July 7, 2021 at 2:02:53 AM UTC+3, Michael S wrote:
> >>> On Tuesday, July 6, 2021 at 8:28:02 PM UTC+3, Kent Dickey wrote:
> >>>> In article <c7bfb14a-2084-41c3...@googlegroups.com>,
> >>>> Michael S <already...@yahoo.com> wrote:
> >>>>>
> >>>>> Those are still variations of the theme that I outlined in the post from
> >>>>> Jul 4, 2021, 1:21:16 PM
> >>>>> As proven in the post from Jul 5, 2021, 12:44:48 PM, as far as original
> >>>>> 1=19 digits challenge is concerned, it's a dead end.
> >>>>> In order to tackle the original challenge, the positive (one-child)
> >>>>> results should somehow be discovered and counted in bunches of of at
> >>>>> least thousands (preferably 100s of thousands) rather than one-by-one.
> >>>>> Just rejecting negatives in bunches is not sufficient.
> >>>> I was just posting code I wrote before your posts.
> >>>>
> >>>> I did not see any "proofs", there was a post with some numbers, with no
> >>>> explanation of where they came from or why we should believe it.
> >>> There was an explanation: the numbers are estimates found by Monte Carlo method.
> >>> For each number of digits I tested 1E7 randomly distributed points and extrapolated.
> >>> Later on I repeated the tests with 1E8 point per range and got approximately the same
> >>> result. That is, estimates could be off by few per cents, but it wouldn't change the conclusion:
> >>> the total number of one-child numbers in range 1:1e19 is too huge for any methods that reject
> >>> candidates in bunches but confirm individually.
> >>> Why should you believe it? Because I said so and I tend to be reliable in that sort of things.
> >>> I didn't post the Monte Carlo code here because
> >>> (a) it is trivial, every decent pro has to be able to code something like that in less than 2 hours
> >>> (b) it is coded in C++ and the group is about C.
> >>> I can save it at my github account if wish to see it.
> >>>
> >>> BTW, here are full results:
> >>> 1: 10 / 10 * 10 = 1.000000000000000e+01
> >>> 2: 20 / 90 * 90 = 2.000000000000000e+01
> >>> 3: 360 / 900 * 900 = 3.600000000000000e+02
> >>> 4: 2701 / 9000 * 9000 = 2.701000000000000e+03
> >>> 5: 4096 / 90000 * 90000 = 4.096000000000000e+03
> >>> 6: 109466 / 900000 * 900000 = 1.094660000000000e+05
> >>> 7: 161022 / 9000000 * 9000000 = 1.610220000000000e+05
> >>> 8: 13068583 / 90000000 * 90000000 = 1.306858300000000e+07
> >>> 9: 237707 / 100000000 * 900000000 = 2.139363000000000e+06
> >>> 10: 0 / 100000000 * 9000000000 = 0.000000000000000e+00
> >>> 11: 78609 / 100000000 * 90000000000 = 7.074810000000000e+07
> >>> 12: 6126028 / 100000000 * 900000000000 = 5.513425200000000e+10
> >>> 13: 11791 / 100000000 * 9000000000000 = 1.061190000000000e+09
> >>> 14: 1137562 / 100000000 * 90000000000000 = 1.023805800000000e+12
> >>> 15: 3414651 / 100000000 * 900000000000000 = 3.073185900000000e+13
> >>> 16: 7992302 / 100000000 * 9000000000000000 = 7.193071800000000e+14
> >>> 17: 198 / 100000000 * 90000000000000000 = 1.782000000000000e+11
> >>> 18: 258937 / 100000000 * 900000000000000000 = 2.330433000000000e+15
> >>> 19: 30 / 100000000 * 9000000000000000000 = 2.700000000000000e+12
> >>> Total 3.084430326475721e+15
> >>>> I wrote
> >>>> some code to get some idea if pruning would work--and for some ranges, it's
> >>>> very effective, for other ranges, it's not effective at all. Basically,
> >>>> to see the timing differences for different ranges. My pruning code showed:
> >>>>
> >>>> size runtime factor number of 1-childs
> >>>> 10^6: 0.046 secs = = 116652
> >>>> 10^7: 0.231 secs = 5.02x = 277674
> >>>> 10^8: 5.374 secs = 23.2x = 13346257
> >>>> 10^9: 11.463 secs =2.13x = 15483217
> >>>>
> >>> I have exact results for up to 13 digits.
> >>> Ndigits N-one-childs
> >>> 1 - 10
> >>> 2 - 20
> >>> 3 - 360
> >>> 4 - 2701
> >>> 5 - 4096
> >>> 6 - 109466
> >>> 7 - 161022
> >>> 8 - 13068583
> >>> 9 - 2136960
> >>> 10 - 0
> >>> 11 - 71101800
> >>> 12 - 55121700430
> >>> 13 - 1057516028
> >>> Pay attention, format is slightly different from yours, yours is accumulated, mine is per specific number of digits.
> >>> 12 and 13 digits took relatively long compute time to find - 38min and 57min respectively. i.e. much more than the time allowed by informal rules of the challenge.
> >> Update:
> >> With better code (posted on comp.arch) I managed to brute-force 14 digits.
> >> It took almost 4 hours on a single core, far away from timing requirements of the challenge.
> >> I expect that 17 digits can be ripped in similar time. May be, 19 digits too, not sure about it.
> >> For 15 digits I expect results in 4-5 days.
> >> But ripping 16 or 18 digits with this code will take many months of single-core compute time.
> >> Current results:
> >> 1 - 9
> >> 2 - 20
> >> 3 - 360
> >> 4 - 2701
> >> 5 - 4096
> >> 6 - 109466
> >> 7 - 161022
> >> 8 - 13068583
> >> 9 - 2136960
> >> 10 - 0
> >> 11 - 71101800
> >> 12 - 55121700430
> >> 13 - 1057516028
> >> 14 - 1023436651875
> >> 15 - ???
> >> 16 - ???
> >> 17 - ???
> >> 18 - ???
> >> 19 - ???
> >>>> This shows pruning working very effectively for 10^9. But 8-digit numbers
> >>>> have so many 1-childs, that pruning the negative just doesn't cut out
> >>>> enough work. It needs to do something to count groups of 1-childs positively.
> >>>>
> >> I am starting to get an idea of how to count in bunches.
> >> Still have one algorithmic difficulty to figure out before I start coding.
> >>>> It's easy to brute force the digits through 10^9. However, something happens
> >>>> when the digits are >= 10. I already reported there are no 1-childs when
> >>>> digits == 10.
> >>> Yes, when the fact is know that's relatively easy to understand.
> >>>> The problem changes for digits >= 11 since individual digits
> >>>> can no longer be 1-childs (other than 0). Rather than trying them all, there's
> >>>> a way to show what patterns result in 1-childs (and not 2-childs or 0-childs),
> >>>> and then just counting those patterns. This is not obvious to me and would
> >>>> require a great deal more study, since it seems to revolve around 19-digit
> >>>> numbers and factors of 19 (and 18, etc.).
> >>>>
> >>>> I don't see how to partition this problem easily. Take 18-digit numbers. You
> >>>> can try all 9-digit numbers and calculate for all 10^9 combos whether that
> >>>> sequence is a 0-child, 1-child, or 2+child. So, all 18-digit numbers of
> >>>> 0-child 9-digit numbers and then 1-child 9-digit numbs, or 1-child 9-digit
> >>>> numbers then 0-child 9-digit numbers concatenated together would give you a
> >>>> 1-child. But that doesn't work: there are new patterns formed which need to
> >>>> be accounted for which could generate another 1-child, making the 18-digit
> >>>> number no longer a 1-child. I don't see how to detect that without forming
> >>>> them.
> >>>>
> >>> Me too.
> >>> And yes, 18 digits are the most problematic by far, but 16 digits would also
> >>> took months of single-core compute time with this sort of algorithm.
> >>>> I suspect there's a pattern, and that if you take a given divisor (say,
> >>>> 18), and form all strings of length 1 through 9, there's a pattern to the
> >>>> number of 1-childs for a given length (and we don't see this solving the
> >>>> problem directly since the divisor is changing as well as the length). And
> >>>> that this pattern results in a formula for 1-childs of 18 digits, something
> >>>> like: raw 1-childs for 10^18 - (raw 1-childs for 10^17) - (a few '18' cases
> >>>> caused by the extra digit going from 17 to 18 digits).
> >>>>
> >>>> Kent
> >
> > 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.
> I've also worked out a "solution", and it agrees with your table above.
> I'm not sure it counts, though, as it runs MUCH slower than yours! E.g.
> for the 19-digit calculation it takes around 4 minutes per digit (so
> over an hour for the whole calculation). I have two big tables, which
> are copied, and just copying them (once per digit) takes perhaps 20
> seconds. Well I was being lazy and I don't have to copy them really,
> but anyway that's only 5 mins of the run time, so perhaps my algorithm
> is different from yours. (Or perhaps it's basically the same but there
> are some implementation optimisations I could be using.)
>
>
> Mike.

On 12/07/2021 10:51, Michael S wrote:
> On Sunday, July 11, 2021 at 6:40:14 PM UTC+3, Mike Terry wrote:
>> On 09/07/2021 13:52, Michael S wrote:
<snip>
....
>>>
>>> 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.
>> I've also worked out a "solution", and it agrees with your table above.
>> I'm not sure it counts, though, as it runs MUCH slower than yours! E.g.
>> for the 19-digit calculation it takes around 4 minutes per digit (so
>> over an hour for the whole calculation). I have two big tables, which
>> are copied, and just copying them (once per digit) takes perhaps 20
>> seconds. Well I was being lazy and I don't have to copy them really,
>> but anyway that's only 5 mins of the run time, so perhaps my algorithm
>> is different from yours. (Or perhaps it's basically the same but there
>> are some implementation optimisations I could be using.)
>>
>>
>> Mike.

Right, what you say below is effectively the logic for my solution, but
my implementation was a bit crappy. I was using a number of huge arrays
where you were using associative containers. At the time I thought the
associative containers would be slower than just looping the tables, due
to key searches and (naively?) memory allocations for the nodes.

I had four arrays, each of 3^d entries [d= #digits = divisor], each
entry being an 8 byte counter. So total virtual memory 32 * 3^d bytes.
This was "manageable" up to around d=18 (run time about 5 minutes) with
run times multiplying by 3 as expected for each increment of d, but d=18
exhausted all physical ram (32 G on my laptop, as I like to run several
VMs without suffering) and d=19 went up by a factor of about 40 rather
than 3! Yesterday I checked paging and it had shot up (as you can
imagine), but nowadays that's not immediately obvious as the disk is
solid state. In the old days I would have heared the paging straight
away, and also Windows 10 seems not to mind so much in terms of
impacting other processes - I hadn't really noticed any slowdown for
other processes at the time!

So I've already started to experiment with an associative container to
see how that goes. (I'm thinking I might need a custom allocator(s) to
give "nearly free" allocations per "table". Don't know about that yet...)

>
>
>
> Let's see.
> My solution is based on following observations:
>
> Observations 1.
> When the numbers are split in n-digit prefix and s-digit suffix then the
> amount of 1-child numbers for all possible suffixes of specific prefix depends
> on number of children of prefix itself (0 or 1, obviously all prefixes with 2
> or more children are irrelevant) and on n values of remainder for "right-edge
> facing" substrings, i.e. substrings [1:n], [2:n],.., [n:n].
> All prefixes that have these characteristic sets the same can be processed
> together as a group. For the rest of discussion I would call such set of
> characteristics simply "a key".
> So far, it gives us nothing*, because possible number of keys = 2 * nDigits**n,
> i.e. for "interesting" values of nDigits the exploration space is bigger than
> original space of "raw" prefixes that contains only 10**n elements.
>
> Observations 2.
> The order of remainders in the key does not matter.
> That's the most important step that vastly reduces the keys space and
> increases # of elements in each group.
>
> Observations 3.
> If several remainders in the key have the same value then only the fact
> of repetition matter, but the number of repetitions of given remainder
> does not matter.
> This observation is probably not very important for increasing # of elements in
> the group == reduction of # of groups, but it allows relatively compact and
> convenient representation of the keys as bit patterns of 2*nDigits bits, where
> one half of the bits marks a presence of particular reminders in the set and
> another half of the bits marks remainders that appear more than once.
> Alternatively, one can use even more compact representation on base 3, where
> trit value=0 of means that respective reminder does not appear in the set,
> value=1 means that it appears once and value=2 means that it appears more than
> once. I didn't try this representation, because I feel that for nDigits <= 32
> it would not make calculations faster. I can consider it for nDigits > 32.
> But for nDigits=33 to 36 I can think for few other ideas of compaction and
> nDigits=37 so far looks obviously out of reach, so I could as well not care
> about it.
>
> Observations 4.
> For prefixes with 1 child, as opposed to prefixes with no children, not just
> a number of repetitions of particular reminder does not matter, but even a fact
> of repetition does not matter. So, key representation for this case could be
> shrunk to nDigit bits.
> That observation is new for me, I don't use it yet so do not know how much it
> helps.

OK, that sounds like my thinking, more or less. I iterate along the
string digit by digit, counting the various prefix categories, e.g. for
a string like "1103" mod 4, successive categories for each round would
go like this:

Notation: <abcd> means
d "occurences" of 0 (mod 4)
c "occurences" of 1 (mod 4)
b "occurences" of 2 (mod 4)
a "occurences" of 3 (mod 4)
with a,b,c,d each being 0,1,or 2. I think this is effectively your
"key" (never needing to track a,b,c,d above 2, as more occurences
behave as for 2 occurences)

"1" : <0010>
"11" : <1010>
"110" : <0201> // 1 mod=0 here
"1103" : <0002>

So counting "occurences" for e.g. "110" I'm interested in the
right-to-left suffixes of the string, which happen to be "0", "10",
"110" having mod 4 remainders 0, 2, 2 respectively, hence "one 0, two
2s" : <0201>. This "key" is always enough to calculate the next line
key given the next digit number to add in. (I think that's the key
insight, reducing the space that needs to be tracked...) The "two 2s"
become "two 0s" due to multiplication by 10 (the number base), and then
"two 3s" due to adding digit 3. And the "one 0" also ends up as "one
3", and finally the digit 3 itself gives us "one 3" : total "four 3s"
but saturation reduces this to "two 3s" key <2000>. All the different
ways <0201> might have arisen from various input strings don't matter
when adding the next digit, just <2000> is all the data we need. Oh,
and I track whether or not a previous mod=0 has occured, independently
of each of the keys, so I have two tables which I call "open" and
"closed" string counts, and key counts transfer from the open to the
closed array when a mod=0 occurs. [Straight away there's an
inefficiency in that some of my array entries are never incremented, yet
I still iterate over them. I'm thinking this becomes a non-issue
switching to an associative array.

So there's a kind of "key arrithmetic" going on, with "multiplications
by 10" and "adding new digit", and I might phrase this in my program's
terms as <0201> x 10 + 3 = <0002> but of course that's not regular
integer multiplication and addition...

>
>
> Now to implementation.
> As mentioned in post above, for associative array at the heart of algorithm I
> use ready-made STL container.
> Specifically, I use std::unordered_map. For this particular job unordered_map
> is better than std::map - both a little faster and consumes less memory.
> I use unsigned 64-bit integers both for key (as explained above) and for value
> == number of elements in prefix group. Since # of elements could sometimes
> exceed 2**64, I use a little trick to handle it - numbers in range [0:2**63-1]
> stored directly, while for bigger numbers, which are extremely rare, stored
> as a pointer (actually, index) into secondary storage.
> Originally, I was holding both "current" n-digit groups and "next" (n+1)-digit
> groups in associative arrays, but with such organization on 64GB machine,
> for nDigits=29 at stages of n=14,15,16 I was running out of memory.
> So, in the up-to-date variant of program, at the end of each sub-stage
> associative array is copied to flat array of (key,value) pairs. The later is
> ~2.5 times more compact. Associative array is freed. This process takes some
> time (not a lot) and only reduces peak memory consumption by factor of 1.5, but
> on this particular machine that made a difference between finishing 29 or
> running out of memory (or into swapping, which is unacceptably slow).
>
> There is one more trick in the final version that I borrowed from brute-force
> implementations of last week - the use of small look-up tables for calculation
> of remainder. Unlike in brute-force, in "smart" variants this trick is not a
> major source of speed-up, because majority of time spent in access of
> associative arrays rather than in "inner loop". But when run time is measured
> in hours then even 20% speed-up is welcome.

On 12/07/2021 16:57, Mike Terry wrote:
> On 12/07/2021 10:51, Michael S wrote:
>> On Sunday, July 11, 2021 at 6:40:14 PM UTC+3, Mike Terry wrote:
>>> On 09/07/2021 13:52, Michael S wrote:
> <snip>
> ...
>>>>
>>>> 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.
>>> I've also worked out a "solution", and it agrees with your table above.
>>> I'm not sure it counts, though, as it runs MUCH slower than yours! E.g.
>>> for the 19-digit calculation it takes around 4 minutes per digit (so
>>> over an hour for the whole calculation). I have two big tables, which
>>> are copied, and just copying them (once per digit) takes perhaps 20
>>> seconds. Well I was being lazy and I don't have to copy them really,
>>> but anyway that's only 5 mins of the run time, so perhaps my algorithm
>>> is different from yours. (Or perhaps it's basically the same but there
>>> are some implementation optimisations I could be using.)
>>>
>>>
>>> Mike.
>
> Right, what you say below is effectively the logic for my solution, but
> my implementation was a bit crappy.  I was using a number of huge arrays
> where you were using associative containers.  At the time I thought the
> associative containers would be slower than just looping the tables, due
> to key searches and (naively?) memory allocations for the nodes.
>
> I had four arrays, each of 3^d entries [d= #digits = divisor], each
> entry being an 8 byte counter.  So total virtual memory 32 * 3^d bytes.
> This was "manageable" up to around d=18 (run time about 5 minutes) with
> run times multiplying by 3 as expected for each increment of d, but d=18
> exhausted all physical ram (32 G on my laptop, as I like to run several
> VMs without suffering) and d=19 went up by a factor of about 40 rather
> than 3!  Yesterday I checked paging and it had shot up (as you can
> imagine), but nowadays that's not immediately obvious as the disk is
> solid state.  In the old days I would have heared the paging straight
> away, and also Windows 10 seems not to mind so much in terms of
> impacting other processes - I hadn't really noticed any slowdown for
> other processes at the time!
>
> So I've already started to experiment with an associative container to
> see how that goes.  (I'm thinking I might need a custom allocator(s) to
> give "nearly free" allocations per "table".  Don't know about that yet...)
>
>>
>>
>>
>> Let's see.
>> My solution is based on following observations:
>>
>> Observations 1.
>> When the numbers are split in n-digit prefix and s-digit suffix then the
>> amount of 1-child numbers for all possible suffixes of specific prefix
>> depends
>> on number of children of prefix itself (0 or 1, obviously all prefixes
>> with 2
>> or more children are irrelevant) and on n values of remainder for
>> "right-edge
>> facing" substrings, i.e. substrings [1:n], [2:n],.., [n:n].
>> All prefixes that have these characteristic sets the same can be
>> processed
>> together as a group. For the rest of discussion I would call such set of
>> characteristics simply "a key".
>> So far, it gives us nothing*, because possible number of keys = 2 *
>> nDigits**n,
>> i.e. for "interesting" values of nDigits the exploration space is
>> bigger than
>> original space of "raw" prefixes that contains only 10**n elements.
>>
>> Observations 2.
>> The order of remainders in the key does not matter.
>> That's the most important step that vastly reduces the keys space and
>> increases # of elements in each group.
>>
>> Observations 3.
>> If several remainders in the key have the same value then only the fact
>> of repetition matter, but the number of repetitions of given remainder
>> does not matter.
>> This observation is probably not very important for increasing # of
>> elements in
>> the group == reduction of # of groups, but it allows relatively
>> compact and
>> convenient representation of the keys as bit patterns of 2*nDigits
>> bits, where
>> one half of the bits marks a presence of particular reminders in the
>> set and
>> another half of the bits marks remainders that appear more than once.
>> Alternatively, one can use even more compact representation on base 3,
>> where
>> trit value=0 of means that respective reminder does not appear in the
>> set,
>> value=1 means that it appears once and value=2 means that it appears
>> more than
>> once. I didn't try this representation, because I feel that for
>> nDigits <= 32
>> it would not make calculations faster. I can consider it for nDigits >
>> 32.
>> But for nDigits=33 to 36 I can think for few other ideas of compaction
>> and
>> nDigits=37 so far looks obviously out of reach, so I could as well not
>> care
>> about it.
>>
>> Observations 4.
>> For prefixes with 1 child, as opposed to prefixes with no children,
>> not just
>> a number of repetitions of particular reminder does not matter, but
>> even a fact
>> of repetition does not matter. So, key representation for this case
>> could be
>> shrunk to nDigit bits.
>> That observation is new for me, I don't use it yet so do not know how
>> much it
>> helps.
>
> OK, that sounds like my thinking, more or less.  I iterate along the
> string digit by digit, counting the various prefix categories, e.g. for
> a string like "1103" mod 4, successive categories for each round would
> go like this:
>
>   Notation: <abcd> means
>        d "occurences" of 0 (mod 4)
>        c "occurences" of 1 (mod 4)
>        b "occurences" of 2 (mod 4)
>        a "occurences" of 3 (mod 4)
>   with a,b,c,d each being 0,1,or 2.  I think this is effectively your
>   "key" (never needing to track a,b,c,d above 2, as more occurences
>   behave as for 2 occurences)
>
>   "1"       : <0010>
>   "11"      : <1010>
>   "110"     : <0201>    // 1 mod=0 here
>   "1103"    : <0002>

CORRECTION: "1103" : <2000> as in the following explation, not <0002>.

>
> So counting "occurences" for e.g. "110" I'm interested in the
> right-to-left suffixes of the string, which happen to be "0", "10",
> "110" having mod 4 remainders 0, 2, 2 respectively, hence "one 0, two
> 2s" : <0201>.  This "key" is always enough to calculate the next line
> key given the next digit number to add in.  (I think that's the key
> insight, reducing the space that needs to be tracked...)  The "two 2s"
> become "two 0s" due to multiplication by 10 (the number base), and then
> "two 3s" due to adding digit 3.  And the "one 0" also ends up as "one
> 3", and finally the digit 3 itself gives us "one 3" : total "four 3s"
> but saturation reduces this to "two 3s" key <2000>.  All the different
> ways <0201> might have arisen from various input strings don't matter
> when adding the next digit, just <2000> is all the data we need.  Oh,
> and I track whether or not a previous mod=0 has occured, independently
> of each of the keys, so I have two tables which I call "open" and
> "closed" string counts, and key counts transfer from the open to the
> closed array when a mod=0 occurs.  [Straight away there's an
> inefficiency in that some of my array entries are never incremented, yet
> I still iterate over them.  I'm thinking this becomes a non-issue
> switching to an associative array.
>
> So there's a kind of "key arrithmetic" going on, with "multiplications
> by 10" and "adding new digit", and I might phrase this in my program's
> terms as <0201> x 10 + 3 = <0002> but of course that's not regular
> integer multiplication and addition...
>
>>
>>
>> Now to implementation.
>> As mentioned in post above, for associative array at the heart of
>> algorithm I
>> use ready-made STL container.
>> Specifically, I use std::unordered_map. For this particular job
>> unordered_map
>> is better than std::map - both a little faster and consumes less memory.
>> I use unsigned 64-bit integers both for key (as explained above) and
>> for value
>> == number of elements in prefix group. Since # of elements could
>> sometimes
>> exceed 2**64, I use a little trick to handle it - numbers in range
>> [0:2**63-1]
>> stored directly, while for bigger numbers, which are extremely rare,
>> stored
>> as a pointer (actually, index) into secondary storage.
>> Originally, I was holding both "current" n-digit groups and "next"
>> (n+1)-digit
>> groups in associative arrays, but with such organization on 64GB machine,
>> for nDigits=29 at stages of n=14,15,16 I was running out of memory.
>> So, in the up-to-date variant of  program, at the end of each sub-stage
>> associative array is copied to flat array of (key,value) pairs. The
>> later is
>> ~2.5 times more compact. Associative array is freed. This process
>> takes some
>> time (not a lot) and only reduces peak memory consumption by factor of
>> 1.5, but
>> on this particular machine that made a difference between finishing 29 or
>> running out of memory (or into swapping, which is unacceptably slow).
>>
>> There is one more trick in the final version that I borrowed from
>> brute-force
>> implementations of last week - the use of small look-up tables for
>> calculation
>> of remainder. Unlike in brute-force, in "smart" variants this trick is
>> not a
>> major source of speed-up, because majority of time spent in access of
>> associative arrays rather than in "inner loop". But when run time is
>> measured
>> in hours then even 20% speed-up is welcome.
>
> I haven't "studied" the above, as I'm still thinking about changing my
> own program to use associative arrays, and having got to this point I
> want to get a finished result myself.  My first (working) solution had
> only simple array(s) to track counts for each key (which I call
> "indexes" which seemed natural for use of arrays, LOL) and simply loop
> over the whole array when iterating for the next digit.  So for length 4
> strings I have (naively) 3^4 = 81 keys <abcd> so I had array length 81
> and looped over it 4 times (once for each digit) - well, you can see
> what I was doing, I expect.  I hadn't properly considered how SPARSE
> these arrays would be, which is what I started wondering about yesterday.
>
> Also, I'm worried about memory allocations used by STL containers,
> wondering if I will need a custom allocator... (but I haven't got to
> that point yet as I need to check the unoptimised container logic
> version works as expected, and anyway I'm unsure how it all works with
> different container types.)  Then there are still other implementation
> choices I made with no real thought at the time.  Like I precalculate
> the x10 operation on indexes, thinking this would be needed multiple
> times, but again how SPARSE are my arrays?  As the string length
> increased just iterating once over EVERY key value to calculate the x10
> result might be worse than calculating it only when required.  (Probably
> not the biggest problem I have though as this is just a one-dimension
> loop.)
>
> So I'm going to carry on on my own for a bit as I've become "hooked" by
> the whole thing, and it's more fun than reading Peter Olcott posts. :)
>
> Anyway, thanks for taking the time to explain your implementation
> details - I'll certainly come back to look at them in more detail when I
> get to my own end point...
>
>
> Mike.
>

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.

Michael S <already5chosen@yahoo.com> writes:

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

This is very impressive. Barvo!

I've not looked at your explanation just in case the mood takes me to
have think about this myself, but I am curious abut one thing... Does
your method bring the compute resources for the 1-10^19 case within the
parameters we've been attributing to Project Euler problems -- about a
minute on a moderate home computer? I think you did say, but I can't
find it now. I'm just wondering if the problem setter had some other
scheme in mind...

--
Ben.

On Wednesday, June 30, 2021 at 12:58:29 PM UTC-5, DFS wrote:
> On 6/30/2021 1:03 PM, David Brown wrote:

> I made the fixes you spotted
>
> * initialized cnt to 0
> * free(pss) in the k loop
> * removed the unused char 'ss'
>
>
> and it now works. Thanks man!

Another option to think about for the "free(pss)" part. You might also consider
using `realloc()` for repeated temporary allocations like this. This probably
isn't a drop-in replacement for your specific code, unfortunately. But it's
an alternate strategy that can save some headaches for some patterns of
memory allocation. (Is that enough weasel words yet?)

char *temp_string = NULL;
while(...){
char *allocation = realloc( temp_string, ... );
if( ! allocation ) error_exit( "memory allocation failed" );
temp_string = allocation;
...
} free( temp_string ), temp_string = NULL;

Notes:

`realloc` may fail! Robust code ought to handle this gracefully somehow.
If realloc fails, it will return NULL. So you don't want to assign the result of the
call directly into your nice variable because then you obliterate your pointer
to the old memory. Oh yes! when realloc fails it doesn't free the old one for you.
So if you just assigned it a NULL from realloc() then you just done did a memory
leak.

`realloc` will accept a NULL pointer and work just like malloc() so as long as
your pointer is initialized to NULL then it fits in to this nice pattern where
you don't have to pull your first iteration out of the loop to change it to malloc()
the first time.

You still have to free() at the end, but only once.

My habit is to assign NULL into the pointer in the same statement as calling free().
I feel it collects the two actions together into a coherent unit where they
naturally belong. Other programmers may have different opinions on this point.

On Monday, July 12, 2021 at 11:30:17 PM UTC+3, Ben Bacarisse wrote:
> Michael S <already...@yahoo.com> writes:
>
> ...
> > 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.
> This is very impressive. Barvo!
>
> I've not looked at your explanation just in case the mood takes me to
> have think about this myself, but I am curious abut one thing... Does
> your method bring the compute resources for the 1-10^19 case within the
> parameters we've been attributing to Project Euler problems -- about a
> minute on a moderate home computer? I think you did say, but I can't
> find it now. I'm just wondering if the problem setter had some other
> scheme in mind...
>
> --
> Ben.

Yes, even the very first totally unoptimized (by later standards) variant calculates 1-1e19 in 6s consuming ~20MB of RAM.

Michael S <already5chosen@yahoo.com> writes:

> On Monday, July 12, 2021 at 11:30:17 PM UTC+3, Ben Bacarisse wrote:
>> Michael S <already...@yahoo.com> writes:
>>
>> ...
>> > 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.
>> This is very impressive. Barvo!
>>
>> I've not looked at your explanation just in case the mood takes me to
>> have think about this myself, but I am curious abut one thing... Does
>> your method bring the compute resources for the 1-10^19 case within the
>> parameters we've been attributing to Project Euler problems -- about a
>> minute on a moderate home computer? I think you did say, but I can't
>> find it now. I'm just wondering if the problem setter had some other
>> scheme in mind...
>
> Yes, even the very first totally unoptimized (by later standards)
> variant calculates 1-1e19 in 6s consuming ~20MB of RAM.

Ah, right. Thanks. I think you did say that already.

--
Ben.

On 12/07/2021 16:57, Mike Terry wrote:
> On 12/07/2021 10:51, Michael S wrote:
>> On Sunday, July 11, 2021 at 6:40:14 PM UTC+3, Mike Terry wrote:
>>> On 09/07/2021 13:52, Michael S wrote:
> <snip>
> ...
>>>>
>>>> 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.
>>> I've also worked out a "solution", and it agrees with your table above.
>>> I'm not sure it counts, though, as it runs MUCH slower than yours! E.g.
>>> for the 19-digit calculation it takes around 4 minutes per digit (so
>>> over an hour for the whole calculation). I have two big tables, which
>>> are copied, and just copying them (once per digit) takes perhaps 20
>>> seconds. Well I was being lazy and I don't have to copy them really,
>>> but anyway that's only 5 mins of the run time, so perhaps my algorithm
>>> is different from yours. (Or perhaps it's basically the same but there
>>> are some implementation optimisations I could be using.)
>>>
>>>
>>> Mike.
>
> Right, what you say below is effectively the logic for my solution, but
> my implementation was a bit crappy.  I was using a number of huge arrays
> where you were using associative containers.  At the time I thought the
> associative containers would be slower than just looping the tables, due
> to key searches and (naively?) memory allocations for the nodes.
>
> I had four arrays, each of 3^d entries [d= #digits = divisor], each
> entry being an 8 byte counter.  So total virtual memory 32 * 3^d bytes.
> This was "manageable" up to around d=18 (run time about 5 minutes) with
> run times multiplying by 3 as expected for each increment of d, but d=18
> exhausted all physical ram (32 G on my laptop, as I like to run several
> VMs without suffering) and d=19 went up by a factor of about 40 rather
> than 3!  Yesterday I checked paging and it had shot up (as you can
> imagine), but nowadays that's not immediately obvious as the disk is
> solid state.  In the old days I would have heared the paging straight
> away, and also Windows 10 seems not to mind so much in terms of
> impacting other processes - I hadn't really noticed any slowdown for
> other processes at the time!
>
> So I've already started to experiment with an associative container to
> see how that goes.  (I'm thinking I might need a custom allocator(s) to
> give "nearly free" allocations per "table".  Don't know about that yet...)
>

It turned out (when I got around to it) that the change to using an
associative container was indeed the performance enabler for the
solution - the run time for my code is now around 6 secs, which is good
enough.

I also experimented with a custom allocator to see what kind of
difference it made (and because I hadn't used one before so I just
wanted to see what was involved...). The program was making 4211050
allocations which were ending up in operator new and then malloc().
With a custom allocator (just assigning addresses sequentially from one
big memory buffer, and ignoring deletes) the run time went from 6.78
seconds to 5.17 seconds - down by 34%, but not really relevant for the
problem as it's all way under the 1 minute threshold.

Mike.

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.