0
$\begingroup$

Given the following facts:

Fact 1. For a natural number $n$, the integer logarithm of that number, denoted by $\sigma (n)$, is the sum, with repetitions, of the prime factors of $n$.
For example: $\sigma (0) = \sigma (1) = 0,\sigma (63) = 13$,...
Fact 2. $\forall n \in \mathbb{N} (n > 1 \Rightarrow n \ge \sigma (n))$

Let $\tau $ be the relation on $\mathbb{N}$ such that:

$\forall n_{1},n_{2}\in \mathbb{N} ({n_1} \tau {n_2} \Leftrightarrow {n_2} = \sigma ({n_1}))$

Let $G$ be the directed graph representing the relation $\tau$ on $\mathbb{N}$. Let $G'$ be the underlying undirected graph of $G$. Prove that there is no cycle of at least length 3 in $G'$.

1 Answers 1

0

The greatest vertex in the cycle would have to be connected to two vertices less than itself, but given the given facts, each vertex $n$ is connected to exactly one vertex less than or equal to itself, namely to $\sigma(n)$.

(The restriction to $n\gt1$ in fact $2$ is superfluous, since $1\ge\sigma(1)=0$.)

  • 0
    That helps, thanks a lot!2012-12-02