wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> medium >> Another ten-digit number
(Message started by: BNC on Feb 13th, 2003, 5:26am)

Title: Another ten-digit number
Post by BNC on Feb 13th, 2003, 5:26am
Look at the number 321:
3 is divisible by 1
32 is divisible by 2
321 is divisible by 3

The mission is to create a similar 10-digit number. The number should contain each digit (0-9) exactly once.
The rule we're looking for is: for any n (n=1..10), the number composed of the n leftmost digits of the number is divisible by n.


Title: Re: Another ten-digit number
Post by towr on Feb 13th, 2003, 7:21am
so we have abcdefghij
a% 1 = 0
ab % 2 = 0
abc % 3 = 0
abcd % 4 = 0
abcde % 5 = 0
abcdef % 6 = 0
abcdefg % 7 = 0
abcdefgh % 8 = 0
abcdefghi % 9 = 0
abcdefghij % 10 = 0

j is obviously 0, so 9 digits left, that's only 362880 permutations, 9 constraints left to check.. Brute force could do it in less than a second probably..
I'll go try that.. :P

Title: Re: Another ten-digit number
Post by towr on Feb 13th, 2003, 8:13am

Code:
start :- permtest([1,2,3,4,5,6,7,8,9], []).

test([], _, _).
test([H|T], X, N):- X2 is 10*X + H, 0 is X2 mod N , N2 is N+1, test(T, X2, N2).

member([H|T], El, T):- H = El.
member([H|T], El, [H|T2]):- member(T, El, T2).

permtest([], L):-test(L, 0, 1), write(L), write('\n'), fail.
permtest(L, T):- member(L, El, RL), permtest(RL, [El|T]).


answer (hidden):
[hide][3,8,1,6,5,4,7,2,9,0][/hide]
...

Title: Re: Another ten-digit number
Post by BNC on Feb 13th, 2003, 8:22am
Yeah....brute force.... why didn't I think of that.... :P

You can get a bit more insight before using the computer.
- What can you say about the location of the "5"?
- Where are the even numbers?
- Can you find (using logic) the numbers next to "5"?


Title: Re: Another ten-digit number
Post by poseur on Feb 13th, 2003, 9:07am
You can figure out a lot by logic. [hide]
The 5 must be fifth and the 0 last.
The even digits must be in even positions.
The first, second, and third set of 3 digits must each add up to a number divisible by 3.
Therefore the 2 numbers next to the 5 must be 4 and 6.
That puts 2 and 8 in the 2nd and 8th positions in some order.
If the 8 was 8th then the previous digit would have to be an even number (4?8 and 6?8 are only divisible by 8 when the middle digit is also even), which we ruled out because the 7th digit must be odd, so the 8 is 2nd and the 2 is 8th.
The same reasoning says the 4 can't be 4th, so the 6 is 4th and the 4 is 6th.
So the 7th digit  is either 3 or 7 to make 4?8 divisible by 8.
The first and third digit, and the seventh and ninth digit must add up to 1 mod 3, so one pair gets the 3 and the other gets the 9.
So there are only 2 possibilities for the 9th digit and each of those has 2 possibilities for the 1st and 3rd digits to test out to reach the final answer. [/hide]


Title: Re: Another ten-digit number
Post by poseur on Feb 13th, 2003, 9:15am
oops, ignore that, I made one conclusion i shouldn't have.

Title: Re: Another ten-digit number
Post by towr on Feb 13th, 2003, 9:29am
the numbers next to five can be either [hide]2 and 8[/hide], or [hide]4 and 6[/hide] (not necessarily the latter), for the reason poseur allready stated, [hide]the first, second and last set of three has to be divisible by three[/hide].

Title: Re: Another ten-digit number
Post by poseur on Feb 13th, 2003, 9:31am
[hide]I should have considered 2 and 8 for the 4th and 6th positions, in which case:
The 2 must be 4th, the 8 6th (according to the 8 position test), forcing the 6 to come 8th and the 4 in 2nd.
But that's ruled out because the 7th digit would have to be a 9 (3 and 7 here would fail the 8 position test, and 1 can not be arranged to fit the 9 position test). That offers just 2 possibilities for the 7 position test, both of which fail. So 2 and 8 can be ruled out for the 4th and 6th positions after all. [/hide]

