login
A257977
Largest k such that there are at least k numbers b_i, 1 <= b_i <= n, each having gcd(b_i,n) >= k.
1
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, 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, 3, 10, 1, 9, 1, 2, 7, 4, 7, 6, 1, 10, 9, 2, 1, 12
OFFSET
1,4
COMMENTS
Initially similar to A070966, it diverges at n = 30. Here a(30) = 6, while A070966(30) = 8.
From Robert Israel, May 28 2015: (Start)
a(p^m) = p^floor(m/2) if p is prime.
a(p*q) = p if p < q are primes.
a(n) >= A033676(n). (End)
First differs from A034880 at a(24). - Sean A. Irvine, Sep 10 2020
LINKS
EXAMPLE
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.
MAPLE
f:= n -> nops(select(`>=`, sort(map(igcd, [$1..n], n), `>`)-[$1..n], 0)):
map(f, [$1..100]); # Robert Israel, May 28 2015
MATHEMATICA
f[n_] := Count[Reverse[Sort[GCD[Range[n], n]]] - Range[n], x_ /; x >= 0]; Table[f[n], {n, 84}]
CROSSREFS
Sequence in context: A355366 A046805 A034880 * A070966 A338669 A219254
KEYWORD
nonn
AUTHOR
Ivan Neretin, May 15 2015
STATUS
approved