cp's OEIS Frontend

A053669 Smallest prime not dividing n.

%I A053669 #116 Jul 02 2025 16:01:59
%S A053669 2,3,2,3,2,5,2,3,2,3,2,5,2,3,2,3,2,5,2,3,2,3,2,5,2,3,2,3,2,7,2,3,2,3,
%T A053669 2,5,2,3,2,3,2,5,2,3,2,3,2,5,2,3,2,3,2,5,2,3,2,3,2,7,2,3,2,3,2,5,2,3,
%U A053669 2,3,2,5,2,3,2,3,2,5,2,3,2,3,2,5,2,3,2,3,2,7,2,3,2,3,2,5,2,3,2,3,2,5,2,3,2
%N A053669 Smallest prime not dividing n.
%C A053669 Smallest prime coprime to n.
%C A053669 Smallest k >= 2 coprime to n.
%C A053669 a(#(p-1)) = a(A034386(p-1)) = p is the first appearance of prime p in sequence.
%C A053669 a(A005408(n)) = 2; for n > 2: a(n) = A112484(n,1). - _Reinhard Zumkeller_, Sep 23 2011
%C A053669 Average value is 2.920050977316134... = A249270. - _Charles R Greathouse IV_, Nov 02 2013
%C A053669 Differs from A236454, "smallest number not dividing n^2", for the first time at n=210, where a(210)=11 while A236454(210)=8. A235921 lists all n for which a(n) differs from A236454. - _Antti Karttunen_, Jan 26 2014
%C A053669 For k >= 0, a(A002110(k)) is the first occurrence of p = prime(k+1). Thereafter p occurs whenever A007947(n) = A002110(k). Thus every prime appears in this sequence infinitely many times. - _David James Sycamore_, Dec 04 2024
%H A053669 T. D. Noe, <a href="/A053669/b053669.txt">Table of n, a(n) for n = 1..10000</a>
%H A053669 Dylan Fridman, Juli Garbulsky, Bruno Glecer, James Grime and Massi Tron Florentin, <a href="https://doi.org/10.1080/00029890.2019.1530554">A Prime-Representing Constant</a>, The American Mathematical Monthly, Vol. 126, No. 1 (2019), pp. 70-73; <a href="https://www.researchgate.net/publication/330746181_A_Prime-Representing_Constant">ResearchGate link</a>.
%H A053669 James Grime and Brady Haran, <a href="https://www.youtube.com/watch?v=_gCKX6VMvmU&amp;t=347s">2.920050977316</a>, Numberphile video (2020)
%H A053669 Igor Rivin, <a href="https://doi.org/10.1016/j.aim.2012.07.018">Geodesics with one self-intersection, and other stories</a>, Advances in Mathematics, Vol. 231, No. 5 (2012), pp. 2391-2412; <a href="http://arxiv.org/abs/0901.2543">arXiv preprint</a>, arXiv:0901.2543 [math.GT], 2009-2011.
%F A053669 a(n) = A071222(n-1)+1. [Because the right hand side computes the smallest k >= 2 such that gcd(n,k) = gcd(n-1,k-1) which is equal to the smallest k >= 2 coprime to n] - _Antti Karttunen_, Jan 26 2014
%F A053669 a(n) = 1 + Sum_{k=1..n}(floor((n^k)/k!)-floor(((n^k)-1)/k!)) = 2 + Sum_{k=1..n} A001223(k)*( floor(n/A002110(k))-floor((n-1)/A002110(k)) ). - _Anthony Browne_, May 11 2016
%F A053669 a(n!) = A151800(n). - _Anthony Browne_, May 11 2016
%F A053669 a(2k+1) = 2. - _Bernard Schott_, Jun 03 2019
%F A053669 Asymptotic mean: lim_{n->oo} (1/n) * Sum_{k=1..n} a(k) = A249270. - _Amiram Eldar_, Oct 29 2020
%F A053669 a(n) = A000040(A257993(n)) = A020639(A276086(n)) = A276086(n) / A324895(n). - _Antti Karttunen_, Apr 24 2022
%F A053669 a(n) << log n. For every e > 0, there is some N such that for all n > N, a(n) < (1 + e)*log n. - _Charles R Greathouse IV_, Dec 03 2022
%F A053669 A007947(n) = A002110(k) ==> a(n) = prime(k+1). - _David James Sycamore_, Dec 04 2024
%e A053669 a(60) = 7, since all primes smaller than 7 divide 60 but 7 does not.
%e A053669 a(90) = a(120) = a(150) = a(180) = 7 because 90,120,150,180 all have same squarefree kernel = 30 = A002110(3), and 7 is the smallest prime which does not divide 30. - _David James Sycamore_, Dec 04 2024
%p A053669 f:= proc(n) local p;
%p A053669 p:= 2;
%p A053669 while n mod p = 0 do p:= nextprime(p) od:
%p A053669 p
%p A053669 end proc:
%p A053669 map(f, [$1..100]); # _Robert Israel_, May 18 2016
%t A053669 Table[k := 1; While[Not[GCD[n, Prime[k]] == 1], k++ ]; Prime[k], {n, 1, 60}] (* _Stefan Steinerberger_, Apr 01 2006 *)
%t A053669 With[{prs=Prime[Range[10]]},Flatten[Table[Select[prs,!Divisible[ n,#]&,1],{n,110}]]] (* _Harvey P. Dale_, May 03 2012 *)
%o A053669 (Haskell)
%o A053669 a053669 n = head $ dropWhile ((== 0) . (mod n)) a000040_list
%o A053669 -- _Reinhard Zumkeller_, Nov 11 2012
%o A053669 (PARI) a(n)=forprime(p=2,,if(n%p,return(p))) \\ _Charles R Greathouse IV_, Nov 20 2012
%o A053669 (Scheme) (define (A053669 n) (let loop ((i 1)) (cond ((zero? (modulo n (A000040 i))) (loop (+ i 1))) (else (A000040 i))))) ;; _Antti Karttunen_, Jan 26 2014
%o A053669 (Python)
%o A053669 from sympy import nextprime
%o A053669 def a(n):
%o A053669     p = 2
%o A053669     while True:
%o A053669         if n%p: return p
%o A053669         else: p=nextprime(p) # _Indranil Ghosh_, May 12 2017
%o A053669 (Python)
%o A053669 # using standard library functions only
%o A053669 import math
%o A053669 def a(n):
%o A053669     k = 2
%o A053669     while math.gcd(n,k) > 1: k += 1
%o A053669     return k # _Ely Golden_, Nov 26 2020
%Y A053669 One more than A071222(n-1).
%Y A053669 Cf. A000040, A020639, A053670, A053671, A053672, A053673, A053674, A055874, A079578, A087560, A096014, A235921, A236454, A249270, A257993 (the indices of these primes), A276086, A324895, A353526, A353528, A353529, A358754, A358755, A370125.
%Y A053669 Cf. A002110, A007947.
%K A053669 nonn,nice,easy
%O A053669 1,1
%A A053669 _Henry Bottomley_, Feb 15 2000
%E A053669 More terms from Andrew Gacek (andrew(AT)dgi.net), Feb 21 2000 and _James Sellers_, Feb 22 2000
%E A053669 Entry revised by _David W. Wilson_, Nov 25 2006