A189172 Largest prime number tried when factoring n using trial division.

1, 1, 1, 2, 2, 2, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 5, 3, 3, 2, 5, 3, 5, 2, 3, 3, 5, 3, 5, 3, 3, 2, 5, 3, 5, 3, 3, 3, 5, 2, 7, 5, 3, 3, 7, 3, 5, 2, 3, 5, 7, 3, 7, 5, 3, 2, 5, 3, 7, 3, 3, 5, 7, 3, 7, 5, 5, 3, 7, 3, 7, 2, 3, 5, 7, 3, 5, 5, 5, 3, 7, 3, 7, 3, 5, 5, 5, 2, 7, 7, 3, 5

Offset: 1

Author

Dan Uznanski, May 02 2011

Keywords

• nonn

Comments

When factoring a number via trial division, one generally continues trying primes until it is certain that the remaining portion of n is prime. Sometimes, it is already clear that the remaining portion is prime before that portion is found; in this case, the last prime tried is the second to last prime factor.

Examples

			A(22) is 3, because after 3 is tried, it is clear that 11 is prime and no more factorization can be done.
A(18) is 3, because despite the largest prime factor (3) being obviously prime, it is not obviously the last factor until the first 3 is factored out.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000

Crossrefs

Like A059396 but also works on composites; uses A006530, A087039, A000040.

Programs

JavaScript

prime(k), not shown, gives A000040[k].
function a(n) {
  var k = 1;
  while (Math.pow(prime(k),2) <= n) {
    var p = prime(k);
    if (n % p == 0) {
      n /= p;
    } else {
      k += 1;
    }
  }
  return p;
}

Mathematica

a[n_] := Module[{m = n, k = 1, p = 1, q}, While[q = Prime[k]; q^2 <= m, p = q; m = m/p^IntegerExponent[m, p]; k++]; p]; Array[a,100] (* T. D. Noe, May 04 2011 *)

Formula

a(n) = max(A087039(n), A007917(A000196(A006530(n)))).