A001783 -id:A001783 - cp's OEIS frontend

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

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

A083267 Product of related numbers (counted in A073757) belonging to n; related = {divisor-set, RRS}: a(n) = A007955(n)*A001783(n).

Original entry on oeis.org

1, 2, 6, 24, 120, 180, 5040, 6720, 60480, 18900, 39916800, 665280, 6227020800, 3783780, 201801600, 2075673600, 355687428096000, 496215720, 121645100408832000, 69837768000, 20858213376000, 604969665300, 25852016738884976640000, 12336143339520, 5170403347776995328000

Offset: 1

Labos Elemer, May 13 2003

nonn

			For n = 10: related terms = {1,2,5,10,3,7,9}, product = 1*2*5*10*1*3*7*9 = 18900 = a(10).

Amiram Eldar, Table of n, a(n) for n = 1..450

Cf. A073757 (count), A083266 (sum), A083268 (LCM), A083267 (product), A001783, A007955.

a[n_] := n^(DivisorSigma[0, n]/2) * Times@@ Select[Range[n], CoprimeQ[n, #] &]; Array[a, 30] (* Amiram Eldar, Jun 20 2024 *)

More terms from Amiram Eldar, Jun 20 2024

A193339 Indices of record values in A001783.

Original entry on oeis.org

1, 3, 4, 5, 7, 9, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241

Offset: 1

M. F. Hasler, Jul 23 2011

nonn

Indices k such that A001783(k) is larger than all preceding terms of that sequence. The corresponding values A001783(k) are given in A193338.
It appears that, except for 1, 2, 4, and 9, this is all and only the primes. (It certainly includes all odd primes.) - Franklin T. Adams-Watters, Aug 11 2011
It appears that this is the sequence of indices of records in A206369. - Michel Marcus, Nov 04 2017

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A067126.

Block[{s = Table[Times @@ Select[Range@ n, CoprimeQ[n, #] &], {n, 250}], t}, t = Union@ FoldList[Max, s]; Map[FirstPosition[s, #][[1]] &, t]] (* or *)
Union[Prime@ Range[2, 53], Range[3]^2] (* Michael De Vlieger, Nov 04 2017 *)

m=0;for(n=1,599,m+0<(m=max(m,A001783(n))) & print1(n", "))

A280258 a(n) = Sum_{d|n} pxi(d), where pxi(m) is the product of totatives of m (A001783).

Original entry on oeis.org

1, 2, 3, 5, 25, 9, 721, 110, 2243, 215, 3628801, 397, 479001601, 20027, 896923, 2027135, 20922789888001, 87334, 6402373705728001, 8729939, 47297536723, 1253566127, 1124000727777607680001, 37182647, 41363226782215962649, 608621584727, 1524503639859202243

Offset: 1

Jaroslav Krizek, Jan 01 2017

nonn

Conjecture: a(n) is odd for numbers in A183300; a(n) is even for numbers in A001105 (2*n^2).

Numbers n such that a(n) is prime: 2, 3, 4, 9, 12, 20, 27, ... (there are no other terms < 742). Corresponding values of primes: 2, 3, 5, 2243, 397, 8729939, 1524503639859202243, ...

			For n=6; sets of totatives of divisors of 6: {1}, {1}, {1, 2}, {1, 5}; a(6) = 1+1+(1*2)+(1*5) = 9.

Robert G. Wilson v, Table of n, a(n) for n = 1..1000

Cf. A001783, A001105, A183300, A280259, A280260.

[&+[&*[h: h in [1..d] | GCD(h,d) eq 1]: d in Divisors(n)]: n in [1..100]];

Table[Sum[Times @@ Select[Range@ d, CoprimeQ[#, d] &], {d, Divisors@ n}], {n, 27}] (* Michael De Vlieger, Jan 01 2017 *)

a(n) = sumdiv(n, d, prod(k=1, d, if (gcd(k,d)==1, k, 1))); \\ Michel Marcus, Jan 02 2017

a(n) = Sum_{d|n} A001783(d).

A128247 a(n) = A001783(n)/A038610(n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 12, 1, 8, 3, 1440, 1, 17280, 3, 112, 45, 29030400, 1, 522547200, 3, 12800, 945, 4828336128000, 1, 38626689024, 4725, 512512000, 2025, 3796230997278720000, 1, 113886929918361600000, 42525, 10436608000, 1403325, 551910745571328, 175

Offset: 1

Leroy Quet, May 03 2007

nonn

			The positive integers which are <= 10 and are coprime to 10 are 1,3,7,9. So a(10) = 1*3*7*9/lcm(1,3,7,9) = 189/63 = 3.

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

Cf. A038610, A001783.

Table[s = Select[Range[1, n], GCD[#, n] == 1 &]; (Times @@ s)/(LCM @@ s), {n, 30}] (* T. D. Noe, Oct 04 2012 *)

def Gauss_factorial(N, n): return mul(j for j in (1..N) if gcd(j, n) == 1)
def L(N, n): return lcm([j for j in (1..N) if gcd(j, n) == 1])
def A128247(n): return Gauss_factorial(n, n)/L(n, n)
[A128247(n) for n in (1..34)] # Peter Luschny, Oct 02 2012

More terms from Sean A. Irvine, Jun 21 2011

A193338 Record values in A001783.

Original entry on oeis.org

1, 2, 3, 24, 720, 2240, 3628800, 479001600, 20922789888000, 6402373705728000, 1124000727777607680000, 304888344611713860501504000000, 265252859812191058636308480000000, 371993326789901217467999448150835200000000

Offset: 1

M. F. Hasler, Jul 23 2011

nonn

Terms of A001783 which are larger than all preceding terms of that sequence. The corresponding indices are given in A193339.

m=0;for(n=1,49,m+0<(m=max(m,A001783(n))) & print1(m", "))

a(n)=A001783(A193339(n))

A280821 Partial products of A001783.

Original entry on oeis.org

1, 1, 2, 6, 144, 720, 518400, 54432000, 121927680000, 23044331520000, 83623270219776000000, 32194959034613760000000, 15421436889514446422016000000000, 297710839152076388177018880000000000, 267015660792140704250415525396480000000000

Offset: 1

Jaroslav Krizek, Jan 11 2017

nonn

A001783(n) = the product of totatives of n.

Project Euler, Problem 754: Product of Gauss Factorials.

Cf. A000178, A001783, A280820, A281027.

[&*[&*[h: h in [1..k] | GCD(h,k) eq 1]: k in [1..n]]: n in [1..100]];

FoldList[#1 #2 &, Table[Times @@ Select[Range@ n, CoprimeQ[n, #] &], {n, 15}]] (* Michael De Vlieger, Jan 11 2017 *)
SetAttributes[Phitorial,{Listable}]
Phitorial[n_]:=n^EulerPhi[n]*Times@@((Factorial[#]/#^#)^MoebiusMu[n/#]&/@Divisors[n])
FoldList[Times,Phitorial[Range[20]]] (* Peter Cullen Burbery, Jul 14 2023 *)

f(n) = prod(k=2, n-1, k^(gcd(k, n)==1)); \\ A001783
a(n) = prod(i=1, n, f(i)); \\ Michel Marcus, Jul 14 2023

a(n) = Product_{i=1..n} A001783(i).

a(n) = A000178(n)/A281027(n). - Amiram Eldar, Aug 16 2025

A280820 Partial sums of A001783.

Original entry on oeis.org

1, 2, 4, 7, 31, 36, 756, 861, 3101, 3290, 3632090, 3632475, 482634075, 482653380, 483550276, 485577301, 20923275465301, 20923275550386, 6423296981278386, 6423296990008107, 6423344287544107, 6423345537481432, 1124007151123145161432, 1124007151123182343577

Offset: 1

Jaroslav Krizek, Jan 08 2017

nonn

A001783(n) = the product of totatives of n.

Cf. A001783, A280821.

[&+[&*[h: h in [1..k] | GCD(h,k) eq 1]: k in [1..n]]: n in [1..100]]

Accumulate@ Table[Times @@ Select[Range@ n, CoprimeQ[n, #] &], {n, 24}] (* Michael De Vlieger, Jan 09 2017 *)

a(n) = Sum_{i=1..n} A001783(i).

A193340 Terms of A001783 which are smaller than the preceding term in that sequence.

Original entry on oeis.org

1, 5, 105, 189, 385, 19305, 85085, 8729721, 1249937325, 37182145, 608142583125, 1452095555625, 215656441, 191898783962510625, 372509404162520625, 29248404810625, 431620764875678503125, 4873615036539089841, 181101347337625, 1553338924739899476440625

Offset: 1

M. F. Hasler, Jul 23 2011

nonn

Appears to be a subsequence of A124441.

Cf. A193338, A193339 for record values in A001783.

m=9;for(n=1,99,m+0>(m=A001783(n)) && print1(m", "))

A023896 Sum of positive integers in smallest positive reduced residue system modulo n. a(1) = 1 by convention.

Original entry on oeis.org

1, 1, 3, 4, 10, 6, 21, 16, 27, 20, 55, 24, 78, 42, 60, 64, 136, 54, 171, 80, 126, 110, 253, 96, 250, 156, 243, 168, 406, 120, 465, 256, 330, 272, 420, 216, 666, 342, 468, 320, 820, 252, 903, 440, 540, 506, 1081, 384, 1029, 500, 816, 624, 1378, 486, 1100, 672

Offset: 1

Olivier Gérard

Sum of totatives of n, i.e., sum of integers up to n and coprime to n.
a(1) = 1, since 1 is coprime to any positive integer.
Row sums of A038566. - Wolfdieter Lang, May 03 2015
Islam & Manzoor prove that a(n) is an injection for n > 1, see links. In other words, if a(m) = a(n), and min(m, n) > 1, then m = n. - Muhammed Hedayet, May 19 2024

			G.f. = x + x^2 + 3*x^3 + 4*x^4 + 10*x^5 + 6*x^6 + 21*x^7 + 16*x^8 + 27*x^9 + ...
a(12) = 1 + 5 + 7 + 11 = 24.
n = 40: The smallest positive reduced residue system modulo 40 is {1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39}. The sum is a(40) = 320. Average is 20.

Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 48, problem 16, the function phi_1(n).
David M. Burton, Elementary Number Theory, p. 171.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 2001, p. 163.
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 111.

Michael De Vlieger, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
John D. Baum, A Number-Theoretic Sum, Mathematics Magazine 55.2 (1982): 111-113.
Geoffrey B. Campbell, Dirichlet summations and products over primes, Int. J. Math. Math. Sci. 16 92) (1993) 359. eq. (3.1)
Muhammed H. Islam and Shahriar Manzoor, φ1 and phitorial are injections, for any positive integer N, where N > 1.
Constantin M. Petridi, The Sums of the k-powers of the Euler set and their connection with Artin's conjecture for primitive roots, arXiv:1612.07632 [math.NT], 2016.
David Zmiaikou, Origamis and permutation groups, Thesis, 2011. See p. 65.

Cf. A000010, A000203, A002180, A045545, A001783, A024816, A066760, A054521, A067392, A038566.
Row sums of A127368, A144734, A144824.
Cf. A000217, A002618, A008683, A009195, A023022, A065484, A076512, A175505, A175506.

a023896 = sum . a038566_row  -- Reinhard Zumkeller, Mar 04 2012

[1] cat [n*EulerPhi(n)/2: n in [2..70]]; // Vincenzo Librandi, May 16 2015

A023896 := proc(n)
    if n = 1 then
        1;
    else
        n*numtheory[phi](n)/2 ;
    end if;
end proc: # R. J. Mathar, Sep 26 2013

a[ n_ ] = n/2*EulerPhi[ n ]; a[ 1 ] = 1; Table[a[n], {n, 56}]
a[ n_] := If[ n < 2, Boole[n == 1], Sum[ k Boole[1 == GCD[n, k]], { k, n}]]; (* Michael Somos, Jul 08 2014 *)

{a(n) = if(n<2, n>0, n*eulerphi(n)/2)};

A023896(n)=n*eulerphi(n)\/2 \\ about 10% faster. - M. F. Hasler, Feb 01 2021

from sympy import totient
def A023896(n): return 1 if n == 1 else n*totient(n)//2 # Chai Wah Wu, Apr 08 2022

def A023896(n): return 1 if n == 1 else n*euler_phi(n)//2
print([A023896(n) for n in range(1, 57)])  # Peter Luschny, Dec 03 2023

a(n) = n*A023022(n) for n > 2.
a(n) = phi(n^2)/2 = n*phi(n)/2 = A002618(n)/2 if n > 1, a(1)=1. See the Apostol reference for this exercise.
a(n) = Sum_{1 <= k < n, gcd(k, n) = 1} k.
If n = p is a prime, a(p) = T(p-1) where T(k) is the k-th triangular number (A000217). - Robert G. Wilson v, Jul 31 2004
Equals A054521 * [1,2,3,...]. - Gary W. Adamson, May 20 2007
a(n) = A053818(n) * A175506(n) / A175505(n). - Jaroslav Krizek, Aug 01 2010
If m,n > 1 and gcd(m,n) = 1 then a(m*n) = 2*a(m)*a(n). - Thomas Ordowski, Nov 09 2014
G.f.: Sum_{n>=1} mu(n)*n*x^n/(1-x^n)^3, where mu(n) = A008683(n). - Mamuka Jibladze, Apr 24 2015
G.f. A(x) satisfies A(x) = x/(1 - x)^3 - Sum_{k>=2} k * A(x^k). - Ilya Gutkovskiy, Sep 06 2019
For n > 1: a(n) = (n*A076512(n)/2)*A009195(n). - Jamie Morken, Dec 16 2019
Sum_{n>=1} 1/a(n) = 2 * A065484 - 1 = 3.407713... . - Amiram Eldar, Oct 09 2023

Typos in programs corrected by Zak Seidov, Aug 03 2010

Name and example edited by Wolfdieter Lang, May 03 2015

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

Extensions

A083267 Product of related numbers (counted in A073757) belonging to n; related = {divisor-set, RRS}: a(n) = A007955(n)*A001783(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A193339 Indices of record values in A001783.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A280258 a(n) = Sum_{d|n} pxi(d), where pxi(m) is the product of totatives of m (A001783).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A128247 a(n) = A001783(n)/A038610(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Extensions

A193338 Record values in A001783.

Views

Author

Keywords

Comments

Programs

PARI

Formula

A280821 Partial products of A001783.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A280820 Partial sums of A001783.