On 02/07/2021 16:52, DFS wrote:
> On 7/1/2021 4:46 AM, David Brown wrote:
>> On 30/06/2021 19:58, DFS wrote:
>
>
>
>> At the very least, paste your code into <https://godbolt.org> and use
>> "gcc -O2 -Wall -Wextra" there.
>
>
> Incredible site - thanks for the link.
>
>
> -Wall -Wextra is pretty strict.  It even warned of unused 'argc' from
> main().
>
>
>
>> There are many things that can affect performance, and Python can be
>> surprisingly efficient at times.  It's fun to try this kind of thing and
>> see how you can improve the speeds.  (You could try pypy, for example.)
>
> I saw Bart tried pypy and got good results.  I tried pypy3 on the below
> and got a 13.8x speed increase over python for F(10^6) and F(10^7).
>
>
>
>>> ================================================================
>>> import sys
>>> start = int(sys.argv[1])
>>> end   = int(sys.argv[2])
>>> div,ocn = 0,0
>>> for i in range(start,end+1):
>>>      istr = str(i)
>>>      ilen = len(istr)
>>>      for j in range(0,ilen):
>>>          for k in range(j+1,ilen+1):
>>>              if int(istr[j:k]) % ilen == 0:
>>>                  div+=1
>>>      if div == 1: ocn+=1
>>>      div = 0
>>> print("\n%d one-child numbers from %d to %d" % (ocn,start,end))
>>> ================================================================
>>>
>>
>

I created my own script version, which got ported to C (see my recent
post), but I also converted it to this Python:

----------------------------------
def onechild(n):
s=str(n)
slen=len(s)

count = (n%slen)==0

for w in range(slen-1):
for i in range(slen-w):
m=int(s[i:i+w+1])
if (m%slen)==0:
count+=1
if count>1: return 0

if count==1: return 1
return 0

n=10_000_000
count=0

for i in range(1,n):
count+=onechild(i)

print("F(",n,") =",count)

----------------------------------

This took the same time as gcc-O3, 9.4 seconds, using PyPy (89 seconds
with CPython).

(Annoyingly, my script interpreter, which is not JITed, took 37 seconds.
But PyPy /does/ love loops with long iterations; it's its thing.

I like interesting new benchmarks, but with ones like this with just one
obvious bottleneck, it's hard to beat tracing JITs when implementing
dynamic bytecode.)

On Friday, July 2, 2021 at 5:49:01 PM UTC+3, Michael S wrote:
> On Friday, July 2, 2021 at 4:44:33 PM UTC+3, Ben Bacarisse wrote:
> > Michael S <already...@yahoo.com> writes:
> >
> > > On Thursday, July 1, 2021 at 12:38:21 PM UTC+3, Ben Bacarisse wrote:
> > >> DFS <nos...@dfs.com> writes:
> > >>
> > >> > On 6/30/2021 7:03 PM, Ben Bacarisse wrote:
> > >> >> DFS <nos...@dfs.com> writes:
> > >> >>
> > >> >>> On 6/30/2021 2:44 PM, Bart wrote:
> > >> >> <cut>
> > >> >>>> But I suspect that in all cases, what is dominant is the conversion
> > >> >>>> from int to text, from text back to int, and applying the mod
> > >> >>>> operator. All things that happen outside of the code generated from
> > >> >>>> your source.
> > >> >>>
> > >> >>> I don't understand 'happen outside'.
> > >> >> I think he means that your calls to atoi are doing most of the work, so
> > >> >> you can't get much more speed from tinkering with the code you actually
> > >> >> wrote.
> > >> >> That's not quite right in that you can get a good speed-up by not
> > >> >> generating all those sub-strings. You already have the full number in
> > >> >> 's' so you can get sub-string numbers by doing this:
> > >> >> char save = s[j+k];
> > >> >> s[j+k] = 0;
> > >> >> ssnbr = atoi(s+j);
> > >> >> s[j+k] = save;
> > >> >
> > >> > Geez, that block means less code overall, and the prog runs
> > >> > significantly faster. Where do you mad geniuses come from?
> > >> Actually there is no genius involved (IMO). It's mostly the result of
> > >> having written and (possibly more importantly) read code for more than
> > >> 40 years. You pick up stuff along the way.
> > >> >> Having said that, Bart's point still holds. This can be seen as a
> > >> >> purely arithmetical problem. There is no need for strings conversions
> > >> >> (and hence atoi) at all. Whether that would make the code faster is not
> > >> >> obvious, but I suspect it might. I've not have time to try it.
> > >> >
> > >> > Careful of gotchas. These are all the substrings of 104, including
> > >> > the leading-zero dropped '04':
> > >> Whether that's a gotcha or not depends on how you tackle the problem.
> > >>
> > >> I've written an arithmetic version (i.e. no strings) and it is
> > >> significantly faster again.
> > >
> > > Does it include replacement of division by reciprocal multiplication?
> > No, it's a plain integer / and % version. Have you got one that does
> > something clever with the divisions?
> >
> > --
> > Ben.
> No, I didn't.
> Have more interesting things to do.
> Besides, brute force is so obvious dead end...

Just to prove to myself that brute force is dead end
Here is rather clever brute force.
It does 1e9 in 26 sec on my aging home PC (i5-3450).

