A351355 Number of ways the numbers from 1..n do not divide numbers from n+1..2n.

0, 1, 3, 8, 13, 21, 31, 42, 55, 71, 87, 107, 128, 150, 174, 203, 231, 260, 294, 328, 364, 404, 442, 486, 530, 576, 624, 674, 726, 780, 838, 895, 953, 1017, 1079, 1146, 1216, 1284, 1354, 1430, 1505, 1583, 1663, 1745, 1827, 1913, 2001, 2091, 2184, 2275, 2371, 2471, 2567, 2669, 2773

Offset

1,3

Links

Table of n, a(n) for n=1..55.

Formula

a(n) = Sum_{k=1..n} Sum_{i=n+1..2n} sign(i mod k).

a(n) = n*(n+1) + A006218(n) - A006218(2n). - Chai Wah Wu, Feb 08 2022

Example

a(5) = 13; there are 13 ways the numbers from 1..5 do not divide the numbers from 6..10. 2 does not divide 7,9 (2 ways) + 3 does not divide 7,8,10 (3 ways) + 4 does not divide 6,7,9,10 (4 ways) + 5 does not divide 6,7,8,9 (4 ways) = 13 ways.

Prog

(Python)
def A351355(n): return 0 if n == 1 else n*n-sum(2*n//k for k in range(2, 2*n))+sum(n//k for k in range(2, n)) # Chai Wah Wu, Feb 08 2022
(Python)
from math import isqrt
def A351355(n): return ((t:=isqrt(m:=n<<1))+(s:=isqrt(n)))*(t-s)+(sum(n//k for k in range(1, s+1))-sum(m//k for k in range(1, t+1))<<1)+n*(n+1) # Chai Wah Wu, Oct 23 2023

Crossrefs

Cf. A006218, A077024.

Sequence in context: A094110 A212649 A084535 * A194427 A335048 A185954

Adjacent sequences: A351352 A351353 A351354 * A351356 A351357 A351358

Keyword

nonn

Author

Wesley Ivan Hurt, Feb 08 2022

Status

approved