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,3

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.

Links

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

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.

Example

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.

Prog

(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)

Crossrefs

Cf. A070306, A181629, A028236.

Sequence in context: A328925 A299020 A343505 * A014665 A055035 A235138

Adjacent sequences: A365684 A365685 A365686 * A365688 A365689 A365690

Keyword

nonn

Author

William P. Orrick, Sep 15 2023

Status

approved