A115561 -id:A115561 - 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

A027746 Irregular triangle in which first row is 1, n-th row (n>1) gives prime factors of n with repetition.

Original entry on oeis.org

1, 2, 3, 2, 2, 5, 2, 3, 7, 2, 2, 2, 3, 3, 2, 5, 11, 2, 2, 3, 13, 2, 7, 3, 5, 2, 2, 2, 2, 17, 2, 3, 3, 19, 2, 2, 5, 3, 7, 2, 11, 23, 2, 2, 2, 3, 5, 5, 2, 13, 3, 3, 3, 2, 2, 7, 29, 2, 3, 5, 31, 2, 2, 2, 2, 2, 3, 11, 2, 17, 5, 7, 2, 2, 3, 3, 37, 2, 19, 3, 13, 2, 2, 2, 5, 41, 2, 3, 7, 43, 2, 2, 11, 3, 3, 5

Offset: 1

Maghraoui Abdelkader

n-th row has length A001222(n) (n>1).

			Triangle begins
  1;
  2;
  3;
  2, 2;
  5;
  2, 3;
  7;
  2, 2, 2;
  3, 3;
  2, 5;
  11;
  2, 2, 3;
  ...

N. J. A. Sloane, First 2048 rows of triangle, flattened
S. von Worley (?), Animated Factorization Diagrams, Oct. 2012.
Brent Yorgey, Factorization diagrams, The Math Less Traveled, Oct 05 2012.

Cf. A000027, A001222, A027748.
a(A022559(A000040(n))+1) = A000040(n).
Column 1 is A020639, columns 2 and 3 correspond to A014673 and A115561.
A281890 measures frequency of each prime in each column, with A281889 giving median values.
Cf. A175943 (partial products), A265110 (partial row products), A265111.

import Data.List (unfoldr)
a027746 n k = a027746_tabl !! (n-1) !! (k-1)
a027746_tabl = map a027746_row [1..]
a027746_row 1 = [1]
a027746_row n = unfoldr fact n where
   fact 1 = Nothing
   fact x = Just (p, x `div` p) where p = a020639 x
-- Reinhard Zumkeller, Aug 27 2011

P:=proc(n) local FM: FM:=ifactors(n)[2]: seq(seq(FM[j][1],k=1..FM[j][2]),j=1..nops(FM)) end: 1; for n from 2 to 45 do P(n) od; # yields sequence in triangular form; Emeric Deutsch, Feb 13 2005

