A257977 - OEIS

%I #24 Sep 11 2020 04:23:02

%S 1,1,1,2,1,2,1,2,3,2,1,4,1,2,3,4,1,4,1,4,3,2,1,6,5,2,3,4,1,6,1,4,3,2,

%T 5,6,1,2,3,8,1,6,1,4,7,2,1,8,7,6,3,4,1,6,5,8,3,2,1,10,1,2,9,8,5,6,1,4,

%U 3,10,1,9,1,2,7,4,7,6,1,10,9,2,1,12

%N Largest k such that there are at least k numbers b_i, 1 <= b_i <= n, each having gcd(b_i,n) >= k.

%C Initially similar to A070966, it diverges at n = 30. Here a(30) = 6, while A070966(30) = 8.

%C From _Robert Israel_, May 28 2015: (Start)

%C a(p^m) = p^floor(m/2) if p is prime.

%C a(p*q) = p if p < q are primes.

%C a(n) >= A033676(n). (End)

%C First differs from A034880 at a(24). - _Sean A. Irvine_, Sep 10 2020

%H Ivan Neretin, <a href="/A257977/b257977.txt">Table of n, a(n) for n = 1..10000</a>

%e Each of the four numbers 4, 6, 8, and 12 has common divisor with 12 which is no less than four. But there are no five such numbers among [1..12]. Hence a(12)=4.

%p f:= n -> nops(select(`>=`,sort(map(igcd,[$1..n],n),`>`)-[$1..n], 0)):

%p map(f, [$1..100]); # _Robert Israel_, May 28 2015

%t f[n_] := Count[Reverse[Sort[GCD[Range[n], n]]] - Range[n], x_ /; x >= 0]; Table[f[n], {n, 84}]

%Y Cf. A033676, A070966.

%K nonn

%O 1,4

%A _Ivan Neretin_, May 15 2015