login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

a(n) is the number of k's in 1..n such that gcd(k,ceiling(n/k)) = 1.
2

%I #17 Oct 26 2019 20:46:10

%S 1,2,2,3,4,5,3,4,6,8,7,8,8,9,8,8,11,12,11,12,12,13,12,13,14,16,15,18,

%T 19,20,16,17,21,21,20,21,23,24,23,24,26,27,21,22,23,24,23,24,27,29,29,

%U 29,30,31,31,32,35,36,35,36,34,35,34,37,42,43,39,40,41,41,37,38,42,43,42

%N a(n) is the number of k's in 1..n such that gcd(k,ceiling(n/k)) = 1.

%C A120886(n) + A120887(n) = n.

%e a(7)=3 because for k=1,2,...,7 we have gcd(k,ceiling(7/k))=1,2,3,2,1,2,1, respectively.

%p a:=proc(n) local ct, k: ct:=0: for k from 1 to n do if gcd(k,ceil(n/k))=1 then ct:=ct+1 else ct:=ct fi od: end: seq(a(n),n=1..85); # _Emeric Deutsch_, Jul 23 2006

%t Table[Length[Select[Table[GCD[k, Ceiling[n/k]], {k, 1, n}], # == 1 &]],{n, 1, 80}] (* _Stefan Steinerberger_, Jul 23 2006 *)

%Y Cf. A120882, A120886.

%K nonn

%O 1,2

%A _Leroy Quet_, Jul 12 2006

%E More terms from _Emeric Deutsch_ and _Stefan Steinerberger_ Jul 23 2006

%E Edited by _N. J. A. Sloane_ at the suggestion of _Andrew S. Plewe_, Jun 12 2007