A053669 - OEIS

%I #115 Feb 13 2025 05:26:34

%S 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 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 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 Smallest prime not dividing n.

%C Smallest prime coprime to n.

%C Smallest k >= 2 coprime to n.

%C a(#(p-1)) = a(A034386(p-1)) = p is the first appearance of prime p in sequence.

%C a(A005408(n)) = 2; for n > 2: a(n) = A112484(n,1). - _Reinhard Zumkeller_, Sep 23 2011

%C Average value is 2.920050977316134... = A249270. - _Charles R Greathouse IV_, Nov 02 2013

%C 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 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 T. D. Noe, <a href="/A053669/b053669.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 James Grime and Brady Haran, <a href="https://www.youtube.com/watch?v=_gCKX6VMvmU&amp;t=347s">2.920050977316</a>, Numberphile video (2020)

%H 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 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 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 a(n!) = A151800(n). - _Anthony Browne_, May 11 2016

%F a(2k+1) = 2. - _Bernard Schott_, Jun 03 2019

%F Asymptotic mean: lim_{n->oo} (1/n) * Sum_{k=1..n} a(k) = A249270. - _Amiram Eldar_, Oct 29 2020

%F a(n) = A000040(A257993(n)) = A020639(A276086(n)) = A276086(n) / A324895(n). - _Antti Karttunen_, Apr 24 2022

%F 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 A007947(n) = A002110(k) ==> a(n) = prime(k+1). - _David James Sycamore_, Dec 04 2024

%e a(60) = 7, since all primes smaller than 7 divide 60 but 7 does not.

%e 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 f:= proc(n) local p;

%p p:= 2;

%p while n mod p = 0 do p:= nextprime(p) od:

%p p

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, May 18 2016

%t Table[k := 1; While[Not[GCD[n, Prime[k]] == 1], k++ ]; Prime[k], {n, 1, 60}] (* _Stefan Steinerberger_, Apr 01 2006 *)

%t With[{prs=Prime[Range[10]]},Flatten[Table[Select[prs,!Divisible[ n,#]&,1],{n,110}]]] (* _Harvey P. Dale_, May 03 2012 *)

%o (Haskell)

%o a053669 n = head $ dropWhile ((== 0) . (mod n)) a000040_list

%o -- _Reinhard Zumkeller_, Nov 11 2012

%o (PARI) a(n)=forprime(p=2,,if(n%p,return(p))) \\ _Charles R Greathouse IV_, Nov 20 2012

%o (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 (Python)

%o from sympy import nextprime

%o def a(n):

%o     p = 2

%o     while True:

%o         if n%p: return p

%o         else: p=nextprime(p) # _Indranil Ghosh_, May 12 2017

%o (Python)

%o # using standard library functions only

%o import math

%o def a(n):

%o     k = 2

%o     while math.gcd(n,k) > 1: k += 1

%o     return k # _Ely Golden_, Nov 26 2020

%Y One more than A071222(n-1).

%Y 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 Cf. A002110, A007947.

%K nonn,nice,easy,changed

%O 1,1

%A _Henry Bottomley_, Feb 15 2000

%E More terms from Andrew Gacek (andrew(AT)dgi.net), Feb 21 2000 and _James A. Sellers_, Feb 22 2000

%E Entry revised by _David W. Wilson_, Nov 25 2006