|
| |
|
|
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.
|
|
895
|
|
|
|
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 indices. - 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
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) = (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)
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:
a(n) = 2 when n == 0 (mod 2);
a(n) = 3 when n == 3 (mod 6);
a(n) = 5 when n == 5 or 25 (mod 30);
a(n) = 7 when n == 7, 49, 77, 91, 119, 133, 161 or 203 (mod 210);
etc. (End)
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
|
|
|
REFERENCES
|
D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section IV.1.
|
|
|
LINKS
|
A. E. Brouwer, Two number theoretic sums, Stichting Mathematisch Centrum. Zuivere Wiskunde, Report ZW 19/74 (1974): 3 pages. [Copy included with the permission of the author.]
|
|
|
FORMULA
|
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 *)
Riffle[Join[{1}, Table[FactorInteger[n][[1, 1]], {n, 3, 101, 2}]], 2] (* Harvey P. Dale, Dec 16 2021 *)
|
|
|
PROG
|
(PARI) A020639(n) = { vecmin(factor(n)[, 1]) } \\ [Will yield an error for n = 1.] - R. J. Mathar, Mar 02 2012
(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
(Haskell)
a020639 n = spf a000040_list where
spf (p:ps) | n < p^2 = n
| mod n p == 0 = p
| otherwise = spf ps
(Sage)
def A020639_list(n) : return [1] + [prime_divisors(n)[0] for n in (2..n)]
(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
(Python)
from sympy import factorint
def a(n): return 1 if n == 1 else min(factorint(n))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice,core
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Expanded definition to make this easier to find. - N. J. A. Sloane, Sep 21 2020
|
|
|
STATUS
|
approved
|
| |
|
|
