Anonymous
Anonymous asked in Science & MathematicsMathematics · 1 month ago

# math problem?

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.

Relevance
• 1 month ago

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!]

• atsuo
Lv 6
1 month ago

I found that the answer was 20241 as the other answerers said .

If the numbers "07ABCD" , "007ABC" , "0007AB" and "00007A" are

But they are not numbers with 6 digits so they may be counted .

For example , "007553" is "7553" so it must be counted .

• nbsale
Lv 6
1 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.

• Anonymous
1 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.

• nbsale
Lv 6
1 month agoReport

I agree that a program is needed, but any language will do. Excel VBA does this in about 3 seconds.