A351362 Number of ways the numbers from 1..n do not divide the numbers from n..2n-1.

0, 1, 4, 8, 14, 22, 32, 42, 57, 72, 88, 108, 129, 151, 177, 203, 232, 262, 295, 329, 367, 405, 443, 487, 532, 577, 627, 675, 727, 783, 839, 895, 956, 1018, 1082, 1148, 1217, 1285, 1357, 1431, 1506, 1586, 1664, 1746, 1832, 1914, 2002, 2092, 2186, 2277, 2374, 2472, 2568, 2672

Offset

1,3

Links

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

Formula

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

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

Example

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

Prog

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

Crossrefs

Cf. A006218, A077024, A351355.

Sequence in context: A024398 A054347 A194149 * A003682 A333700 A011897

Adjacent sequences: A351359 A351360 A351361 * A351363 A351364 A351365

Keyword

nonn

Author

Wesley Ivan Hurt, Feb 08 2022

Status

approved