[seqfan] Re: Probability of identical sequences

[David Seal]

> This question came to me when I was trying this algorithm: Exchange n and 2n.
> Each term gets changed only once. 
> a(1)=2 and a(2)=1.
> a(3)=6 and a(6)=3
> etc.
> The sequence I got was 
> 2, 1, 6, 8, 10, 3, 14, 4, 18, 5, 22, 24, 26, 7, 30, 32, 34, 9, 38, 40, 42,
> 11, 46, 12, 50, 13
> 
> This sequence seems identical to A073675 (Rearrangement of natural numbers
> such that a(n) is the smallest proper divisor of n not included earlier but if
> no such divisor exists then a(n) is the smallest proper multiple of n not
> included earlier, subject always to the condition that a(n) is not equal to n.)

It is identical to A073675, assuming that you mean that you start with a(n) = n for all n and work upwards through values of n, swapping a(n) and a(2n) if neither of them has been swapped before. To see this, first note that when you get to n in that upwards scan, a(2n) has definitely not been swapped before, since the only two swaps it can possibly be involved in are of a(n) and a(2n) and of a(2n) and a(4n), and neither of those has been reached earlier in the upwards scan. So every term does get swapped - i.e. we end up with a(n) always equal to n/2 or 2n, never to n, and it is n/2 if a(n/2) was swapped with a(n) when n/2 was encountered earlier in the scan and 2n if it wasn't.

Then consider the exponent of 2 in the prime factorisation of n. If it is 0 (i.e. n is odd), n/2 wasn't encountered earlier in the scan because it isn't an integer, so a(n) = 2n. That implies that if it is 1, a(n/2) was swapped when n/2 was encountered earlier in the scan, so it isn't swapped again and a(n) = n/2. Which in turn implies that if it is 2, a(n/2) wasn't swapped when n/2 was encountered earlier in the scan (though it was even earlier when n/4 was encountered) and so a(n) = 2n. And so on, so that one can inductively prove that

a(n) = 2n if the exponent of 2 in the prime factorisation of n is even;
       n/2 if the exponent of 2 in the prime factorisation of n is odd.

But that's equivalent to what the formula section of A073675 says, so the two sequences are identical.

David


> On 13 January 2020 at 19:06 Ali Sada via SeqFan <seqfan at list.seqfan.eu> wrote:
> 
> 
> Hi Everyone, 
> 
> If we have two sequences, A and B, with different definitions. However, when we calculate k terms for each sequence, all of these terms are identical. If we can’t prove that definition A equals to definition B, what’s the probability that A and B are identical? Is it zero, since we are dealing with infinite terms? Or is it a function of k?  
> 
> This question came to me when I was trying this algorithm: Exchange n and 2n. Each term gets changed only once. 
> a(1)=2 and a(2)=1.
> a(3)=6 and a(6)=3
> etc.
> The sequence I got was 
> 2, 1, 6, 8, 10, 3, 14, 4, 18, 5, 22, 24, 26, 7, 30, 32, 34, 9, 38, 40, 42, 11, 46, 12, 50, 13
> 
> This sequence seems identical to A073675 (Rearrangement of natural numbers such that a(n) is the smallest proper divisor of n not included earlier but if no such divisor exists then a(n) is the smallest proper multiple of n not included earlier, subject always to the condition that a(n) is not equal to n.)
> 
> This example might not reflect my question above exactly. I am just trying to show why I asked the question.
> 
> Best,
> 
> Ali
> 
> 
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/