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]
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 ]
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 ]
LikeLike
Frits 8:15 pm on 21 January 2021 Permalink |
Python 3.9 introduced multiple arguments version of math.gcd.
Without imports.
LikeLike