Can we prove this sequence is a permutation of positive integers?

[Ali Sada]

Hi everyone,

Hope all is well. 

Starting with a list of positive integers, L. At step n, swap L(n) with the least multiple of L(n)+1 that has not previously been used as a swap target. The sequence consists of the successive swap targets divided by 2.


• Step 1: L(1) = 1, L(1)+1 = 2, multiples of 2 → choose 2.
a(1) = 2/2 = 1.

• Step 2: L(2) = 1, L(1)+1 = 2,  2 is used → choose 4.
a(2) = 4/2 = 2.

• Step 3: L(3) = 3, L(3)+1 = 4,  4 is used → choose 8.
a(3) = 8/2 = 4, and so on.

1,2,4,3,6,5,8,10,15,7,12,9,14,11,16,20,18,21,30,22,33,13,24,36,26,17,28,35,45,25,32,40,34,19,54,27,38,23,60,44,42,39,66,46,69,29,48,72,50,55,52,65,81,63,56,70,58,31,90,80,62,37,64,96,99,77,68,51,105,49,108,78,74,41,76,57,117,75,120,88,82,43,84,126,86,47,132,92,135,150,138,94,141,53,144,168,98,91,100,125.

Best,

Ali 

[Elijah Beregovsky]

Hello Ali!

Thank you for this puzzle, I enjoyed solving it. I hope my proof is correct:

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16…

2,1,3,4,5,6,7,8,9,10,11,12,13,14,15,16…

2,4,3,1,5,6,7,8,9,10,11,12,13,14,15,16…

2,4,8,1,5,6,7,3,9,10,11,12,13,14,15,16…

2,4,8,6,5,1,7,3,9,10,11,12,13,14,15,16…

2,4,8,6,12,1,7,3,9,10,11,5,13,14,15,16…

2,4,8,6,12,10,7,3,9,1,11,5,13,14,15,16…

2,4,8,6,12,10,16,3,9,1,11,5,13,14,15,7…

…

The resulting sequence is a permutation of positive even integers iff

1. All targets of swaps are even
2. Every even number is a target of some swap

A swap target k*(L(n)+1) is always larger than the swap source L(n), thus, once a number is a target of a swap, its place in the list gets fixed. That also means that no swap source has been a swap target before, every swap source L(n)<=n, and the earliest a number n can be a swap source is at step n.

1. For all swap targets to be even it is enough for all swap sources to be odd. Let’s prove that is indeed the case by induction. 

• L(1)=1
• Suppose for all k<n L(k) is odd. 
• If L(n) has already been a swap source, it is odd by induction hypothesis. 
• If L(n) has never been a swap source, then L(n)=n, and n has never been a swap target. This implies n-1 has never been a swap source, therefore L(n-1)≠n-1. This is only possible if n-1 has been a swap target before, which by induction hypothesis means n-1 is even. Therefore L(n)=n is odd.

2. Suppose some even number Y never is a target of a swap. That means Y is sent forwards by swaps indefinitely: at infinite number of occasions L(n)=Y — an even source, which would violate (1).

Have a nice day!

Elijah

[Ali Sada]

Hi Elijah,

Thank you very much for your encouraging response. I really appreciate it. I have proposed the sequence  A398799. Can you please add your proof? 

Best,

Ali

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/4CCC3F31-A23F-4E3F-92E4-E87BDDB445E9%40gmail.com.