How many integers between 1 and 1,000,000,000,000 have a sum of its digits equal to 13?

Question

(thats between 1 and 10^12)

NONE???? Karlo just listed 5 of them.....

paulburns84:
Is there a point to your answer or do you just not know?

The point to this question is indeed to get people to think, and to provide math aficionados with a problem they might not have seen and beyond the usual homework-related dreck on this thread.

note to someantha
thats why I chose 10^12. so that computer solutions would take a long time.
however, a visual basic program i wrote computed it for 1 to 1000000 in 6 seconds, so you should either check your algorithm or switch languages. this problem can be solved mathematically using combinitorial analysis.

HINT:
If m and k are fixed positive integers, then:
The number of solutions of:
x(1) + x(2) + x(3) + ... + x(k) = m
in positive integers is:
C(m-1,k-1)
and in non-negative integers is:
C(m+k-1, k-1)

Note to:Phil Mack
I was looking for a mathematical solution, as this is the mathematics section.
Can your program tell me how many such numbers are between 1 and 10^(10^20)? I'll accept the answer in exponential notation with 15 digits of the mantissa.

Answer 1

Edit: I get 2,491,776

The restriction of 9 being the largest number(digit) that can be used eliminates, for example, partitions of 13 such as 10,3; 11,2 and 12,1. if you use your hint then for 2 terms x(1) + x(2) =13 then k=2 and (m-1)C(k-1) = 12C1 = 12 which is twice what it should be. Normal partition calculations will give us 94 85 76 but we have to use "compositions" to include all distinct orderings so that 49 58 and 67 are included, and all possible compositions of term length 2 to 12 are included:

Compositions of 13 (max 9) with x terms (x = 2 to 12):

X
2) 6
3) 57
4) 216
5) 495
6) 792
7) 924
8) 792
9) 495
10) 220
11) 66
12) 12

Now each of these can be treated as a simple combinations problem where we let n = 12 and r = 2-12

6 x 12C2 = 396
57 x 12C3 = 12540
216 x 12C4 = 106920
495 x 12C5 = 392040
792 x 12C6 = 731808
924 x 12C7 = 731808
792 x 12C8 = 392040
495 x 12C9 = 108900
220 x 12C10 = 14520
66 x 12C11 = 792
12 x1 =12

Grand Total: 2,491,776

Answer 2

The point of his question is to get people to think.
Let C(n,r) be the choose function.

label the digits a≤b≤c≤d≤e≤f≤g≤h≤i≤j≤k≤l

If l=9:
k=4 ==> the rest are 0
you have 12 choises for l and 11 choices for k or 132 choices.
k=3 ==> j=1 and the rest are 0
you have 12 choices for l, 11 choices for k, and 10 choices for j. (1320 choices)
k=2:
j=2==> everything else is 0. You have 12,C(11,2) choices,
j=1==>i=1. 12•11•10•9•C(8,2)
k=1==>j,i,h=1==>12•11•9•8•C(7,4)
l=8:
k=5: 12,11
k=4,j=1:12,11,10
k=3, j=2: 12,11,10
k=3, j,i=1: 12, 11, C(10,2)
k,j=2, i=1: 12, 11, C(10,2)
k=2, j,i,h=1: 12, 11, C(10,3)
k,j,i,h,g=1: 12, C(10,5)
l=7:
k=6: 12, 11
k=5, j=1: 12, 11, 10
k=4, j=2, 12, 11, 10
k=4, j,i=1 12, 11, C(10,2)
k,j=3: 12, C(11,2)
k=3,j=2, i=1: 12, 11, 10, 9
k=3, j,i,h=1, 12, 11, C(10,3)
k,j,i=2: 12, C(11,3)
k,j=2, i,h=1: 12, C(11,2), C(9,2) (this is where I am not sure)
k=2, j,i,h,g=1: 12, 11, C(10,4)
k,j,i,h,g,f: 12, C(11,6)
l,k=6, j=1: 12, C(11,2)
l=6, k=5, j=2: 12, 11, 10
l=6, k=5, j,i=1: 12, 11, C(10,2)
l=6, k=4, j=3: 12, 11, 10
l=6, k=4, j=2, i=1: 12, 11, C(10,2)
l=6, k=4, j,i,h=1: 12, 11, C(10,3)
l=6, k,j=3, i=1, 12, 11, C(10,2)
l=6, k=3, j,i=2, 12, 11, C(10,2)
l=6, k=3, j=2, i,h=1: 12, 11, 10, C(9,2)
j,i,h,g=1: 12, 11, C(10,4)
k,j,i=2, h=1: 12, 11, C(10,3)
k,j=2, i,h,g=1: 12, C(11,3), C(8,2)
k=2, j,i,h,g,f=1, 12, 11, C(10,5)
k,j,i,h,g,f,e=1: 12, C(11,7)
l,k=5, j=3: 12, C(11,2)
k,j=4: 12, C(11,2)
k=4, j=3, i=1: 12, 11, 10, 9
k=4, j,i=2: 12, 11, C(10,2)
k=4, j=2, i,h=1: 12, 11, 10, C(9,2)
k=4, j,i,h,g=1: 12, 11, C(10,4)
k,j=3, i=2: 12, 11, C(10,2)

. . this is boring, someone else can finish it, and change it so the combinitorics is correct . . .

please tell me about the mistakes I made. I haven't studied combinitorics yet, and am very shaky on the subject. Also, if you have any suggestions for a book to read on the subject, that would be cool too.

Answer 3

There are 2491776 integers between 1 and 1,000,000,000,000 that have a sum of its digits equal to 13.

I figured this out by writing a vb.net program that iteratively constructed 12 digit numbers, one digit at a time that met the constraints. So long as a partial number met the constraints, the construction continued, else the iteration continued. The method found all possible numbers in the given range meeting the given criteria in under 9 seconds.

I can supply the complete list of numbers or the source code, but neither will fit in this box.

Answer 4

[edited]

Well...

The lowest number is 49, and highest is 940,000,000,000.

You can add one to any digit except 9, but have to subtract 1 from somewhere else (except 0).

Starting with the highest number and:

one digit at a time gets you 130 (13*10) [edit]
two digits at a time gets you +18*9

I think Jimbo is on to something...
I get P(13,3) = 35 though

Answer 5

edit:

combinawhozit? wtf?

i've updated my SQL statement to run in VB. it's humming along, and i'll let you know the outcome. so far, it's counted over 7 million
with over 26K qualifying integers.

after counting past 30 million, there are just over 60K that qualify. maybe a real math person will get this figured out with their secret knowledge. i'm gonna' leave it running for a few hours. bye for now...

Answer 6

Is there a point to this question or are you just curious to know?
------
The point of my answer was to ask you what the point of your question was. Got the point? Off the top of my head, no I don't know. And I think it would take the best part of a week to work it out!

Answer 7

None

Answer 8

hmm.. let's see.. there's 91111, 19111, 11911, 11191, 11119, etc. omg, there's a lot..

Answer 9

it's more than 97.

my guess is 522,956,204?

Answer 10

1000000000