cp's OEIS Frontend

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

%I A365687 #21 Nov 30 2023 12:38:18
%S A365687 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,
%T A365687 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,
%U A365687 12,18,14,58,2,60,15,18,32,24,1,66,16,22,2,70,12,72,18,20
%N A365687 a(n) = number of fractions m/n, 0 <= m < n, gcd(m,n) = 1 whose partial fraction decomposition has integer part 0.
%C A365687 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.
%C A365687 If 0 < m / n < 1 and gcd(m,n) = 1 then the integer part satisfies 1 - k <= z <= 0.
%C A365687 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.
%C A365687 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.
%F A365687 a(n) = phi(n) if n is a prime power.
%F A365687 a(n) = phi(n) / 2 if n is the product of powers of two distinct primes.
%F A365687 a(n) = 0 if n is in A181629, that is, if n is a nonhyperbolic number.
%F A365687 a(n) = A070306(n) if n is a prime power or a product of powers of two distinct primes.
%e A365687 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:
%e A365687    1/10 = -1 + 1/2 + 3/5
%e A365687    3/10 = -1 + 1/2 + 4/5
%e A365687    7/10 = 1/2 + 1/5
%e A365687    9/10 = 1/2 + 2/5.
%o A365687 (SageMath)
%o A365687 def a(n):
%o A365687     b = n
%o A365687     fs = factor(b)
%o A365687     # bzList will hold Bezout coefficients to express 1/n as combination
%o A365687     # of the reciprocals of the prime power factors of n. ppList will
%o A365687     # hold the prime power factors themselves.
%o A365687     bzList = []
%o A365687     bz0 = 1
%o A365687     ppList = []
%o A365687     for f in fs:
%o A365687         q = f[0]^f[1]
%o A365687         ppList.append(q)
%o A365687         b = b / q
%o A365687         bzThis = xgcd(q,b)
%o A365687         bzList.append(bz0*bzThis[2])
%o A365687         bz0 = bz0 * bzThis[1]
%o A365687     ct = 0
%o A365687     for j in n.coprime_integers(n):
%o A365687         if sum(floor(j*bzList[i]/ppList[i])\
%o A365687          for i in range(len(ppList))) == 0:
%o A365687             ct = ct + 1
%o A365687     return(ct)
%Y A365687 Cf. A070306, A181629, A028236.
%K A365687 nonn
%O A365687 1,3
%A A365687 _William P. Orrick_, Sep 15 2023