cp's OEIS Frontend

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

%I A219839 #67 Feb 23 2025 02:41:05
%S A219839 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,
%T A219839 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,
%U A219839 0,2,12,11,0,12,0,1,17,2,8,15,0,8,13,1,0,18
%N A219839 a(n) is the number of odd integers in 2..(n-1) that have a common factor (other than 1) with n.
%C A219839 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
%C A219839 From _Wolfdieter Lang_, Nov 23 2020: (Start)
%C A219839 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}).
%C A219839 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)
%H A219839 Lei Zhou, <a href="/A219839/b219839.txt">Table of n, a(n) for n = 1..10000</a>
%F A219839 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
%F A219839 Sum_{k=1..n} a(k) ~ c*n^2, where c = 1/4 - 2/Pi^2 = 0.04735763... (A190357). - _Amiram Eldar_, Feb 23 2025
%e A219839 n=1: there is no odd number greater than 2 but smaller than 1-1=0, so a(1)=0.
%e A219839 Same for n=2,3.
%e A219839 n=4: 3 is the only odd number in 2..(4-1), and GCD(3,4)=1, so a(4)=0.
%e A219839 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.
%e A219839 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.
%e A219839 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
%e A219839 From _Wolfdieter Lang_, Sep 23 2013: (Start)
%e A219839 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.
%e A219839 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)
%e A219839 From _Wolfdieter Lang_, Nov 23 2020: (Start)
%e A219839 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).
%e A219839 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).
%e A219839 a(15) = 7 - 4 = 3, and A111774(6) = 15 = A337940(3, 3) = A337940(4, 1) (multiplicity 2 = A338428(6)). (End)
%t A219839 Table[Count[Range[3, n - 1, 2], _?(GCD[n, #] > 1 &)], {n, 100}] (* _T. D. Noe_, Nov 30 2012 *)
%t A219839 a[1] = 0; a[n_] := Floor[n/2] - EulerPhi[2*n]/2; Array[a, 80] (* _Amiram Eldar_, Nov 28 2020 *)
%o A219839 (PARI) a(n) = sum(i=2, n-1, (i%2) && (gcd(i,n)!=1)); \\ _Michel Marcus_, Aug 07 2018
%Y A219839 Cf. A000010, A016035 (see 1st comment there), A004526, A055034, A111774, A174090, A190357, A337940, A338428.
%K A219839 nonn,easy
%O A219839 1,12
%A A219839 _Lei Zhou_, Nov 29 2012