#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>

static bool isOneChild(const uint8_t *digits, int nDigits, const uint8_t *remTab)
{ int nChilds = 0;
for (int beg = 0; beg < nDigits; ++beg) {
unsigned r = 0;
for (int end = beg; end < nDigits; ++end) {
r = remTab[r*10+digits[end]];
if (r == 0) {
++nChilds;
}
}
if (nChilds > 1)
return false;
}
return nChilds == 1;
}

static unsigned long long countOneChildsInRange(uint64_t first, uint64_t last, int nDigits, bool print)
{ // initialize look-up table
uint8_t remTab[200];
for (int i = 0; i < nDigits*10; ++i)
remTab[i] = i % nDigits;

// initialize array of digits
uint8_t digits[20];
uint64_t x = first;
for (int i = 0; i < nDigits; ++i) {
digits[nDigits-1-i] = x % 10;
x /= 10;
}

unsigned long long cnt = 0;
for (x = first; x <= last; ++x) {
if (isOneChild(digits, nDigits, remTab)) {
++cnt;
if (print)
printf("%llu\n", (unsigned long long)x);
}
uint8_t lsDig = digits[nDigits-1] + 1;
digits[nDigits-1] = lsDig;
if (lsDig == 10) {
digits[nDigits-1] = 0;
for (int i = nDigits-2; i >= 0; --i) {
uint8_t d = digits[i] + 1;
if (d == 10) {
digits[i] = 0;
} else {
digits[i] = d;
break;
}
}
lsDig = 0;
}
}
return cnt;
}

int count_digits(unsigned long long x)
{ int c = 0;
while (x) {
++c;
x /= 10;
}
return c;
}

unsigned long long ndig_max(int nDigits)
{ unsigned long long x = 1;
for (int i = 0; i < nDigits; ++i)
x *= 10;
return x - 1;
}

int main(int argz, char** argv)
{ if (argz < 3) {
fprintf(stderr, "Consult DFS!\n");
return 1;
}

char* endp;
unsigned long long first = strtoull(argv[1], &endp, 0);
if (endp == argv[1]) {
fprintf(stderr, "%s is not a number.\n", argv[1]);
return 1;
}

unsigned long long last = strtoull(argv[2], &endp, 0);
if (endp == argv[2]) {
fprintf(stderr, "%s is not a number.\n", argv[2]);
return 1;
}

bool print = false;
if (argz > 3 && argv[3][0]=='p')
print = true;

unsigned long long cnt = 0;
while (first <= last) {
int nDigits = count_digits(first);
unsigned long long rangeLast = ndig_max(nDigits);
if (rangeLast > last)
rangeLast = last;
cnt += countOneChildsInRange(first, rangeLast, nDigits, print);
first = rangeLast + 1;
}
printf("Found %llu one-childs\n", cnt);

return 0;
}

On 7/2/2021 12:16 PM, Bart wrote:

> I created my own script version, which got ported to C (see my recent
> post), but I also converted it to this Python:
>
> ----------------------------------
> def onechild(n):
>     s=str(n)
>     slen=len(s)
>
>     count = (n%slen)==0
>
>     for w in range(slen-1):
>         for i in range(slen-w):
>             m=int(s[i:i+w+1])
>             if (m%slen)==0:
>                 count+=1
>                 if count>1: return 0
>
>     if count==1: return 1
>     return 0
>
> n=10_000_000
> count=0
>
> for i in range(1,n):
>     count+=onechild(i)
>
> print("F(",n,") =",count)
>
> ----------------------------------
>
> This took the same time as gcc-O3, 9.4 seconds, using PyPy (89 seconds
> with CPython).

F(10^7) 7.2s here, with pypy3.
F(10^8) 86.2S

(old system i5-750@2.67GHz)

> (Annoyingly, my script interpreter, which is not JITed, took 37 seconds.
> But PyPy /does/ love loops with long iterations; it's its thing.
>
> I like interesting new benchmarks, but with ones like this with just one
> obvious bottleneck, it's hard to beat tracing JITs when implementing
> dynamic bytecode.)

The pypy people have done a remarkable job in speeding up python code.

The pypy interpreter itself looks to have been written in python
https://downloads.python.org/pypy/pypy3.7-v7.3.5-src.tar.bz2

https://www.pypy.org/people.html

On 02/07/2021 17:25, Michael S wrote:
> On Friday, July 2, 2021 at 5:49:01 PM UTC+3, Michael S wrote:
>> On Friday, July 2, 2021 at 4:44:33 PM UTC+3, Ben Bacarisse wrote:

