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, for 1 <= k <= n, where gcd(k,floor(n/k)) = 1.
2

%I #16 Oct 20 2019 01:54:34

%S 1,2,3,3,4,6,7,6,6,8,9,10,11,13,14,12,13,14,15,15,17,19,20,19,19,21,

%T 20,20,21,27,28,25,26,28,29,28,29,31,33,31,32,36,37,37,36,38,39,37,37,

%U 38,39,39,40,40,42,41,43,45,46,49,50,52,52,48,49,54,55,55,56,60,61,57,58

%N a(n) is the number of k's, for 1 <= k <= n, where gcd(k,floor(n/k)) = 1.

%C A120881(n) + a(n) = n.

%e For n = 8, we have the pairs {k,floor(n/k)} of {1,8},{2,4},{3,2},{4,2},{5,1},{6,1},{7,1},{8,1}. From these pairs we get the GCD's 1,2,1,2,1,1,1,1. 6 of these GCD's are = 1. So a(8) = 6.

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

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

%Y Cf. A120881.

%K nonn

%O 1,2

%A _Leroy Quet_, Jul 12 2006

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