A344589 Number of divisors d of n for which A011772(d) < A011772(n), where A011772(n) is the smallest number m such that m(m+1)/2 is divisible by n.

0, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 5, 1, 3, 3, 4, 1, 4, 1, 5, 2, 3, 1, 6, 2, 2, 3, 3, 1, 7, 1, 5, 3, 2, 3, 5, 1, 3, 2, 5, 1, 7, 1, 5, 5, 3, 1, 9, 2, 4, 3, 5, 1, 7, 2, 7, 2, 2, 1, 9, 1, 3, 5, 6, 3, 5, 1, 3, 3, 7, 1, 11, 1, 2, 4, 5, 3, 4, 1, 9, 4, 2, 1, 11, 3, 3, 3, 6, 1, 11, 3, 4, 2, 3, 3, 10, 1, 4, 5, 6, 1, 7, 1, 7, 6

Offset

1,4

Links

Antti Karttunen, Table of n, a(n) for n = 1..65537

Formula

a(n) = Sum_{d|n} [A011772(d) < A011772(n)], where [ ] is the Iverson bracket.

a(n) = A000005(n) - A344590(n).

Prog

(PARI)
A011772(n) = { if(n==1, return(1)); my(f=factor(if(n%2, n, 2*n)), step=vecmax(vector(#f~, i, f[i, 1]^f[i, 2]))); forstep(m=step, 2*n, step, if(m*(m-1)/2%n==0, return(m-1)); if(m*(m+1)/2%n==0, return(m))); }; \\ From A011772
A344589(n) = { my(x=A011772(n)); sumdiv(n, d, A011772(d)<x); };
(Python)
from itertools import combinations
from functools import reduce
from operator import mul
from sympy import factorint, divisors
from sympy.ntheory.modular import crt
def A011772(n):
    plist = [p**q for p, q in factorint(2*n).items()]
    if len(plist) == 1:
        return n-1 if plist[0] % 2 else 2*n-1
    return min(min(crt([m, 2*n//m], [0, -1])[0], crt([2*n//m, m], [0, -1])[0]) for m in (reduce(mul, d) for l in range(1, len(plist)//2+1) for d in combinations(plist, l)))
def A344589(n):
    m = A011772(n)
    return sum(1 for d in divisors(n) if A011772(d) < m) # Chai Wah Wu, Jun 02 2021

Crossrefs

Cf. A000005, A011772, A344590.

Sequence in context: A299201 A342085 A050379 * A153024 A066921 A076649

Adjacent sequences: A344586 A344587 A344588 * A344590 A344591 A344592

Keyword

nonn

Author

Antti Karttunen, Jun 01 2021

Status

approved