1:21 AM
@Vepir Nothing much. Just going through my CS assignments.
Here's the whole question
Say we have a list A which has the integers from 1 to n and is unordered
Each time we parse the array we swap the \$A[i]\$ value with \$A[A[i]]\$
For some \$n\$ what is the maximum number of times that we have to parse the array to sort it?
Here is the pseudocode:
count=0
while(arr not sorted)
{
for(i=0 to arr_length)
{
temp=arr[i]
arr[i]=arr[arr[i]]
arr[arr[i]]=temp
}
count+=1
}
Peter ran a program in PARI and conjectured that we need at most \$\lfloor \log_2(n) \rfloor\$ iterations
The conjecture seems promising but we haven't been able to prove it

7 hours later…
8:09 AM
@Mathphile I would propose a modification of the conjecture: permutations whose longest cycle is \$k\$ need at most \$\lfloor\log_2(k)\rfloor\$ iterations.
Maybe this can be proven by observing the symmetric group of \$n\$-th order \$S_n\$.

8:22 AM
Or maybe we can prove this by induction if it holds that applying one iteration to a permutation, reduces its cycles by at least a half.

I mean this question :
-4

I understand that this is a question that sounds either out-of-topic or odd, but I felt an urge to ask. Has any mathematician proved (or at least tried to prove) the existence or absence of God ? NB : I am no atheist, but I felt like asking this.. the answer to this question is something interest...

@Vepir

@Vepir @Vepir what do you mean by longest cycle?

@Mathphile Every permutation is the product of disjoint cycles.

@Peter is this from abstract algebra?
Sadly my knowledge in abstract algebra is pretty much 0

I am not quite sure which topic it is.

8:43 AM
@Mathphile I mean Permutation Cycle
@Peter I would close it as off-topic. Maybe if the OP rigorously defined some "God axioms" we could talk about that, but even then the states: "...usually without controversy.", but all such proofs usually attract controversy because of the axioms that we start from in the first place.

@Vepir I guess that may be a better way to state it if you want to use group theoretical methods

@Mathphile is that a standard CS assigment or something more? The proof shouldn't be complicated if it was handed out as an assigment.

@Vepir this isn't part of any assignment of mine
I created this question from my own curosity

It reminds me of a similar problem to find the minimal time to sort an array using only swaps, which can be shown to be \$O(n \log n)\$.
It boils down to representing the permutation as the product of cycles
Btw the largest "near counter-example" to my latest question that I found so far is \$(2^{33}-33^2 ) \color{red}{+ 1}\$ can be represented as a sum of four \$a^b-b^a,1\lt a\lt b\$ numbers.

9:40 AM
@Mathphile For starters, the lower bound for "most iterations" holds because \$(2,3,4,\dots,n,1)\$ is sorted in exactly \$\lfloor \log_2(n) \rfloor\$ iterations (which is not hard to show).

10:01 AM
@Mathphile wait a minute,

If A[x]=y and A[y]=z, then when we reach A[x], we swap it with A[A[x]]=A[y], which results in A[x]=z and A[y]=y. That is, the A[A[i]] will get sorted every time or stay sorted if it already is, i.e. you can't swap the sorted index from a non-sorted index.

This means that if A[A[i]] is smaller than A[i], we will sort more than half elements in the iteration, and else, we will run across at least half many already sorted elements meaning that we will sort at least half.
Q.E.D. ?

10:13 AM
That is, for every x=1,2,3,...,n, we reach A[x] and swap it with A[A[x]]. That is,

- if A[x]=x, nothing changes

- if A[x]!=x, then wlog A[x]=y and A[y]=z which results in A[A[x]]=A[y]=y being sorted, and A[x]=z

That is, at every step, we either sort one element or do nothing. If we sort something, we have either A[A[x]]<A[x] or A[A[x]]>x. We want to find out what is the maximal number of times we can "do nothing". The worst case scenario is to "kill" elements in front us, i.e. assume A[A[x]]>A[x] (almost) always.

3 hours later…
12:43 PM
@Vepir Congrats on 10k

12:59 PM
Thanks, it was my 200th post.
(201th actually, there is one answer that will be undeleted in November, when the competition related to it ends. I didn't know the author took it from an ongoing competition until they addmited it when I asked for the source.)

1:51 PM
@Mathphile Hi, I continued my \$2020^n+3\$-search and PFGW resumed without a reason. Hope this does not mean anything bad for the calculation. Maybe, you doublecheck the range \$[14\ 100,15\ 400]\$