Author 
Topic: Number Theory (Read 775 times) 

anonymous
Guest

Find all positive integers n such that 0,1,...,n1 can be rearranged into a(0),a(1),...,a(n1) that satisfied the following condition: the numbers a(0),a(0)a(1),...,a(0)a(1)...a(n1) give different remainder when divided by n.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Number Theory
« Reply #1 on: Jul 7^{th}, 2003, 3:56am » 
Quote Modify

on Jul 7^{th}, 2003, 12:10am, anonymous wrote:the numbers a(0),a(0)a(1),...,a(0)a(1)...a(n1) 
 What's happening here? I doubt it's multiplication, but concattenation also gives problems for n>10, unless you do the numbers in base n. I really need a more precise description of what's happening.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



wowbagger
Uberpuzzler
Gender:
Posts: 727


Re: Number Theory
« Reply #2 on: Jul 7^{th}, 2003, 4:10am » 
Quote Modify

on Jul 7^{th}, 2003, 3:56am, towr wrote: I haven't looked into the problem, but the notation used without any further explanation implies multiplication (imho).


IP Logged 
"You're a jerk, <your surname>!"



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Number Theory
« Reply #3 on: Jul 7^{th}, 2003, 4:16am » 
Quote Modify

Yes, but then the answer is rather trivial, since you can't get different remainders for x and x*1, or x*0 and x*0*a(i)..a(j). So the answer is n=1,2.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



wowbagger
Uberpuzzler
Gender:
Posts: 727


Re: Number Theory
« Reply #4 on: Jul 7^{th}, 2003, 4:49am » 
Quote Modify

on Jul 7^{th}, 2003, 4:16am, towr wrote: How about n = 3? a(j) = (1, 2, 0) works, doesn't it?


IP Logged 
"You're a jerk, <your surname>!"



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Number Theory
« Reply #5 on: Jul 7^{th}, 2003, 4:56am » 
Quote Modify

hmm.. you're right.. So it just always has to start with 1 and end with 0..


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



anonymous
Guest

Yes, it's multiplication. This is an old Bulgarian problem. The official problem text can be found on problems.math.umr.edu, but I've forgotten which year.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Number Theory
« Reply #7 on: Jul 7^{th}, 2003, 5:21am » 
Quote Modify

so far I have 1: [0] 2: [1,0] 3: [1,2,0] 4: [1,3,2,0] 5: [1,2,4,3,0] 7: [1,3,4,6,2,5,0] 11: [1,7,6,4,5,2,3,8,10,9,0]

« Last Edit: Jul 7^{th}, 2003, 7:05am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Number Theory
« Reply #8 on: Jul 7^{th}, 2003, 7:39am » 
Quote Modify

Hmm... I think the solution is going to be {1,4,p where p is prime}. I can show that any composite number greater than 4 cannot do this, and I found an easy way to generate the sequence for any prime number. Now I just have to figure out why it works! Think on this: 13: 1,2,8,10,11,9,12,3,6,4,5,7,0 I also think the question would be more intuitive if we used the numbers 1..N rather than 0..N1. UPDATE: Yes, I think I can show that this method always works. So the numbers this works for are: {1, 4, all prime numbers}

« Last Edit: Jul 7^{th}, 2003, 8:22am by James Fingas » 
IP Logged 
Doc, I'm addicted to advice! What should I do?



DH
Guest

on Jul 7^{th}, 2003, 7:39am, James Fingas wrote: Think on this: 13: 1,2,8,10,11,9,12,3,6,4,5,7,0 I also think the question would be more intuitive if we used the numbers 1..N rather than 0..N1. UPDATE: Yes, I think I can show that this method always works. So the numbers this works for are: {1, 4, all prime numbers} 
 Yeap ... I found the same method and it's pretty easy to show that it always works.


IP Logged 



