How many positive integers less than one million has a digit sum of 20, and does not contain any two-digit substring whose digit sum is 7? For example, 123563 is one of those numbers while 435 and 123455 are not.
- husoskiLv 71 month agoFavorite Answer
I agree that a computer will get this done in reasonable time. You can use math to cut down the size of the problem a bit.
The digital sum of a number has the same modulo 9 remainder as the original did. That's the basis of the well-known "divisible by 9 or 3" test. Since 20 = 9*2 + 2, you only have to look at numbers with a remainder of 2, modulo 9.
The smallest number with a digital sum of 20 is 299 and the largest under a million is 992,000. You only have to look at numbers of the form n = 9k + 2 from 299 through 992,000. That's "only" 110,190 numbers to test; rather that 999,999.
In a language like Python, you can get this done in a few minutes of coding (most spent on writing the test for consecutive digit pairs adding to 7. The number 776 should be acceptable, since neither 7+7 nor 7+6 is 7, but it's an easy coding error to treat that as the number 000776 and reject it because 0+7 = 7.
I get an answer of 20,241 acceptable numbers in under 2 seconds of run time without even bothering with the modulo 9 speedups or using "fast" methods to turn a number into a list of digits with no leading zeroes.
[Aside: You don't need C++ for this!]
- atsuoLv 61 month ago
You said "The answer is not 20241" , so what is your answer ?
I found that the answer was 20241 as the other answerers said .
If the numbers "07ABCD" , "007ABC" , "0007AB" and "00007A" are
rejected then 19908 becomes the answer . Is your answer 19908 ?
But they are not numbers with 6 digits so they may be counted .
For example , "007553" is "7553" so it must be counted .
- nbsaleLv 61 month ago
I agree with husoski's answer of 20241.
I do most of my work in Excel, so I just used a VBA macro for this. Only took about 25 lines, including set up and output.
- Anonymous1 month ago
There will be a lot.
A program in C++ or Java is needed to solve this as it has the ability to process every integer digit wise at high speed and give you the total number.
- How do you think about the answers? You can sign in to vote the answer.
- DixonLv 71 month ago
All these sort of questions are best solved with quick test-and-count computer script