The Foundations: Logic and Proofs 20. Determine whether these are valid arguments a

EXAMPLE 23
The
3
x
+
1
Conjecture
Let
T
be the transformation that sends an even integer
x
to
x/
2 and
an odd integer
x
to 3
x
+
1. A famous conjecture, sometimes known as the
3
x
+
1 conjec-
ture
, states that for all positive integers
x
, when we repeatedly apply the transformation
T
,
we will eventually reach the integer 1. For example, starting with
x
=
13, we find
T (
13
)
=
3
·
13
+
1
=
40,
T (
40
)
=
40
/
2
=
20,
T (
20
)
=
20
/
2
=
10,
T (
10
)
=
10
/
2
=
5,
T (
5
)
=
3
·
5
+
1
=
16,
T (
16
)
=
8,
T (
8
)
=
4,
T (
4
)
=
2, and
T (
2
)
=
1. The 3
x
+
1 conjecture has
been verified using computers for all integers
x
up to 5
.
6
·
10
13
.
The 3
x
+
1 conjecture has an interesting history and has attracted the attention of mathe-
maticians since the 1950s. The conjecture has been raised many times and goes by many other
names, including the Collatz problem, Hasse’s algorithm, Ulam’s problem, the Syracuse prob-
lem, and Kakutani’s problem. Many mathematicians have been diverted from their work to spend
time attacking this conjecture. This led to the joke that this problem was part of a conspiracy
Watch out! Working on
the 3
x
+
1 problem can
be addictive.
to slow down American mathematical research. See the article by Jeffrey Lagarias [La10] for a
fascinating discussion of this problem and the results that have been found by mathematicians
attacking it.
▲
In Chapter 4 we will describe additional open questions about prime numbers. Students
already familiar with the basic notions about primes might want to explore Section 4.3, where
these open questions are discussed. We will mention other important open questions throughout
the book.