So, the problem was to find a number that is one more than seventeen times the total of its digits.
There's no simple analytical solution, as it's a multi-variable problem. For example, if the solution has three digits a, b and c, then:
17(a + b + c) + 1 = 100a + 10b + c
... which simplifies to the Diophantine equation ...
83a -7b - 16c = 1
... and you could construct similar equations for any assumed number of digits. Generally, linear Diophantine equations have an infinite number of solutions. For example:
if {a, b, c} satisfy 83a -7b - 16c = 1
then so do {a + 7k, b+83k, c} where k is any integer
But this may not be the case when there are further restrictions; in the example above, for instance, the variables all have to be in the range 0-9.
There are methods for tackling equations of this format - see Extended Euclidean Algorithm - but I'm not sufficiently au fait with number theory to try that route. So it looked at first glance as if enumeration of cases would be necessary, trying all numbers of the form 1 modulo 17 (that is 18, 35, 52, ...). It could be a long task if the number is large, but it's easily programmed in a maths package; I still use my old copy of Derive 5. However, number-crunching puzzles is a bit of a last resort.
Then it occurred to me that the solution ...
n = 17 * (digit sum of n) + 1
... might be amenable to an iterative process: seeding the formula with an assumed digit sum, then using the answer to make a new seed, and so on, iterating until a stable result appears (or it goes cyclic). Furthermore the format suggested to me that the whole thing might be cyclic modulo 17, so only seeds up to 16 needed trying. So:
1: 18, 154, 171, 154 ... gone cyclic
2: 35, 137, 188, 290, 188 ... gone cyclic
3: 52, 120, 52 ... gone cyclic
4: 69, 256, 222, 103, 69 ... gone cyclic
5: 86, 239, 239 ... stable solution.
And there it is, far sooner than I'd expected: 239 = 17*(2+3+9) + 1
From the stated terms of the puzzle, I assume 239 is a unique solution. But how do we know? It leaves me wondering if there's a more rigorous and/or more efficient way of getting to the answer, and of showing that it's unique.
At the very least, it can be assumed there would be a finite number of solutions, as number size rapidly outstrips the sum of its digits (for a n-digit number, the order of magnitude increases as 10^n, while the maximum digit sum is 9n).
Iteration, by the way, is an immensely powerful tool for some problems virtually impossible to solve in other ways. I knew of it as a standard mathematical procedure for finding roots to equations, but Douglas Hofstadter's book Metamagical Themas introduced me to the idea of using it for problems that don't involve continuous functions. Hofstadter refers to its use for creating "self-enumerating pangrams", like this example by Lee Sallows.
This pangram tallies five As, one B, one C, two Ds, twenty-eight Es, eight Fs, six Gs, eight Hs, thirteen Is, one J, one K, three Ls, two Ms, eighteen Ns, fifteen Os, two Ps, one Q, seven Rs, twenty-five Ss, twenty-two Ts, four Us, four Vs, nine Ws, two Xs, four Ys, and one Z.
The problem is to find the right numbers so that the sentence is correctly self-referential. To produce the one above, Sallows used dedicated combinatorial hardware, and offered a challenge that no-one would be able to find a self-enumerating pangram beginning "This computer-generated pangram contains ..." within ten years.
In fact it was found quite rapidly by Larry Tesler, using an iterative method. It turns out that there is no need to slog through the entire search space for all 26 variables. Remarkably, you can start out with random seed values - "one A, two Bs, three Cs ..." or whatever - and iterate as I did with the Mindbender puzzle. Not all seed sets work; the iteration will get stuck in a loop. But many do converge on a solution.
.
Addendum: Felix Grant at The Growlery just posted a response - The quick'n'dirty approach to puzzles - describing a spreadsheet solution to the Mindbender problem which, whatever its level of elegance may be, highlights the sheer computational power available nowadays. It took a few seconds to get a solution - I remember using a Sinclair ZX81 to do similar puzzles from PC Plus in the late 1980s. Something like this would have taken hours, even with pre-analysis to reduce the search space.
Addendum 2: Following Felix and Dr C's lead, I also tried computing and graphing a table.
Let f(n) = 17*(digitsum)+1
For three digits, the function in Derive is:
f(n) := 17·(MOD(n, 10) + MOD(FLOOR(n/10), 10) + MOD(FLOOR(n/100), 10)) + 1
Now plot n-f(n) against n.
Interesting pattern. It shows, empirically at least, that the only possible solution(s) can lie between n=100 and n=300. After that, n permanently overtakes f(n).
- Ray
No comments:
Post a Comment