On Tuesday, July 6, 2021 at 3:43:03 AM UTC+3, Kent Dickey wrote:
> In article <87a6n0c...@bsb.me.uk>,
> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
> >Michael S <already...@yahoo.com> writes:
> >
> >> On Sunday, July 4, 2021 at 4:01:17 PM UTC+3, Ben Bacarisse wrote:
> >>> Michael S <already...@yahoo.com> writes:
> >>>
> >>> > But the challenge appears to suggest that it should be done in 1
> >>> > minute of compute time. So far, I didn't figure out how to do it so
> >>> > quickly.
> >>> No, me neither. And I'm not usually drawn to problems that use an
> >>> arbitrary base (my code had a base argument in case there was something
> >>> interesting about other bases) so I've not given it much thought. But I
> >>> admit to be being intrigued now.
> >>>
> >>
> >> I did something that I should have do from the beginning - estimate of
> >> result by Monte Carlo method (with 10M random samples per range).
> >> Estimate = 3.1e15, majority of it in 18-digit and 16-digit ranges.
> >> 3.1e15 * 1 nsec = 35 days. It means that algorithms that are based on
> >> examination of each and every results are hopeless even if preliminary
> >> filtering before examination is near-perfect and final examination is
> >> blazingly fast.
> >
> >Interesting. Thanks.
> >
> >--
> >Ben.
> I wrote 2 programs to try to calculate this.
>
> First, there's no nead to atoi/sprintf or whatever. Just do operations
> on an array of bytes, and form the numbers with num = (num * 10) + dig
> as needed. I'll attach my initial code to show the basic idea.
>
> My main idea was to do exclusion based on initial digits. If the first
> five digits (for an example) of an 11-digit number have two children,
> then we don't need to look at any more of the remaining 6 digits: we can skip
> them all with next = cur + (10^6).
>
> I've gotten through 10^10. All 10-digit numbers have no one-childs (I didn't
> realize this until the code finished). Let's say the number is 1234567890..
> This has the number 0 and 90 (and others) which are multiples of 10, so no
> one child. To be divisible by 10, we need exactly one digit to be 0. But then
> we have 0 and some multiple of 10 due to the previous digit--so no one-childs.
> So code should just skip all 10-digit numbers.
>
> My next idea was to pre-calc for each digit length (as we move to 11 digit
> numbers, calculate using a divisor of 11, for example), pre-calculate the
> children for all 6 digit numbers from 000000 to 999999 using that length
> divisor. Use this for initial prunings, and to avoid doing any checking
> of 1-to-5 digit numbers (it's all rolled up). We need just 3 answers (2 bis)
> of info per numbers: 0 children, 1 child, 2+ children. It's probably not worth
> it to pack 4 results per byte, but maybe it is. Code still must check 7+
> digit sequences with divides, but this takes away a lot of work.
>
> So, 1-8 digit numbers took 5 seconds. 1-9 digit numbers took 11 seconds--
> so just over twice as long.
>
> Here's the basic code:
>
> // See https://projecteuler.net/problem=413
>
> #include <stdio.h>
> #include <stdlib.h>
>
> typedef unsigned long long dword64;
> typedef unsigned int word32;
> typedef unsigned char byte;
>
> int
> calc_one_child(byte *bptr, int len)
> {
> dword64 num, div_val, div;
> int num_divs;
> int i, thislen, j;
>
> div_val = len;
> num_divs = 0;
> #if 0
> printf("calc_one_child, len:%d, value:%d%d%d%d\n", len,
> bptr[3], bptr[2], bptr[1], bptr[0]);
> #endif
> for(i = len - 1; i >= 0; i--) {
> // printf("i:%d\n", i);
> for(thislen = 1; thislen <= (i+1); thislen++) {
> num = 0;
> for(j = 0; j < thislen; j++) {
> num = (num * 10) + bptr[i - j];
> // printf(" this_len:%d, j:%d\n", thislen, j);
> }
> div = num / div_val;
> if((div * div_val) == num) {
> num_divs++;
> #if 0
> printf("num:%d is divisible by %d\n", num,
> div_val);
> #endif
> if(num_divs >= 2) {
> return num_divs;
> }
> }
> }
> }
> return num_divs;
> }
>
> int
> main(int argc, char **argv)
> {
> byte array[20];
> dword64 dstart, dend, dtmp, dcount, dstart_save;
> int len, ret;
> int i;
>
> if(argc < 3) {
> fprintf(stderr, "Usage: %s start end\n", argv[0]);
> exit(1);
> }
> dstart = strtoll(argv[1], 0, 0);
> dstart_save = dstart;
> dend = strtoll(argv[2], 0, 0);
> for(i = 0; i < 20; i++) {
> array[i] = 0;
> }
> dtmp = dstart;
> len = 0;
> for(i = 0; i < 20; i++) {
> array[i] = dtmp % 10;
> dtmp = dtmp / 10;
> if(dtmp == 0) {
> len = i + 1;
> break;
> }
> }
> printf("len: %d\n", len);
>
> dcount = 0;
> while(dstart < dend) {
> ret = calc_one_child(&array[0], len);
> if(ret == 1) {
> // printf("%lld is a one-child\n", dstart);
> dcount++;
> }
> dstart++;
> for(i = 0; i < 20; i++) {
> array[i]++;
> if(array[i] < 10) {
> break;
> }
> array[i] = 0;
> if(len < (i + 2)) {
> len = i + 2;
> }
> }
> }
> printf("One-child between %lld and %lld = %lld\n", dstart_save, dend,
> dcount);
> }
>
> And here's the code with some pruning ability (it forms the numbers more
> efficiently, which save about 20% as well):
>
> // See https://projecteuler.net/problem=413
>
> #include <stdio.h>
> #include <stdlib.h>
>
> typedef unsigned long long dword64;
> typedef unsigned int word32;
> typedef unsigned char byte;
>
> #define DO_PRINT 0
>
> int
> calc_one_child(byte *bptr, int len)
> {
> dword64 num, div_val, div, mul;
> int num_divs;
> int i, j;
>
> div_val = len;
> num_divs = 0;
> #if DO_PRINT
> printf("calc_one_child, len:%d, value:%d%d%d%d\n", len,
> bptr[3], bptr[2], bptr[1], bptr[0]);
> #endif
> for(i = len - 1; i >= 0; i--) {
> // This is the 'end' digit, look to higher MSBs
> #if DO_PRINT
> printf("i:%d\n", i);
> #endif
> num = 0;
> mul = 1;
> for(j = i; j < len; j++) {
> num = num + (bptr[j] * mul);
> mul = mul * 10;
> div = num / div_val;
> #if DO_PRINT
> printf("j:%d %lld / %lld = %lld\n", j,
> num, div_val, div);
> #endif
> if((div * div_val) == num) {
> num_divs++;
> #if DO_PRINT
> printf("num:%lld is divisible by %lld\n",
> (dword64)num, (dword64)div_val);
> #endif
> if(num_divs >= 2) {
> return i;
> }
> }
> }
> }
> return -num_divs; // 1->-1, 0->0
> }
>
> int
> main(int argc, char **argv)
> {
> byte array[20];
> dword64 dstart, dend, dtmp, dcount, dstart_save, dinc;
> int len, ret;
> int i;
>
> if(argc < 3) {
> fprintf(stderr, "Usage: %s start end\n", argv[0]);
> exit(1);
> }
> dstart = strtoll(argv[1], 0, 0);
> dstart_save = dstart;
> dend = strtoll(argv[2], 0, 0);
> for(i = 0; i < 20; i++) {
> array[i] = 0;
> }
> dtmp = dstart;
> len = 0;
> for(i = 0; i < 20; i++) {
> array[i] = dtmp % 10;
> dtmp = dtmp / 10;
> if(dtmp == 0) {
> len = i + 1;
> break;
> }
> }
> printf("len: %d\n", len);
>
> dcount = 0;
> while(dstart < dend) {
> ret = calc_one_child(&array[0], len);
> if(ret < 0) {
> #if DO_PRINT
> printf("%lld is a one-child\n", dstart);
> #endif
> dcount++;
> ret = 0;
> }
> dinc = 1;
> for(i = 0; i < ret; i++) {
> array[i] = 0;
> dinc = dinc * 10;
> }
> dstart += dinc;
> for(; i < 20; i++) {
> array[i]++;
> if(array[i] < 10) {
> break;
> }
> array[i] = 0;
> if(len < (i + 2)) {
> len = i + 2;
> }
> }
> }
> printf("One-child between %lld and %lld = %lld\n", dstart_save, dend,
> dcount);
> }

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.