A079578 -id:A079578 - cp's OEIS frontend

A053669 Smallest prime not dividing n.

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, 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, 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

Offset: 1

Henry Bottomley, Feb 15 2000

Smallest prime coprime to n.
Smallest k >= 2 coprime to n.
a(#(p-1)) = a(A034386(p-1)) = p is the first appearance of prime p in sequence.
a(A005408(n)) = 2; for n > 2: a(n) = A112484(n,1). - Reinhard Zumkeller, Sep 23 2011
Average value is 2.920050977316134... = A249270. - Charles R Greathouse IV, Nov 02 2013
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
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

			a(60) = 7, since all primes smaller than 7 divide 60 but 7 does not.
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

T. D. Noe, Table of n, a(n) for n = 1..10000
Dylan Fridman, Juli Garbulsky, Bruno Glecer, James Grime and Massi Tron Florentin, A Prime-Representing Constant, The American Mathematical Monthly, Vol. 126, No. 1 (2019), pp. 70-73; ResearchGate link.
James Grime and Brady Haran, 2.920050977316, Numberphile video (2020)
Igor Rivin, Geodesics with one self-intersection, and other stories, Advances in Mathematics, Vol. 231, No. 5 (2012), pp. 2391-2412; arXiv preprint, arXiv:0901.2543 [math.GT], 2009-2011.

One more than A071222(n-1).
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.
Cf. A002110, A007947.

a053669 n = head $ dropWhile ((== 0) . (mod n)) a000040_list
-- Reinhard Zumkeller, Nov 11 2012

f:= proc(n) local p;
p:= 2;
while n mod p = 0 do p:= nextprime(p) od:
p
end proc:
map(f, [$1..100]); # Robert Israel, May 18 2016

Table[k := 1; While[Not[GCD[n, Prime[k]] == 1], k++ ]; Prime[k], {n, 1, 60}] (* Stefan Steinerberger, Apr 01 2006 *)
With[{prs=Prime[Range[10]]},Flatten[Table[Select[prs,!Divisible[ n,#]&,1],{n,110}]]] (* Harvey P. Dale, May 03 2012 *)

a(n)=forprime(p=2,,if(n%p,return(p))) \\ Charles R Greathouse IV, Nov 20 2012

from sympy import nextprime
def a(n):
    p = 2
    while True:
        if n%p: return p
        else: p=nextprime(p) # Indranil Ghosh, May 12 2017

# using standard library functions only
import math
def a(n):
    k = 2
    while math.gcd(n,k) > 1: k += 1
    return k # Ely Golden, Nov 26 2020

(define (A053669 n) (let loop ((i 1)) (cond ((zero? (modulo n (A000040 i))) (loop (+ i 1))) (else (A000040 i))))) ;; Antti Karttunen, Jan 26 2014

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
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
a(n!) = A151800(n). - Anthony Browne, May 11 2016
a(2k+1) = 2. - Bernard Schott, Jun 03 2019
Asymptotic mean: lim_{n->oo} (1/n) * Sum_{k=1..n} a(k) = A249270. - Amiram Eldar, Oct 29 2020
a(n) = A000040(A257993(n)) = A020639(A276086(n)) = A276086(n) / A324895(n). - Antti Karttunen, Apr 24 2022
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
A007947(n) = A002110(k) ==> a(n) = prime(k+1). - David James Sycamore, Dec 04 2024

More terms from Andrew Gacek (andrew(AT)dgi.net), Feb 21 2000 and James Sellers, Feb 22 2000

Entry revised by David W. Wilson, Nov 25 2006

A085229 Smallest number which is coprime to n and to a(n-1), and is not yet in the sequence; a(1)=1.

Original entry on oeis.org

1, 3, 2, 5, 4, 7, 6, 11, 8, 9, 10, 13, 12, 17, 14, 15, 16, 19, 18, 23, 20, 21, 22, 25, 24, 29, 26, 27, 28, 31, 30, 37, 32, 33, 34, 35, 36, 41, 38, 39, 40, 43, 42, 47, 44, 45, 46, 49, 48, 53, 50, 51, 52, 55, 54, 59, 56, 57, 58, 61, 60, 67, 62, 63, 64, 65, 66, 71, 68

Offset: 1

Reinhard Zumkeller, Jun 22 2003

nonn

Permutation of natural numbers with inverse A085230: a(A085230(n))=A085230(a(n))=n.
From Michael De Vlieger, Apr 13 2022: (Start)
Theorem 1: 2 | a(2k+1) for k > 0, consequence of the lexically earliest and coprimality axioms. Even numbers appear in order as a consequence of the latter axiom and since numbers are either even or odd.
Corollary: the only fixed point is a(1) = 1.
Theorem 2: Generally, if prime p | a(n) then p is coprime to a(n +/- 1). For p = 2, 2 | a(2k+1) for k > 0 since 2 is the smallest prime. For odd p it is not necessarily true that given p | a(n) -> p | a(n+2) or p | a(n-2), since there may be a smaller m such that (a(n-1), m) = 1, q | m for prime q < p, and is not in a(1..n-1).
For these reasons, if we also set a(2) = 3, then we need not also check (n, a(n)) = 1, since it isn't possible. If we do not check (n, a(n)) = 1 and set a(2) = 3, 2 would follow 1 since 1 is coprime to all numbers.
Theorem 3: 3 | a(3k+1) for k > 1. Proof: For even k, 6 | a(3k+1), i.e., 6 | a(n) : n mod 6 = 1, and it is easy to see that since even numbers appear in order in the sequence, these even multiples of 3 are also in order. Because 3 | a(n) : n mod 6 = 1, we cannot have 3 | a(n) for n congruent to 0 or 2 (mod 6). Furthermore, we know that 2 | a(n) for n congruent to 3 or 5 (mod 6). So 3 | a(n) odd : n mod 6 = 4, that is, 3 | a(3k+1) for k > 1.
Theorem 4: Odd primes q set records. Proof: (q, a(n-1)) = 1 as a consequence of lexically earliest axiom that rules out equality, and by the definition of prime. 2 is displaced on account of the axiom that bans equality between n and a(n). Therefore, whereupon q is the smallest unused odd number, it enters the sequence.
A consequence of theorems 1 and 3 is that powers of 2 and those of 3 excepting 3 itself do not set records, since their adjacency is governed by a(n-1). The powers of other primes do set records since coprimality does not depend on multiplicity.
The smallest composite record is a(24) = 25. Smallest record m with omega(m) > 1 is a(54) = 55. Powers of 2 and 3 are absent from records for n <= 2^20. (End)

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Michael De Vlieger, Annotated log-log scatterplot of a(n) for n = 1..256, showing records in red, local minima in blue, and highlighting fixed points in amber and primes in green.
Amit Kumar Basistha and Eugen J. Ionascu, A special sequence and primorial numbers, arXiv:2302.02838 [math.NT], 2023.
Index entries for sequences that are permutations of the natural numbers

Cf. A079578, A084937, A093714.

nn = 10000; c[] = 0; a[1] = c[1] = 1; a[2] = 3; c[3] = u = 2; Do[k = u; While[Nand[c[k] == 0, CoprimeQ[a[i-1], k]], k++]; Set[{a[i], c[k]}, {k, i}]; If[a[i] == u, While[c[u] > 0, u++]], {i, 3, nn}]; Array[a, nn] (* _Michael De Vlieger, Apr 13 2022 *)

from math import gcd
from itertools import count, islice
def agen(): # generator of terms
    an, aset = 1, {1}
    for n in count(2):
        yield an
        k = 1
        while k in aset or any(gcd(t, k) != 1 for t in [n, an]): k+= 1
        aset.add(k)
        an = k
print(list(islice(agen(), 69))) # Michael S. Branicky, Apr 13 2022

A116933 Smallest k greater than 0 such that n+k*p is a prime, where p is the smallest coprime greater than n+1.

Original entry on oeis.org

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

Offset: 1

Reinhard Zumkeller, Feb 27 2006

nonn

a(n) = (A116934(n) - n)/A079578(n).

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

Cf. A010051, A079578.

a116933 n = head [k | k <- [1..], a010051' (n + k * a079578 n) == 1]
-- Reinhard Zumkeller, Oct 01 2014

A116934 First prime in the arithmetic progression (n+k*p: k>0), where p is the smallest coprime greater than n+1.

Original entry on oeis.org

7, 7, 13, 11, 19, 17, 43, 19, 31, 23, 37, 29, 43, 31, 83, 73, 131, 41, 61, 43, 67, 47, 73, 53, 79, 113, 317, 59, 277, 67, 97, 67, 103, 71, 109, 241, 193, 79, 367, 83, 127, 89, 223, 373, 139, 193, 439, 101, 151, 103, 157, 107, 163, 113, 283, 233, 293, 241, 181, 127, 313

Offset: 1

Reinhard Zumkeller, Feb 27 2006

nonn

a(n) = n + A116933(n)*A079578(n).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences related to primes in arithmetic progressions
Eric Weisstein's World of Mathematics, Dirichlet's Theorem.

Cf. A088732.

Cf. A010051, A079578, A116933.

a116934 n = head [q | k <- [1..], let q = n + k * a079578 n,
                      a010051' q == 1]
-- Reinhard Zumkeller, Oct 01 2014

cp's OEIS Frontend

A053669 Smallest prime not dividing n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Python

Scheme

Formula

Extensions

A085229 Smallest number which is coprime to n and to a(n-1), and is not yet in the sequence; a(1)=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

A116933 Smallest k greater than 0 such that n+k*p is a prime, where p is the smallest coprime greater than n+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A116934 First prime in the arithmetic progression (n+k*p: k>0), where p is the smallest coprime greater than n+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell