S2T2

Jim Randell 9:35 am on 31 October 2021 Permalink Reply
Tags: by: R. Crosbie-Hill   

• 

  Jim Randell 9:36 am on 31 October 2021 Permalink | Reply

  Again, the advent of computers means that this problem can be tackled with a very simple program, that constructs all possible rearrangements of the digits, and counts those that are divisible by 11.

  The following Python program runs in 56ms.

  Run: [ @replit ]

  from enigma import (subsets, nconcat, icount, printf)
  
  # find numbers that are multiples of 11
  def m11s(ds):
    for ss in subsets(ds, size=len, select="P"):
      n = nconcat(ss)
      if n % 11 == 0:
        yield n
  
  for ds in [(1, 2, 3, 4, 5), (1, 2, 3, 4, 5, 6), (1, 2, 3, 4, 5, 6, 7)]:
    t = icount(m11s(ds))
    printf("{ds} -> {t}")
  

  Solution: (a) 0; (b) 0; (c) 576.

  We can be a bit cleverer though.

  One test for divisibility by 11 is to calculate the alternating sum of the digits (i.e. 1st digit − 2nd digit + 3rd digit − 4th digit + …), and if this is divisible by 11, then the original number is divisible by 11. And it also means that any number formed by rearrangement of the digits, providing the digits originally in odd positions are still in odd positions (and the digits in even positions are still in even positions), will also be divisible by 11.

  The following Python program is a longer, but more efficient method of counting the numbers. (And indeed the internal runtime decreases from 9.03ms to 151µs).

  from enigma import (subsets, factorial, printf)
  
  # count the number of multiples of 11 that can be made from digits ds
  def count_m11s(ds):
    r = 0
    t = sum(ds)
    # consider the 2nd, 4th, ... digits
    n = len(ds)
    k = n // 2
    for ss in subsets(ds, size=k):
      if (t - 2 * sum(ss)) % 11 == 0:
        r += factorial(k) * factorial(n - k)
    return r
  
  for ds in [(1, 2, 3, 4, 5), (1, 2, 3, 4, 5, 6), (1, 2, 3, 4, 5, 6, 7)]:
    t = count_m11s(ds)
    printf("{ds} -> {t}")
  

  In the case of the digits (1, 2, 3, 4, 5, 6, 7), we find that the following numbers in (odd) and (even) positions will form multiples of 11:

  (2, 3, 4, 5) + (1, 6, 7)
  (1, 3, 4, 6) + (2, 5, 7)
  (1, 2, 5, 6) + (3, 4, 7)
  (1, 2, 4, 7) + (3, 5, 6)

  Each collection of digits contributes factorial(4) × factorial(3) = 144 numbers to the total.

  So the answer is: 4 × 144 = 576.

  LikeLike

• 

  GeoffR 12:37 pm on 31 October 2021 Permalink | Reply

  from itertools import permutations
  
  cnt5, cnt6, cnt7 = 0, 0, 0
  
  # 5 consecutive digits - divisibility by 11
  for p1 in permutations((1,2,3,4,5)):
      a,b,c,d,e = p1
      num1 = 10000*a + 1000*b + 100*c + 10*d + e
      if num1 % 11 == 0: cnt5 += 1
  
  print('5 digits divisibility count = ', cnt5)
  
  # 6 consecutive digits - divisibility by 11
  for p2 in permutations((1,2,3,4,5,6)):
      a,b,c,d,e,f = p2
      num2 = 100000*a + 10000*b + 1000*c + 100*d + 10*e + f
      if num2 % 11 == 0: cnt6 += 1
  
  print('6 digits divisibility count = ', cnt6)
  
  # 7 consecutive digits - divisibility by 11
  for p3 in permutations((1,2,3,4,5,6,7)):
      a,b,c,d,e,f,g = p3
      num3 = 1000000*a + 100000*b + 10000*c + 1000*d + 100*e + 10*f + g
      if num3 % 11 == 0: cnt7 += 1
  
  print('7 digits divisibility count = ', cnt7)
  
  # 5 digits divisibility count =  0
  # 6 digits divisibility count =  0
  # 7 digits divisibility count =  576
  
  

  LikeLike