|
%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
|
