A048669 -id:A048669 - cp's OEIS frontend

A132468 Longest gap between numbers relatively prime to n.

0, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 3, 1, 3, 2, 1, 1, 3, 1, 3, 2, 3, 1, 3, 1, 3, 1, 3, 1, 5, 1, 1, 2, 3, 2, 3, 1, 3, 2, 3, 1, 5, 1, 3, 2, 3, 1, 3, 1, 3, 2, 3, 1, 3, 2, 3, 2, 3, 1, 5, 1, 3, 2, 1, 2, 5, 1, 3, 2, 5, 1, 3, 1, 3, 2, 3, 2, 5, 1, 3, 1, 3, 1, 5, 2, 3, 2, 3, 1, 5, 2, 3, 2, 3, 2, 3, 1, 3, 2, 3, 1, 5, 1, 3, 4

Offset: 1

Michael Kleber, Nov 16 2007

nonn

Here "gap" does not include the endpoints.

a(n) is given by the maximum length of a run of numbers satisfying one congruence modulo each of n's distinct prime factors. It follows that if m is the number of distinct prime factors of n and each of n's prime factors is greater than m then a(n) = m. - Thomas Anton, Dec 30 2018

			E.g. n=3: the longest gap in 1, 2, 4, 5, 7, ... is 1, between 2 and 4, so a(3) = 1.

N. J. A. Sloane, Table of n, a(n) for n = 1..20000
Mario Ziller, John F. Morack, Algorithmic concepts for the computation of Jacobsthal's function, arXiv:1611.03310 [math.NT], 2016.

Equals A048669(n) - 1.

See also A048670, A049298, A070791, A070194.

a:=[];
for n from 1 to 120 do
s:=[seq(j,j=1..4*n)];
rec:=0;
   for st from 1 to n do
   len:=0;
    for i from 1 to n while gcd(s[st+i-1],n)>1 do len:=len+1; od:
    if len>rec then rec:=len; fi;
   od:
a:=[op(a),rec];
od:
a; # N. J. A. Sloane, Apr 18 2017

