[Exercise] Russian lucky bus ticket

Joe

In Russia, bus tickets have 6 digits. A ticket is believed to be "lucky" if the sum of its first 3 digits equals the sum of its last 3 digits. For example:

• 132501 lucky
• 436922 lucky
• 873012 not lucky

The goal of the exercise is to calculate the number of lucky tickets.

(I did not come up with this problem, it is somewhat famous in mathematical circles. This blog post traces back the introduction of this problem to professor A. A. Kirillov, from University of Pennsylvania).

xterm

Cool exercise! I can think of many ways to deal with it that i'll write up tonight.

Meanwhile, here's a brute forced ugly one liner.

len([i for i in range(1,999999) 
       if sum(map(int,('%(#)06d' % {'#':i})[:3])) ==  
          sum(map(int,('%(#)06d' % {'#':i})[3:]))
])

Joe

Here's my first version. It's a little less brute-force-y than xterm's.

totsize = 6

def firsthalf(size=totsize/2, s=[]):
''' This function generates all the permutations of 0-9 digits repeated totsize/2 times'''
    if size == 0:
        return s

    if len(s) == 0:
        t = [ [x] for x in xrange(10)]
    else:
        t = [ i + [j] for i in s
              for j in xrange(10)]
    
    
    return firsthalf(size-1, t)


def luckynbs(size=totsize/2, s=firsthalf()):
''' This function will append 0-9 digits to the above generated list.
Each iteration will append one digit to the existing, filtering out all the wrong
cases as it detects them.
 - If the new digit makes the right sum greater than the left sum, it is directly dismissed
 - If the new digit makes the right sum so little than even filling the rest with 9s is too low than it is dismissed.
'''

    if size == 0:
        return s

    t = [ i + [j] for i in s for j in xrange(10)
          if sum(i[:totsize/2]) >= sum(i[totsize/2:])+j
          if sum(i[:totsize/2]) <= sum(i[totsize/2:])+j+(9*(size-1))]

    return luckynbs(size-1, t)

print len(luckynbs())

Also, I want to look into some calculation of the output without generating all the results. Any math wizz in the house?

yasamoka

Damn it rahmu, i was studying a bit just now, and saw your exercise. I wrote down the code on a piece of paper. Yes there is an easy way to do it without calculating all the numbers, and it involves only x^1/2 calculations, where x is the number of calculations for brute-force method. Will post my code now.

EDIT: Ok, here is the code. Written with the scripting language AutoIT:

a = number of digits
b = digit sum groups (say you have 6 digits, you need to add each 3 digits, you have 2 digit sum groups then)
c = number of digits to add up (=a/b)

$a = 6
$b = 2
$c = $a / $b

Dim $sum[9*$c + 1]
$d = 0

$f = 0
For $f = 0 to 10^$c - 1 Step 1
   $g = 1
   For  $g = 1 to StringLen(String($f)) Step 1
	  $d = $d + Number(StringRight(StringLeft(String($f),$g),1))
	  $sum[$d] = $sum[$d] + 1
	  $d = 0
   Next
Next

Dim $e
Dim $h
For $h = 0 to 9*$c Step 1
   $e = $e + ($sum[$h])^$b
Next

MsgBox(0,"Number of lucky tickets","The number of lucky tickets is: " & $e)

What this code does is:

1) Takes c, the number of digits to add up. Calculates the sum of digits of each of the numbers from 0 to 10^c - 1 (which is 999 for 3 digits), and adds to the elements of the array (sum). For example, if the sum is 16 for the number 835, then 1 is added to the element sum[16].

Taking cue from calculations in Probability, permutations, and the like in Mathematics, if there are x cases where the sum of the first 3 digits is y, then there is also the same number of cases for the last 3-digits. Considering that we want to calculate the total number of cases where sum1 = sum2, we square x. So the number of cases where sum1=sum2=x is x^2. We repeat for each sum (from 0 to 9*numberofdigits).

Joe

Found it!

def nbrperm(n):
    return len([(i, j, k) for i in xrange(10)
                for j in xrange(10)
                for k in xrange(10)
                if i + j + k == n])


print sum(nbrperm(x) * nbrperm(x) for x in xrange(28))

The sum of 3 digits is a number between 0 and 27. The function nbrperm calculates the number of permutations (i, j, k) such as i+j+k == n.

For each n such as 0 <= n <= 27, you can have nbrperm(n) permutation on each side, hence the squaring.

EDIT: reduce(operator.add) is the same thing as sum ... :-/

yasamoka

My God, I just posted that...

longbit

counter=0
for i in range(999):
    for j in range(999):
        if((i/100)+(i%100/10)+(i%10)==(j/100)+(j%100/10)+(j%10)):
           counter=counter+1
print counter

Yes... not java this time, i am refreshing my python knowledge so...

arithma

def nbrperm(n):
	if(n>(27)/2):
		n =27-n
	return (n+1)*(n+2)/2

print sum([ nbrperm(x) * nbrperm(x) for x in xrange(28)])

Joe

xterm wrote

