A136623 a(n) is the largest prime power that is <=n and is coprime to n.

1, 1, 2, 3, 4, 5, 5, 7, 8, 9, 9, 11, 11, 13, 13, 13, 16, 17, 17, 19, 19, 19, 19, 23, 23, 25, 25, 27, 27, 29, 29, 31, 32, 31, 32, 31, 32, 37, 37, 37, 37, 41, 41, 43, 43, 43, 43, 47, 47, 49, 49, 49, 49, 53, 53, 53, 53, 53, 53, 59, 59, 61, 61, 61, 64, 61, 64, 67, 67, 67, 67, 71, 71, 73

Offset

1,3

Comments

a(n) = A031218(n-1) for all n where 2 <= n <= 33.

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Example

The largest prime power that is <= 34 is 32 = 2^5. But 32 is not coprime to 34. The next smaller prime power is 31 = 31^1. 31 is indeed coprime to 34; so a(34) = 31.

Maple

f:= proc(n) local k;
  for k from n by -1 do
    if igcd(k, n)=1 and nops(numtheory:-factorset(k))<=1 then return k fi
  od
end proc:
map(f, [$1..100]); # Robert Israel, Jan 17 2018

Mathematica

a[n_] := For[k = n, True, k--, If[CoprimeQ[n, k] && PrimeNu[k] == 1, Return[k]]]; a[1] = a[2] = 1;
Array[a, 100] (* Jean-François Alcover, Aug 19 2020 *)

Prog

(PARI) a(n) = {x=n; while((matsize(factor(x))[1]>1) | (gcd(x, n)!=1), x--); x} \\ Michael B. Porter, Oct 07 2009

Crossrefs

Cf. A031218.

Sequence in context: A073137 A345965 A131233 * A031218 A357004 A357005

Adjacent sequences: A136620 A136621 A136622 * A136624 A136625 A136626

Keyword

nonn

Author

Leroy Quet, Apr 14 2008

Extensions

More terms from Michael B. Porter, Oct 07 2009

Status

approved