A189172 - OEIS

%I #15 Jun 23 2022 20:30:28

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

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

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

%N Largest prime number tried when factoring n using trial division.

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

%H T. D. Noe, <a href="/A189172/b189172.txt">Table of n, a(n) for n = 1..10000</a>

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

%e A(22) is 3, because after 3 is tried, it is clear that 11 is prime and no more factorization can be done.

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

%t 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 *)

%o (JavaScript) prime(k), not shown, gives A000040[k].

%o function a(n) {

%o   var k = 1;

%o   while (Math.pow(prime(k),2) <= n) {

%o     var p = prime(k);

%o     if (n % p == 0) {

%o       n /= p;

%o     } else {

%o       k += 1;

%o     }

%o   }

%o   return p;

%o }

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

%K nonn

%O 1,4

%A _Dan Uznanski_, May 02 2011