A combinatorial problem on arithmetic progressions

[David W. Wilson]

Santi Spadaro wrote:
> 
> Hi everyone! It's a great pleasure for me to partecipate in the
> SeqFan Mailing List. I'm a physics student from Sicily. To be exact I
> live in a village named Pagliara but I study physics at the
> University of Messina.
> 
> I would like to begin my contribution to the list with the following
> simple combinatorial problem:
> 
> "How many arithmetic progressions of k terms and any mean can be
> extracted from the set of the first n natural numbers?"
> 
> I myself had proposed it to me a few years ago, and I resolved it for any k.
> The solution for k=3 is the sequence named "Quarter Squares", and for
> k>3 I also found sequences which are in NJA Sloane's Encyclopedia.
> 
> I recently submitted a comment on Quarter Squares to NJAS's OEIS
> dealing with it, so I would like to know: has anyone of you ever
> heard of this problem, or a problem similar to it?
> 
> Thank you very much, I hope not to have bored you...
> 
> Cheers
> 
> Santi Spadaro

It's a nitpick, but we are counting only AP's with positive difference
(i.e, increasing APs).  On n contiguous integers, the number of such AP's
with k terms is

    f_k(n) = (n-m)(n+m-k)/(2k)  where  m = n mod k.