cp's OEIS Frontend

A020639 Lpf(n): least prime dividing n (when n > 1); a(1) = 1. Or, smallest prime factor of n, or smallest prime divisor of n.

%I A020639 #231 Feb 16 2025 08:32:33
%S A020639 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,
%T A020639 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,
%U A020639 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
%N A020639 Lpf(n): least prime dividing n (when n > 1); a(1) = 1. Or, smallest prime factor of n, or smallest prime divisor of n.
%C A020639 Also, the largest number of distinct integers such that all their pairwise differences are coprime to n. - _Max Alekseyev_, Mar 17 2006
%C A020639 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
%C A020639 a(n) = least m > 0 for which n! + m and n - m are not relatively prime. - _Clark Kimberling_, Jul 21 2012
%C A020639 For n > 1, a(n) = the smallest k > 1 that divides n. - _Antti Karttunen_, Feb 01 2014
%C A020639 For n > 1, records are at prime indices. - _Zak Seidov_, Apr 29 2015
%C A020639 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
%C A020639 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
%C A020639 From _Stanislav Sykora_, Jul 29 2017: (Start)
%C A020639 For n > 1, a(n) is also the smallest k, 1 < k <= n, for which the binomial(n,k) is not divisible by n.
%C A020639 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) = (1/p!)*Product_{i=0..p-1} (n-i). Since p is a divisor of n, it cannot be a divisor of any of the remaining 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)
%C A020639 From _Bob Selcoe_, Oct 11 2017, edited by _M. F. Hasler_, Nov 06 2017: (Start)
%C A020639 a(n) = prime(j) when n == J (mod A002110(j)), n, j >= 1, where J is the set of numbers <= A002110(j) with smallest prime factor = prime(j). The number of terms in J is A005867(j-1). So:
%C A020639 a(n) = 2 when n == 0 (mod 2);
%C A020639 a(n) = 3 when n == 3 (mod 6);
%C A020639 a(n) = 5 when n == 5 or 25 (mod 30);
%C A020639 a(n) = 7 when n == 7, 49, 77, 91, 119, 133, 161 or 203 (mod 210);
%C A020639 etc. (End)
%C A020639 For n > 1, a(n) is the leftmost term, other than 0 or 1, in the n-th row of A127093. - _Davis Smith_, Mar 05 2019
%D A020639 D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section IV.1.
%H A020639 Daniel Forgues, <a href="/A020639/b020639.txt">Table of n, a(n) for n = 1..100000</a> (terms 1..10000 from T. D. Noe)
%H A020639 A. E. Brouwer, <a href="/A046670/a046670.pdf">Two number theoretic sums</a>, Stichting Mathematisch Centrum. Zuivere Wiskunde, Report ZW 19/74 (1974): 3 pages. [Copy included with the permission of the author.]
%H A020639 OEIS Wiki, <a href="/wiki/Least_prime_factor_of_n">Least prime factor of n</a>
%H A020639 David Singmaster, <a href="/A005178/a005178.pdf">Letter to N. J. A. Sloane</a>, Oct 3 1982.
%H A020639 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LeastPrimeFactor.html">Least Prime Factor</a>
%H A020639 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A020639 A014673(n) = a(A032742(n)); A115561(n) = a(A054576(n)). - _Reinhard Zumkeller_, Mar 10 2006
%F A020639 A028233(n) = a(n)^A067029(n). - _Reinhard Zumkeller_, May 13 2006
%F A020639 a(n) = A027746(n,1) = A027748(n,1). - _Reinhard Zumkeller_, Aug 27 2011
%F A020639 For n > 1: a(n) = A240694(n,2). - _Reinhard Zumkeller_, Apr 10 2014
%F A020639 a(n) = A000040(A055396(n)) = n / A032742(n). - _Antti Karttunen_, Mar 07 2017
%F A020639 a(n) has average order n/(2 log n) [Brouwer] - _N. J. A. Sloane_, Sep 03 2017
%p A020639 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
%t A020639 f[n_]:=FactorInteger[n][[1,1]]; Join[{1}, Array[f,120,2]]  (* _Robert G. Wilson v_, Apr 06 2011 *)
%t A020639 Join[{1}, Table[If[EvenQ[n], 2, FactorInteger[n][[1,1]]], {n, 2, 120}]] (* _Zak Seidov_, Nov 17 2013 *)
%t A020639 Riffle[Join[{1},Table[FactorInteger[n][[1,1]],{n,3,101,2}]],2] (* _Harvey P. Dale_, Dec 16 2021 *)
%o A020639 (PARI) A020639(n) = { vecmin(factor(n)[,1]) } \\ [Will yield an error for n = 1.] - _R. J. Mathar_, Mar 02 2012
%o A020639 (PARI) A020639(n)=if(n>1, if(n>n=factor(n,0)[1,1], n, factor(n)[1,1]), 1) \\ Avoids complete factorization if possible. Often the smallest prime factor can be found quickly even if it is larger than primelimit. If factoring takes too long for large n, use debugging level >= 3 (\g3) to display the smallest factor as soon as it is found. - _M. F. Hasler_, Jul 29 2015
%o A020639 (Haskell)
%o A020639 a020639 n = spf a000040_list where
%o A020639   spf (p:ps) | n < p^2      = n
%o A020639              | mod n p == 0 = p
%o A020639              | otherwise    = spf ps
%o A020639 -- _Reinhard Zumkeller_, Jul 13 2011
%o A020639 (Sage)
%o A020639 def A020639_list(n) : return [1] + [prime_divisors(n)[0] for n in (2..n)]
%o A020639 A020639_list(97) # _Peter Luschny_, Jul 16 2012
%o A020639 (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
%o A020639 (Sage) [trial_division(n) for n in (1..100)] # _Giuseppe Coppoletta_, May 25 2016
%o A020639 (Python)
%o A020639 from sympy import factorint
%o A020639 def a(n): return 1 if n == 1 else min(factorint(n))
%o A020639 print([a(n) for n in range(1, 98)]) # _Michael S. Branicky_, Dec 09 2021
%Y A020639 Cf. A090368 (bisection).
%Y A020639 Cf. A000040, A009190, A006530, A034684, A028233, A034699, A053585.
%Y A020639 See also A032742, A055396, A068319, A088377, A007978, A053669, A117818.
%Y A020639 Cf. A046669 (partial sums), A072486 (partial products).
%Y A020639 Cf. A002110, A005867.
%Y A020639 Cf. A127093.
%K A020639 nonn,easy,nice,core
%O A020639 1,2
%A A020639 _David W. Wilson_
%E A020639 Deleted wrong comment from M. Lagneau in 2012, following an observation by _Gionata Neri_. - _M. F. Hasler_, Aug 11 2015
%E A020639 Edited by _M. F. Hasler_, Nov 06 2017
%E A020639 Expanded definition to make this easier to find. - _N. J. A. Sloane_, Sep 21 2020