New Scientist Enigma 531 – Petits Fours
by Chris Maslanka
From Issue #1683, 23rd September 1989
“Four-armed is four-warmed,” declared Professor Torqui as he placed the petits fours in the oven in his lab at the Department of Immaterial Science and Unclear Physics.
“There are 4444 of them: a string of 4s. By which I mean, naturally enough, a number in base 10 all of whose digits are 4. Do you like my plus fours? (*) Speaking of 10s and plus fours, you can hardly be unaware of the fact that all positive integral powers of 10 (except 10^1, poor thing) are expressible as sums of strings of 4s.
The most economical way of expressing 10^2 as a sum of strings of 4s (that is, the one using fewest strings and hence fewest 4s) uses seven 4s:
10^2 = 44 + 44 + 4 + 4 + 4
The most economical means of expressing 10^3 as a sum of strings of 4s requires sixteen 4s:
10^3 = 444 + 444 + 44 + 44 + 4 + 4 + 4 + 4 + 4 + 4
“Now, it’s four o’clock, and just time for this puzzle: Give me some-where to put my cake stand and I will make a number of petits fours which is an integral positive power of 10 such that the number of 4s required to write it as a sum of strings of 4s in the most economical way is itself a string of 4s.”
What is the smallest number of petits fours Torqui’s boast would commit him to baking? (Express your answer as a power of 10).
(*) £44-44 from Whatsit Forum.
This teaser can be solved manually by considering the following sum:\[\begin{array}{rr}\text{value} & \text{digits}\\444….44 & n\\444….44 & n\\44….44 & n-1\\44….44 & n-1\\4….44 & n-2\\4….44 & n-2\\4….44 & n-2\\4….44 & n-2\\ \hline 999999996 & 9n-12 \\ \hline\\ \end{array}\]This shows that \(10^n – 4\) can be expressed as the sum of numbers using only the digit four with a total of \(9n -12\) fours. So \(10^n\) will use a total of \(9n-11\) fours. We are told that to find a power of 10 for which the number of fours used consists only of fours:\[9n-11=4(10^k-1)/9\] for an integer \(k\). Rearranging this gives:\[81n=4\cdot10^k + 95\]. We can solve this for \(n\) by reducing it modulo \(10^k\):\[n=81^{-1}\cdot 95\pmod{10^k}\]where we need the modular inverse of \(81\) modulo \(10^k\). For \(k=1,2\) and \(3\) this has the values \(1\), \(21\) and \(321\) respectively. Trialling these values shows that \(n=495\) for \(k=3\) with \(10^{495}\) requiring a total of 4444 fours.
Here are two Python solutions, one based on the analysis above and the other using a constructive approach: