Numbers for which Euler Phi Function of 2n + 1 is less than that of 2n

From ProofWiki
Jump to navigation Jump to search

Theorem

The sequence of positive integers for which:

$\map \phi {2 n + 1} < \map \phi {2 n}$

begins:

$157, 262, 367, 412, \ldots$

This sequence is A001837 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).


Proof

\(\ds 2 \times 157\) \(=\) \(\ds 314\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 157}\) \(=\) \(\ds 156\) $\phi$ of $314$
\(\ds 2 \times 157 + 1\) \(=\) \(\ds 315\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 157 + 1}\) \(=\) \(\ds 144\) $\phi$ of $315$
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 157 + 1}\) \(<\) \(\ds \map \phi {2 \times 157}\)


\(\ds 2 \times 262\) \(=\) \(\ds 524\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 262}\) \(=\) \(\ds 260\) $\phi$ of $524$
\(\ds 2 \times 262 + 1\) \(=\) \(\ds 525\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 262 + 1}\) \(=\) \(\ds 240\) $\phi$ of $525$
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 262 + 1}\) \(<\) \(\ds \map \phi {2 \times 262}\)


\(\ds 2 \times 367\) \(=\) \(\ds 734\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 367}\) \(=\) \(\ds 366\) $\phi$ of $734$
\(\ds 2 \times 367 + 1\) \(=\) \(\ds 735\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 367 + 1}\) \(=\) \(\ds 336\) $\phi$ of $735$
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 367 + 1}\) \(<\) \(\ds \map \phi {2 \times 367}\)


\(\ds 2 \times 412\) \(=\) \(\ds 824\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 412}\) \(=\) \(\ds 408\) $\phi$ of $824$
\(\ds 2 \times 412 + 1\) \(=\) \(\ds 825\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 412 + 1}\) \(=\) \(\ds 400\) $\phi$ of $825$
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 412 + 1}\) \(<\) \(\ds \map \phi {2 \times 412}\)


\(\ds 2 \times 472\) \(=\) \(\ds 944\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 472}\) \(=\) \(\ds 464\) $\phi$ of $944$
\(\ds 2 \times 472 + 1\) \(=\) \(\ds 945\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 472 + 1}\) \(=\) \(\ds 432\) $\phi$ of $945$
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 472 + 1}\) \(<\) \(\ds \map \phi {2 \times 472}\)


\(\ds 2 \times 487\) \(=\) \(\ds 974\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 487}\) \(=\) \(\ds 486\) $\phi$ of $974$
\(\ds 2 \times 487 + 1\) \(=\) \(\ds 975\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 487 + 1}\) \(=\) \(\ds 480\) $\phi$ of $975$
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 487 + 1}\) \(<\) \(\ds \map \phi {2 \times 487}\)


\(\ds 2 \times 577\) \(=\) \(\ds 1154\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 577}\) \(=\) \(\ds 576\) $\phi$ of $1154$
\(\ds 2 \times 577 + 1\) \(=\) \(\ds 1155\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 577 + 1}\) \(=\) \(\ds 480\) $\phi$ of $1155$
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 577 + 1}\) \(<\) \(\ds \map \phi {2 \times 577}\)


\(\ds 2 \times 682\) \(=\) \(\ds 1364\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 682}\) \(=\) \(\ds 600\) $\phi$ of $1364$
\(\ds 2 \times 682 + 1\) \(=\) \(\ds 1365\)
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 682 + 1}\) \(=\) \(\ds 576\) $\phi$ of $1365$
\(\ds \leadsto \ \ \) \(\ds \map \phi {2 \times 682 + 1}\) \(<\) \(\ds \map \phi {2 \times 682}\)




Sources