Let me start by defining what I mean by an arithmetic progression: an arithmetic progression of integers is a sequence of the form \[ (a + bi) = (a, a+b, a+2b, \ldots, a+kb) \] for a fixed pair of integers \((a,b)\). For simplicity, let me use \(\[1,N\]\) to denote the interval (that contains integers only) between 1 and N. Today’s question is
How many arithmetic progressions of integers can we fit into the interval \(\[1,N\]\)?
Let us start simple: if we let \(a=1\) and \(b=1\), and fix the length as \(k\) then the first sequence we have simply starts at 1 and ends at k \[ 1,2,\ldots,k \] and the last sequence that would fit in the interval ends with \(N\). So, \[ 1 + (N-k), 2 + (N-k), \ldots, N\]
If we let \(LP(N,k,b)\) as the number of arithmetic progressions in \(\[1,N\]\) of length \(k\) that go by gaps of size \(b\), we see that \[ LP(N,k,1) = N-k+1 \] a similar argument for \(b\>1\) yields \[ LP(N,k,b) = N-b(k-1) \] as long as \(1\leq b\leq \lfloor N/(k-1)\rfloor\). For the number \(LP(N,k)\) of all arithmetic progressions of length \(k\) regarless of the parameter \(b\) we must calculate the sum \[ LP(N,k) = \sum_{b=1}^{\left\lfloor\frac{N}{k-1}\right\rfloor} LP(N,k,b) = \sum_{b=1}^{\lfloor\frac{N}{k-1}\rfloor} N - b(k-1) = N\left\lfloor\frac{N}{k-1}\right\rfloor - \frac{k-1}{2}\left\lfloor\frac{N}{k-1}\right\rfloor\left(\left\lfloor\frac{N}{k-1}\right\rfloor + 1\right) \] And if we need the number \(LP(N)\) of all arithmetic progressions in the interval \(\[1,N\]\) we would have to calculate \[ LP(N) = \sum_{k=2}^N LP(N,k) \]
The implementation is straight-forward:
(defun linear-progressions (n k)
(let ((a (truncate n (1- k)))
(b (/ (1- k) 2)))
(- (* n a) (* b a (1+ a)))))
(defun all-linear-progressions (n)
(loop for i from 2 to n sum (linear-progressions n i)))LINEAR-PROGRESSIONS
ALL-LINEAR-PROGRESSIONSLet us test:
(linear-progressions 3 2)
(all-linear-progressions 3)
(loop for i from 2 to 20 collect (linear-progressions 20 i))
(loop for i from 2 to 100 collect (all-linear-progressions i))3
4
(190 90 57 40 30 24 19 16 13 10 9 8 7 6 5 4 3 2 1)
(1 4 9 17 27 41 57 77 100 127 156 191 228 269 314 364 416 474 534 600 670 744
820 904 991 1082 1177 1278 1381 1492 1605 1724 1847 1974 2105 2245 2387 2533
2683 2841 3001 3169 3339 3515 3697 3883 4071 4269 4470 4677 4888 5105 5324
5551 5782 6021 6264 6511 6760 7021 7284 7551 7824 8104 8388 8680 8974 9274
9578 9890 10204 10530 10858 11190 11528 11872 12220 12576 12934 13302 13675
14052 14431 14822 15217 15616 16019 16430 16843 17268 17697 18132 18571 19014
19461 19920 20381 20848 21321)