|
%I #98 Dec 03 2022 19:41:02
%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
%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&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
%e a(60) = 7, since all primes smaller than 7 divide 60 but 7 does not.
%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.
%K nonn,nice,easy
%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
|
