login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A020639 Lpf(n): least prime dividing n (when n > 1); a(1) = 1. 609
1, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 29, 2, 31, 2, 3, 2, 5, 2, 37, 2, 3, 2, 41, 2, 43, 2, 3, 2, 47, 2, 7, 2, 3, 2, 53, 2, 5, 2, 3, 2, 59, 2, 61, 2, 3, 2, 5, 2, 67, 2, 3, 2, 71, 2, 73, 2, 3, 2, 7, 2, 79, 2, 3, 2, 83, 2, 5, 2, 3, 2, 89, 2, 7, 2, 3, 2, 5, 2, 97 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Also, the largest number of distinct integers such that all their pairwise differences are coprime to n. - Max Alekseyev, Mar 17 2006

The unit 1 is not a prime number (although it has been considered so in the past). 1 is the empty product of prime numbers, thus 1 has no least prime factor. - Daniel Forgues, Jul 05 2011

a(n) = least m > 0 for which n! + m and n - m are not relatively prime. - Clark Kimberling, Jul 21 2012

For n > 1, a(n) = the smallest k > 1 that divides n. - Antti Karttunen, Feb 01 2014

For n > 1, records are at prime n's: 2, 3, 5, 7, 11, ... - Zak Seidov, Apr 29 2015

The initials "lpf" might be mistaken for "largest prime factor" (A009190), using "spf" for "smallest prime factor" would avoid this. - M. F. Hasler, Jul 29 2015

n = 89 is the first index > 1 for which a(n) differs from the smallest k > 1 such that (2^k + n - 2)/k is an integer. - M. F. Hasler, Aug 11 2015

From Stanislav Sykora, Jul 29 2017: (Start)

For n > 1, a(n) is also the smallest k, 1 < k <= n, for which the binomial(n,k) is not divisible by n.

Proof: (A) When k and n are relatively prime then binomial(n,k) is divisible by n because k*binomial(n,k) = n*binomial(n-1,k-1). (B) When gcd(n,k) > 1, one of its prime factors is the smallest; let us denote it p, p <= k, and consider the binomial(n,p) = (Product_{i=0..p-1}(n-i))/p!. Since p is a divisor of n, it cannot be a divisor of any of the ramaining numerator factors. It follows that, denoting as e the largest e > 0 such that p^e|n, the numerator is divisible by p^e but not by p^(e+1). Hence, the binomial is divisible by p^(e-1) but not by p^e and therefore not divisible by n. Applying (A), (B) to all considered values of k completes the proof. (End)

REFERENCES

D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section IV.1.

LINKS

T. D. Noe, Table of n, a(n) for n=1..10000 (extended to 100000 by Daniel Forgues)

A. E. Brouwer, Two number theoretic sums, Stichting Mathematisch Centrum. Zuivere Wiskunde, Report ZW 19/74 (1974): 3 pages. [Cached copy, included with the permission of the author]

OEIS Wiki, Least prime factor of n

David Singmaster, Letter to N. J. A. Sloane, Oct 3 1982.

Eric Weisstein's World of Mathematics, Least Prime Factor

Index entries for "core" sequences

FORMULA

A014673(n) = a(A032742(n)); A115561(n) = a(A054576(n)). - Reinhard Zumkeller, Mar 10 2006

A028233(n) = a(n)^A067029(n). - Reinhard Zumkeller, May 13 2006

a(n) = A027746(n,1) = A027748(n,1). - Reinhard Zumkeller, Aug 27 2011

For n > 1: a(n) = A240694(n,2). - Reinhard Zumkeller, Apr 10 2014

a(n) = A000040(A055396(n)) = n / A032742(n). - Antti Karttunen, Mar 07 2017

a(n) has average order n/(2 log n) [Brouwer[ - N. J. A. Sloane, Sep 03 2017

MAPLE

A020639 := proc(n) if n = 1 then 1; else min(op(numtheory[factorset](n))) ; end if; end proc: seq(A020639(n), n=1..20) ; # R. J. Mathar, Oct 25 2010

MATHEMATICA

f[n_]:=FactorInteger[n][[1, 1]]; Join[{1}, Array[f, 120, 2]]  (* Robert G. Wilson v, Apr 06 2011 *)

Join[{1}, Table[If[EvenQ[n], 2, FactorInteger[n][[1, 1]]], {n, 2, 120}]] (* Zak Seidov, Nov 17 2013 *)

PROG

(PARI) A020639(n) = { vecmin(factor(n)[, 1]) } /* R. J. Mathar, Mar 02 2012 */

(Haskell)

a020639 n = spf a000040_list where

  spf (p:ps) | n < p^2      = n

             | mod n p == 0 = p

             | otherwise    = spf ps

-- Reinhard Zumkeller, Jul 13 2011

(Sage)

def A020639_list(n) : return [1] + [prime_divisors(n)[0] for n in (2..n)]

A020639_list(97) # Peter Luschny, Jul 16 2012

(Scheme) (define (A020639 n) (if (< n 2) n (let loop ((k 2)) (cond ((zero? (modulo n k)) k) (else (loop (+ 1 k))))))) ;; Antti Karttunen, Feb 01 2014

(PARI) A020639(n)=if(n>1, if(n>n=factor(n, 0)[1, 1], n, factor(n)[1, 1]), 1) \\ Avoid complete factorization if not needed. Often the smallest prime factor can be found quickly even if it is larger than primelimit. Using debugging level >= 3 (\g3), factors will be printed as they are found, and factorization may then be interrupted. - M. F. Hasler, Jul 29 2015

(Sage) [trial_division(n) for n in (1..100)] # Giuseppe Coppoletta, May 25 2016

CROSSREFS

Cf. A090368 (bisection).

Cf. A000040, A009190, A006530, A034684, A028233, A034699, A053585.

See also A032742, A055396, A068319, A088377, A007978, A053669, A117818.

Cf. A046669 (partial sums), A072486 (partial products).

Sequence in context: A135679 A092028 * A092067 A214606 A079879 A071889

Adjacent sequences:  A020636 A020637 A020638 * A020640 A020641 A020642

KEYWORD

nonn,easy,nice,core

AUTHOR

David W. Wilson

EXTENSIONS

Deleted wrong comment from M. Lagneau in 2012, following an observation by Gionata Neri. - M. F. Hasler, Aug 11 2015

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified October 18 03:13 EDT 2017. Contains 293486 sequences.