row[n_] := Flatten[ Table[#[[1]], {#[[2]]}] & /@ FactorInteger[n]]; Flatten[ Table[ row[n], {n, 1, 45}]] (* Jean-François Alcover, Dec 01 2011 *)

A027746_row(n,o=[1])=if(n>1,concat(apply(t->vector(t[2],i,t[1]), Vec(factor(n)~))),o) \\ Use %(n,[]) if you want the more natural [] for the first row. - M. F. Hasler, Jul 29 2015

def factors(n: int) -> list[int]:
    p = n
    L:list[int] = []
    for f in range(2, p + 1):
        if f * f > p: break
        while True:
            q, r = divmod(p, f)
            if r != 0: break
            L.append(f)
            p = q
            if p == 1: return L
    L.append(p)
    return L  # Peter Luschny, Jul 18 2024

v=[1]
for k in [2..45]: v.extend(p for (p, m) in factor(k) for _ in range(m))
print(v) # Giuseppe Coppoletta, Dec 29 2017

Product_{k=1..A001222(n)} T(n,k) = n.
From Reinhard Zumkeller, Aug 27 2011: (Start)
A001414(n) = Sum_{k=1..A001222(n)} T(n,k), n>1;
A006530(n) = T(n,A001222(n)) = Max_{k=1..A001222(n)} T(n,k);
A020639(n) = T(n,1) = Min_{k=1..A001222(n)} T(n,k). (End)

More terms from James Sellers

A014673 Smallest prime factor of greatest proper divisor of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 2, 3, 5, 1, 2, 1, 7, 5, 2, 1, 3, 1, 2, 7, 11, 1, 2, 5, 13, 3, 2, 1, 3, 1, 2, 11, 17, 7, 2, 1, 19, 13, 2, 1, 3, 1, 2, 3, 23, 1, 2, 7, 5, 17, 2, 1, 3, 11, 2, 19, 29, 1, 2, 1, 31, 3, 2, 13, 3, 1, 2, 23, 5, 1, 2, 1, 37, 5, 2, 11, 3, 1, 2, 3, 41, 1, 2, 17, 43, 29, 2, 1, 3, 13, 2, 31, 47

Offset: 1

Reinhard Zumkeller, Jun 24 2003

nonn

For n > 1: a(n) = 1 iff n is prime; a(A001358(n)) = A084127(n); a(A025475(n)) = A020639(A025475(n)). [corrected by Peter Munn, Feb 19 2017]
When n is composite, this is the 2nd factor when n is written as a product of primes in nondecreasing order. For example, 12 = 2*2*3, so a(12) = 2. - Peter Munn, Feb 19 2017
For all sufficiently large n the median value of a(1), a(2), ... a(n) is A281889(2) = 7. - Peter Munn, Jul 12 2019

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A001222, A001358, A020639, A025475, A027746, A032742, A054576, A084127, A085392, A085393, A115561, A117357, A117358, A281889.

PrimeFactors[ n_ ] := Flatten[ Table[ # [ [ 1 ] ], {1} ] & /@ FactorInteger[ n ] ]; f[ n_ ] := Block[ {gpd = Divisors[ n ][ [ -2 ] ]}, If[ gpd == 1, 1, PrimeFactors[ gpd ][ [ 1 ] ] ] ]; Table[ If[ n == 1, 1, f[ n ] ], {n, 1, 95} ]
(* Second program: *)
Table[If[Or[PrimeQ@ n, n == 1], 1, FactorInteger[n/SelectFirst[Prime@ Range@ PrimePi[Sqrt@ n], Divisible[n, #] &]][[1, 1]] ], {n, 94}] (* Michael De Vlieger, Aug 14 2017 *)

lpf(n)=if(n>1,factor(n)[1,1],1)
a(n)=lpf(n/lpf(n)) \\ Charles R Greathouse IV, May 09 2013

a(n)=if(n<4||isprime(n),return(1)); my(f=factor(n)); if(f[1,2]>1, f[1,1], f[2,1]) \\ Charles R Greathouse IV, May 09 2013

(define (A014673 n) (A020639 (/ n (A020639 n)))) ;; Code for A020639 given under that entry - Antti Karttunen, Aug 12 2017

a(n) = A020639(A032742(n)).
A117357(n) = A020639(A054576(n)); A117358(n) = A032742(A054576(n)) = A054576(n)/A117357(n). - Reinhard Zumkeller, Mar 10 2006
If A001222(n) >= 2, a(n) = A027746(n,2), otherwise a(n) = 1. - Peter Munn, Jul 13 2019

A281889 a(n) is the least integer k such that more than half of all integers are divisible by a product of n integers chosen from 2..k.

Original entry on oeis.org

3, 7, 433, 9257821

Offset: 1

Peter Munn, Feb 01 2017

The n chosen integers need not be distinct.
By "more than half of all integers" we mean more precisely "more than half of the integers in -m..m, for all sufficiently large m (depending on n)", and similarly with 1..m for "more than half of all positive integers".
Equivalently, a(n) is the least prime p such that more than half of all positive integers can be written as a product of primes of which n or more are not greater than p. (In this sense, a(n) might be called the median n-th least prime factor of the integers.)
The number of integers that satisfy the "product of primes" criterion for p = prime(m) is the same in every interval of primorial(m)^n integers and is A281891(m,n). Primorial(m) = A002110(m), product of the first m primes.
a(n) is the least k = prime(m) such that 2 * A281891(m,n) > A002110(m)^n.
a(n) is the least k such that more than half of all positive integers equate to the volume of an orthotope with integral sides at least n of which are orthogonal with length between 2 and k inclusive.
The next term is estimated to be a(5) ~ 3*10^18.

			For n=1, we have a(1) = 3 since for all m > 1, more than half of the integers in -m..m are divisible by an integer chosen from 2..3, i.e., either 2 or 3. We must have a(1) > 2, because the only integer in 2..2 is 2, but in each interval -2m-1..2m+1, only 2m+1 integers are even, so 2 is not a divisor of more than half of all integers in the precise sense given above.

Other sequences about medians of prime factors: A126282, A126283, A284411, A290154.

Cf. A002110, A014673, A016088, A027746, A115561, A281891, A309366.

A117358 a(n) = A032742(A032742(A032742(n))) = ((n/lpf(n))/lpf(n/lpf(n)))/lpf((n/lpf(n))/lpf(n/lpf(n))), where lpf=A020639, least prime factor.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 3, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 6, 1, 1, 1, 1, 1, 3, 1, 7, 1, 1, 1, 5, 1, 1, 1, 8, 1, 1, 1, 1, 1, 1, 1, 9, 1, 1, 1, 1, 1, 1, 1, 10, 3, 1, 1, 7, 1, 1, 1, 11, 1, 5, 1, 1, 1, 1, 1, 12, 1, 1, 1, 5, 1, 1, 1

Offset: 1

Reinhard Zumkeller, Mar 10 2006

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537
Eric Weisstein's World of Mathematics, Least Prime Factor

Cf. A014673, A032742, A037144, A033987, A054576, A115561.

f[n_] := n/FactorInteger[n][[1, 1]]; (* f is A032742 *)
a[n_] := f@ f@ f@ n;
Array[a, 100] (* Jean-François Alcover, Dec 09 2021 *)
Table[Nest[#/FactorInteger[#][[1,1]]&,n,3],{n,110}] (* Harvey P. Dale, Oct 10 2024 *)

(define (A117358 n) (A032742 (A032742 (A032742 n)))) ;; Antti Karttunen, Dec 07 2017

a(n) = A032742(A032742(A032742(n))) = A032742(A054576(n)) = A054576(n)/A115561(n).

a(A037144(n)) = 1, a(A033987(n)) > 1.

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

A027746 Irregular triangle in which first row is 1, n-th row (n>1) gives prime factors of n with repetition.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A014673 Smallest prime factor of greatest proper divisor of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Scheme

Formula

A281889 a(n) is the least integer k such that more than half of all integers are divisible by a product of n integers chosen from 2..k.

Views

Author

Keywords

Comments

Examples

Crossrefs

A117358 a(n) = A032742(A032742(A032742(n))) = ((n/lpf(n))/lpf(n/lpf(n)))/lpf((n/lpf(n))/lpf(n/lpf(n))), where lpf=A020639, least prime factor.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Scheme

Formula