login
A264100
Sum of the lengths of the arithmetic progressions in {1,2,3,...,n}, including trivial arithmetic progressions of lengths 1 and 2.
1
0, 1, 4, 12, 26, 50, 82, 130, 188, 265, 358, 473, 602, 765, 944, 1151, 1386, 1657, 1948, 2284, 2642, 3048, 3490, 3972, 4480, 5056, 5666, 6322, 7022, 7784, 8578, 9452, 10360, 11337, 12366, 13453, 14592, 15831, 17110, 18453, 19856, 21357, 22902, 24551
OFFSET
0,3
COMMENTS
Conjecture: the second differences give A007503(n+1), the sum of the divisors (A000203) plus the number of divisors (A000005) of n+1.
The first differences trivially are the total length of such sequences that end in n+1. Mapping each sequence to a different sequence by adding 1 to each term, we see that the second differences are the number of sequences up to n+2 that include both 1 and n+2. For each divisor d of n+1, there is a single such sequence of length d+1 (with increment (n+1)/d). The second difference is then sum_{d|n+1} d+1, which is sigma(n+1) + tau(n+1), as claimed. - Franklin T. Adams-Watters, Nov 05 2015
FORMULA
a(n) = n + Sum_{k=2..n} k*floor((n-1)/(k-1))*(2*n-(k-1)*floor((n+k-2)/(k-1)))/2.
EXAMPLE
For n = 3 the arithmetic progressions are (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3) and the respective lengths are (1), (1), (1), (2), (2), (2), (3), so a(3) = 1 + 1 + 1 + 2 + 2 + 2 + 3 = 12.
The first difference at 2, sequences ending with 3, are (3), (1, 3), (2, 3), and (1, 2, 3), total length 8 = 12-4. The second difference at 2, sequences starting with 1 and ending with 4 are (1, 4) and (1, 2, 3, 4), total length 6 = 26 - 2*12 +4.
PROG
(PARI) vector(50, n, n--; n + sum(k=2, n, k*floor((n-1)/(k-1))*(2*n-(k-1)*floor((n+k-2)/(k-1)))/2)) \\ Altug Alkan, Nov 04 2015
CROSSREFS
KEYWORD
nonn
AUTHOR
Gionata Neri, Nov 03 2015
STATUS
approved