A196437 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

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.

LINKS

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

FORMULA

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

EXAMPLE

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.

PROG

(PARI)

GCQ_A(a, b) = { forstep(m=min(a, b)-1, 2, -1, if(a%m && b%m, return(m))); 0; };