A124740 -id:A124740 - cp's OEIS frontend

A057475 Number of k, 1 <= k <= n, such that gcd(n,k) = gcd(n+1,k) = 1.

1, 1, 1, 2, 1, 2, 3, 3, 2, 4, 3, 4, 5, 3, 4, 8, 5, 6, 7, 5, 5, 10, 7, 7, 9, 8, 8, 12, 7, 8, 15, 10, 9, 11, 8, 12, 17, 11, 9, 16, 11, 12, 19, 11, 11, 22, 15, 14, 17, 13, 15, 24, 17, 14, 17, 15, 17, 28, 15, 16, 29, 17, 18, 24, 15, 20, 31, 21, 15, 24, 23, 24, 35, 19, 19, 28, 18, 24, 31, 22

Offset: 1

Leroy Quet, Sep 27 2000

nonn

Number of numbers between 1 and n-1 coprime to n(n+1).

It is conjectured that every positive integer appears. - Jon Perry, Dec 12 2002

			a(8) = 3 because 1, 5 and 7 are all relatively prime to both 8 and 9.
a(9) counts those numbers coprime to 90, i.e., 1 and 7, hence a(9) = 2.

Cf. A000040, A000010, A065474, A118854, A124738, A124739, A124740, A124741.

Cf. A057828, A002378.

