Enigmatic Code

Programming Enigma Puzzles

Enigma 1258: Not so secret

From New Scientist #2414, 27th September 2003 [link]

George’s supposedly secret four-digit PIN code is the product of five different prime numbers. It is also the product of the ages of Fred, George and Herb. George’s age is the average of the other two. Only one of the trio is a teenager.

What is the PIN code?

[enigma1258]

Advertisements

13 responses to “Enigma 1258: Not so secret

  1. Jim Randell 4 February 2015 at 8:07 am

    Programmatically we can examine all 4-digit numbers, look for ones with 5 distinct prime factors, and then assign them to ages to fit the conditions (which is how I wrote my first program). This Python program takes a more efficient approach. It runs in 34ms.

    from enigma import irange, factor, printf
    
    # suppose F < G < H
    #
    # G is the average of F and H so H = G + (G - F)
    #
    # and PIN = FxGxH is 4-digit
    
    for F in irange(1, 19, step=2):
      # factors of F must be distinct
      f = factor(F)
      if len(set(f)) != len(f): continue
      for G in irange(F + 1, 50):
        H = G + (G - F)
        PIN = F * G * H
        if PIN < 1000: continue
        if PIN > 9999: break
        # exactly one of them is a teenager
        if sum(1 for x in (F, G, H) if 12 < x < 20) != 1: continue
        # factors of F, G, H must be 5 distinct primes
        g = factor(G)
        h = factor(H)
        fs = f + g + h
        if not(len(set(fs)) == len(fs) == 5): continue
    
        printf("PIN={PIN} [F={F} {f}, G={G} {g}, H={H} {h}]")
    

    Solution: The PIN is 9570.

    The ages are 15, 22 and 29. Which have factors of (3, 5), (2, 11) and (29).

  2. arthurvause 4 February 2015 at 11:50 am

    Another variation

    """
    assume 2G=F+H
    Two of F,G,H are odd, so F and H have to be odd to make F+H even.
    H<=79 , otherwise, if H=81, Pin >= 3*81*(3+81)/2 = 10206 i.e. not 4 digits
    """
    from itertools import combinations
    from fractions import gcd
    
    teenagers = set(range(13,20))
    primes = set([2]+range(3,100,2))-set([n*(n+k) for n in (3,5,7) for k in xrange(0,100/n+1,2)])
    candidates = [p for p in primes if p<=79] + [p*q for p,q in combinations(primes,2) if p*q<=79]
    
    for F,H in combinations(candidates,2):
      if F%2 and H%2:                             # F and H have to be odd
        G=(F+H)/2
        if G in candidates:
          if len( set((F,G,H)) & teenagers )==1:  # exactly one of F,G,H is a teenager
            if len( set((F,G,H)) & primes ) == 1: # exactly one of F,G,H is prime
              if 1000<=F*G*H<=9999:               # pin is 4 digit
                if gcd(gcd(F,G),H)==1:            # F,G,H are composed of different primes
                  print F,G,H, ", Pin =",F*G*H
    
    • Brian Gladman 5 February 2015 at 3:16 pm

      HI Arthur,

      When the five prime factors are split among the three ages, they can split (1,1,3) or (1,2,2). How did you eliminate the (1,1,3) split?

      Although I can see why F and H can only have one or two prime factors, I am not sure why G cannot have three prime factors (c.f. the ‘G in candidates’ test and the only one of (F,G,H) is prime test).

    • Brian Gladman 5 February 2015 at 6:09 pm

      Here is a further development of Arthur’s approach that runs on Python 3. It uses my Python number theory library but can be modified relatively easily to use Jim’s enigma.py.

      from itertools import combinations
      from number_theory import factors, gcd, Primes
      
      # let ages be F, G = (F + H) / 2 and H with F < G < H - only one of
      # these has 2 as a factor and it must be G since F + H must be even
      # for G to be an integer; H must be less than 80, otherwise the PIN
      # will be > 10000; F and H both have one or two prime factors since
      # the lowest odd number with 3 distinct prime factors is 105
      
      odd_primes = set(Primes().list(3, 80))
      # candidates for lowest and highest ages (both must be odd)
      candidates = (odd_primes | 
          set(p * q for p, q in combinations(odd_primes, 2) if p * q < 80))
      
      # try all combinations for the lowest and highest ages
      for F, H in combinations(candidates, 2):
        # check that the middle age (F + H) / 2 is even and has
        # at most two odd prime factors
        q, r = divmod(F + H, 4)
        if not r and q in candidates:
          # compile the ages and the PIN
          ages, pin = set((F, 2 * q, H)), 2 * F * q * H
          # check for only one teenager
          if len(ages & set(range(13, 20))) == 1:
            # check for a 4 digit PIN and ages that are all coprime      
            if 1000 < pin < 10000 and gcd(*ages) == 1:
              # check for a PIN with exactly five prime factors
              f = tuple(factors(pin))
              if len(f) == len(set(f)) == 5:
                print('PIN = {}, ages = {}'.format(pin, tuple(sorted(ages))))
      
  3. geoffrounce 4 February 2015 at 1:40 pm
    from enigma import factor
    from itertools import permutations
    
    def isprime(n): 
        for x in range(2, int(n**0.5)+1): 
            if n % x == 0: 
                return False 
        return True
    
    for pin in range(9999,999,-1):
        cnt = 0
        f = factor(pin)
        s = set(f)
        if len(set(s))== 5 and all (isprime(x) for x in  s):
          for p in permutations(s):
            F,G,H = p[0]*p[1], p[2]*p[3], p[4]
            if G == (F+H)/2:
              if F in range(13,20): cnt += 1
              if G in range(13,20): cnt += 1
              if H in range(13,20): cnt += 1
              if cnt == 1:
                print('Pin={}, Fred={},George={},Herb={}'.format(pin,F,G,H))
    
    • arthurvause 5 February 2015 at 10:32 am

      Hi Geoff,
      Isn’t your solution making the assumption that the middle number is a composite? As it turns out, the middle number of the solution is composite, but I’m not sure whether that can be assumed in the search.

      • geoffrounce 5 February 2015 at 2:19 pm

        Hi Arthur, Two can be a factor of only one of the three ages, and if it was a
        factor of either the lowest or highest age, the middle age wouldn’t be
        an integer. So, yes, the middle age has 2 as a factor, which makes it
        composite (it can’t be 2)

  4. Brian Gladman 4 February 2015 at 3:00 pm

    My, this one is popular! Mine is essentially the same as Jim’s.

    from itertools import count
    from number_theory import factors
    
    # the ages (a < b < c) are different primes or the product of
    # different primes, which means that 2 is a factor of only one
    # of them; since 2 * b = a + c, a and c must be odd and b even
    for a in range(1, 21, 2):
      for b in count(a + 1, 2):
        c = 2 * b - a
        # form the PIN such that 1000 <= PIN < 10000
        pin = a * b * c
        if pin >= 10000:
          break
        if pin >= 1000:
          # factor the PIN and look for five distinct prime factors
          f = tuple(factors(pin))
          if len(f) == len(set(f)) == 5:
            # check that only one is a teenager
            if tuple(12 < x < 20 for x in (a, b, c)).count(True) == 1:
              fs = 'PIN = {}, ages = {}, factors = {}'
              print(fs.format(pin, (a, b, c), f))
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: