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.

5 Answers

Relevance
  • 1 month ago
    Favorite 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!]

    • Login to reply the answers
  • atsuo
    Lv 6
    1 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 .

    • Login to reply the answers
  • 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.

    • Login to reply the answers
  • 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.

    • Login to reply the answers
  • How do you think about the answers? You can sign in to vote the answer.
  • Dixon
    Lv 7
    1 month ago

    All these sort of questions are best solved with quick test-and-count computer script

    • Login to reply the answers
Still have questions? Get your answers by asking now.