S2T2

Jim Randell 4:36 pm on 13 May 2022 Permalink Reply
Tags: by: Andrew Skidmore ( 85 )   

• 

  Jim Randell 5:19 pm on 13 May 2022 Permalink | Reply

  We need to find a collection of digits from which the PIN and exactly 5 other rearrangements can be made. So we need there to be 6 different arrangements in total.

  Selections of digits with the same pattern (e.g. “three different digits”, “two pairs of digits”, which we might write as (1, 1, 1) and (2, 2)) will have the same number of arrangements of the digits. So in the following program, if a pattern produces a number of arrangements that is not 6, we abandon testing that pattern. (Another way to check a pattern would be to check that its multinomial coefficient is 6, see [@replit]).

  This Python program runs in 58ms. (Internal run time is 4.18ms).

  Run: [ @replit ]

  from enigma import (
    defaultdict, irange, nconcat, subsets, decompose, multiset, factor,
    seq_all_different as all_different, is_square_p, singleton, map2str, printf
  )
  
  # group numbers by the number of prime factors, subject to:
  # - a number cannot be prime
  # - a number cannot have a repeated prime factor
  def group(ns):
    d = defaultdict(list)
    for n in ns:
      fs = factor(n)
      # none of the numbers are prime
      if len(fs) == 1: return
      # none of the numbers has a repeated prime factor
      if not all_different(fs): return
      # record this number
      d[len(fs)].append(n)
    return d
  
  # n = number of digits in the PIN
  # k = number of different digits in the PIN
  for (k, n) in subsets(irange(1, 5), size=2, select="R"):
    # calculate repetitions of digits
    for rs in decompose(n, k, increasing=0, sep=0, min_v=1):
      # choose digits
      for ds in subsets(irange(1, 9), size=k):
        # allocate the digits
        m = multiset.from_pairs(zip(ds, rs))
        # the sum of the digits is a square number
        if not is_square_p(m.sum()): continue
        # calculate the number of arrangements
        ns = list(nconcat(*x) for x in subsets(m, size=n, select="mP"))
        # we need 6 arrangements
        if len(ns) != 6: break
        # group the numbers by the number of prime factors
        d = group(ns)
        if d is None: continue
        # check there are only two different numbers of factors
        if len(d.keys()) != 2: continue
        # and one of these corresponds to only one number
        pk = singleton(k for (k, vs) in d.items() if len(vs) == 1)
        if pk is None: continue
        # output solution
        PIN = singleton(d[pk])
        printf("PIN={PIN} {d}", d=map2str(d, arr="->", enc="[]"))
  

  Solution: The PIN is 1771.

  ---

  The PIN has a factorisation into 3 different primes: 1771 = 7 × 11 × 13.

  And the other 5 rearrangements of the digits all have factorisations into 2 different primes:

  1177 = 11 × 107
  1717 = 17 × 101
  7117 = 11 × 647
  7171 = 71 × 101
  7711 = 11 × 701

  LikeLike

• 

  GeoffR 3:09 pm on 15 May 2022 Permalink | Reply

  It looks as though the PIN number has to be three, four or five digits long.

  I thought a 3-digit pin would not give enough rearrangements and a 5-digit pin would give more than five rearrangements.

  I assumed only a four digit number, compose of two different digits, would give the requisite five rearrangements, as shown at the start of the code.

  # Assume only  a four-digit number made of two different
  # digits (A,B) can give five possible total rearrangements
  # of the PIN number
  # e.g. AABB, ABAB, ABBA, BAAB, BABA, BBAA
  
  from itertools import permutations
  from enigma import factor, is_square, is_prime
  
  # choose two non-zero digits for the four digit PIN
  for p1 in permutations('123456789', 2):
    a, b = p1
    # check sum of digits is a square
    if not is_square(2 * int(a) + 2 * int(b)):
       continue
    # form six numbers from two different digits
    n1 = int(a + a + b + b)
    n2 = int(a + b + a + b)
    n3 = int(a + b + b + a)
    n4 = int(b + a + a + b)
    n5 = int(b + a + b + a)
    n6 = int(b + b + a + a)
    # check all six numbers are not prime
    if all(not is_prime(x) for x in (n1, n2, n3, n4, n5, n6)):
      # find number of prime factors of the six numbers
      f1 = len(factor(n1))
      f2 = len(factor(n2))
      f3 = len(factor(n3))
      f4 = len(factor(n4))
      f5 = len(factor(n5))
      f6 = len(factor(n6))
      # check there are only two different numbers
      # of factors for the six numbers
      if len(set((f1, f2, f3, f4, f5, f5, f6))) == 2:
        # find the unique number of factors
        # to give the PIN number
        if f1 not in (f2, f3, f4, f5, f6):
          print(f"PIN = {n1}")
        elif f2 not in (f1, f3, f4, f5, f6):
          print(f"PIN = {n2}")
        elif f3 not in (f1, f2, f4, f5, f6):
          print(f"PIN = {n3}")
        elif f4 not in (f1, f2, f3, f5, f6):
          print(f"PIN = {n4}")
        elif f5 not in (f1, f2, f3, f4, f6):
          print(f"PIN = {n5}")
        elif f6 not in (f1, f2, f3, f4, f5):
          print(f"PIN = {n6}")
  
  
  
  

  LikeLike

  • 

    Jim Randell 3:32 pm on 15 May 2022 Permalink | Reply

    @GeoffR: Actually a 3-digit PIN consisting of 3 different digits will have the required 6 arrangements.

    LikeLike

• 

  GeoffR 3:34 pm on 15 May 2022 Permalink | Reply

  @Jim: Yes, I overlooked that when thinking of repeated digits

  LikeLike

• 

  Frits 1:12 pm on 17 May 2022 Permalink | Reply

  Based on GeoffR’s method.

    
  # assume only a four-digit number made of two different
  # digits (A,B) can give five other rearrangements of the PIN number
  # e.g. AABB, ABAB, ABBA, BAAB, BABA, BBAA
  #
  # or 
  #
  # the PIN number has 3 digits which are all different
  # resulting in 6 arrangements
  # e.g. ABC, ACB, BAC, BCA, CAB, CBA
   
  from itertools import permutations, combinations
  from enigma import factor, is_square
  
  # loop over three-digit and four-digit numbers
  for nd in [3, 4]:
    # choose non-zero digits for the nd-digit PIN
    for comb in combinations('123456789', 6 - nd):
      dgts = list(comb) if nd == 3 else list(comb * 2)
       
      # check sum of digits is a square
      if not is_square(sum(int(x) for x in dgts)):
        continue
        
      nums = [int(''.join(x)) for x in set(permutations(dgts))]  
      fs   = [factor(x) for x in nums]
   
      # none are prime and none have repeated prime factors
      if any(len(x) == 1 or len(x) != len(set(x)) for x in fs): continue
      
      n_fs  = [len(x) for x in fs]
      
      # check for exactly two different numbers of factors
      if len(set(n_fs)) == 2:
        # find the unique number of factors
        uniq = [i for i, x in enumerate(n_fs) if n_fs.count(x) == 1]
  
        if uniq:
          print(f"PIN = {nums[uniq[0]]}")
  

  LikeLike