>>>> Does it include replacement of division by reciprocal multiplication?
>>> No, it's a plain integer / and % version. Have you got one that does
>>> something clever with the divisions?
>>>
>>> --
>>> Ben.
>> No, I didn't.
>> Have more interesting things to do.
>> Besides, brute force is so obvious dead end...
>
>
> Just to prove to myself that brute force is dead end
> Here is rather clever brute force.
> It does 1e9 in 26 sec on my aging home PC (i5-3450).
>
> #include <stdint.h>
> #include <stdbool.h>
> #include <stdlib.h>
> #include <stdio.h>
>
> static bool isOneChild(const uint8_t *digits, int nDigits, const uint8_t *remTab)
> {
> int nChilds = 0;
> for (int beg = 0; beg < nDigits; ++beg) {
> unsigned r = 0;
> for (int end = beg; end < nDigits; ++end) {
> r = remTab[r*10+digits[end]];
> if (r == 0) {
> ++nChilds;
> }
> }
> if (nChilds > 1)
> return false;
> }
> return nChilds == 1;
> }
>
> static unsigned long long countOneChildsInRange(uint64_t first, uint64_t last, int nDigits, bool print)
> {
> // initialize look-up table
> uint8_t remTab[200];
> for (int i = 0; i < nDigits*10; ++i)
> remTab[i] = i % nDigits;
>
> // initialize array of digits
> uint8_t digits[20];
> uint64_t x = first;
> for (int i = 0; i < nDigits; ++i) {
> digits[nDigits-1-i] = x % 10;
> x /= 10;
> }
>
> unsigned long long cnt = 0;
> for (x = first; x <= last; ++x) {
> if (isOneChild(digits, nDigits, remTab)) {
> ++cnt;
> if (print)
> printf("%llu\n", (unsigned long long)x);
> }
> uint8_t lsDig = digits[nDigits-1] + 1;
> digits[nDigits-1] = lsDig;
> if (lsDig == 10) {
> digits[nDigits-1] = 0;
> for (int i = nDigits-2; i >= 0; --i) {
> uint8_t d = digits[i] + 1;
> if (d == 10) {
> digits[i] = 0;
> } else {
> digits[i] = d;
> break;
> }
> }
> lsDig = 0;
> }
> }
> return cnt;
> }
>
> int count_digits(unsigned long long x)
> {
> int c = 0;
> while (x) {
> ++c;
> x /= 10;
> }
> return c;
> }
>
> unsigned long long ndig_max(int nDigits)
> {
> unsigned long long x = 1;
> for (int i = 0; i < nDigits; ++i)
> x *= 10;
> return x - 1;
> }
>
> int main(int argz, char** argv)
> {
> if (argz < 3) {
> fprintf(stderr, "Consult DFS!\n");
> return 1;
> }
>
> char* endp;
> unsigned long long first = strtoull(argv[1], &endp, 0);
> if (endp == argv[1]) {
> fprintf(stderr, "%s is not a number.\n", argv[1]);
> return 1;
> }
>
> unsigned long long last = strtoull(argv[2], &endp, 0);
> if (endp == argv[2]) {
> fprintf(stderr, "%s is not a number.\n", argv[2]);
> return 1;
> }
>
> bool print = false;
> if (argz > 3 && argv[3][0]=='p')
> print = true;
>
> unsigned long long cnt = 0;
> while (first <= last) {
> int nDigits = count_digits(first);
> unsigned long long rangeLast = ndig_max(nDigits);
> if (rangeLast > last)
> rangeLast = last;
> cnt += countOneChildsInRange(first, rangeLast, nDigits, print);
> first = rangeLast + 1;
> }
> printf("Found %llu one-childs\n", cnt);
>
> return 0;
> }

Well, it's fast (about 65 seconds on my machine, perhaps 20 times as
fast as my program). But I can't say it's that easy to follow!

