A088377 -id:A088377 - 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.

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

Offset: 1

David W. Wilson

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
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) = (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)
From Bob Selcoe, Oct 11 2017, edited by M. F. Hasler, Nov 06 2017: (Start)
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

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

Daniel Forgues, Table of n, a(n) for n = 1..100000 (terms 1..10000 from T. D. Noe)
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.]
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

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).
Cf. A002110, A005867.
Cf. A127093.

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

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

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

A020639(n) = { vecmin(factor(n)[,1]) } \\ [Will yield an error for n = 1.] - R. J. Mathar, Mar 02 2012

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

from sympy import factorint
def a(n): return 1 if n == 1 else min(factorint(n))
print([a(n) for n in range(1, 98)]) # Michael S. Branicky, Dec 09 2021

def A020639_list(n) : return [1] + [prime_divisors(n)[0] for n in (2..n)]
A020639_list(97) # Peter Luschny, Jul 16 2012

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

(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

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

Deleted wrong comment from M. Lagneau in 2012, following an observation by Gionata Neri. - M. F. Hasler, Aug 11 2015
Edited by M. F. Hasler, Nov 06 2017
Expanded definition to make this easier to find. - N. J. A. Sloane, Sep 21 2020

A080257 Numbers having at least two distinct or a total of at least three prime factors.

Original entry on oeis.org

6, 8, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100

Offset: 1

Reinhard Zumkeller, Feb 10 2003

Complement of A000430; A080256(a(n)) > 3.
A084114(a(n)) > 0, see also A084110.
Also numbers greater than the square of their smallest prime-factor: a(n)>A020639(a(n))^2=A088377(a(n));
a(n)>A000430(k) for n<=13, a(n) < A000430(k) for n>13.
Numbers with at least 4 divisors. - Franklin T. Adams-Watters, Jul 28 2006
Union of A024619 and A033942; A211110(a(n)) > 2. - Reinhard Zumkeller, Apr 02 2012
Also numbers > 1 that are neither prime nor a square of a prime. Also numbers whose omega-sequence (A323023) has sum > 3. Numbers with omega-sequence summing to m are: A000040 (m = 1), A001248 (m = 3), A030078 (m = 4), A068993 (m = 5), A050997 (m = 6), A325264 (m = 7). - Gus Wiseman, Jul 03 2019
Numbers n such that sigma_2(n)*tau(n) = A001157(n)*A000005(n) >= 4*n^2. Note that sigma_2(n)*tau(n) >= sigma(n)^2 = A072861 for all n. - Joshua Zelinsky, Jan 23 2025

			8=2*2*2 and 10=2*5 are terms; 4=2*2 is not a term.
From _Gus Wiseman_, Jul 03 2019: (Start)
The sequence of terms together with their prime indices begins:
   6: {1,2}
   8: {1,1,1}
  10: {1,3}
  12: {1,1,2}
  14: {1,4}
  15: {2,3}
  16: {1,1,1,1}
  18: {1,2,2}
  20: {1,1,3}
  21: {2,4}
  22: {1,5}
  24: {1,1,1,2}
  26: {1,6}
  27: {2,2,2}
  28: {1,1,4}
  30: {1,2,3}
  32: {1,1,1,1,1}
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A001248, A001221, A001222, A006881, A030078, A088381, A088383, A000005.

Cf. A060687, A118914, A323014, A323023, A325249.

a080257 n = a080257_list !! (n-1)
a080257_list = m a024619_list a033942_list where
   m xs'@(x:xs) ys'@(y:ys) | x < y  = x : m xs ys'
                           | x == y = x : m xs ys
                           | x > y  = y : m xs' ys
-- Reinhard Zumkeller, Apr 02 2012

Select[Range[100],PrimeNu[#]>1||PrimeOmega[#]>2&] (* Harvey P. Dale, Jul 23 2013 *)

PARI
```
is(n)=omega(n)>1 || isprimepower(n)>2
```

is(n)=my(k=isprimepower(n)); if(k, k>2, !isprime(n)) \\ Charles R Greathouse IV, Jan 23 2025

a(n) = n + O(n/log n). - Charles R Greathouse IV, Sep 14 2015

Definition clarified by Harvey P. Dale, Jul 23 2013

A247180 Numbers with nonrepeating smallest prime factor.

Original entry on oeis.org

2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 18, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 46, 47, 50, 51, 53, 54, 55, 57, 58, 59, 61, 62, 65, 66, 67, 69, 70, 71, 73, 74, 75, 77, 78, 79, 82, 83, 85, 86, 87, 89, 90, 91, 93, 94, 95, 97, 98

Offset: 1

Reinhard Zumkeller, Nov 23 2014

nonn

Complement of the union of {1} and A283050. The asymptotic density of this sequence is 1 - A283071 = 0.6699019646... - Amiram Eldar, Dec 08 2020

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A020639, A088377, A067029, A283050, A283071.

Subsequences: A005117, A016825.

a247180 n = a247180_list !! (n-1)
a247180_list = filter ((== 1) . a067029) [1..]

Select[Range[100],FactorInteger[#][[1,2]]==1&] (* Harvey P. Dale, Jan 29 2020 *)

isok(m) = (m>1) && (factor(m)[1,2] == 1); \\ Michel Marcus, Dec 08 2020

a(n) mod A088377(a(n)) > 0;

A067029(a(n)) = 1.

A068319 a(n) = if n <= lpf(n)^2 then lpf(n) else a(lpf(n) + n/lpf(n)), where lpf = least prime factor, A020639.

Original entry on oeis.org

1, 2, 3, 2, 5, 5, 7, 5, 3, 7, 11, 5, 13, 3, 5, 7, 17, 11, 19, 5, 7, 13, 23, 3, 5, 5, 5, 7, 29, 17, 31, 11, 3, 19, 5, 5, 37, 7, 7, 13, 41, 23, 43, 3, 11, 5, 47, 5, 7, 5, 5, 7, 53, 29, 7, 17, 13, 31, 59, 11, 61, 3, 3, 19, 11, 5, 67, 5, 5, 37, 71, 7, 73, 7

Offset: 1

Reinhard Zumkeller, Feb 27 2002, Jul 13 2007

n>1: a(n) is prime and a(n)=n iff n is prime.

a(n) = if n <= A088377(n) then A020639(n) else a(A111234(n)).

			a(12)=a(2*6)=a(8)=a(2*4)=a(6)=a(2*3)=a(5)=a(5*1)=5.

R. Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A032742.

a068319 n = if n <= spf ^ 2 then spf else a068319 $ spf + div n spf
            where spf = a020639 n
-- Reinhard Zumkeller, Jun 24 2013

lpf[n_] := FactorInteger[n][[1, 1]]; a[n_] := a[n] = If[n <= lpf[n]^2, lpf[n], a[lpf[n] + n/lpf[n]]]; Table[a[n], {n, 1, 74}](* Jean-François Alcover, Dec 21 2011 *)

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Sage

Sage

Scheme

Formula

Extensions

A080257 Numbers having at least two distinct or a total of at least three prime factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Formula

Extensions

A247180 Numbers with nonrepeating smallest prime factor.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A068319 a(n) = if n <= lpf(n)^2 then lpf(n) else a(lpf(n) + n/lpf(n)), where lpf = least prime factor, A020639.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

A088378 a(n) = (smallest prime factor of n)^3; a(1) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A088379 a(n) = (smallest prime factor of n)^4; a(1) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula