A196438 a(n) is the number of integers k <= n such that GCQ_A(n, k) >= 2 (see definition in comments).

0, 0, 1, 1, 3, 2, 5, 5, 6, 7, 9, 7, 11, 11, 12, 13, 15, 14, 17, 16, 18, 19, 21, 19, 23, 23, 24, 25, 27, 26, 29, 29, 30, 31, 33, 31, 35, 35, 36, 36, 39, 38, 41, 41, 42, 43, 45, 43, 47, 47

Offset: 1

Author

Jaroslav Krizek, Nov 26 2011

Keywords

• nonn

Comments

Definition of GCQ_A: The greatest common non-divisor of type A (GCQ_A) of two positive integers a and b (a<=b) is the largest positive non-divisor q of numbers a and b such that 1<=q<=a common to a and b; GCQ_A(a, b) = 0 if no such c exists.

GCQ_A(1, b) = GCQ_A(2, b) = 0 for b >=1. GCQ_A(a, b) = 0 or >= 2.

a(n) is also the number of number k <= n such that LCQ_A(n, k) >= 2.

Definition of LCQ_A: The least common non-divisor of type A (LCQ_A) of two positive integers a and b (a<=b) is the least positive non-divisor q of numbers a and b such that 1<=q<=a common to a and b; LCQ_A(a, b) = 0 if no such c exists.

LCQ_A(1, b) = LCQ_A(2, b) = 0 for b >=1. LCQ_A(a, b) = 0 or >= 2.

Examples

			For n = 6, a(6) = 2 because there are 2 cases with GCQ_A(6, k) >= 2:
GCQ_A(6, 1) = 0, GCQ_A(6, 2) = 0, GCQ_A(6, 3) = 0, GCQ_A(6, 4) = 0, GCQ_A(6, 5) = 4, GCQ_A(6, 6) = 5.
Also there are 2 cases with LCQ_A(6, k) >= 2:
LCQ_A(6, 1) = 0, LCQ_A(6, 2) = 0, LCQ_A(6, 3) = 0, LCQ_A(6, 4) = 0, LCQ_A(6, 5) = 4, LCQ_A(6, 6) = 4.
		

Links

• David A. Corneth, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A196437, A196439, A196440, A196441, A196442, A196443, A196444.

Programs

PARI

GCQ_A(a, b)=m = min(a, b); if(m < 3, return(0)); da = Set(divisors(a)); db = Set(divisors(b)); s = Set(vector(m-1,i,i)); s = setminus(s, da); s = setminus(s, db); if(#s==0,0,s[#s])
a(n) = sum(i=3,n,GCQ_A(i, n)>=2) \\ David A. Corneth, Aug 04 2017

PARI

GCQ_A(a, b)=forstep(m=min(a,b)-1,2,-1, if(a%m && b%m, return(m))); 0
a(n) = sum(i=3,n,GCQ_A(i, n)>=2) \\ Charles R Greathouse IV, Aug 26 2017

Formula

a(n) = n - A196437(n).