Date: Sun, 4 Nov 2007 00:40:34 -0700
From: "Max Alekseyev" <maxale(AT)gmail.com>
Subject: Proof of a conjecture concerning A131883 and A036912.

On 10/30/07, Vladeta Jovovic wrote:

> > %I A131883
> > %S A131883 1,2,2,2,2,4,4,4,4,4,4,6,6,6,6,6,6,8,8,8
> > %N A131883 a(n) = the minimum value from among
> > (phi(n+1),phi(n+2),phi(n+3),...,phi(2n)), where phi(m) is the number of
> > positive integers which are coprime to m and are <= m.
> > %C A131883 Conjecture: After omitting multiple occurrences we get A036912.
> > %A A131883 Vladeta Jovovic (vladeta(AT)Eunet.yu), Oct 31 2007

Before going on, I need the following theorem.

Theorem. For any integers n, m such that 2n<m, there exists an integer
k in [n+1,2n] such that phi(k)<phi(m).

Proof. Without loss of generality we may assume that m is odd. Indeed,
if m is even then we can replace m with m'=m/2 (if m'>2n) to decrease
m not increasing phi(m), or take k=m' (if m'<=2n) to complete the
proof.
Let q be a prime divisor of m, i.e., m=q*t for some integer t. If m=q
then phi(m)=m-1 and we can simply take k=n to complete the proof. For
the rest assume that q<m. Consider the following cases:
1) If t>2n then since phi(t)<phi(m) we can replace m with t. Only a
finite number of such replacements is possible (since m is decreasing
each time).
2) If n+1 <= t <= 2n, then take k=t to complete the proof.
3) If t<=n then there exists integer s<=q-1 such that (n+1)/t <= s <=
2n/t. Then for k=s*t we have n+1 <= k <= 2n and
phi(k) = phi(s*t) <= s*phi(t) <= (q-1)*phi(t) <= phi(q*t) = phi(m)
and we need to show that at least one of these inequalities is strict.
If they all <= are equalities then s=q-1 (which is even) divides t,
implying that m is even. This contradiction proves that at least one
of inequalities is strict, implying that phi(k) < phi(m).
Q.E.D.

Corollary. A131883 is non-decreasing.
Indeed, if A131883(n+1) < A131883(n) then min{ phi(2n+1), phi(2n+2) }
< min{ phi(n+1), phi(n+2), ..., phi(2n) } but this contradicts to
Theorem for m=2n+1 or m=2n+2.

I will prove that sequences A036912 and A131883 are equal as sets.
Together with their monotonicity, it will give the required proof that
after omitting multiple occurrences in A131883 we get A036912. I will
show that if t belongs to one of A036912 and A131883 then it also
belongs to the other.

1) If A131883(n)=t then t = min{ phi(n+1), ..., phi(2n) }. Let m be
the maximum number from the interval [n+1,2n] such that t = phi(m).
First note that A057635(t) = m. Indeed, if A057635(t) > m then by
definition of m we have A057635(t) > 2n. By Theorem, there exists k in
[n+1,2n] such that phi(k) < phi(A057635(t))=t, a contradiction to t =
min{ phi(n+1), ..., phi(2n) }.
Now, I will show that t belongs to A036912, i.e., for all k<t,
A057635(k)<m. Assume the contrary, i.e., for some k<t, A057635(k)>=m.
Then A057635(k)>2n since otherwise we have min{ phi(n+1), ..., phi(2n)
} <= k < t, a contradiction. Then again, by Theorem, there exists s in
[n+1,2n] such that phi(s) < phi(A057635(k)) = k < t, a contradiction
to t = min{ phi(n+1), ..., phi(2n) }. This contradiction proves that
for all k<t, A057635(k)<m, i.e., t belongs to A036912.

2) If t belong to A036912 then n = A057635(t) > max{ A057635(1),
A057635(2), ..., A057635(t-1) }.
Our goal is to show that t=A131883(n-1), i.e., t=phi(n) equals min{
phi(n), ..., phi(2n-2) }. Assume that min{ phi(n), ..., phi(2n-2) } =
phi(k) < phi(n)=t with n<k<=2n-2. Then A057635(phi(k)) >= k > n =
A057635(t), a contradiction to the fact that t belongs to A036912.
This contradiction proves that min{ phi(n), ..., phi(2n-2) } = phi(n)
= t, i.e., t=A131883(n-1).

The proof of the conjecture is complete.

Note that the proof give the following explicit relationship between
A131883, A036912, and A057635. Namely, for t belonging to A036912, we
have t=A131883(A057635(t)-1). In other words,

A036912(n) = A131883(A057635(A036912(n))-1) for all n.