MathDB
Problems
Contests
National and Regional Contests
PEN Problems
PEN M Problems
17
M 17
M 17
Source:
May 25, 2007
modular arithmetic
Recursive Sequences
Problem Statement
A sequence of integers,
{
a
n
}
n
≥
1
\{a_{n}\}_{n \ge 1}
{
a
n
}
n
≥
1
with
a
1
>
0
a_{1}>0
a
1
>
0
, is defined by
a
n
+
1
=
a
n
2
if
n
≡
0
(
m
o
d
4
)
,
a_{n+1}=\frac{a_{n}}{2}\;\;\; \text{if}\;\; n \equiv 0 \;\; \pmod{4},
a
n
+
1
=
2
a
n
if
n
≡
0
(
mod
4
)
,
a
n
+
1
=
3
a
n
+
1
if
n
≡
1
(
m
o
d
4
)
,
a_{n+1}=3 a_{n}+1 \;\;\; \text{if}\;\; n \equiv 1 \; \pmod{4},
a
n
+
1
=
3
a
n
+
1
if
n
≡
1
(
mod
4
)
,
a
n
+
1
=
2
a
n
−
1
if
n
≡
2
(
m
o
d
4
)
,
a_{n+1}=2 a_{n}-1 \;\;\; \text{if}\;\; n \equiv 2 \; \pmod{4},
a
n
+
1
=
2
a
n
−
1
if
n
≡
2
(
mod
4
)
,
a
n
+
1
=
a
n
+
1
4
if
n
≡
3
(
m
o
d
4
)
.
a_{n+1}=\frac{a_{n}+1}{4}\;\;\; \text{if}\;\; n \equiv 3 \; \pmod{4}.
a
n
+
1
=
4
a
n
+
1
if
n
≡
3
(
mod
4
)
.
Prove that there is an integer
m
m
m
such that
a
m
=
1
a_{m}=1
a
m
=
1
.
Back to Problems
View on AoPS