It seems to rely on the fact that consecutive numbers are being tested,
so can optimise blocks all having the same numbers of digits. (Exactly
how, I don't know yet.)

So I guess it can't be used to get the one-child status of an arbitrary
number. That's probably the only advantage of the simpler algorithm,
other than being simpler.

On 2021-07-02, Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> DFS <nospam@dfs.com> writes:
>
>> Not bad numbers for python and F(10^7), but this code is part of me
>> trying to solve Project Euler 413, which asks for F(10^19).
>
> I didn't know that. As you say, a different algorithm is called for.
>
> (My best naive version gets F(10^9) in 4m21.489s and F(10^7) in 2.177s.)

The obvious thing here is to encode custom divisibility tests for
d = [1,19].

For certain divisors, we can test divisibility on the base 10
representation without converting to integer. It's a waste of
time to convert "1235" into 1235 to test it for divisibility by 5,
when we just have to apply the condition "last digit is 0 or 5".

Moreover, in the d=5 case, we can short-circuit to an answer
for each five-digit number. It's a one-child if it starts with 5.
and doesn't contain 0 or any other 5.

int onechild_d5(char *num)
{
return num[0] == '5' && strpbrk(num + 1, "05") == 0;
}

Proof:

1. If the number contains a 5 or 0 in any position other than the first,
then it has at least two substrings divisible by 5: that 0 or 5 itself,
plus strings terminating in that 0 or 5. Therefore, the one-child number
doesn't have a 5 or 0 in any position other than first.

2. A number cannot have leading zeros under the rules, therefore a
one-child number doesn't have a 0 in the first position.

3. The one-child number for d = 5 must have a 0 or 5 somewhere;
therefore it must have a 5 in the first position.

I would write onechild_d1 through onechild_d19 functions, stuffing
them with d-specific shortcuts. Put them into a table, and then
drive them with a main program that does this:

int d;
long long one_child_count;

for (oc = 0, d = 1; d <= 19; d++) {
char n[20];

/* generate d-digit number in n,
stepping it from 100...000 to 99999. */

oc += (octab[d](n) != 0);
}

Incrementing n textually might be faster than repeated sprintfs. So that
is to say, for a given d, we fill the buffer n with:

"10000000" // 1 followed by d-1 zeros

Then we increment textually. We maintain a pointer to the last digit.
If it is '9', we set it to zero, and increment the next digit, otherwise
we increment it.

Dollars to doughnuts says this will beat sprintf because there are no
divisions by ten going on.

The next level of optimization would be to leave the child counting
to the d-specific routines:

/* return number of one-child five-digit numbers */
long long onechild_count_d5(void)
{
/* All these are of the form 5nnnn where the nnnn part
does not contain 0 or 5 anywhere. */

/* In other words, the number of combinations of the 8 digits
1-4, 6-9. */

return 8 * 8 * 8 * 8;
}

This is just an example; I don't mean to insinuate that optimizing d = 5
makes a significant difference if you're going after F(10**19).

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

Kaz Kylheku <563-365-8930@kylheku.com> writes:

> On 2021-07-02, Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>> DFS <nospam@dfs.com> writes:
>>
>>> Not bad numbers for python and F(10^7), but this code is part of me
>>> trying to solve Project Euler 413, which asks for F(10^19).
>>
>> I didn't know that. As you say, a different algorithm is called for.
>>
>> (My best naive version gets F(10^9) in 4m21.489s and F(10^7) in 2.177s.)
>
> The obvious thing here is to encode custom divisibility tests for
> d = [1,19].
>
> For certain divisors, we can test divisibility on the base 10
> representation without converting to integer. It's a waste of
> time to convert "1235" into 1235 to test it for divisibility by 5,
> when we just have to apply the condition "last digit is 0 or 5".

In the "arithmetic" versions, there are no strings.

> Moreover, in the d=5 case, we can short-circuit to an answer
> for each five-digit number. It's a one-child if it starts with 5.
> and doesn't contain 0 or any other 5.

Yes, there are various opportunities for short-circuiting many cases. I
wonder if that's enough to make 10^19 tractable.

Also, problems like this are supposed to be satisfying, and
special-casing sub-string divisibility for lots of different lengths
does not meet that criterion (in my view).
>
> int onechild_d5(char *num)
> {
> return num[0] == '5' && strpbrk(num + 1, "05") == 0;
> }
>
> Proof:
>
> 1. If the number contains a 5 or 0 in any position other than the first,
> then it has at least two substrings divisible by 5: that 0 or 5 itself,
> plus strings terminating in that 0 or 5. Therefore, the one-child number
> doesn't have a 5 or 0 in any position other than first.
>
> 2. A number cannot have leading zeros under the rules, therefore a
> one-child number doesn't have a 0 in the first position.
>
> 3. The one-child number for d = 5 must have a 0 or 5 somewhere;
> therefore it must have a 5 in the first position.
>
> I would write onechild_d1 through onechild_d19 functions, stuffing
> them with d-specific shortcuts. Put them into a table, and then
> drive them with a main program that does this:
>
> int d;
> long long one_child_count;
>
> for (oc = 0, d = 1; d <= 19; d++) {
> char n[20];
>
> /* generate d-digit number in n,
> stepping it from 100...000 to 99999. */
>
> oc += (octab[d](n) != 0);
> }
>
> Incrementing n textually might be faster than repeated sprintfs. So that
> is to say, for a given d, we fill the buffer n with:
>
> "10000000" // 1 followed by d-1 zeros
>
> Then we increment textually. We maintain a pointer to the last digit.
> If it is '9', we set it to zero, and increment the next digit, otherwise
> we increment it.
>
> Dollars to doughnuts says this will beat sprintf because there are no
> divisions by ten going on.

If you wanted to use the string representation then stepping is surely
going to be a win. Mind you, I'd use digit values rather that ASCII
0-9. Maybe that's what you were thinking anyway.

--
Ben.

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Kaz Kylheku <563-365-8930@kylheku.com> writes:

>> Dollars to doughnuts says this will beat sprintf because there are no
>> divisions by ten going on.
>
> If you wanted to use the string representation then stepping is surely
> going to be a win. Mind you, I'd use digit values rather that ASCII
> 0-9. Maybe that's what you were thinking anyway.

But neither stepping digits or running a counter can possibly get you to
10**19 in reasonable time. I estimate that, on laptop, just running a
loop from 1 to 10**19 will take more than 130 years.

--
Ben.

On Friday, July 2, 2021 at 8:34:16 PM UTC+3, Bart wrote:
> On 02/07/2021 17:25, Michael S wrote:
> > On Friday, July 2, 2021 at 5:49:01 PM UTC+3, Michael S wrote:
> >> On Friday, July 2, 2021 at 4:44:33 PM UTC+3, Ben Bacarisse wrote:
>
> >>>> Does it include replacement of division by reciprocal multiplication?
> >>> No, it's a plain integer / and % version. Have you got one that does
> >>> something clever with the divisions?
> >>>
> >>> --
> >>> Ben.
> >> No, I didn't.
> >> Have more interesting things to do.
> >> Besides, brute force is so obvious dead end...
> >
> >
> > Just to prove to myself that brute force is dead end
> > Here is rather clever brute force.
> > It does 1e9 in 26 sec on my aging home PC (i5-3450).
> >
> > #include <stdint.h>
> > #include <stdbool.h>
> > #include <stdlib.h>
> > #include <stdio.h>
> >
> > static bool isOneChild(const uint8_t *digits, int nDigits, const uint8_t *remTab)
> > {
> > int nChilds = 0;
> > for (int beg = 0; beg < nDigits; ++beg) {
> > unsigned r = 0;
> > for (int end = beg; end < nDigits; ++end) {
> > r = remTab[r*10+digits[end]];
> > if (r == 0) {
> > ++nChilds;
> > }
> > }
> > if (nChilds > 1)
> > return false;
> > }
> > return nChilds == 1;
> > }
> >
> > static unsigned long long countOneChildsInRange(uint64_t first, uint64_t last, int nDigits, bool print)
> > {
> > // initialize look-up table
> > uint8_t remTab[200];
> > for (int i = 0; i < nDigits*10; ++i)
> > remTab[i] = i % nDigits;
> >
> > // initialize array of digits
> > uint8_t digits[20];
> > uint64_t x = first;
> > for (int i = 0; i < nDigits; ++i) {
> > digits[nDigits-1-i] = x % 10;
> > x /= 10;
> > }
> >
> > unsigned long long cnt = 0;
> > for (x = first; x <= last; ++x) {
> > if (isOneChild(digits, nDigits, remTab)) {
> > ++cnt;
> > if (print)
> > printf("%llu\n", (unsigned long long)x);
> > }
> > uint8_t lsDig = digits[nDigits-1] + 1;
> > digits[nDigits-1] = lsDig;
> > if (lsDig == 10) {
> > digits[nDigits-1] = 0;
> > for (int i = nDigits-2; i >= 0; --i) {
> > uint8_t d = digits[i] + 1;
> > if (d == 10) {
> > digits[i] = 0;
> > } else {
> > digits[i] = d;
> > break;
> > }
> > }
> > lsDig = 0;
> > }
> > }
> > return cnt;
> > }
> >
> > int count_digits(unsigned long long x)
> > {
> > int c = 0;
> > while (x) {
> > ++c;
> > x /= 10;
> > }
> > return c;
> > }
> >
> > unsigned long long ndig_max(int nDigits)
> > {
> > unsigned long long x = 1;
> > for (int i = 0; i < nDigits; ++i)
> > x *= 10;
> > return x - 1;
> > }
> >
> > int main(int argz, char** argv)
> > {
> > if (argz < 3) {
> > fprintf(stderr, "Consult DFS!\n");
> > return 1;
> > }
> >
> > char* endp;
> > unsigned long long first = strtoull(argv[1], &endp, 0);
> > if (endp == argv[1]) {
> > fprintf(stderr, "%s is not a number.\n", argv[1]);
> > return 1;
> > }
> >
> > unsigned long long last = strtoull(argv[2], &endp, 0);
> > if (endp == argv[2]) {
> > fprintf(stderr, "%s is not a number.\n", argv[2]);
> > return 1;
> > }
> >
> > bool print = false;
> > if (argz > 3 && argv[3][0]=='p')
> > print = true;
> >
> > unsigned long long cnt = 0;
> > while (first <= last) {
> > int nDigits = count_digits(first);
> > unsigned long long rangeLast = ndig_max(nDigits);
> > if (rangeLast > last)
> > rangeLast = last;
> > cnt += countOneChildsInRange(first, rangeLast, nDigits, print);
> > first = rangeLast + 1;
> > }
> > printf("Found %llu one-childs\n", cnt);
> >
> > return 0;
> > }
> Well, it's fast (about 65 seconds on my machine,

Your ability to enjoy slow PCs does not surprise me any more.

> perhaps 20 times as
> fast as my program).

