[seqfan] Re: a(n)th term is twice a(n)

[Hagen von Eitzen]

Jack Brennen schrieb:
> I assume that you're not allowing repeats in the sequence...
>
> It appears that the sequence repeats the pattern:
>
> a(6x) = 6x+1
> a(6x+1) = 12x+2
> a(6x+2) = 12x+4
> a(6x+3) = 6x+5
> a(6x+4) = 12x+8
> a(6x+5) = 12x+10
>
> with only a sparse set of exceptions...
>
> All but three of the exceptions fit this pattern:
>
> a(6*2^n) = 12*2^n
> a(6*2^n+1) = 6*2^n+2
> a(9*2^n) = 18*2^n
> a(9*2^n+1) = 9*2^n+2
>
> And three small exceptions seem to complete the sequence:
>
> a(3) = 1
> a(5) = 6
> a(7) = 9
>   
And here's a proof of that observation (written ad hoc with probably a 
few case distinctions too many):

Let  a  be the sequence defined by Eric (i.e. the lexically first 
injective map a:N->N with a(a(n))=2a(n) ) and b the sequence defined by 
Jack, i.e. for n >= 9 we have
(i)   b(n) = 2*n if n = 3*2^k or n = 9*2^k or n = 2 (mod 3) or ( n = 1 
(mod 3)  and (n-1)/3 has an odd divisor >3)
(ii)  b(n) = n + 1 if n = 3*2^k+1 or n = 9*2^k + 1 or  (n = 0 (mod 6) 
and n/3 has an odd divisor >3)
(iii) b(n) = n + 2 if n = 3 (mod 6)
Note that each n >= 9 is covered exactly once.

If  b(n) = 2n = m+1 = b(m) then m is odd, hence m = 3*2^k + 1 or m = 
9*2^k + 1, hence n = 3*2^(k-1) + 1 or n = 9*2^(k-1) + 1; in both cases n 
= 1 mod 3, hence (n-1)/3 = 2^(k-1) or = 3*2^(k-1); since this has no odd 
divisor > 3, we cannot have b(n) = 2n.
If  b(n) = 2n = m+2 = b(m) then m = 3 (mod 6), hence m+2 odd -- 
contradiction
If  b(n) = n+1 = m+2 = b(m) then m = 3 (mod 6) hence n = 4 (mod 6); this 
is only possible with n = 9*2^0 + 1 = 10, implying m = 9, but then b(m) 
= 18.
Therefore, b is injective at least for n >= 9. Since b(n) <= 2n, only 
finitely many tests with b(1), b(2), ...,, b(18) show that b is 
injective on all of N.

For some n >= 9 let m = b(m).
We have to show that b(m) = 2*m, i.e. that m = 3*2^k or m = 9*2^k or m = 
2 (mod 3) or (m = 1 (mod 3)  and (m-1)/3 has an odd divisor >3).
If n = 3 (mod 6), then m = n+2 = 2 (mod 3). => OK
If n = 3*2^k+1 or n = 9*2^k + 1, then m = n+1 = 2 (mod 3). => OK
If n = 0 (mod 6) and n/3 has an odd divisor >3 then m = n+1 = 1 (mod 3) 
and (m-1)/3 = n/3 has an odd divisor >3. => OK
If n = 3*2^k, then m = 2n = 3*2^(k+1). => OK
If n = 9*2^k, then m = 2n = 9*2^(k+1). => OK
If n = 2 (mod 3) then m = 2n = 4 (mod 6), i.e. m = 1 (mod 3) and (m-1)/3 
is odd and >(2*9-1)/3 > 3. => OK
If n = 1 (mod 3) and (n-1)/3 has an odd divisor > 3, then m = 2n = 2 
(mod 3). => OK
Therefore b(b(n)) = 2*b(n) for all n >= 9 and as readily checked b(b(n)) 
= 2*b(n) for all n.

Assume that a differs from b.
Let n be minimal with a(n) != b(n). Then clearly a(n) < b(n) by 
definition of a.
By checking initial values, we may assume that n >= 9.
m := a(n) must be such that a(m) = 2*m.
If m < n, this implies a(m) = b(m) = 2*m, i.e. m is one of 1, 2, 4, 6, 
8, 9 or m > 9 and as described in (i).
If m  in {1,2,4,6,8,9} we can already find  k < 9 < n with a(k) = b(k) = m.
If m = 3*2^k, then k>0 as a(3)=1 and we need a(m) = 2m; and k>1 as we 
already excluded m = 6.
But then m = b(m/2) = a(m/2).
If m = 9*2^k, then k>0 as already a(7)=9. But then m = b(m/2) = a(m/2).
If m = 2 (mod 3), the following cases arise:
a) m = 5 (mod 6). Then m-2 = 3 (mod 6), hence a(m-2) = b(m-2) = m.
b) m = 2 (mod 6) and (m-2)/6 has no odd divisor > 3. Then m-1 is of the 
form 3*2^k or 9*2^k, hence a(m-1) = b(m-1) = m.
c) m = 2 (mod 6) and (m-2)/6 has an odd divisor > 3. Then m/2 = 1 (mod 
3) and (m/2-1)/3 has an odd divisor > 3, i.h. a(m/2) = b(m/2) = m.
If m = 1 (mod 3) and (m-1)/3 has an odd factor > 3, the following cases 
arise:
a) m even. Then m/2 = 2 (mod 3), hence a(m/2) = b(m/2) = m.
b) m odd. Then (m-1) = 0 (mod 6 and (m-1)/3 has an odd factor > 3, hence 
a(m-1) = b(m-1) = m
In all these cases we  find that a(n) = m = a(k) for some k < n, 
contradicting the injectivity of a.
Therefore m >= n.

If m=n, we find that a(n) = a(m) = 2m contradicts a(n) = m.
Therefore m > n.
But this is only possible with m = n+1 and b(n) = n+2.
This implies n = 3 (mod 6), hence m is even and m/2 = 2 (mod 3), thus m 
= b(m/2) = a(m/2), again contradicting injectivity of a.

QED