New Scientist Enigma 518 – Day of Reckoning
by Chris Maslanka
From Issue #1670, 24th June 1989
Nugel, Chancellor of the Exchequer of Planet-X, was to bring before the Prime Minister the results of his latest calculations of the planetary trade deficit. The calculation had proved awkward (but not as awkward, he thought ruefully, as trying to account for them was going to be) and he had asked the Minister for More Mathematics (who had attended the same school many moons ago) to process the figures in secret on his Megathon computer. The result arrived while the Chancellor was already waiting to be admitted to The Presence an he read the missive at once:
“A boring task, my dear Nugel, but an aesthetic result: your trade deficit in Zloots is represented by the smallest integer which is simultaneously half a perfect square, a third of a perfect cube, a fifth of a perfect fifth power and a seventh of a perfect seventh power.”
Seventh heaven was where Nugel wasn’t when close inspection of the letter failed to reveal the number. He felt let down by his ex-prefect. What on Planet-X was the old coot on about. With a sigh and resourceful to the last, he took out his battered Clackulator and set to work. In the background he could hear the voice of the only minister (Prime or Composite) to have survived 19 terms of office.
Can you find the trade deficit in Zloots (give your answer as a product of powers of prime numbers) before Nugel becomes the ex-Chancellor of the Exchequer?
Consider the power of 2 in the number. Since the number is a third of a cube, a fifth of a fifth power and a seventh of a seventh power, the power of two in the number must be a multiple of 3, 5 and 7, so the factor of 2 in the number is of the form \(2^{3\cdot 5\cdot 7\cdot a}\) for some integer \(a\).
Similar arguments for 3, 5 and 7 lead to the form of number as:\[\begin{align}N&=2^{3\cdot 5\cdot 7\cdot a} \cdot 3^{2\cdot 5\cdot 7\cdot b} \cdot 5^{2\cdot 3\cdot 7\cdot c} \cdot 7^{2\cdot 3\cdot 5\cdot d}\\&= 2^{105a} \cdot 3^{70b} \cdot 5^{42c} \cdot 7^{30d}\end{align}\]
for integer \(a\), \(b\), \(c\) and \(d\). Now:
1) \(2N\) is a square which means that:\[105a+1=0\mod2\implies a=1\mod2\]
2) \(3N\) is a cube which means that:\[70b+1=0\mod3\implies b=2\mod3\]
3) \(5N\) is a fifth power which means that:\[42c+1=0\mod5\implies c=2\mod5\]
4) \(7N\) is a seventh power which means that:\[30d+1=0\mod7\implies c=3\mod7\]Since we need the smallest value of \(N\), we hence obtain:\[N=2^{105}\cdot3^{140}\cdot5^{84}\cdot7^{90}\]
The Python interactive shell enables us to evaluate arithmetic with large integers quite easily.
Brian’s answer has near instantaneous evaluation in the Python shell when we enter:
>>> n = 2**105 * 3**140 * 5**84 * 7**90
>>> n
150462810922326152710290228433686961530697356776074449373600
141938371053848189980134027578261857302770024765419887333164
323078738017254430529707573248000000000000000000000000000000
000000000000000000000000000000000000000000000000000000
The number of digits in this large integer is also easily evaluated if we enter the following in the Python shell:
>>> print(len(str(n)))
234
We can also format the answer with thousands digit comma separators if we enter the following in the Python shell:
>>> print(“{:,d}”.format(n))
150,462,810,922,326,152,710,290,228,433,686,961,530,697,356,776,074,449,373,600,
141,938,371,053,848,189,980,134,027,578,261,857,302,770,024,765,419,887,333,164,
323,078,738,017,254,430,529,707,573,248,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000