If your program uses strings then only 20 times is a little disappointing.

> But I can't say it's that easy to follow!

Because I wrote it for myself, as a one time exercise and put in virtually no comments.
Still, even in commentless state, it's likely easier to follow for most people than
the code of DFS that started this thread.

>
> It seems to rely on the fact that consecutive numbers are being tested,
> so can optimise blocks all having the same numbers of digits. (Exactly
> how, I don't know yet.)
>
> So I guess it can't be used to get the one-child status of an arbitrary
> number.

It can. It just would be much slower at that then function built for a purpose of
examining a single number. But, I'd guess, even in this scenario it would be within
factor of 3-5 from the best speed achievable with atoi()/strtoull().

> That's probably the only advantage of the simpler algorithm,
> other than being simpler.

I did a simple "pure arithmetic" variant as well. It's really quite short and is closer to an ideal
of mindless brute force. It ended up ~7 times slower than the variant presented above which
is not that bad relatively to speed reported by other posters. Something like 1.5 times faster than
Ben's.

But utility of "mindless brute force" in this challenge is not to be fast, but too look fast and be slow,
in order to convince people that the challenge can't be solved on this path.

On Friday, July 2, 2021 at 9:48:30 PM UTC+3, Ben Bacarisse wrote:
> Ben Bacarisse <ben.u...@bsb.me.uk> writes:
> > Kaz Kylheku <563-36...@kylheku.com> writes:
>
> >> Dollars to doughnuts says this will beat sprintf because there are no
> >> divisions by ten going on.
> >
> > If you wanted to use the string representation then stepping is surely
> > going to be a win. Mind you, I'd use digit values rather that ASCII
> > 0-9. Maybe that's what you were thinking anyway.
> But neither stepping digits or running a counter can possibly get you to
> 10**19 in reasonable time. I estimate that, on laptop, just running a
> loop from 1 to 10**19 will take more than 130 years.
>
> --
> Ben.

I think that given ~10 GB of RAM I know how to solve it in approximately 300 core*months, which is borderline doable.
The idea is that, for the hardest case of 19 digits there are 32609741 9-digit strings with no children,
145677482 10-digit strings with no children, 173961837 9-digit strings with one child
and 1044700906 10-digit strings with one child. We can keep all those strings in memory
and examine all combinations of no children with no children and of no children with one child.

For 18 digits there are 68336577 9-digit strings with no children and 176666866 9-digit strings with one child. So, several times fewer suspect combinations.

For 17 digits there are 23501420 9-digit strings with no children,
5218154 8-digit strings with no children, 147342610 9-digit strings with one child
and 23421431 8-digit strings with one child.

For 16 digits there are 17401442 8-digit strings with no children and 25360875 8-digit strings with one child.

And so on, fewer digits, the easier.

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.

Michael S <already5chosen@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.

--
Ben.

On 04/07/2021 09:27, Michael S wrote:
> On Friday, July 2, 2021 at 8:34:16 PM UTC+3, Bart wrote:

>> Well, it's fast (about 65 seconds on my machine,
>
> Your ability to enjoy slow PCs does not surprise me any more.

It's not that slow if my 2010 AMD-whatever is only 2.5 times as slow as
an Intel i5. Or is your main machine even faster?

(My machine can build all of my language projects from scratch (some 100
modules and 150Kloc) in about half a second. The compiler isn't even
optimised. It's hard to see the benefit of spending £100s on a faster
machine.)

>
>> perhaps 20 times as
>> fast as my program).
>
> If your program uses strings then only 20 times is a little disappointing.

