

A219839


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


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 the following way as shown in the proposed analytic Mathematica program:
For any number n, it can be factored to prime factorization 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, ..., np_j (when n is even) or n2*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 vise versa.
Taking the statistical result of this, we can make the analytic function
i_1+i_2+..+i_mi_1u2i_1u3...i_(m1)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..n1 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 ngon. The following will explain this. In the regular ngon 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 ngon.  Wolfdieter Lang, Sep 23 2013


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, 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 11=0, so a(1)=0.
Same for n=2,3.
n=4: 3 is the only odd number in 2..(41), 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..(n1) 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..(61), 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 15gon 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 ngon comment above. (End)


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*(1fc)/2]]; ans]; Table[a[n], {i, 1, 100}] (* Lei Zhou, Simplified Analytic method, Dec 06 2012 *)


PROG

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


CROSSREFS

Cf. A016035 (see 1st comment there).
Sequence in context: A136493 A132213 A202502 * A154312 A236076 A119900
Adjacent sequences: A219836 A219837 A219838 * A219840 A219841 A219842


KEYWORD

nonn,easy


AUTHOR

Lei Zhou, Nov 29 2012


STATUS

approved



