[News]

News: Welcome to The Oktave Forum.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

Here is another puzzle that I'm actually facing. I think I have the answer for this, but am not sure. Would like to hear more responses.

You are given a set of n numbers 0, 1, 2, ... n-1.

A k-sieve is defined as a line that starts from 0 and connects the k^th element after 0 and the k^th element further on and so on. If the sieve goes beyond n-1, it wraps around using the mod n operator. Whenever the sieve intersects itself, it is abandoned and the next free element is chosen to start the next sieve.

Hence, a 2-sieve over the sequence 0,1,2,3,4,5 looks like this: 0 -- 2 -- 4 -- 0, 1 -- 3 -- 5 -- 1.

A 2-sieve on the sequence 0,1,2,3,4,5,6 looks as: 0 -- 2 -- 4 -- 6 -- 1 -- 3 -- 5 -- 0.

A 3-sieve on the above looks as: 0 -- 3 -- 6 -- 2 -- 5 -- 1 -- 4 -- 0.

You see what I am getting at. No matter what sequence I try and what is the value of k for the sieve, I am getting perfect circles. A sieve is never intersecting itself anywhere else but at the starting number.

But can we prove this? Or refute this assertion with a counter example?

-Sri

[aditya]

aditya

aditya

Show aditya's last posts.

Show general stats for aditya.

• 
• Administrator
• Jr. Member
• Karma: 8
• Posts: 52

Let us take a k-sieve and assume that it intersects itself at x. Working backwards, it means that the path has reached x twice: once originally and once for the intersection. Both the starting points will be k steps away from x in the same direction. So both the points will be the same. It means the intersection never happened at x but it actually happened at x-k. But x-k will satisfy the same properties as x. The only condition when we get two different solutions is when the path starts at x itself; then there will be two unique points x and x-k. So the intersection will always happen at the starting position.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

...Both the starting points will be k steps away from x in the same direction....

This is where the modulo problem comes in isn't it? x can be reached from behind and from front after spilling over n and wrapping around the numbers. So it should also depend on n, in addition to k, I feel..

[aditya]

aditya

aditya

Show aditya's last posts.

Show general stats for aditya.

• 
• Administrator
• Jr. Member
• Karma: 8
• Posts: 52

...Both the starting points will be k steps away from x in the same direction....

This is where the modulo problem comes in isn't it? x can be reached from behind and from front after spilling over n and wrapping around the numbers. So it should also depend on n, in addition to k, I feel..

No it does not.

Because the numbers 1 to n-1 are on a circle and the k steps are counted on the circle. So, if you count back k steps from any point you'll land on a unique point.

It is independent of n.

[sshankarverma]

sshankarverma

sshankarverma

Show sshankarverma's last posts.

Show general stats for sshankarverma.

• 
• Newbie
• Karma: 2
• Posts: 2

AS I THINK.......
Let suppose we are forming a sieve of k and we have numbers 0,1,2,3,....................n-1,(n numbers)
the series will start from 0 and would be like
o.....k......2k.....
and suppose it exeeds at "ak" (ak>n) then the next number in the series will be ak-n,
The series would be now like
0....k......2k.............................ak-n.....ak-n+k...
but we know that   ak-n!=k,2k....... for any value of a,except ak-n=0, means its comes to it starting point.
the series willrotate like a circle.
again if we say that every numbers of the given number series does not appear in the sieve then it will continue in the same manner as
0.....k....................................ak-n......ak-n+k.........ak-n+2k.............
in this way the in between number be never be equls to any other number except when it comes to its starting point.
And every number of the given series will come in the sieve.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

but we know that   ak-n!=k,2k....... for any value of a,except ak-n=0, means its comes to it starting point.
the series will rotate like a circle.

The first part is ok, that ak-n != k, 2k, etc. but it could be any remainder as well when n is not divisible by k.

In any case, I think the previous explanation by Aditya is valid; I have not been able to find any caveat in it as yet. I have another proof, which I'll give later on.

-Sri

[sshankarverma]

sshankarverma

sshankarverma

Show sshankarverma's last posts.

Show general stats for sshankarverma.

• 
• Newbie
• Karma: 2
• Posts: 2

yes i know that it may be any number as n is not divisble by k.Remainder may be any nuber but again
 let the remainder be b
then agin the series will continue like
b.....b+k..... and so on  and it will not take any value from the upper series as b,b+k...... != 0,k ,2k......
so it will take different value from the other sieve .
and this will continue untill each number occures in any sieve.