Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #161546 > unrolled thread
| Started by | DFS <nospam@dfs.com> |
|---|---|
| First post | 2021-06-30 12:26 -0400 |
| Last post | 2021-07-01 10:49 +0200 |
| Articles | 20 on this page of 64 — 11 participants |
Back to article view | Back to comp.lang.c
Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-06-30 12:26 -0400
Re: Losing my mind: results change with/without printf() statements David Brown <david.brown@hesbynett.no> - 2021-06-30 19:03 +0200
Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-06-30 13:58 -0400
Re: Losing my mind: results change with/without printf() statements Bart <bc@freeuk.com> - 2021-06-30 19:44 +0100
Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-06-30 16:16 -0400
Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-01 00:03 +0100
Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-06-30 23:54 -0400
Re: Losing my mind: results change with/without printf() statements David Brown <david.brown@hesbynett.no> - 2021-07-01 10:56 +0200
Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-01 10:38 +0100
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-02 02:49 -0700
Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-02 14:44 +0100
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-02 07:48 -0700
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-02 09:25 -0700
Re: Losing my mind: results change with/without printf() statements Bart <bc@freeuk.com> - 2021-07-02 18:33 +0100
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-04 01:27 -0700
Re: Losing my mind: results change with/without printf() statements Bart <bc@freeuk.com> - 2021-07-04 15:19 +0100
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-04 09:04 -0700
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-04 09:51 -0700
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-02 03:20 -0700
Re: Losing my mind: results change with/without printf() statements Bart <bc@freeuk.com> - 2021-07-02 11:42 +0100
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-02 04:47 -0700
Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-02 15:21 +0100
Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-07-02 11:37 -0400
Re: Losing my mind: results change with/without printf() statements Bart <bc@freeuk.com> - 2021-07-02 17:06 +0100
Re: Losing my mind: results change with/without printf() statements Kaz Kylheku <563-365-8930@kylheku.com> - 2021-07-02 17:41 +0000
Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-02 19:09 +0100
Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-02 19:48 +0100
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-04 03:21 -0700
Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-04 14:01 +0100
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-05 02:44 -0700
Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-05 14:43 +0100
Re: Losing my mind: results change with/without printf() statements kegs@provalid.com (Kent Dickey) - 2021-07-05 19:42 -0500
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-06 03:36 -0700
Re: Losing my mind: results change with/without printf() statements kegs@provalid.com (Kent Dickey) - 2021-07-06 12:27 -0500
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-06 16:02 -0700
Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-07-06 20:30 -0400
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-08 01:02 -0700
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-09 05:52 -0700
Re: Losing my mind: results change with/without printf() statements kegs@provalid.com (Kent Dickey) - 2021-07-09 08:24 -0500
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-09 07:20 -0700
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-10 15:27 -0700
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-12 00:56 -0700
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-12 12:01 -0700
Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-12 21:30 +0100
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-13 00:33 -0700
Re: Losing my mind: results change with/without printf() statements Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-13 22:58 +0100
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-20 13:38 -0700
Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-07-09 11:23 -0400
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-09 08:43 -0700
Re: Losing my mind: results change with/without printf() statements Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-07-11 16:40 +0100
Re: Losing my mind: results change with/without printf() statements Michael S <already5chosen@yahoo.com> - 2021-07-12 02:51 -0700
Re: Losing my mind: results change with/without printf() statements Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-07-12 16:57 +0100
Re: Losing my mind: results change with/without printf() statements Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-07-12 17:25 +0100
Re: Losing my mind: results change with/without printf() statements Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-07-20 18:03 +0100
Re: Losing my mind: results change with/without printf() statements David Brown <david.brown@hesbynett.no> - 2021-07-01 10:46 +0200
Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-07-02 11:52 -0400
Re: Losing my mind: results change with/without printf() statements Bart <bc@freeuk.com> - 2021-07-02 17:16 +0100
Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-07-02 13:27 -0400
Re: Losing my mind: results change with/without printf() statements luser droog <luser.droog@gmail.com> - 2021-07-12 16:19 -0700
Re: Losing my mind: results change with/without printf() statements Barry Schwarz <schwarzb@delq.com> - 2021-06-30 11:36 -0700
Re: Losing my mind: results change with/without printf() statements DFS <nospam@dfs.com> - 2021-06-30 16:03 -0400
Re: Losing my mind: results change with/without printf() statements Barry Schwarz <schwarzb@delq.com> - 2021-06-30 13:22 -0700
Re: Losing my mind: results change with/without printf() statements David Brown <david.brown@hesbynett.no> - 2021-07-01 11:03 +0200
Re: Losing my mind: results change with/without printf() statements Rosario19 <Ros@invalid.invalid> - 2021-07-01 10:49 +0200
Page 2 of 4 — ← Prev page 1 [2] 3 4 Next page →
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2021-07-02 04:47 -0700 |
| Message-ID | <99f4da00-9206-4702-8ac7-515c5b21af92n@googlegroups.com> |
| In reply to | #161582 |
On Friday, July 2, 2021 at 1:43:06 PM UTC+3, Bart wrote: > On 02/07/2021 11:20, Michael S wrote: > > On Wednesday, June 30, 2021 at 11:16:53 PM UTC+3, DFS wrote: > >> On 6/30/2021 2:44 PM, Bart wrote: > > >>> I tried it on N=10,000,000, and gcc-O3 took 41 seconds. PyPy > >>> (accelerated version of Python) took 17 seconds. > >> 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). > >> > >> You can't brute force that with a desktop PC. > > > > If you understand that it can't be done by brute force then why are you trying to do just that? > > Supposedly, the speed of your code could be improved by factor of 10 or, with a bit of algorithmic > > smarts, even by factor of 100. It's still does not bring your to the point where we can tackle the challenge > > either with a single desktop PC or with networks of few thousands of 50-core servers. > It wouldn't get very far using 'int' types either, which limits it to > F(10^9). It would need to use uint64_t (with changes to atoi etc) to > manage F(10^19). > > I guess that's why that limit was chosen. > > Python of course could go well beyond F10^19), given enough time. Read posts of Ben Bacarisse. atai() or similar functions are not needed at all. If you are a bit smart about algorithms then 64-bit arithmetic is not needed either. In fact, even 32-bit arithmetic is not necessary. Suppose, you have a substring "abc...x". You have its reminder r1 already calculated. Then, for a substring "abc...xy" reminder is equal to (r1*10+x) % nDig. For nDig<=19 all numbers involved in calculations fit in uint8_t. As a next step, you can replace modulo operation with table lookup, which would be quicker, because lookup table is small and easily fits in L1D cache. But all that wouldn't help to even remotely approach a problem of size 10**19.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-07-02 15:21 +0100 |
| Message-ID | <87a6n4hk4c.fsf@bsb.me.uk> |
| In reply to | #161555 |
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.) -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2021-07-02 11:37 -0400 |
| Message-ID | <GoGDI.4118$D71.3961@fx06.iad> |
| In reply to | #161586 |
On 7/2/2021 10:21 AM, Ben Bacarisse 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.) That's very good. "Each problem has been designed according to a 'one-minute rule', which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute." https://projecteuler.net
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2021-07-02 17:06 +0100 |
| Message-ID | <sbndho$1ip$1@dont-email.me> |
| In reply to | #161586 |
On 02/07/2021 15:21, Ben Bacarisse 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.)
>
For F(10^7) I got 9.4 seconds with gcc-O3 with the C version below that
uses atoi equivalents. I seem to remember that my machine is quite a bit
slower than yours. Use of u64 rather than int doesn't affect the results.
I started on a version with no text conversions, but it got messy.
---------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef unsigned long long u64;
u64 strsubstring(char* s, int length) {
u64 result;
char c;
c=s[length];
s[length]=0;
result=atoll(s);
s[length]=c;
return result;
}
int onechild(u64 n) {
char s[128];
int slen=sprintf(s,"%llu",n);
int count;
u64 m;
count=(n%slen)==0;
for (int w=0; w<(slen-1); ++w) {
for (int i=0; i<slen-w; ++i) {
m=strsubstring(s+i,w+1);
if ((m%slen)==0) {
++count;
if (count>1) return 0;
}
}
}
return count==1;
}
int main(void) {
int count=0;
u64 n=10000000;
for (int i=1; i<n; ++i) {
count+=onechild(i);
}
printf("F(%llu) = %d\n",n, count);
}
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2021-07-02 17:41 +0000 |
| Message-ID | <20210702095301.721@kylheku.com> |
| In reply to | #161586 |
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
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-07-02 19:09 +0100 |
| Message-ID | <874kdch9k0.fsf@bsb.me.uk> |
| In reply to | #161601 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-07-02 19:48 +0100 |
| Message-ID | <87y2aoft70.fsf@bsb.me.uk> |
| In reply to | #161602 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2021-07-04 03:21 -0700 |
| Message-ID | <6751375f-4ddb-4ee3-b05a-919a0d57c306n@googlegroups.com> |
| In reply to | #161603 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-07-04 14:01 +0100 |
| Message-ID | <87o8bicjxo.fsf@bsb.me.uk> |
| In reply to | #161638 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2021-07-05 02:44 -0700 |
| Message-ID | <5c9ca972-f228-4702-81b3-4823bb06e49bn@googlegroups.com> |
| In reply to | #161642 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-07-05 14:43 +0100 |
| Message-ID | <87a6n0c1ux.fsf@bsb.me.uk> |
| In reply to | #161659 |
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.
[toc] | [prev] | [next] | [standalone]
| From | kegs@provalid.com (Kent Dickey) |
|---|---|
| Date | 2021-07-05 19:42 -0500 |
| Message-ID | <2pmdnZmxQ42VOn79nZ2dnUU7-S_NnZ2d@giganews.com> |
| In reply to | #161667 |
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);
}
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2021-07-06 03:36 -0700 |
| Message-ID | <c7bfb14a-2084-41c3-beea-438139f73393n@googlegroups.com> |
| In reply to | #161688 |
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.
[toc] | [prev] | [next] | [standalone]
| From | kegs@provalid.com (Kent Dickey) |
|---|---|
| Date | 2021-07-06 12:27 -0500 |
| Message-ID | <a_CdnUJgh4wOD3n9nZ2dnUU7-XvNnZ2d@giganews.com> |
| In reply to | #161696 |
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
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2021-07-06 16:02 -0700 |
| Message-ID | <bdc09058-f92c-4084-92c2-5186bfea63bcn@googlegroups.com> |
| In reply to | #161700 |
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
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2021-07-06 20:30 -0400 |
| Message-ID | <KA6FI.173$Yv3.34@fx41.iad> |
| In reply to | #161708 |
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
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2021-07-08 01:02 -0700 |
| Message-ID | <ad435f65-f4c1-4db7-a565-5404767814ebn@googlegroups.com> |
| In reply to | #161708 |
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
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2021-07-09 05:52 -0700 |
| Message-ID | <06a1aff4-365a-4f91-91d1-56dead415871n@googlegroups.com> |
| In reply to | #161742 |
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.
[toc] | [prev] | [next] | [standalone]
| From | kegs@provalid.com (Kent Dickey) |
|---|---|
| Date | 2021-07-09 08:24 -0500 |
| Message-ID | <GuWdnTUsM4OE03X9nZ2dnUU7-R-dnZ2d@giganews.com> |
| In reply to | #161782 |
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
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2021-07-09 07:20 -0700 |
| Message-ID | <eb8e43ea-3529-47ab-97f8-c374c1fceec8n@googlegroups.com> |
| In reply to | #161783 |
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
[toc] | [prev] | [next] | [standalone]
Page 2 of 4 — ← Prev page 1 [2] 3 4 Next page →
Back to top | Article view | comp.lang.c
csiph-web