Quantas progressões aritméticas de k termos com razão inteira positiva existem no conjunto {1,...,n}?

Fórmula: \( \displaystyle \sum_{d=1}^{\lfloor (n-1)/(k-1)\rfloor} \bigl(n-(k-1)d\bigr)\)

Para cada razão inteira \(d\ge1\) tal que \((k-1)d\le n-1\), o primeiro termo \(a\) pode variar de \(1\) até \(n-(k-1)d\), resultando em \(n-(k-1)d\) progressões com essa razão, somando-se sobre todas as razões possíveis.

Exemplo: Seja \(n=10\), \(k=4\). Calcula-se \(\lfloor(10-1)/(4-1)\rfloor=\lfloor9/3\rfloor=3\).
Para \(d=1\): \(10-(4-1)\cdot1=7\).
Para \(d=2\): \(10-(4-1)\cdot2=4\).
Para \(d=3\): \(10-(4-1)\cdot3=1\).
Total: \(7+4+1=12\) progressões aritméticas de 4 termos em \{1,…,10\}.