Author |
Topic: Another ten-digit number (Read 2175 times) |
|
BNC
Uberpuzzler
Gender: 
Posts: 1732
|
 |
Another ten-digit number
« on: Feb 13th, 2003, 5:26am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Another ten-digit number
« Reply #1 on: Feb 13th, 2003, 7:21am » |
Quote Modify
|
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.. 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Another ten-digit number
« Reply #2 on: Feb 13th, 2003, 8:13am » |
Quote Modify
|
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):
[3,8,1,6,5,4,7,2,9,0]
...
|
| « Last Edit: Feb 13th, 2003, 8:14am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Another ten-digit number
« Reply #3 on: Feb 13th, 2003, 8:22am » |
Quote Modify
|
Yeah....brute force.... why didn't I think of that....
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"?
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
poseur
Guest
|
|
Re: Another ten-digit number
« Reply #4 on: Feb 13th, 2003, 9:07am » |
Quote Modify
 Remove
|
You can figure out a lot by logic.
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.
|
|
IP Logged |
|
|
|
poseur
Guest
|
|
Re: Another ten-digit number
« Reply #5 on: Feb 13th, 2003, 9:15am » |
Quote Modify
Remove
|
oops, ignore that, I made one conclusion i shouldn't have.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Another ten-digit number
« Reply #6 on: Feb 13th, 2003, 9:29am » |
Quote Modify
|
the numbers next to five can be either 2 and 8, or 4 and 6 (not necessarily the latter), for the reason poseur allready stated, the first, second and last set of three has to be divisible by three.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
poseur
Guest
|
|
Re: Another ten-digit number
« Reply #7 on: Feb 13th, 2003, 9:31am » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Another ten-digit number
« Reply #8 on: Feb 18th, 2003, 7:45am » |
Quote Modify
|
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:
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! 
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print