Problem 413

[mrush425]

I am having an issue with problem 413. Before I run the entire code I wanted to make sure that I could make F(10^3) work. I am coming up with an answer of 384 not 389. At first i assumed something was wrong with my code, but i struggled to find errors. So I manually did it, and found 384 solutions as well. If someone wouldn't mind running their program using 10^3 rather than 10^19, and display all the numbers that are 3 digit one child numbers that would be awesome. I have a feeling I am just not 100% certain of all the rules of a 3 digit one child number. Thanks!

[Marcus_Andrews]

If you have a three digit number abc, then only one of the following is true if it is also a one-child number:

a is divisible by 3
b is divisible by 3
c is divisible by 3
ab is divisible by 3
bc is divisible by 3
abc is divisible by 3

You can test this by simply iterating through all 3-digit numbers and performing the divisibility checks.

[jtymann]

My question can be answered pretty quickly if you can answer this question... is 1414111 a one-child number?

My questions basically arises from the fact that the substring 14 occurs twice. Also 14 is the only possible substring that is divisible by 7. So if we count duplicate substrings this is not a one-child number. If we don't count duplicates it is a one-child number.

Further Explanation. Ignoring repeats, here are all the possible substrings:
1,4,14,41,11,141,414,411,111,1414,4141,1411,4111,14141,41411,14111,141411,414111

The only one of these substrings that is divisible by 7 is 14. So if that is our set of substrings, that would imply this is a one-child number.

However if we take the same number and show all possible substrings including duplicates, 14 would should up twice. Implying it is not a one child number.

Can anyone clear this up for me?

[Marcus_Andrews]

No, 1414111 is not a one-child number because there are three substrings divisible by 7 (the first and second 14, as well as 1414)

[jtymann]

Hmm, looks like i messed up doing that on by hand.

So should I ignore duplicates or count them? Or are there no such numbers where counting duplicate substrings matter, as there will always be another substring that matches as well?

[thundre]

So should I ignore duplicates or count them?

Count them. A duplicate substring which is divisible by n makes it at least a 2-child number.

Think of it this way: If you have identical twins, you do not have an only child.

[Marcus_Andrews]

To clarify my earlier response, here are the children for 1414111:

1414111

1414111

1414111

Hmm, looks like i messed up doing that on by hand.

So should I ignore duplicates or count them? Or are there no such numbers where counting duplicate substrings matter, as there will always be another substring that matches as well?

You should always count them.

[mrush425]

Thanks guys for all the help. I realized I was doing two things different from what the problem was asking.

First, I was treating 323 as a 3 digit number, I was counting the two threes as the same substring. Because I was doing this, I was getting 384, which just happened to be really close.

The really issue was I was not looking at all the N digit numbers less than. So When the number was F(1000), I was only looking at the 3 digit one child numbers instead of including the 1 and 2 digit ones.

Thanks for all the responses!