OFFSET
1,3
COMMENTS
Note that the numbers in row n > 1 are at least d_1 - d_2 >= n - n/lpf(n), and the inequality is strict unless n is prime, where lpf(n) = A020639(n) is the smallest prime divisor of n.
For n != 2, we can always suppose that d_i != 2: 2 can only be the penultimate member of (d_1,...,d_k), but (d_1,...,d_{k-2},2,1) and (d_1,...,d_{k-2},1) give the same alternating sum.
Let S(n) = {Sum_{i=1..k} (-1)^i d_i : n = d_1 > d_2 > ... > d_k = 1, d_{i+1} | d_i}, then by enumerating d_2, we have S(n) = U_{d|n,d<n} (n - S(d)) = n - U_{d|n,d<n} S(d), where n - S = {n - a : a in S}. As an example, this implies that S(2^m) is the set of odd numbers in the range [2^(m-1),2^m] for m >= 2.
If we define T(n) = {Sum_{i=1..k} (-1)^i d_i : d_1 > d_2 > ... > d_k = 1, d_1 | n, d_{i+1} | d_i}, then T(n) = U_{d|n} S(d) by definition. By considering the cases d_1 = n and d_1 < n, we have T(n) = S(n) U (n - S(n)). Note that this union is a disjoint union for n > 2, as S(n) contains only numbers > n/2 and hence n - S(n) contains only numbers < n/2.
Note that m in S(n) does not imply k*m in S(k*n) for k > 1, for example 97 = 100 - 4 + 1 is in S(100), but 388 = 4*97 is not in S(400).
LINKS
Jianing Song, Table of n, a(n) for n = 1..22617 (Rows n = 1..1000)
EXAMPLE
Table reads
1,
1,
2,
3,
4,
4, 5,
6,
5, 7,
7, 8,
6, 9,
10,
7, 8, 9, 10, 11,
12,
8, 13,
11, 13, 14,
9, 11, 13, 15,
16,
10, 11, 13, 14, 16, 17,
18,
11, 14, 16, 17, 19,
...
PROG
(PARI) setm(a, S) = Set(vector(#S, i, a-S[i]))
S(n) = if(n==1, [1], my(v=[]); fordiv(n, d, if(d<n, v=setunion(v, S(d)))); setm(n, v))
CROSSREFS
KEYWORD
AUTHOR
Jianing Song, Aug 21 2024
STATUS
approved