login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A219839 a(n) is the number of odd integers in 2..(n-1) 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, ..., 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 vise 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

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

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 *)

PROG

(PARI) a(n) = sum(i=2, n-1, (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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 29 16:43 EDT 2020. Contains 334704 sequences. (Running on oeis4.)