OFFSET
1,12
COMMENTS
Besides the trial division method which is represented in the first Mathematica program, this sequence can also be generated analytically as shown in the proposed analytic Mathematica program:
Any number n
can be factored as:
n=p_1^k_1*p_2^k_2...p_m^k_m
and the set of prime factors of n can be listed as {p_1, p_2,..., p_m}.
If p_1=2, the odd prime factor set will be {p_2, p_3,...,p_m} otherwise {p_1, p_2,...,p_m}, and p_j <= n, j=1..m. (p_1 = n when n is prime}
For all odd numbers greater than 2 and smaller than n, there will be p_j, 3*p_j, 5*p_j, ..., n-p_j (when n is even) or n-2*p_j (when n is odd) that have common factor p_j with n.
If we sum this over 1..m, the numbers divisible by p_j1*p_j2 are double counted, and vice versa.
Taking the statistical result of this, we can make the analytic function
i_1+i_2+..+i_m-i_1u2-i_1u3-...-i_(m-1)u(m)+i_1u2u3.... to count up the total numbers of odd numbers that has common divisor with n, where i_(a)u(b)u(c) denotes the number of odd numbers in 3..n-1 that have common factor p_a*p_b*p_c with n.
Such method gives the same sequence in the data. And, a1=Table[a[i],{i,1,10000}] is confirmed equal to the result from the table generated by the trial division method by DeleteDuplicates[a2 - a1] = {0}
To get the first 10000 terms, the trial division method took 48.56 seconds, while the analytic method took 0.84 seconds. This significant speed advantage provides the value of the longer analytic program.
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}).
LINKS
Lei Zhou, Table of n, a(n) for n = 1..10000
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
EXAMPLE
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).
MATHEMATICA
Table[Count[Range[3, n - 1, 2], _?(GCD[n, #] > 1 &)], {n, 100}] (* T. D. Noe, Nov 30 2012 *)
a[n_] := Block[{b = FactorInteger[n], c, lb, ss, lss, fc, nm,
ans = 0}, lb = Length[b]; c = Table[b[[k]][[1]], {k, 1, lb}];
If[(c[[1]] == 2) || (c[[1]] == 1), c = Part[c, 2 ;; Length[c]]];
ss = Subsets[c]; lss = Length[ss];
If[lss != 1,
Do[fc = Product[ss[[i]][[j]], {j, 1, Length[ss[[i]]]}];
If[EvenQ[Length[ss[[i]]]], fc = -fc]; nm = n;
If[OddQ[nm], nm = nm - Abs[fc]];
ans = ans + nm/fc/2, {i, 2, lss}]]; ans];
Table[a[n], {i, 1, 100}] (* Lei Zhou, Fast Analytic method, Nov 30 2012 *)
a[n_] := Block[{b = FactorInteger[n], c, lth, fc=1, nm, ans = 0}, lth = Length[b]; c = Table[b[[k, 1]], {k, lth}]; If[(c[[1]] == 2) || (c[[1]] == 1), lth=Length[c]; c = Part[c, 2 ;; lth]; lth--]; If[lth>0, Do[fc=fc*(c[[i]]-1)/c[[i]], {i, lth}]; ans=Floor[n*(1-fc)/2]]; ans]; Table[a[n], {i, 1, 100}] (* Lei Zhou, Simplified Analytic method, Dec 06 2012 *)
a[1] = 0; a[n_] := Floor[n/2] - EulerPhi[2*n]/2; Array[a, 80] (* Amiram Eldar, Nov 28 2020 *)
PROG
(PARI) a(n) = sum(i=2, n-1, (i%2) && (gcd(i, n)!=1)); \\ Michel Marcus, Aug 07 2018
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Lei Zhou, Nov 29 2012
STATUS
approved