a[ n_ ] := (Max[ Drop[ #,1 ]-Drop[ #,-1 ] ]-1&)[ Select[ Range[ n+1 ],GCD[ #,n ]==1& ] ]
Do[Print[n, " ", a[n]],{n,20000}]

a(n) = 1 at every prime power.

Incorrect formula removed by Thomas Anton, Dec 30 2018

A128707 Least number having the maximal distance between consecutive integers coprime to n.

Original entry on oeis.org

1, 1, 2, 1, 4, 1, 6, 1, 2, 3, 10, 1, 12, 5, 4, 1, 16, 1, 18, 3, 5, 9, 22, 1, 4, 11, 2, 5, 28, 1, 30, 1, 10, 15, 13, 1, 36, 17, 11, 3, 40, 5, 42, 9, 4, 21, 46, 1, 6, 3, 16, 11, 52, 1, 9, 5, 17, 27, 58, 1, 60, 29, 5, 1, 24, 7, 66, 15, 22, 3, 70, 1, 72, 35, 4, 17, 20, 11, 78, 3, 2, 39, 82, 5, 33

Offset: 1

T. D. Noe, Mar 24 2007

nonn

Let j(n) be the Jacobsthal function (A048669): maximal distance between consecutive integers coprime to n. Then a(n) is the least k>0 such that k+1,k+2,...k+j(n)-1 are not coprime to n. If n is prime and e>0, then j(n^e)=2 and a(n^e)=n-1. If n>2 is prime, then a(2n)=n-2. If m is the squarefree kernel of n (A007947), then j(n)=j(m) and a(n)=a(m). For composite n, a(n)A055932. When n is the product of the first r primes (A002110), then a(n)+1 begins (or is inside) a prime gap of size at least A048670(r).

			The numbers coprime to 10 are 1,3,7,9,11,13,17,19,... Observe that the differences are periodic: 2,4,2,2,2,4,2,... The largest distance between the coprime numbers is 4, which first occurs between 3 and 7. Hence j(10)=4 and a(10)=3.

T. D. Noe, Table of n, a(n) for n=1..10000

Cf. A128708 (number of times the maximal value occurs).

JacobsthalPos[n_] := Module[{g,d,mx,pos}, g=Select[Range[n+1], GCD[n,# ]==1&]; d=Rest[g]-Most[g]; mx=Max@@d; pos=Position[d,mx,1,1][[1,1]]; g[[pos]]]; Table[JacobsthalPos[n], {n,100}]

A049298 Take reduced residue systems of n, generate its first differences, dRRS(n); sequence gives maximal value of dRSSS(n).

Original entry on oeis.org

0, 0, 2, 2, 2, 4, 2, 2, 2, 4, 2, 4, 2, 4, 3, 2, 2, 4, 2, 4, 3, 4, 2, 4, 2, 4, 2, 4, 2, 6, 2, 2, 3, 4, 3, 4, 2, 4, 3, 4, 2, 6, 2, 4, 3, 4, 2, 4, 2, 4, 3, 4, 2, 4, 3, 4, 3, 4, 2, 6, 2, 4, 3, 2, 3, 6, 2, 4, 3, 6, 2, 4, 2, 4, 3, 4, 3, 6, 2, 4, 2, 4, 2, 6, 3, 4, 3, 4, 2, 6, 3, 4, 3, 4, 3, 4, 2, 4, 3, 4, 2, 6, 2, 4, 5

Offset: 1

Labos Elemer

nonn

Greatest values occur at primorial numbers (A002110).

			If n is prime, its reduced residue system consists of all numbers below n. But the difference 2 arises from d=1-(n-1)=-n+2 (mod n).

Cf. A048670. Essentially same as A048669.

A285183 Nearest integer to n*omega(n)/phi(n).

Original entry on oeis.org

0, 2, 2, 2, 1, 6, 1, 2, 2, 5, 1, 6, 1, 5, 4, 2, 1, 6, 1, 5, 4, 4, 1, 6, 1, 4, 2, 5, 1, 11, 1, 2, 3, 4, 3, 6, 1, 4, 3, 5, 1, 11, 1, 4, 4, 4, 1, 6, 1, 5, 3, 4, 1, 6, 3, 5, 3, 4, 1, 11, 1, 4, 4, 2, 3, 10, 1, 4, 3, 9, 1, 6, 1, 4, 4, 4, 3, 10, 1, 5, 2, 4, 1, 11, 3, 4, 3, 4, 1, 11, 3, 4, 3, 4, 3, 6

Offset: 1

N. J. A. Sloane, Apr 19 2017

nonn

n*omega(n)/phi(n) appears in certain bounds of Erdős for the Jacobsthal function g(n) (A048669).

József Sándor, Dragoslav S. Mitrinovic, and Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, Chapter I, p. 34, section I.32.3.

Vincenzo Librandi, Table of n, a(n) for n = 1..10000
Paul Erdős, On the integers relatively prime to n and on a number theoretic function considered by Jacobsthal, Math. Scand., 10, 1962, 163-170.

Cf. A000010 (phi), A001221 (omega), A048669.

[Round(n*#PrimeDivisors(n)/EulerPhi(n)): n in [1..100]]; // Vincenzo Librandi, Apr 21 2017

Digits:=30;
A001221 := proc(n) nops(numtheory[factorset](n)) end proc:
with(numtheory);
f:=n->round(n*A001221(n)/phi(n));
t1:=[seq(f(n),n=1..130)];

Round[Table[(n PrimeNu[n] + 1/2)/EulerPhi[n], {n, 1, 100}]] (* Vincenzo Librandi, Apr 21 2017 - confirmed by Giovanni Resta *)

a(n) = {my(f = factor(n)); round(n*omega(f)/eulerphi(f));} \\ Amiram Eldar, Apr 25 2024

A192224 P-integers: n such that the first phi(n) primes coprime to n form a reduced residue system modulo n, where phi is Euler's totient function A000010.

Original entry on oeis.org

2, 4, 6, 12, 18, 30

Offset: 1

Jonathan Sondow, Jun 29 2011

Pomerance proved that the sequence is finite and conjectured that 30 is the largest element. Hajdu and Saradha proved Recamán's conjecture that 2 is the only prime P-integer. Both proofs use Jacobsthal's function A048669.
Hajdu, Saradha, and Tijdeman have a conditional proof of Pomerance's conjecture, assuming the Riemann Hypothesis.
Shichun Yanga and Alain Togbéb have proved Pomerance's conjecture. - Jonathan Sondow, Jun 14 2014

			12 is a P-integer because phi(12) = 4 and the first four primes coprime to 12 are 5, 7, 11, 13, which are pairwise incongruent modulo 12.
8 is not a P-integer because phi(8) = 4 and the first four primes coprime to 8 are 3, 5, 7, 11, but 3 == 11 (mod 8).

B. M. Recamán, Problem 672, J. Recreational Math. 10 (1978), 283.

L. Hajdu, On a conjecture of Pomerance and the Jacobsthal function, 27th Journées Arithmétiques
L. Hajdu and N. Saradha, On a problem of Recaman and its generalization
L. Hajdu, N. Saradha, and R. Tijdeman, On a conjecture of Pomerance, arXiv:1107.5191 [math.NT], 2011.
C. Pomerance, A note on the least prime in an arithmetic progression, J. Number Theory 12 (1980), 218-223.
Shichun Yanga and Alain Togbéb, Proof of the P-integer conjecture of Pomerance, J. Number Theory, 140 (2014), 226-234. DOI: 10.1016/j.jnt.2014.01.014.

Cf. A000010 (Euler totient function phi), A048669 (Jacobsthal function).

A176526 Arises in cyclotomic integers, fusion categories and subfactors.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 28, 30, 35, 36, 40, 42, 45, 48, 50, 60, 70, 72, 75, 80, 84, 90, 100, 105, 120, 140, 144, 150, 180, 200, 210, 240, 300, 360, 420, 600, 720

Offset: 1

Jonathan Vos Post, Apr 19 2010

Appears in Calegari, proof of 4.2.5. Lemma, p. 12.

Frank Calegari, Scott Morrison, Noah Snyder, Cyclotomic integers, fusion categories, and subfactors, arXiv:1004.0665 [math.NT], 2010.
J. H. Conway and A. J. Jones, Trigonometric Diophantine equations (on vanishing sums of roots of unity), Acta Arith. XXX (1976) 229-240. MR0422149.

Cf. A048669.

cp's OEIS Frontend

A132468 Longest gap between numbers relatively prime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A128707 Least number having the maximal distance between consecutive integers coprime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A049298 Take reduced residue systems of n, generate its first differences, dRRS(n); sequence gives maximal value of dRSSS(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

A285183 Nearest integer to n*omega(n)/phi(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

A192224 P-integers: n such that the first phi(n) primes coprime to n form a reduced residue system modulo n, where phi is Euler's totient function A000010.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A176526 Arises in cyclotomic integers, fusion categories and subfactors.

Views

Author

Keywords

Comments

Links

Crossrefs