A365687 - OEIS

%I #21 Nov 30 2023 12:38:18

%S 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 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 12,18,14,58,2,60,15,18,32,24,1,66,16,22,2,70,12,72,18,20

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

%C 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 If 0 < m / n < 1 and gcd(m,n) = 1 then the integer part satisfies 1 - k <= z <= 0.

%C 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 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 a(n) = phi(n) if n is a prime power.

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

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

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

%e 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    1/10 = -1 + 1/2 + 3/5

%e    3/10 = -1 + 1/2 + 4/5

%e    7/10 = 1/2 + 1/5

%e    9/10 = 1/2 + 2/5.

%o (SageMath)

%o def a(n):

%o     b = n

%o     fs = factor(b)

%o     # bzList will hold Bezout coefficients to express 1/n as combination

%o     # of the reciprocals of the prime power factors of n. ppList will

%o     # hold the prime power factors themselves.

%o     bzList = []

%o     bz0 = 1

%o     ppList = []

%o     for f in fs:

%o         q = f[0]^f[1]

%o         ppList.append(q)

%o         b = b / q

%o         bzThis = xgcd(q,b)

%o         bzList.append(bz0*bzThis[2])

%o         bz0 = bz0 * bzThis[1]

%o     ct = 0

%o     for j in n.coprime_integers(n):

%o         if sum(floor(j*bzList[i]/ppList[i])\

%o          for i in range(len(ppList))) == 0:

%o             ct = ct + 1

%o     return(ct)

%Y Cf. A070306, A181629, A028236.

%K nonn

%O 1,3

%A _William P. Orrick_, Sep 15 2023