All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Wanted: gifted numbers (Posted on 2016-05-24)
How many positive integers are there, fitting the following description ("gifted" numbers):

a. The total number of digits is below 13.
b. The number of even digits is twice the number of odd digits .
c. The even digits within the number read from left to right form a non-decreasing sequence
d. The odd digits within the number may appear in any order.
e. The s.o.d. of the number is less than 69.

Few samples of qualifying numbers: 300, 254, 436111878, 653766668.

 No Solution Yet Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer assisted solution Comment 1 of 1
The item causing the most difficulty is rule e, making a simple combinatorics problem complex.

First, let's consider ways of choosing the 2, 4, 6 or 8 even digits. We need to consider separately those that have a zero (which is necessarily an initial zero due to rule c) and those that do not.

The sequence of numbers represent how many ways of making a given total using the given number of even digits. Only the even totals are shown, to save space, as odd totals will never occur; the counts start with zero. For example the sequence 0 0 1 1 2 2 2 1 1 at the beginning of the 2-digit possibilities without leading zeros represent the number of ways of producing totals of 0, 2, 4, etc.  To be specific, no ways of getting zero or 2, as that would entail that at least one be a zero; there's only one way of getting 4 or 6 (22 or 24 respectively); two ways each of 8, 10 or 12 (26, 44; 28, 46; 48, 66); and one way each for 14 or 16 (68 or 88 respectively).

`2 of even digits:with leading zeros 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0    5without leading zeros 0 0 1 1 2 2 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0    10`
`4 of even digits:with leading zeros 1 1 2 3 4 4 5 4 4 3 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0    35without leading zeros 0 0 0 0 1 1 2 3 4 4 5 4 4 3 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0    35`
`6 of even digits:with leading zeros 1 1 2 3 5 6 8 9 11 11 12 11 11 9 8 6 5 3 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0    126without leading zeros 0 0 0 0 0 0 1 1 2 3 4 5 7 7 8 8 8 7 7 5 4 3 2 1 1 0 0 0 0 0 0 0 0    84`

`8 of even digits:with leading zeros 1 1 2 3 5 6 9 11 14 16 19 20 23 23 24 23 23 20 19 16 14 11 9 6 5 3 2 1 1 0 0 0 0    330without leading zeros 0 0 0 0 0 0 0 0 1 1 2 3 4 5 7 8 10 11 12 12 13 12 12 11 10 8 7 5 4 3 2 1 1    165`
Totals appear at the end of each row above

1 odd digits
1    1         5        30
2    0         0         0
3    1         5        30
4    0         0         0
5    1         5        30
6    0         0         0
7    1         5        30
8    0         0         0
9    1         5        30
10    0         0         0
11    0         0         0
12    0         0         0
13    0         0         0
14    0         0         0
15    0         0         0
16    0         0         0
17    0         0         0
18    0         0         0
19    0         0         0
20    0         0         0
21    0         0         0
22    0         0         0
23    0         0         0
24    0         0         0
25    0         0         0
26    0         0         0
27    0         0         0
28    0         0         0
29    0         0         0
30    0         0         0
31    0         0         0
32    0         0         0
33    0         0         0
34    0         0         0
35    0         0         0
36    0         0         0

2 odd digits
1    0         0         0
2    1       175       525
3    0         0         0
4    2       350      1050
5    0         0         0
6    3       525      1575
7    0         0         0
8    4       700      2100
9    0         0         0
10    5       875      2625
11    0         0         0
12    4       700      2100
13    0         0         0
14    3       525      1575
15    0         0         0
16    2       350      1050
17    0         0         0
18    1       175       525
19    0         0         0
20    0         0         0
21    0         0         0
22    0         0         0
23    0         0         0
24    0         0         0
25    0         0         0
26    0         0         0
27    0         0         0
28    0         0         0
29    0         0         0
30    0         0         0
31    0         0         0
32    0         0         0
33    0         0         0
34    0         0         0
35    0         0         0
36    0         0         0

3 odd digits
1    0         0         0
2    0         0         0
3    1      3528      7056
4    0         0         0
5    3     10584     21168
6    0         0         0
7    6     21168     42336
8    0         0         0
9   10     35280     70560
10    0         0         0
11   15     52920    105840
12    0         0         0
13   18     63504    127008
14    0         0         0
15   19     67032    134064
16    0         0         0
17   18     63504    127008
18    0         0         0
19   15     52920    105840
20    0         0         0
21   10     35280     69720
22    0         0         0
23    6     21168     41328
24    0         0         0
25    3     10584     20160
26    0         0         0
27    1      3528      6468
28    0         0         0
29    0         0         0
30    0         0         0
31    0         0         0
32    0         0         0
33    0         0         0
34    0         0         0
35    0         0         0
36    0         0         0

4 odd digits
1    0         0         0
2    0         0         0
3    0         0         0
4    1     54450     81675
5    0         0         0
6    4    217800    324720
7    0         0         0
8   10    544500    806850
9    0         0         0
10   20   1089000   1593900
11    0         0         0
12   35   1905750   2737350
13    0         0         0
14   52   2822820   3963960
15    0         0         0
16   68   3680160   5015340
17    0         0         0
18   80   4303200   5623200
19    0         0         0
20   85   4530075   5638050
21    0         0         0
22   80   4197600   4910400
23    0         0         0
24   68   3500640   3803580
25    0         0         0
26   52   2599740   2599740
27    0         0         0
28   35   1686300   1541925
29    0         0         0
30   20    917400    752400
31    0         0         0
32   10    432300    316800
33    0         0         0
34    4    160380    102960
35    0         0         0
36    1     36795     20295

In each case, the third and fourth columns indicate counts, when the total of odd numbers on that line is combined with the eligible totals of ways of sums of even digits so that the overall total is less than 69.  It is in this stage that the separation of zero-containing even sequences from the rest is important.

