MathDB

Divisibility sequence equals identity infinitely many times.

Source: Israel Olympic Revenge 2020 SL N1.

May 3, 2022

number theorydivisible

Problem Statement

Let

a_1,a_2,a_3,...

be an infinite sequence of positive integers. Suppose that a sequence

a_1,a_2,\ldots

of positive integers satisfies

a_1=1

and

a_{n}=\sum_{n\neq d|n}a_d

for every integer

n>1

. Prove that the exist infinitely many integers

k

such that

a_k=k