Prev: WinMenus version 1.0 ...
Next: counting how many positive integers <n have digits that add up to m
From: Willem on 23 May 2010 07:23
Willem wrote:
) This is absolute peanuts compared to some of the other things I mentioned.

Here's a setup to a simple recursive solution:

- The function cnt(m, x) equals the number of integers lower than 10^x
with a digit sum equal to m.

(To get the count for arbitrary n, you need a second function, that
divides up n into its digits and then calculates for each digit.)

The base is easy:

- cnt(m, 0) :=
1 if m == 0
0 otherwise

Now here's the really nice bit:
If you can calculate how many hits there are in a set of, say, 100 numbers,
then you can use that to calculate the number of hits in a set of 1000
numbers. You see, the number of hits in, say, the range 800-899 is equal
to the number of hits in 00-99 for a target that is 8 less.

Or, more precisely:
- cnt(m, x) :=
sum (0 <= i <= 9) { cnt(m - i, x-1) }

Now, if you apply this blindly, you still end up doing N calculations.
But you might notice that you're doing the same calculation a lot of times.
So if you store those calculations, it will go a lot faster.

You can do this bottom-up, if you keep a table. You just need to figure
out the minimum and maximum number of m that needs calculating.

The start of the table would be something like:

1
1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1
1 3 6 10 15 21 28 36 45 55 63 69 73 75 75 73 69 63 55 45 36 28 21 15 ...

The first column is for m=0, the first row is for x=0 (or n=1)
Basically, each cell in the table is the sum of the 10 cells in
the row above it, ending on the same column.

(For example, there are 75 numbers < 1000 with a digit sum of 14)

So you need a maximal width of the target m you're looking for,
and a height of the number of digits in n.


Of course, with this you won't find the actual numbers, just the count.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
From: S Perryman on 23 May 2010 07:54
superpollo wrote:

> S Perryman ha scritto:

>> Daniel T. wrote:

>>> My first thought is that there might be a formula that will return
>>> the result with no loops.

>> My first reply to you is :

>> What formula are you offering for computing the desired result .... ??

> maybe some generating function magic ?

m=10, n = 12345 :

Smallest number is 19.
Break into 1 | 9.
There are (9 - 1) + 1 numbers < 100 (19, 28, ... 91) .

Somehow compute the next number.
x = 109 (19 + 90) .
Break into 10 | 9. Break into (10 mod 10) | 9 = 0 | 9.
There are (9 - 0) + 1 = 10 numbers < 200 (109, 118, ... 190) .

Compute the next number.
x = 208 (109 + 99) .
Break into 20 | 8. Break into (20 mod 10) | 8 = 0 | 8
There are (8 - 0) + 1 = 9 numbers less in 300.

And so on.


So there are variant conditions as to when to add 90 or 99 to
get the start of the next block of numbers.

But there are also some deviant cases. :-(
For example : x = 901.

Meaning 9 | 1.
1 - 9 + 1 does not equal 2 (901, 910) .

The next number is 1009.
901 + 90 = 991. 901 + 99 = 1000. Both are wrong.

However, 910 (the last number in the block) + 99 = 1009.


Regards,
Steven Perryman
From: S Perryman on 23 May 2010 13:27
Daniel T. wrote:

> S Perryman <a(a)a.net> wrote:

>>Daniel T. wrote:

>>>My first thought is that there might be a formula that will return the
>>>result with no loops.

>>What formula are you offering for computing the desired result .... ??

> I spent a few minutes (maybe as many as 30) on this question. Like I
> said, my feeling is that there is a formula for this, but my math skills
> are not up to the task.

I feel there is not an exact formula as such, in the manner of something
like the sum of all squares etc.

Although computing the first number that meets the criteria is
universally ok, as is calculating the 'delta' between successive numbers in
a 'block' of such numbers, for me tis the non-obvious univeral means at the
moment of identifying the start number (see my other posts) in each
block based on info inherent on previous blocks, that is the issue for me
regarding the possibility of such a formula.


Regards,
Steven Perryman
From: superpollo on 23 May 2010 17:43
superpollo ha scritto:
> S Perryman ha scritto:
>> Daniel T. wrote:
>>
>>> superpollo <utente(a)esempio.net> wrote:
>>
>>>> in python:
>>
>>>> def prttn(m, n):
>>>> tot = 0
>>>> for i in range(n):
>>>> s = str(i)
>>>> sum = 0
>>>> for j in range(len(s)):
>>>> sum += int(s[j])
>>>> if sum == m:
>>>> tot += 1
>>>> return tot
>>
>>>> any suggestion for improvement?
>>
>>> My first thought is that there might be a formula that will return
>>> the result with no loops.
>>
>> My first reply to you is :
>>
>> What formula are you offering for computing the desired result .... ??
>
> maybe some generating function magic ?

like this:

(%i12) taylor (((1-x^10)/(1-x))^7, x, 0, 31);

(%o12)
1+7*x+28*x^2+84*x^3+210*x^4+462*x^5+924*x^6+1716*x^7+3003*x^8+5005*x^9
+8001*x^10+12327*x^11+18368*x^12+26544*x^13+37290*x^14+51030*x^15

+68145*x^16+88935*x^17+113575*x^18+142065*x^19+174195*x^20+209525*x^21
+247380*x^22+286860*x^23+326865*x^24+366135*x^25+403305*x^26
+436975*x^27+465795*x^28+488565*x^29+504315*x^30+512365*x^31
^^^^^^

bye
First  |  Prev  | 
Pages: 1 2 3
Prev: WinMenus version 1.0 ...
Next: counting how many positive integers <n have digits that add up to m