You mean, you expected it to be slower (more than 20 times) or faster?

I didn't make any attempt at a fast program except to implement a
slightly simpler algorithm than the OP's, and one I could understand.

But since it depends heavily on atoll(), I made a custom version of that
(in newstrsubstring() below). That made it 3 times faster.

I then got a further 50% boost by replacing sprintf with atoi.

Now it's only about 4.5 times slower than your version. (290 seconds vs
66 seconds for F(10^9).)

So if yours was to take 7,000 years for F(10^9) based on your i5, mine
would now take only 30,000 years instead of 140,000. Lopping off 110,000
years is not a bad result for 5 minutes' work...

------------------------------------------

u64 strsubstring(char* s, int length) {
u64 result;
char c;

c=s[length];
s[length]=0;
result=atoll(s);
s[length]=c;
return result;
}

u64 newstrsubstring(char* s, int length) {
// length should be >=1
u64 result;

result=*s-'0';
++s;
while (--length) {
result=result*10+*s -'0';
++s;
}
return result;
}

>> That's probably the only advantage of the simpler algorithm,
>> other than being simpler.
>
> I did a simple "pure arithmetic" variant as well. It's really quite short and is closer to an ideal
> of mindless brute force. It ended up ~7 times slower than the variant presented above which
> is not that bad relatively to speed reported by other posters. Something like 1.5 times faster than
> Ben's.

So somewhat slower than mine now, but mine still uses strings.

On Sunday, July 4, 2021 at 5:20:01 PM UTC+3, Bart wrote:
> On 04/07/2021 09:27, Michael S wrote:
> > On Friday, July 2, 2021 at 8:34:16 PM UTC+3, Bart wrote:
>
> >> Well, it's fast (about 65 seconds on my machine,
> >
> > Your ability to enjoy slow PCs does not surprise me any more.
> It's not that slow if my 2010 AMD-whatever is only 2.5 times as slow as
> an Intel i5. Or is your main machine even faster?

This home desktop is from 2012 and even then was considered inexpensive, while not the cheapest possible.
Naturally, PCs I use to do a "real work" like FPGA development are significantly faster.

>
> (My machine can build all of my language projects from scratch (some 100
> modules and 150Kloc) in about half a second. The compiler isn't even
> optimised. It's hard to see the benefit of spending £100s on a faster
> machine.)

Comfortable web browsing, may be?

> >
> >> perhaps 20 times as
> >> fast as my program).
> >
> > If your program uses strings then only 20 times is a little disappointing.
> You mean, you expected it to be slower (more than 20 times) or faster?
>

I meant to say that I expected for may program to be more than 20 times faster than variants resembling one in the first post of this thread.

> I didn't make any attempt at a fast program except to implement a
> slightly simpler algorithm than the OP's, and one I could understand.
>
> But since it depends heavily on atoll(), I made a custom version of that
> (in newstrsubstring() below). That made it 3 times faster.
>
> I then got a further 50% boost by replacing sprintf with atoi.
>
> Now it's only about 4.5 times slower than your version. (290 seconds vs
> 66 seconds for F(10^9).)
>

