Est. 1998 — 27 years of woodworking knowledge
Tuesday puzzle
Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number should satisfy the following requirements:
a. The number should be divisible by 9.
b. If the most right digit is removed, the remaining number should be divisible by 8.
c. If then again the most right digit is removed, the remaining number should be divisible by 7.
d. etc. until the last remaining number of one digit which should be divisible by 1.
Re: Tuesday puzzle
Do algorithmic solutions count?
It was a fun recursive programming exercise. I'll hold off on the output to give others a chance.
Re: Tuesday puzzle
Yes, the algorithm should enable others to find it also.
Re: Tuesday puzzle
Here is the code in C#. Should not be hard to convert to C, C++, Java etc.
using System;
namespace NumberGenerator
{
class Program
{
// recursive function to generate a 9 digit number such that:
// 1) each digit is unique
// 2) each left justified substring is divisible by the number of digits in it
//
// We start with an empty 'baseString' at level 1.
// At each level, we attempt to append a digit to the baseString such that it meets the constraints.
// If we are successful in adding a digit, we call the function recursively to try the next level.
// If we succeed in adding a digit at level 9, we are done!
//
static bool generate(int level, string baseString)
{
for (int digit = 1; digit <= 9; digit++) // Test each of the nine possible digits at each level
{
if (!baseString.Contains(digit.ToString())) // Make sure digit has not been used already
{
string newBaseString = baseString + digit.ToString(); // append the new digit
int newBaseInteger = int.Parse(newBaseString); // convert the newBaseString to an integer for testing
if (newBaseInteger % level == 0) // Check that the newBaseNumber is evenly divisible by 'level'
{
if (level == 9) // We have 9 digits. We are done!
{
Console.WriteLine("Answer: " + newBaseString); // Print result
Console.WriteLine(newBaseString + " / " + level + " = " + (newBaseInteger / level)); // Show work at each level
return true;
}
if (generate(level + 1, newBaseString)) // not done yet. Make a recursive call to generate the next level
{
Console.WriteLine(newBaseString + " / " + level + " = " + (newBaseInteger / level)); // Show work at each level
return true;
}
}
}
}
return false; // no valid solution with this baseString
}
static void Main(string[] args)
{
generate(1, ""); // Call at level one with an empty string
Console.ReadLine(); // wait for CR to exit.
}
}
}
Sorry for the formatting
The indentation got lost in the posting. Anyone know how to post formatted text?
Use...
You can preserve the formatting by surrounding the text with
< pre > </pre>
Human algorithm
I see this one is solved via computer. When I solved it with pencil and paper, I had to do a little trial and error, but observing some facts allowed me to reduce the number of possibilities from 9! to about 1/2 dozen.
I numbered the digits d1 - d9, and observed the following:
1) Even numbered digits were even, and odd-numbered ones were odd.
2) d1+d2+d3 was a multiple of 3, as were d4+d5+d6 and d7+d8+d9
3) d5 is 5
4) d4 and d8 must be 2 and 6 (in either order), since the preceding digit is odd, and d3d4 and d7d8 are both multiples of 4
5) (2), (3), and (4) => d4d5d6 = 258 or 654.
6) if 258, then d7d8d9 is 963, and d1d2d3 is 147 or 741. Neither satisfies the divisibility by 7 test on the first 7 digits.
7) So d4d5d6 = 654.
All of the above only allowed a few possibilities for the other digits, and I tested possibilities with the divide by 7 test, and came up with an answer whose prime factorization is 3^2*109*1000667
Re: Human algorithm
I agree with the algorithm, but the factorization does not work for me. (assuming that 3^2 is three squared;-) with your numbers unless I am reading something wrong. I would get factors of:
3^2 * 109 * 389047
Answer
The answer is 381654729. Thanks for playing and for the two that got it.
Re: Human algorithm
Whoops. Looks like I can't divide by 7 in my head too well. Using a calculator shows my answer to be wrong. I agree with yours.
Re: Answer
"for the two that got it"
Make that "one" :-(
Re: Answer
We will call this 1/2 credit. You had the algorithm and everything else down. You just did like I do sometimes and got 2+2=5 or something like that ;-)