A219839 a(n) is the number of odd integers in 2..(n-1) that have a common factor (other than 1) with n.

0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 2, 0, 1, 3, 0, 0, 3, 0, 2, 4, 1, 0, 4, 2, 1, 4, 2, 0, 7, 0, 0, 6, 1, 5, 6, 0, 1, 7, 4, 0, 9, 0, 2, 10, 1, 0, 8, 3, 5, 9, 2, 0, 9, 7, 4, 10, 1, 0, 14, 0, 1, 13, 0, 8, 13, 0, 2, 12, 11, 0, 12, 0, 1, 17, 2, 8, 15, 0, 8, 13, 1, 0, 18

Offset: 1

Author

Lei Zhou, Nov 29 2012

Keywords

• nonn
• easy

Comments

a(n) is also the number of linearly dependent diagonal/side length ratios R(n,k), in the regular n-gon. The following will explain this. In the regular n-gon inscribed in a circle the number of distinct diagonals including the side is floor(n/2). Not all of the corresponding length ratios R(n,k) = d(n,k)/d(n,1), k = 1..floor(n/2), with d(n,1) = s(n) (the length of the side), d(n,2) the length of the smallest diagonal, etc., are linearly independent because C(n,R(n,2)) = 0, where C is the minimal polynomial of R(n,2) = 2*cos(Pi/n) (see A187360) with degree delta(n) = A055034(n). Thus every ratio R(n,j), with j = delta(n)+1, ..., floor(n/2) can be expressed as a linear combination of the independent R(n,k), k=1, ..., delta(n). See the comment from Sep 21 2013 on A053121 for powers of R(n,2) (called there rho(N)). Therefore, a(n) = floor(n/2) - delta(n) is, for n>=2, the number of linearly dependent ratios R(n,k) in the regular n-gon. - Wolfdieter Lang, Sep 23 2013

From Wolfdieter Lang, Nov 23 2020: (Start)

This sequence gives the difference between the number of odd numbers in the smallest nonnegative residue system modulo n (called here RS(n)) and the smallest nonnegative restricted residue system (called here RRS(n), but RRS(1) = {1}, not {0}).

This sequence can be used to find sequence A111774 by recording the positions of the entries >= 1. See a W. Lang comment there, and also A337940, for the proof. Hence the complement of A111774, given in A174090, is given by the numbers m with a(m) = 0. (End)

Examples

			n=1: there is no odd number greater than 2 but smaller than 1-1=0, so a(1)=0.
Same for n=2,3.
n=4: 3 is the only odd number in 2..(4-1), and GCD(3,4)=1, so a(4)=0.
For any prime numbers and numbers in the form of 2^n, no odd number in 2..(n-1) has common factor with n, so a(p)=0 and a(2^n)=0, n>0.
n=6: 3,5 are odd numbers in 2..(6-1), and GCD(3,6)=3>1 and GCD(5,6)=1, so a(6)=1.
n=15: candidates are 3,5,7,9,11,13.  3, 5, and 9 have greater than 1 common factors with 15, so a(15)=3
From _Wolfdieter Lang_, Sep 23 2013: (Start)
Example n = 15 for a(n) = floor(n/2) - delta(n): 1, 3, 5, 7, 9, 11, 13 take out 1, 7, 9, 11, leaving 3, 5, 13. Therefore, a(15) = 7 - 4 = 3. See the formula above for delta.
In the regular 15-gon the 3 (= a(15)) diagonal/side ratios R(15, 5), R(15, 6) and R(15,7) can be expressed as linear combinations of the R(15,j), j=1..4.  See the n-gon comment above. (End)
From _Wolfdieter Lang_, Nov 23 2020: (Start)
n = 1: RS(1) = {0}, RRS(1) = {1}, hence a(1) = 0 - 1 = 0. Here RRS(1) is not {0}(standard) because delta(1) := 1 (the degree of minimal polynomial for 2*cos(Pi//1) = -2 which is x+2, see A187360).
n = 6: RS(6) = {0, 1, 2, 3, 4, 5} and RRS(6) = {1,5}, hence a(6) = 3 - 2 = 1, and A111774(1) = 6 = A337940(1, 1).
a(15) = 7 - 4 = 3, and A111774(6) = 15 = A337940(3, 3) = A337940(4, 1) (multiplicity 2 = A338428(6)). (End)
		

Links

• Lei Zhou, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A016035 (see 1st comment there), A004526, A055034, A111774, A174090, A190357, A337940, A338428.

Programs

Mathematica

Table[Count[Range[3, n - 1, 2], ?(GCD[n, #] > 1 &)], {n, 100}] (* _T. D. Noe, Nov 30 2012 *)
a[1] = 0; a[n_] := Floor[n/2] - EulerPhi[2*n]/2; Array[a, 80] (* Amiram Eldar, Nov 28 2020 *)

PARI

a(n) = sum(i=2, n-1, (i%2) && (gcd(i,n)!=1)); \\ Michel Marcus, Aug 07 2018

Formula

a(n) = floor(n/2) - delta(n), with floor(n/2) = A004526 and delta(n) = A055034(n) = phi(2*n)/2, for n >= 2, with Euler's phi A000010. See the Aug 17 2011 comment on A055034. For n = 1 this would be -1, not 0, because delta(1) = 1. - Wolfdieter Lang, Sep 23 2013

Sum_{k=1..n} a(k) ~ c*n^2, where c = 1/4 - 2/Pi^2 = 0.04735763... (A190357). - Amiram Eldar, Feb 23 2025