S2T2

Jim Randell 8:11 am on 21 January 2021 Permalink Reply
Tags: by: Richard Furner   

• 

  Jim Randell 8:11 am on 21 January 2021 Permalink | Reply

  This Python program narrows down the candidate pairs until there is only one left, so if there is a solution this must be it.

  It runs in 49ms.

  Run: [ @replit ]

  from enigma import (subsets, irange, prime_factor, mgcd, unpack, printf)
  
  # check a number is _not_ an exact power
  check = lambda n, gcd=unpack(mgcd): gcd(e for (p, e) in prime_factor(n)) == 1
  
  # record totals and pairs of numbers
  ss = list((A + B, A, B) for (A, B) in subsets(irange(2, 8), size=2) if B % A != 0)
  
  # for each total that is not an exact power, add in B to the total
  while len(ss) > 1:
    ss = list((t + B, A, B) for (t, A, B) in ss if check(t))
  
  # output candidate solutions
  for (t, A, B) in ss:
    printf("A={A} B={B}")
  

  Solution: The two numbers are 6 and 8.

  To show that this is indeed a solution we need to show that (6 + 8k) can never be a non trivial exact power.

  To find a counter example, we are looking for for some positive integers k, a, n, where n ≥ 2, such that:

  6 + 8k = a^n
  2(3 + 4k) = a^n

  Clearly the LHS is a multiple of 2. So the RHS must also be a multiple of 2, so let: a = 2b.

  2(3 + 4k) = (2b)^n
  2(3 + 4k) = (2^n)(b^n)
  3 + 4k = 2^(n − 1)(b^n)

  Clearly the RHS is divisible by 2, but the LHS is not divisible by 2.

  So (6 + 8k) can never be an exact power of an integer.

  ---

  Most of the pairs drop out fairly quickly, but (3, 7) hangs in until we get to 2187 = 3 + 312×7 = 3^7.

  Leaving (6, 8) as the only remaining candidate.

  LikeLike

  • 

    Jim Randell 11:06 am on 21 January 2021 Permalink | Reply

    Here is a more efficient program that reuses the code I wrote for Enigma 1777 to generate powers in numerical order.

    Then for each power we remove pairs of numbers that can be used to make that power, until there is only a single pair remaining.

    Run: [ @replit ]

    from enigma import (Primes, irange, subsets, div, printf)
    
    # generate powers in numerical order (starting from 2 ** 2)
    def powers():
      base = { 2: 2 }
      power = { 2: 4 }
      maxp = 2
      primes = Primes(32, expandable=1).generate(maxp + 1)
      while True:
        # find the next power
        n = min(power.values())
        yield n
        # what powers are involved
        ps = list(p for (p, v) in power.items() if v == n)
        # increase the powers
        for p in ps:
          base[p] += 1
          power[p] = pow(base[p], p)
        # do we need to add in a new power?
        if maxp in ps:
          maxp = next(primes)
          base[maxp] = 2
          power[maxp] = pow(2, maxp)
    
    # possible pairs of numbers
    ss = list((A, B) for (A, B) in subsets(irange(2, 8), size=2) if B % A != 0)
    
    # consider increasing powers
    for n in powers():
      # remove any pairs that can make n
      ss = list((A, B) for (A, B) in ss if div(n - A, B) is None)
      if len(ss) < 2:
        printf("solution: {ss}")
        break
    

    LikeLike

  • 

    Frits 8:15 pm on 21 January 2021 Permalink | Reply

    Python 3.9 introduced multiple arguments version of math.gcd.

    Without imports.

    def prime_factors(n):
      i = 2
      factors = []
      while i * i <= n:
        if n % i:
          i = 3 if i == 2 else i + 2
        else:
          n //= i
          factors.append(i)
      if n > 1:
        factors.append(n)
        
      return factors
       
    def is_a_power(n):
      pf = prime_factors(n)
      if len(pf) < 2: 
        return False
        
      # occurences of digits  
      oc = {pf.count(x) for x in set(pf)}
      if mult_gcd(list(oc)) == 1:
        return False
      return True
    
    # calculate greatest common divisor of multiple numbers  
    def mult_gcd(li):
      if len(li) == 1:
        return li[0]
    
      for i in range(len(li) - 1):
        a = li[i]
        b = li[i+1]
        while b:
          (a, b) = (b, a % b)
        
        if a == 1: return a
        
        li[i+1] = a
      return a  
    
    # record totals and pairs of numbers
    ss = [(A + B, A, B) for A in range(2, 8) for B in range(A, 9) if B % A != 0]
     
    # for each total that is not an exact power, add in B to the total
    while len(ss) > 1:
      ss = list((t + B, A, B) for (t, A, B) in ss if not is_a_power(t))
      
    # output candidate solutions
    for (t, A, B) in ss:
      print(f"A={A} B={B}")  
    

    LikeLike