Well, string-to-number and number-to-string conversions are biggest offenders in original code.
Or did he also have memory allocation in the inner loop? I don't remember.
So, if you replaced conversions with custom routines, you're already pretty close to my variant.
The only remaining major difference is my use of look-up tables instead of modulo operations.
I also saved a little time by not doing number-to-string conversion in the 3rd innermost loop,
for (x = first; x <= last; ++x) {...}
but that's probably not very significant if at all significant.

> So if yours was to take 7,000 years for F(10^9) based on your i5, mine
> would now take only 30,000 years instead of 140,000. Lopping off 110,000
> years is not a bad result for 5 minutes' work...
>

You mean F(10**19) ?
I am afraid your estimate is too optimistic, at least for your code and your PC.
I expect F(10**19) to take 4*1e10 as much time as F(10**9), which would be 370,000 years.

> ------------------------------------------
> u64 strsubstring(char* s, int length) {
> u64 result;
> char c;
>
> c=s[length];
> s[length]=0;
> result=atoll(s);
> s[length]=c;
> return result;
> }
> u64 newstrsubstring(char* s, int length) {
> // length should be >=1
> u64 result;
>
> result=*s-'0';
> ++s;
> while (--length) {
> result=result*10+*s -'0';
> ++s;
> }
> return result;
> }
>
>
> >> That's probably the only advantage of the simpler algorithm,
> >> other than being simpler.
> >
> > I did a simple "pure arithmetic" variant as well. It's really quite short and is closer to an ideal
> > of mindless brute force. It ended up ~7 times slower than the variant presented above which
> > is not that bad relatively to speed reported by other posters. Something like 1.5 times faster than
> > Ben's.
> So somewhat slower than mine now, but mine still uses strings.

But running "arithmetic" variant on my home PC is faster than your code on your home PC :-)
BTW, I don't think that your code could be still considered as "uses strings" in C language sense of the word.

On Sunday, July 4, 2021 at 7:04:46 PM UTC+3, Michael S wrote:
> I also saved a little time by not doing number-to-string conversion in the 3rd innermost loop,
> for (x = first; x <= last; ++x) {...}
> but that's probably not very significant if at all significant.

I measured it.
Without this optimization the programs runs ~1.5 times slower. So, optimization is not insignificant.
But I admit that at minimal performance cost it can be expressed in more comprehensible way.

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

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.

Michael S <already5chosen@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.

In article <87a6n0c1ux.fsf@bsb.me.uk>,
Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>Michael S <already5chosen@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);
}

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);
> }

In article <c7bfb14a-2084-41c3-beea-438139f73393n@googlegroups.com>,
Michael S <already5chosen@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. 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

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.

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

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

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.

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

On 7/6/2021 7:02 PM, Michael S wrote:

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

Per the problem description F(10^1) = 9, which means 0 isn't included.

https://projecteuler.net/problem=413

You may have some insights if you look at the numbers like this:

N Substrings * = one-child
--- ----------------------- ---------------
81. [8, 81, 1] *
82. [8, 82, 2]
83. [8, 83, 3] *
84. [8, 84, 4]
85. [8, 85, 5] *
86. [8, 86, 6]
87. [8, 87, 7] *
88. [8, 88, 8]
89. [8, 89, 9] *
90. [9, 90, 0]
91. [9, 91, 1]
92. [9, 92, 2]
93. [9, 93, 3]
94. [9, 94, 4]
95. [9, 95, 5]
96. [9, 96, 6]
97. [9, 97, 7]
98. [9, 98, 8]
99. [9, 99, 9]
100. [1, 10, 100, 0, 0, 0]
101. [1, 10, 101, 0, 1, 1] *
102. [1, 10, 102, 0, 2, 2]
103. [1, 10, 103, 0, 3, 3]
104. [1, 10, 104, 0, 4, 4] *
105. [1, 10, 105, 0, 5, 5]
106. [1, 10, 106, 0, 6, 6]
107. [1, 10, 107, 0, 7, 7] *
108. [1, 10, 108, 0, 8, 8]
109. [1, 10, 109, 0, 9, 9]
110. [1, 11, 110, 1, 10, 0] *
111. [1, 11, 111, 1, 11, 1] *
112. [1, 11, 112, 1, 12, 2] *
113. [1, 11, 113, 1, 13, 3] *
114. [1, 11, 114, 1, 14, 4] *
115. [1, 11, 115, 1, 15, 5] *
116. [1, 11, 116, 1, 16, 6] *
117. [1, 11, 117, 1, 17, 7] *
118. [1, 11, 118, 1, 18, 8] *
119. [1, 11, 119, 1, 19, 9] *
120. [1, 12, 120, 2, 20, 0]
121. [1, 12, 121, 2, 21, 1]
122. [1, 12, 122, 2, 22, 2] *
123. [1, 12, 123, 2, 23, 3]
124. [1, 12, 124, 2, 24, 4]
125. [1, 12, 125, 2, 25, 5] *
126. [1, 12, 126, 2, 26, 6]
127. [1, 12, 127, 2, 27, 7]
128. [1, 12, 128, 2, 28, 8] *
129. [1, 12, 129, 2, 29, 9]
130. [1, 13, 130, 3, 30, 0]
131. [1, 13, 131, 3, 31, 1] *
132. [1, 13, 132, 3, 32, 2]
133. [1, 13, 133, 3, 33, 3]
134. [1, 13, 134, 3, 34, 4] *
135. [1, 13, 135, 3, 35, 5]
136. [1, 13, 136, 3, 36, 6]
137. [1, 13, 137, 3, 37, 7] *
138. [1, 13, 138, 3, 38, 8]
139. [1, 13, 139, 3, 39, 9]
140. [1, 14, 140, 4, 40, 0] *
141. [1, 14, 141, 4, 41, 1] *
142. [1, 14, 142, 4, 42, 2] *
143. [1, 14, 143, 4, 43, 3] *
144. [1, 14, 144, 4, 44, 4] *
145. [1, 14, 145, 4, 45, 5] *
146. [1, 14, 146, 4, 46, 6] *
147. [1, 14, 147, 4, 47, 7] *
148. [1, 14, 148, 4, 48, 8] *
149. [1, 14, 149, 4, 49, 9] *