len([i for i in range(1,999999) 
       if sum(map(int,('%(#)06d' % {'#':i})[:3])) ==  
          sum(map(int,('%(#)06d' % {'#':i})[3:]))
])

You're missing one solution: '000000'

arithma wrote

def nbrperm(n):
    if(n>(27)/2):
        n = 27-n
    return (n+1)*(n+2)/2

print sum([ nbrperm(x) * nbrperm(x) for x in xrange(28)])

This code returns 75376, the result should be 55251. I'm not sure what you're trying to do.

Side note: In Python the sum function can take a generator as an argument. It'd be better to replace your last line with:

print sum(nbrperm(x) * nbrperm(x) for x in xrange(28))

arithma

This should explain why I thought I am into something:

def nbr_perm(n):
    return len([(i, j, k) for i in xrange(10)
                for j in xrange(10)
                for k in xrange(10)
                if i + j + k == n])


def const_perm(n):
    if(n>(27)/2):
        n = 27-n
    return (n+1)*(n+2)/2

for i in xrange(28):
	print str(i) + ": " + str(nbr_perm(i))
	print str(i) + ": " + str(const_perm(i))

arithma

Here we go:

def const_perm(n):
  if(n>(27)/2):
    n = 27-n
  res = (n+1)*(n+2)/2	
  if (n>9):
    for x in xrange(10,n+1):
      res -= ((n-x)+1)*3
  return res

The real challenge would be to generalize the above to any digital system and for any number of digits.
I may be able to extend it manually for 4 digits for example, but I am not sure how to extend it automatically.

geek

A different solution using partitions:

n = 3; ds = Range[0, 9];
g[p_] := Multinomial[Sequence @@ Tally[p][[All, 2]]];
f[x_] := Total[g /@ IntegerPartitions[x, {n}, ds]];
f /@ Range[n Min[ds], n Max[ds]]
Total[#^2 & /@ %]

{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75, 75, 73, 69, 63, 55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
55252

One hundred twenty-eight binary digits? Sure.

n = 64; ds = Range[0, 1];

{1,64,2016,41664,635376,7624512,74974368,621216192,4426165368,27540584512,151473214816,743595781824,3284214703056,13136858812224,47855699958816,159518999862720,488526937079580,1379370175283520,3601688791018080,8719878125622720,19619725782651120,41107996877935680,80347448443237920,146721427591999680,250649105469666120,401038568751465792,601557853127198688,846636978475316672,1118770292985239888,1388818294740297792,1620288010530347424,1777090076065542336,1832624140942590534,1777090076065542336,1620288010530347424,1388818294740297792,1118770292985239888,846636978475316672,601557853127198688,401038568751465792,250649105469666120,146721427591999680,80347448443237920,41107996877935680,19619725782651120,8719878125622720,3601688791018080,1379370175283520,488526937079580,159518999862720,47855699958816,13136858812224,3284214703056,743595781824,151473214816,27540584512,4426165368,621216192,74974368,7624512,635376,41664,2016,64,1}
23951146041928082866135587776380551750

Sixteen hexadecimal digits? No problem, captain!

n = 8; ds = Range[0, 15];

{1,8,36,120,330,792,1716,3432,6435,11440,19448,31824,50388,77520,116280,170544,245149,346040,480412,656840,885390,1177704,1547052,2008344,2578095,3274336,4116464,5125024,6321416,7727520,9365232,11255904,13419709,15874952,18637348,21719288,25129114,28870424,32941428,37334376,42035079,47022544,52268744,57738544,63389804,69173680,75035144,80913744,86744569,92459384,97987900,103259144,108202894,112751144,116839564,120408920,123406419,125786944,127514144,128561344,128912240,128561344,127514144,125786944,123406419,120408920,116839564,112751144,108202894,103259144,97987900,92459384,86744569,80913744,75035144,69173680,63389804,57738544,52268744,47022544,42035079,37334376,32941428,28870424,25129114,21719288,18637348,15874952,13419709,11255904,9365232,7727520,6321416,5125024,4116464,3274336,2578095,2008344,1547052,1177704,885390,656840,480412,346040,245149,170544,116280,77520,50388,31824,19448,11440,6435,3432,1716,792,330,120,36,8,1}
395320344293410544

Notice that the cost can be halved because the list of order-dependent partitions count is symmetric.

Let's verify this approach by computing a few values. For n = {0, 1, 2, 3, 4, 5}, we get the following sequence: {1, 10, 670, 55252, 4816030, 432457640}. A quick look-up returns this sequence, with an equivalent problem, a summation formula, and a Mathematica goody!

Johnaudi

This seems like an interesting exercise.

C# below.

        public static uint getLuckyTickets()
        {
            uint _count = 0;
            for (int i = 0; i < 1000000; i++)
            {
                int[] _s = i.ToString("000000").ToCharArray().Select(t => Convert.ToInt32(t)).ToArray();


                _count += (_s[0] + _s[1] + _s[2] == _s[3] + _s[4] + _s[5]) ? 1u : 0u;
            }
            return _count;
        }