A196437 a(n) = the number of numbers k <= n such that GCQ_A(n, k) = LCQ_A(n, k) = 0 (see definition in comments).

1, 2, 2, 3, 2, 4, 2, 3, 3, 3, 2, 5, 2, 3, 3, 3, 2, 4, 2, 4, 3, 3, 2, 5, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 2, 5, 2, 3, 3, 4, 2, 4, 2, 3, 3, 3, 2, 5, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 2, 7, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 2, 5, 2, 3, 3, 3, 2, 4, 2, 4, 3, 3, 2, 5, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 2, 5, 2, 3, 3, 4, 2, 4, 2, 3, 3

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.

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) = 4 because there are 4 cases with GCQ_A(6, k) = 0:
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 4 cases with LCQ_A(6, k) = 0: 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

• Antti Karttunen, Table of n, a(n) for n = 1..65537

Crossrefs

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

Programs

PARI

GCQ_A(a, b) = { forstep(m=min(a, b)-1, 2, -1, if(a%m && b%m, return(m))); 0; };
A196438(n) = sum(i=3, n, GCQ_A(i, n)>=2);
A196437(n) = (n - A196438(n)); \\ Antti Karttunen, Mar 20 2018, based on Charles R Greathouse IV's Aug 26 2017 PARI-program in A196438.

Formula

a(n) = n - A196438(n).

Extensions

More terms from Antti Karttunen, Mar 20 2018