Title: Re: Another ten-digit number
Post by James Fingas on Feb 18th, 2003, 7:45am
I have a novel way of approaching this one (i.e. it's not just brute force):

Probably most of you know that for a number to be divisible by 3, the sum of its digits must be divisible by 3.

For a number to be divisible by 6, the sum of its digits must be divisible by 3 AND it must have a ones digit that is even. We could also say that the ones digit, plus four times the sum of the remaining digits is divisible by 6.

There are similar rules for every natural divisor. The rule for 7 goes like this: If the ones digit, plus the tens digit times 3, plus the hundreds digit times 2, plus the thousands digit times 6, plus the ten-thousands digit times 4, plus the hundred thousands digit times 5, plus the millions digit, plus the ten millions digit times 3, etc. is divisible by 7, then the number is divisible by 7.

We have a factor for each digit in the number, and then we multiply the factors by the digits and add, and if the result is divisible by our divisor, then the original number is too. Here are the factors for some small divisors:

1  : 1  0  0  0  0  0  0  0 ...
2  : 1  0  0  0  0  0  0  0 ...
3  : 1  1  1  1  1  1  1  1 ...
4  : 1  2  0  0  0  0  0  0 ...
5  : 1  0  0  0  0  0  0  0 ...
6  : 1  4  4  4  4  4  4  4 ...
7  : 1  3  2  6  4  5  1  3 ... (or 1  3  2 -1 -3 -2  1  3 ...)
8  : 1  2  4  0  0  0  0  0 ...
9  : 1  1  1  1  1  1  1  1 ...
10 : 1  0  0  0  0  0  0  0 ...
11 : 1 10  1 10  1 10  1 10 ... (or 1 -1  1 -1  1 -1  1 -1 ...)
12 : 1 10  4  4  4  4  4  4 ...

If you examine the factors, it is fairly easy to figure out how I got them ;) Anyways, the important point of this is that these factors can solve the problem for us! Here is how it works out:

1) a is divisible by 1
2) b is divisible by 2
3) a + b + c is divisible by 3
4) 2c + d is divisible by 4
5) e is divisible by 5
6) 4a + 4b + 4c + 4d + 4e + f is divisible by 6
7) a + 5b + 4c + 6d + 2e + 3f + g is divisible by 7
8 ) 4f + 2g + h is divisible by 8
9) a + b + c + d + e + f + g + h + i is divisible by 9
10) j is divisible by 10

Obviously, the only candidate for j is 0.

With 0 gone, the only candidate for e is 5.

Looking at the form of 2,4,6, and 8, we can see that b,d,f, and h all need to be even. That leaves us with odd values for a,c,f, and i.

From 4, we can see that d needs to be equal to 2 (modulo 4). So d is either 2 or 6.

From 8, and knowing that f is even, we can see that h needs to be 2 or 6 (modulo 8 ), so if d=2, h=6, and if d=6, h=2.

Continuing:[hide]
From 6, and knowing that a+b+c is divisible by 3, e is 5, and d is either 2 or 6, we know that either 8 + 20 + f is divisible by 6 (f=2 or f=8 ) or 24 + 20 + f is divisible by 6 (f=4 or f=10). Therefore, if d is 2, then f is 8, and if d is 6, then f is 4.

9 will be true no matter what, since 1+8 + 2+7 + ... + 9 is divisible by 9.

From 3, and knowing that d is either 4 or 8, then if b=4, a+c modulo 3 is equal to 2. In that case, both of a and c will be from {1,7}. If b=8, then a+c modulo 3 is 1, so one of a or c is from the set {1,7}, and the other is from the set {3,9}.

From 8, we know that if g mod 4 is congruent to 1, then h is 6, and if g mod 4 is congruent to 3, then h is 2. Therefore, if d=2, then g=1 or g=9, and if d=6, g=3 or g=7.

From the two possibilities for d, and 7, if d=2, then (5b+6d+2e+3f)=66. Therefore, (a+4c+g)%7 = 4. If d=6, then (5b+6d+2e+3f)=98. Therefore, (a+4c+g)%7 = 0.

If d=2, a and c will contribute a+4c modulo 7, which will be either (1+4*7)=29%7=1, or (7+4*1)=11%7=4. In the first case, g must be 6, which it cannot be, and in the second, g must be 0 or 7, which is also not allowed. So d cannot be 2.

Therefore, d=6, b=8, f=4, h=2, and g=3 or g=7. One of a and c is from {1,7}, and the other is from {3,9}.

If g=3, then a+4c is congruent to 4 modulo 7. If c=1, then a=7, which is impossible because a must be from {3,9}. If c=7, then a=4, which is impossible, because 4 is taken. If c=9, then a=3, which is impossible, because a must be from {1,7}. Therefore, g cannot be 3, and so g=7.

One of a and c is 1, and the other is from {3,9}. If a=1, then 4c%7 = 6, which is impossible for integer c. If c=1, then a%7=3, which is possible, giving a=3.

Therefore, our only possibility is: 3816547290
Yo! Check it out! 8)[/hide]



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board