Brain-Teaser 683: Powerless
From The Sunday Times, 18th August 1974 [link]
I have here two positive single figure numbers, each less than 9. Neither is a factor of the other. I add the larger number to the smaller.
Then, to that total I again add the original larger number, and to the new total I again add the original larger number and may, if I like, continue this process indefinitely, but never shall I obtain a total which is a “power” of any whole number whatsoever.
What are my two numbers?
This puzzle was included in the book Brain Teasers (1982, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.
[teaser683]
Frits and 
GeoffR and 
Hugh Casement, 
John Crabtree, and 
Tony Brooke-Taylor, and 2 others are discussing. 
Geoff, 
Jim Randell 8:11 am on 21 January 2021 Permalink |
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: [ @repl.it ]
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:
Clearly the LHS is a multiple of 2. So the RHS must also be a multiple of 2, so let: a = 2b.
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 |
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: [ @repl.it ]
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}") breakLikeLike
Frits 8:15 pm on 21 January 2021 Permalink |
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