Let's take the last line above to explain the entries in columns 3 and 4.  That line shows how many ways 4 odd digits totalling 36 can be combined with 8 even digits, in accordance with the rules, to form such a 12-digit number.

(If there had been more than one way for the odd numbers to add to the given value, as in the case of a total of 34, we would have had to multiply by that number of ways--in the case of 34, that would be 4, as 9997, 9979, 9799 and 7999.)

As the digits must not total more than 68, the eight even digits must not total over 68 - 36 = 32.

The ways that a set of eight even digits that include at least one zero can add to zero through 32 are (increments of 2):

1 1 2 3 5 6 9 11 14 16 19 20 23 23 24 23 23

The first digit must be odd, as the lowest (and therefore first) even digit is zero. Thereafter, any of the C(11,3) = 165 ways of arranging the remaining three odd digits together with the eight chosen even digits might be used.  This multiplies out to the 36795 shown in column 3 for this entry.

The ways that a set of eight even digits that do not include at least one zero can add to zero through 32 are (increments of 2):

0 0 0 0 0 0 0 0 1 1 2 3 4 5 7 8 10

This time any of the C(12,4) = 495 ways of arranging the four odd digits together with the eight chosen even digits might be used.  This multiplies out to the 20295 shown in column 4 for this entry.

All the entries in all the columns 3 and 4 for 3-, 6-, 9- and 12-digit numbers add up to the answer:

73,849,286 numbers that fit the pattern asked for.

DefDbl A-Z
Dim crlf\$, ct(64, 1, 8), oddct(36, 4), ctForLen(12), overtot

Form1.Visible = True

Text1.Text = ""
crlf = Chr\$(13) + Chr\$(10)

For a = 0 To 8 Step 2
For b = a To 8 Step 2
ab = a + b
If a = 0 Then
ct(ab, 0, 2) = ct(ab, 0, 2) + 1
Else
ct(ab, 1, 2) = ct(ab, 1, 2) + 1
End If
For c = b To 8 Step 2
For d = c To 8 Step 2
abcd = ab + c + d
If a = 0 Then
ct(abcd, 0, 4) = ct(abcd, 0, 4) + 1
Else
ct(abcd, 1, 4) = ct(abcd, 1, 4) + 1
End If
For e = d To 8 Step 2
For f = e To 8 Step 2
abcdef = abcd + e + f
If a = 0 Then
ct(abcdef, 0, 6) = ct(abcdef, 0, 6) + 1
Else
ct(abcdef, 1, 6) = ct(abcdef, 1, 6) + 1
End If
For g = f To 8 Step 2
For h = g To 8 Step 2
abcdefgh = abcdef + g + h
If a = 0 Then
ct(abcdefgh, 0, 8) = ct(abcdefgh, 0, 8) + 1
Else
ct(abcdefgh, 1, 8) = ct(abcdefgh, 1, 8) + 1
End If

Next
Next
Next
Next
Next
Next
Next
Next

For ndig = 2 To 8 Step 2
Text1.Text = Text1.Text & ndig & " of even digits:" & crlf
For z = 0 To 1
If z = 0 Then
Text1.Text = Text1.Text & "with leading zeros" & crlf
Else
Text1.Text = Text1.Text & "without leading zeros" & crlf
End If
tt = 0
For t = 0 To 64 Step 2
Text1.Text = Text1.Text & Str(ct(t, z, ndig))
tt = tt + ct(t, z, ndig)
Next
Text1.Text = Text1.Text & "    " & tt & crlf
Next
Text1.Text = Text1.Text & crlf
Next

For a = 1 To 9 Step 2
oddct(a, 1) = oddct(a, 1) + 1
For b = 1 To 9 Step 2
ab = a + b
oddct(ab, 2) = oddct(ab, 2) + 1
For c = 1 To 9 Step 2
abc = ab + c
oddct(abc, 3) = oddct(abc, 3) + 1
For d = 1 To 9 Step 2
abcd = abc + d
oddct(abcd, 4) = oddct(abcd, 4) + 1
Next
Next
Next
Next

For nOdddig = 1 To 4
Text1.Text = Text1.Text & nOdddig & " odd digits" & crlf
For t = 1 To 36
Text1.Text = Text1.Text & mform(t, "#0") & mform(oddct(t, nOdddig), "####0")
toteven = 0
For i = 0 To 68 - t
If i <= 64 Then
toteven = toteven + ct(i, 0, 2 * nOdddig)
End If
Next
expCt = oddct(t, nOdddig) * toteven * combi(3 * nOdddig - 1, nOdddig - 1)
Text1.Text = Text1.Text & mform(expCt, "#########0")
overtot = overtot + expCt
toteven = 0
For i = 0 To 68 - t
If i <= 64 Then
toteven = toteven + ct(i, 1, 2 * nOdddig)
End If
Next
expCt = oddct(t, nOdddig) * toteven * combi(3 * nOdddig, nOdddig)
Text1.Text = Text1.Text & mform(expCt, "#########0")
Text1.Text = Text1.Text & crlf
overtot = overtot + expCt
Next
Text1.Text = Text1.Text & crlf
Next

Text1.Text = Text1.Text & crlf & overtot & " done"

End Sub

Function mform\$(x, t\$)
a\$ = Format\$(x, t\$)
If Len(a\$) < Len(t\$) Then a\$ = Space\$(Len(t\$) - Len(a\$)) & a\$
mform\$ = a\$
End Function

Function combi(n, r)
c = 1
For i = n To n - r + 1 Step -1
c = c * i
Next
For i = 2 To r
c = c / i
Next
combi = c
End Function

 Posted by Charlie on 2016-05-24 16:06:42

 Search: Search body:
Forums (0)