A360452 Number of fractions c/d with |c| <= d <= 2n and odd denominator when factors of 2 are canceled.

0, 3, 7, 15, 27, 39, 59, 83, 99, 131, 167, 191, 235, 275, 311, 367, 427, 467, 515, 587, 635, 715, 799, 847, 939, 1023, 1087, 1191, 1271, 1343, 1459, 1579, 1651, 1747, 1879, 1967, 2107, 2251, 2331, 2451, 2607, 2715, 2879, 3007, 3119, 3295, 3439, 3559, 3703, 3895, 4015

Offset: 0

Author

M. F. Hasler, Mar 26 2023

Keywords

• nonn
• easy

Comments

Using d <= 2n or d <= 2n-1 gives the same result, therefore we use 2n and not just n for the upper limit of the denominator. Indeed, using an even d will only yield the same simplified fractions with odd denominators as one gets for d/2.

Examples

			For n = 0, there is no possible fraction, since the denominator can't be zero.
For n = 1, we have a(1) = #{ -1/1, 0/1, 1/1} = 3; using denominator d = 2 would not give other elements with odd denominator after cancellations, cf. comments.
For n = 2, we have a(2) = #{-1/1, -2/3, -1/3, 0, 1/3, 2/3, 1/1} = 7.
For n = 3, we have a(3) = #{-1/1, -4/5, -2/3, -3/5, -2/5, -1/3, -1/5, 0, 1/5, 1/3, 2/5, 3/5, 2/3, 4/5, 1/1} = 15. As explained in comments, only odd d are useful.
		

Crossrefs

Cf. A099957, A049691.

Programs

PARI

a(n)=#Set(concat([[c/d|c<-[-d..d],d && denominator(c/d)%2]|d<-[0..n*2]])) \\ For illustration only. Remove the # to see the elements. Obviously the code could be optimized.

PARI

apply( {A360452(n) = sum(i=0, n-1, eulerphi(2*i+1))*2+!!n}, [0..10]) \\ This should be used to define the "official" function A360452.

Python

# uses programs from A002088 and A049690
def A360452(n): return (A002088((n<<1)-1)-A049690(n-1)<<1)|1 if n else 0 # Chai Wah Wu, Aug 04 2024

Formula

a(n) = 2*A099957(n)+1 for n > 0.