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

Author

Antti Karttunen, Jun 01 2021

Keywords

• nonn

Links

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

Crossrefs

Cf. A000005, A011772, A344590.

Programs

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)
				

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

Formula

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

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