# Is it Number Theory or Combinatorics ?

**Discrete Mathematics**Level 5

For \(k≥1\), let \(a_{k}\) be the greatest divisor of \(k\) which is not a multiple of \(3\).

Set \(S_{0}=0\) and \(S_{k}=a_{1}+a_{2}+...+a_{k}\) for \(k≥1\).

Find the number of integers \(k\) with \(0≤k<3^{15}\) such that \(S_{k}\) is divisible by \(3\).

**Note** A generalization of this problem was once proposed for **IMO**.

Try other interesting combinatorics in my set Hard