login
A365687
a(n) = number of fractions m/n, 0 <= m < n, gcd(m,n) = 1 whose partial fraction decomposition has integer part 0.
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.
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
KEYWORD
nonn
AUTHOR
William P. Orrick, Sep 15 2023
STATUS
approved