[#[k:k in [1..n]| Gcd(n,k) eq Gcd(n+1,k) and Gcd(n,k) eq 1]: n in [1..80]]; // Marius A. Burtea, Oct 15 2019

A057475 := proc(n)
    local a,k ;
    a :=  0;
    for k from 1 to n do
        if igcd(k,n) = 1 and igcd(k,n+1)=1 then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc:
seq(A057475(n),n=1..80) ; # R. J. Mathar, May 13 2025

a[ n_ ] := Length @ Select[ Range[ n ], GCD[ n, # ] == GCD[ n + 1, # ] == 1 & ]; Table[ a[ n ], {n, 80} ] (* Ray Chandler, Dec 06 2006 *)

newphi(v)=local(vl,fl,np); vl=length(v); np=0; for (s=1,v[1],fl=false; for (r=1,vl,if (gcd(s,v[r])>1,fl=true; break)); if (fl==false,np++)); np
v=vector(2); for (i=1,500,v[1]=i; v[2]=i+1; print1(newphi(v)","))

From Reinhard Zumkeller, May 02 2006: (Start)
a(A000040(n)-1) = A000010(A000040(n)-1);
a(A000040(n)) = A000010(A000040(n)+1)-1;
a(A118854(n)-1) = a(A118854(n)). (End)
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Product_{p prime} (1 - 2/p^2) = 0.322634... (A065474). - Amiram Eldar, Dec 10 2024
a(n) = A057828(A002378(n)). - Ridouane Oudra, May 30 2025

A124738 Irregular table where the n-th row consists of those positive integers which are coprime to both n and n+1 and which are <= n.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 5, 1, 3, 5, 1, 5, 7, 1, 7, 1, 3, 7, 9, 1, 5, 7, 1, 5, 7, 11, 1, 3, 5, 9, 11, 1, 11, 13, 1, 7, 11, 13, 1, 3, 5, 7, 9, 11, 13, 15, 1, 5, 7, 11, 13, 1, 5, 7, 11, 13, 17, 1, 3, 7, 9, 11, 13, 17, 1, 11, 13, 17, 19, 1, 5, 13, 17, 19, 1, 3, 5, 7, 9, 13, 15, 17, 19, 21, 1, 5, 7, 11, 13

Offset: 1

Leroy Quet, Nov 06 2006

The n-th row has A057475(n) terms.

			The positive integers which are coprime to 8 and which are <= 8 are 1,3,5,7. The integers which are coprime to 9 and which are <= 9 are 1, The integers in both these sequences (1,5,7) make up the row of A124738.

Cf. A057475, A124739, A124740, A124741.

f[n_] := Select[Range[n], GCD[n, # ] == GCD[n + 1, # ] == 1 &]; Flatten[Table[f[n], {n, 23}]] (* Ray Chandler, Nov 10 2006 *)

Extended by Ray Chandler, Nov 10 2006

A124741 a(n) = largest of those positive integers which are coprime to both n and n+1 and which are <= n.

Original entry on oeis.org

1, 1, 1, 3, 1, 5, 5, 7, 7, 9, 7, 11, 11, 13, 13, 15, 13, 17, 17, 19, 19, 21, 19, 23, 23, 25, 25, 27, 23, 29, 29, 31, 31, 33, 31, 35, 35, 37, 37, 39, 37, 41, 41, 43, 43, 45, 43, 47, 47, 49, 49, 51, 49, 53, 53, 55, 55, 57, 53, 59, 59, 61, 61, 63, 61, 65, 65, 67, 67, 69, 67, 71, 71

Offset: 1

Leroy Quet, Nov 06 2006

nonn

			The positive integers which are coprime to 8 and which are <= 8 are 1,3,5,7. The positive integers which are coprime to 9 and which are <= 9 are 1, 2,4,5,7,8. So a(8) = 7, which is the largest of those integers in both these sequences (1,5,7).

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A057475, A124738, A124739, A124740.

f[n_] := Last @ Select[Range[n], GCD[n, # ] == GCD[n + 1, # ] == 1 &];Table[f[n], {n, 75}] (* Ray Chandler, Nov 10 2006 *)
Join[{1},Table[Max[Intersection[Select[Range[n-1],CoprimeQ[ #,n]&],Select[ Range[n-1],CoprimeQ[#,n+1]&]]],{n,2,80}]] (* Harvey P. Dale, Jul 08 2018 *)

Extended by Ray Chandler, Nov 10 2006

A124739 a(n) = sum of those positive integers which are coprime to both n and n+1 and which are <= n.

Original entry on oeis.org

1, 1, 1, 4, 1, 6, 9, 13, 8, 20, 13, 24, 29, 25, 32, 64, 37, 54, 61, 61, 55, 110, 73, 91, 111, 108, 114, 168, 91, 120, 225, 170, 153, 199, 144, 216, 305, 221, 175, 320, 211, 252, 397, 261, 249, 506, 337, 342, 423, 351, 403, 624, 433, 410, 483, 431, 493, 812, 421, 480

Offset: 1

Leroy Quet, Nov 06 2006

nonn

			The positive integers which are coprime to 8 and which are <= 8 are 1,3,5,7. The integers which are coprime to 9 and which are <= 9 are 1, The integers in both these sequences (1,5,7) are added get a(8) = 13.

Cf. A057475, A124738, A124740, A124741.

f[n_] := Plus @@ Select[Range[n], GCD[n, # ] == GCD[n + 1, # ] == 1 &];Table[f[n], {n, 60}] (* Ray Chandler, Nov 10 2006 *)

Extended by Ray Chandler, Nov 10 2006

A160377 Phi-torial of n (A001783) modulo n.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 1, 8, 9, 10, 1, 12, 13, 1, 1, 16, 17, 18, 1, 1, 21, 22, 1, 24, 25, 26, 1, 28, 1, 30, 1, 1, 33, 1, 1, 36, 37, 1, 1, 40, 1, 42, 1, 1, 45, 46, 1, 48, 49, 1, 1, 52, 53, 1, 1, 1, 57, 58, 1, 60, 61, 1, 1, 1, 1, 66, 1, 1, 1, 70, 1, 72, 73, 1, 1, 1, 1, 78, 1, 80, 81, 82, 1, 1, 85, 1, 1

Offset: 1

J. M. Bergot, May 11 2009

nonn

Is a(n)<> 1 iff n in A033948, n>2? [R. J. Mathar, May 21 2009]

Same as A103131, except there -1 appears instead of n-1. By Gauss's generalization of Wilson's theorem, a(n)=-1 means n has a primitive root (n in A033948) and a(n)=1 means n has no primitive root (n in A033949). [T. D. Noe, May 21 2009]

			Phi-torial of 12 equals 1*5*7*11=385 which leaves a remainder of 1 when divided by 12.
Phi-torial of 14 equals 1*3*5*9*11*13=19305 which leaves a remainder of 13 when divided by 14.

Amiram Eldar, Table of n, a(n) for n = 1..10000
John B. Cosgrave and Karl Dilcher, Extensions of the Gauss-Wilson Theorem, Integers: Electronic Journal of Combinatorial Number Theory, Vol. 8 (2008), Article #A39.
Eric Weisstein's World of Mathematics, Wilson's Theorem.

Cf. A124740 (one of just four listing "product of coprimes").

copr := proc(n) local a,k ; a := {1} ; for k from 2 to n-1 do if gcd(k,n) = 1 then a := a union {k} ; fi; od: a ; end:
A001783 := proc(n) local c; mul(c,c= copr(n)) ; end:
A160377 := proc(n) A001783(n) mod n ; end: seq( A160377(n),n=1..100) ; # R. J. Mathar, May 21 2009
A160377 := proc(n) local k, r; r := 1:
for k to n do if igcd(n,k) = 1 then r := modp(r*k, n) fi od;
r end: seq( A160377(i), i=1..88); # Peter Luschny, Oct 20 2012

Table[nn = n; a = Select[Range[nn], CoprimeQ[#, nn] &];
Mod[Apply[Times, a], nn], {n, 1, 88}] (* Geoffrey Critzer, Jan 03 2015 *)

def A160377(n):
    r = 1
    for k in (1..n):
        if gcd(n, k) == 1: r = mod(r*k, n)
    return r
[A160377(n) for n in (1..88)]  # Peter Luschny, Oct 20 2012

a(n) = A001783(n) mod n. - R. J. Mathar, May 21 2009
For n>2, a(n)=n-1 if A060594(n)=2; otherwise a(n)=1. - Max Alekseyev
a(n) = Gauss_factorial(n, n) modulo n. (Definition of the Gauss factorial in A216919.) - Peter Luschny, Oct 20 2012

Edited and extended by R. J. Mathar and Max Alekseyev, May 21 2009

cp's OEIS Frontend

A057475 Number of k, 1 <= k <= n, such that gcd(n,k) = gcd(n+1,k) = 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A124738 Irregular table where the n-th row consists of those positive integers which are coprime to both n and n+1 and which are <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A124741 a(n) = largest of those positive integers which are coprime to both n and n+1 and which are <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A124739 a(n) = sum of those positive integers which are coprime to both n and n+1 and which are <= n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Extensions

A160377 Phi-torial of n (A001783) modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

Extensions