login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A189172 Largest prime number tried when factoring n using trial division. 1
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

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.

LINKS

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

FORMULA

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

EXAMPLE

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.

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

PROG

(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;

}

CROSSREFS

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

Sequence in context: A184172 A125973 A227196 * A286888 A257212 A001031

Adjacent sequences:  A189169 A189170 A189171 * A189173 A189174 A189175

KEYWORD

nonn

AUTHOR

Dan Uznanski, May 02 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 28 19:16 EDT 2021. Contains 347717 sequences. (Running on oeis4.)