They definitely follow patterns.

* All 2-digit numbers of even-odd are one-child.

* 3-digit numbers beginning with the same 2 numbers are one-child,
unless those 2 starting numbers are factors of 3

110. [1, 11, 110, 1, 10, 0] *
111. [1, 11, 111, 1, 11, 1] *
112. [1, 11, 112, 1, 12, 2] *
113. [1, 11, 113, 1, 13, 3] *
114. [1, 11, 114, 1, 14, 4] *
115. [1, 11, 115, 1, 15, 5] *
116. [1, 11, 116, 1, 16, 6] *
117. [1, 11, 117, 1, 17, 7] *
118. [1, 11, 118, 1, 18, 8] *
119. [1, 11, 119, 1, 19, 9] *

220. [2, 22, 220, 2, 20, 0] *
221. [2, 22, 221, 2, 21, 1] *
222. [2, 22, 222, 2, 22, 2] *
223. [2, 22, 223, 2, 23, 3] *
224. [2, 22, 224, 2, 24, 4] *
225. [2, 22, 225, 2, 25, 5] *
226. [2, 22, 226, 2, 26, 6] *
227. [2, 22, 227, 2, 27, 7] *
228. [2, 22, 228, 2, 28, 8] *
229. [2, 22, 229, 2, 29, 9] *

330. [3, 33, 330, 3, 30, 0]
331. [3, 33, 331, 3, 31, 1]
332. [3, 33, 332, 3, 32, 2]
333. [3, 33, 333, 3, 33, 3]
334. [3, 33, 334, 3, 34, 4]
335. [3, 33, 335, 3, 35, 5]
336. [3, 33, 336, 3, 36, 6]
337. [3, 33, 337, 3, 37, 7]
338. [3, 33, 338, 3, 38, 8]
339. [3, 33, 339, 3, 39, 9]

440. [4, 44, 440, 4, 40, 0] *
441. [4, 44, 441, 4, 41, 1] *
442. [4, 44, 442, 4, 42, 2] *
443. [4, 44, 443, 4, 43, 3] *
444. [4, 44, 444, 4, 44, 4] *
445. [4, 44, 445, 4, 45, 5] *
446. [4, 44, 446, 4, 46, 6] *
447. [4, 44, 447, 4, 47, 7] *
448. [4, 44, 448, 4, 48, 8] *
449. [4, 44, 449, 4, 49, 9] *

550. [5, 55, 550, 5, 50, 0] *
551. [5, 55, 551, 5, 51, 1] *
552. [5, 55, 552, 5, 52, 2] *
553. [5, 55, 553, 5, 53, 3] *
554. [5, 55, 554, 5, 54, 4] *
555. [5, 55, 555, 5, 55, 5] *
556. [5, 55, 556, 5, 56, 6] *
557. [5, 55, 557, 5, 57, 7] *
558. [5, 55, 558, 5, 58, 8] *
559. [5, 55, 559, 5, 59, 9] *

660. [6, 66, 660, 6, 60, 0]
661. [6, 66, 661, 6, 61, 1]
662. [6, 66, 662, 6, 62, 2]
663. [6, 66, 663, 6, 63, 3]
664. [6, 66, 664, 6, 64, 4]
665. [6, 66, 665, 6, 65, 5]
666. [6, 66, 666, 6, 66, 6]
667. [6, 66, 667, 6, 67, 7]
668. [6, 66, 668, 6, 68, 8]
669. [6, 66, 669, 6, 69, 9]

770. [7, 77, 770, 7, 70, 0] *
771. [7, 77, 771, 7, 71, 1] *
772. [7, 77, 772, 7, 72, 2] *
773. [7, 77, 773, 7, 73, 3] *
774. [7, 77, 774, 7, 74, 4] *
775. [7, 77, 775, 7, 75, 5] *
776. [7, 77, 776, 7, 76, 6] *
777. [7, 77, 777, 7, 77, 7] *
778. [7, 77, 778, 7, 78, 8] *
779. [7, 77, 779, 7, 79, 9] *

etc

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

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

In article <06a1aff4-365a-4f91-91d1-56dead415871n@googlegroups.com>,
Michael S <already5chosen@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"? Does it extend beyond 19 digits (which is what
fits in a long long)?

Kent

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

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