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
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
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
Comments