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.
FORMULA
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
KEYWORD
nonn
AUTHOR
William P. Orrick, Sep 15 2023
STATUS
approved