A365687 a(n) = number of fractions m/n, 0 <= m < n, gcd(m,n) = 1 whose partial fraction decomposition has integer part 0.

1, 1, 2, 2, 4, 1, 6, 4, 6, 2, 10, 2, 12, 3, 4, 8, 16, 3, 18, 4, 6, 5, 22, 4, 20, 6, 18, 6, 28, 0, 30, 16, 10, 8, 12, 6, 36, 9, 12, 8, 40, 1, 42, 10, 12, 11, 46, 8, 42, 10, 16, 12, 52, 9, 20, 12, 18, 14, 58, 2, 60, 15, 18, 32, 24, 1, 66, 16, 22, 2, 70, 12, 72, 18, 20

Offset: 1

Author

William P. Orrick, Sep 15 2023

Keywords

• nonn

Comments

If n = p_1^r_1 p_2^r_2 ... p_k^r_k where p_1, ..., p_k are distinct primes, the partial fraction decomposition of m/n has the form z + Sum_{i=1..k} a_i / p_i^r_i = z + Sum_{i=1..k} Sum_{j=1..r_i} a_ij / p_i^j where 0 < a_i < p_i^r_i, gcd(a_i,p_i) = 1, and where 0 <= a_ij < p_i (a_ij > 0 when j = r_i). z is the integer part.

If 0 < m / n < 1 and gcd(m,n) = 1 then the integer part satisfies 1 - k <= z <= 0.

If n is a nonhyperbolic number, which means that Sum_{i=1..k} 1 / p_i^r_i >= 1, then the integer part is not zero for any m/n with 0 < m / n < 1, gcd(m,n) = 1.

Assuming gcd(m,n) = 1, if m/n has integer part z then (n - m)/n has integer part 1 - k - z. This means there are equally many reduced fractions with denominator n > 1 between 0 and 1 having integer part z and integer part 1 - k - z.

Examples

			a(10) = 2 because, of the four nonnegative reduced fractions less than 1 with denominator 10, two of them (7/10 and 9/10) have integer part 0:
   1/10 = -1 + 1/2 + 3/5
   3/10 = -1 + 1/2 + 4/5
   7/10 = 1/2 + 1/5
   9/10 = 1/2 + 2/5.
		

Crossrefs

Cf. A070306, A181629, A028236.

Programs

SageMath

def a(n):
    b = n
    fs = factor(b)
    # bzList will hold Bezout coefficients to express 1/n as combination
    # of the reciprocals of the prime power factors of n. ppList will
    # hold the prime power factors themselves.
    bzList = []
    bz0 = 1
    ppList = []
    for f in fs:
        q = f[0]^f[1]
        ppList.append(q)
        b = b / q
        bzThis = xgcd(q,b)
        bzList.append(bz0*bzThis[2])
        bz0 = bz0 * bzThis[1]
    ct = 0
    for j in n.coprime_integers(n):
        if sum(floor(j*bzList[i]/ppList[i])\
         for i in range(len(ppList))) == 0:
            ct = ct + 1
    return(ct)

Formula

a(n) = phi(n) if n is a prime power.

a(n) = phi(n) / 2 if n is the product of powers of two distinct primes.

a(n) = 0 if n is in A181629, that is, if n is a nonhyperbolic number.

a(n) = A070306(n) if n is a prime power or a product of powers of two distinct primes.