A007735 -id:A007735 - cp's OEIS frontend

A046073 Number of squares in multiplicative group modulo n.

1, 1, 1, 1, 2, 1, 3, 1, 3, 2, 5, 1, 6, 3, 2, 2, 8, 3, 9, 2, 3, 5, 11, 1, 10, 6, 9, 3, 14, 2, 15, 4, 5, 8, 6, 3, 18, 9, 6, 2, 20, 3, 21, 5, 6, 11, 23, 2, 21, 10, 8, 6, 26, 9, 10, 3, 9, 14, 29, 2, 30, 15, 9, 8, 12, 5, 33, 8, 11, 6, 35, 3, 36, 18, 10, 9, 15, 6, 39, 4, 27, 20, 41, 3, 16, 21

Offset: 1

Eric W. Weisstein

a(n) is the number of different diagonal elements in Cayley table for multiplicative group modulo n. But the fact that the same number of different elements are on the diagonal of the Cayley table does not mean in every case that these groups are isomorphic. - Artur Jasinski, Jul 03 2010

The number of quadratic residues modulo n that are coprime to n. These residues are listed in A096103. - Peter Munn, Mar 10 2021

Daniel Shanks, Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 95, 1993.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Steven R. Finch and Pascal Sebah, Square and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.
Eric Weisstein's World of Mathematics, Modulo Multiplication Group.
Eric Weisstein's World of Mathematics, Quadratic Residue.

Cf. A046072, A007735, A060594, A000010, A087692, A000224.
Row lengths of A096103.
Positions of ones: A018253.

F:= n -> nops({seq}(`if`(igcd(t,n)=1,t^2 mod n,NULL), t=1..floor(n/2))):
1, seq(F(n), n=2..100); # Robert Israel, Jan 04 2015
# 2nd program
A046073 := proc(n)
    local a,p,e,pf;
    a := 1;
    for pf in ifactors(n)[2] do
        p := op(1,pf) ;
        e := op(2,pf) ;
        if p = 2 then
            a := a*p^max(e-3,0) ;
        else
            a := a*(p-1)/2*p^(e-1) ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Oct 03 2016

Table[EulerPhi[n]/Sum[Boole[Mod[k^2, n] == 1] + Boole[n == 1], {k, n}], {n, 86}] (* or *)
Table[Apply[Times, FactorInteger[n] /. {p_, e_} /; p > 0 :> Which[p == 1, 1, p == 2, 2^Max[e - 3, 0], True, (p - 1) p^(e - 1)/2]], {n, 86}] (* Michael De Vlieger, Jul 18 2017 *)

A060594(n) = if(n<=2, 1, 2^#znstar(n)[3]); \\ This function from Joerg Arndt, Jan 06 2015
A046073(n) = eulerphi(n)/A060594(n); \\ Antti Karttunen, Jul 17 2017, after Sharon Sela's Mar 09 2002 formula.

A046073(n)=if(n>4,(n=znstar(n))[1]>>#n[3],1) \\ Avoids duplicate computation of phi(n). - M. F. Hasler, Nov 27 2017, typo fixed Mar 11 2021

from sympy import factorint, prod
def a(n): return 1 if n==1 else prod([2**max(e - 3, 0) if p==2 else (p - 1)*p**(e - 1)//2 for p, e in factorint(n).items()])
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 17 2017

(define (A046073 n) (cond ((= 1 n) n) ((even? n) (* (A000079 (max (- (A007814 n) 3) 0)) (A046073 (A028234 n)))) (else (* (/ 1 2) (- (A020639 n) 1) (/ (A028233 n) (A020639 n)) (A046073 (A028234 n)))))) ;; Antti Karttunen, Jul 17 2017, after the given multiplicative formula.

a(n) * A060594(n) = A000010(n) = phi(n) (This gives a formula for a(n) using the one in A060594(n) ). - Sharon Sela (sharonsela(AT)hotmail.com), Mar 09 2002
Multiplicative with a(2^e) = 2^max(e-3,0), a(p^e) = (p-1)*p^(e-1)/2 for p an odd prime.
Sum_{k=1..n} a(k) ~ c * n^2/sqrt(log(n)), where c = (43/(80*sqrt(Pi))) * Product_{p prime} (1+1/(2*p))*sqrt(1-1/p) = 0.24627260085060864229... (Finch and Sebah, 2006). - Amiram Eldar, Oct 18 2022

Edited and verified by Franklin T. Adams-Watters, Nov 07 2006

A054705 Number of powers of 4 modulo n.

Original entry on oeis.org

1, 2, 1, 2, 2, 2, 3, 3, 3, 3, 5, 2, 6, 4, 2, 3, 4, 4, 9, 3, 3, 6, 11, 3, 10, 7, 9, 4, 14, 3, 5, 4, 5, 5, 6, 4, 18, 10, 6, 4, 10, 4, 7, 6, 6, 12, 23, 3, 21, 11, 4, 7, 26, 10, 10, 5, 9, 15, 29, 3, 30, 6, 3, 4, 6, 6, 33, 5, 11, 7, 35, 5, 9, 19, 10, 10, 15, 7, 39, 4, 27, 11, 41, 4, 4, 8, 14, 7, 11

Offset: 1

Henry Bottomley, Apr 20 2000

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from David W. Wilson)

Cf. A007735, A244415.

Cf. A054703 (base 2), A054704 (3), A054706 (5), A054707 (6), A054708 (7), A054709 (8), A054717 (9), A054710 (10), A351524 (11), A054712 (12), A054713 (13), A054714 (14), A054715 (15), A054716 (16).

a[n_] := IntegerExponent[2*n, 4] + MultiplicativeOrder[4, n/2^IntegerExponent[n, 2]]; Array[a, 100] (* Amiram Eldar, Aug 25 2024 *)

a(n) = A007735(n) + A244415(n). - Amiram Eldar, Aug 25 2024

A007737 Period of repeating digits of 1/n in base 6.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 10, 1, 12, 2, 1, 1, 16, 1, 9, 1, 2, 10, 11, 1, 5, 12, 1, 2, 14, 1, 6, 1, 10, 16, 2, 1, 4, 9, 12, 1, 40, 2, 3, 10, 1, 11, 23, 1, 14, 5, 16, 12, 26, 1, 10, 2, 9, 14, 58, 1, 60, 6, 2, 1, 12, 10, 33, 16, 11, 2, 35, 1, 36, 4, 5, 9, 10, 12, 78, 1, 1, 40, 82, 2, 16, 3, 14, 10

Offset: 1

N. J. A. Sloane, Hal Sampson (hals(AT)easynet.com)

Not multiplicative. Smallest counterexample: a(77)=10, but a(7) = 2 and a(11) = 10. - Mitch Harris, May 16 2005.

Cf. A007733 (base 2), A007734 (3), A007735 (4), A007736 (5), A007738 (7), A007739 (8), A007740 (9), A007732 (10).

DigitCycleLength[r_Rational, b_Integer?Positive] := MultiplicativeOrder[b, FixedPoint[ Quotient[#, GCD[#, b]] &, Denominator[r]]]; DigitCycleLength[1, b_Integer?Positive] = 1; Array[ DigitCycleLength[1/#, 6] &, 80] (* Robert G. Wilson v, Jun 10 2011 *)
a[n_] := MultiplicativeOrder[6, n/Times @@ ({2, 3}^IntegerExponent[n, {2, 3}])]; Array[a, 100] (* Amiram Eldar, Aug 26 2024 *)

a(n)=znorder(Mod(6, n/2^valuation(n, 2)/3^valuation(n, 3))); \\ Joerg Arndt, Dec 14 2014

More terms from David W. Wilson

A066799 Square array read by antidiagonals of eventual period of powers of k mod n; period of repeating digits of 1/n in base k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 1, 1, 1, 2, 1, 4, 2, 1, 1, 1, 1, 1, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 6, 1, 1, 1, 1, 2, 2, 1, 2, 3, 2, 6, 1, 1, 1, 1, 1, 4, 1, 6, 1, 1, 4, 1, 1, 1, 1, 1, 4, 1, 2, 2, 3, 4, 10, 1, 1, 1, 2, 1, 2, 2, 1, 1, 6, 2, 5, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 5, 2, 12

Offset: 1

Henry Bottomley, Dec 20 2001

The determinant of the n X n matrix made from the northwest corner of this array is 0^(n-1). - Iain Fox, Mar 12 2018

			Rows start: 1,1,1,1,1,...; 1,1,1,1,1,...; 1,2,1,1,2,...; 1,1,2,1,1; 1,4,4,2,1,... T(3,2)=2 since the powers of 2 become 1,2,1,2,1,2,... mod 3 with period 2. T(4,2)=1 since the powers of 2 become 1,2,0,0,0,0,... mod 4 with eventual period 1.
Beginning of array:
+-----+--------------------------------------------------------------------
| n\k |  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  ...
+-----+--------------------------------------------------------------------
|  1  |  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, ...
|  2  |  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, ...
|  3  |  1,  2,  1,  1,  2,  1,  1,  2,  1,  1,  2,  1,  1,  2,  1,  1, ...
|  4  |  1,  1,  2,  1,  1,  1,  2,  1,  1,  1,  2,  1,  1,  1,  2,  1, ...
|  5  |  1,  4,  4,  2,  1,  1,  4,  4,  2,  1,  1,  4,  4,  2,  1,  1, ...
|  6  |  1,  2,  1,  1,  2,  1,  1,  2,  1,  1,  2,  1,  1,  2,  1,  1, ...
|  7  |  1,  3,  6,  3,  6,  2,  1,  1,  3,  6,  3,  6,  2,  1,  1,  3, ...
|  8  |  1,  1,  2,  1,  2,  1,  2,  1,  1,  1,  2,  1,  2,  1,  2,  1, ...
| ... |

Iain Fox, Antidiagonals n = 1..141 of array, flattened

Columns are A000012, A007733, A007734, A007735, A007736, A007737, A007738, A007739, A007740, A007732. A002322 is the highest value in each row and the least common multiple of each row, while the number of distinct values in each row is A066800.

t[n_, k_] := For[p = PowerMod[k, n, n]; m = n + 1, True, m++, If[PowerMod[k, m, n] == p, Return[m - n]]]; Flatten[Table[t[n - k + 1, k], {n, 1, 14}, {k, n, 1, -1}]] (* Jean-François Alcover, Jun 04 2012 *)

a(n, k) = my(p=k^n%n); for(m=n+1, +oo, if(k^m%n==p, return(m-n))) \\ Iain Fox, Mar 12 2018

T(n, k) = T(n, k-n) if k > n.
T(n, n) = T(n, n+1) = 1.
T(n, n-1) = 2.

A007740 Period of repeating digits of 1/n in base 9.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 1, 1, 2, 5, 1, 3, 3, 2, 2, 8, 1, 9, 2, 3, 5, 11, 1, 10, 3, 1, 3, 14, 2, 15, 4, 5, 8, 6, 1, 9, 9, 3, 2, 4, 3, 21, 5, 2, 11, 23, 2, 21, 10, 8, 3, 26, 1, 10, 3, 9, 14, 29, 2, 5, 15, 3, 8, 6, 5, 11, 8, 11, 6, 35, 1, 6, 9, 10, 9, 15, 3, 39, 2, 1, 4, 41, 3, 8, 21, 14, 5, 44, 2, 3, 11, 15, 23

Offset: 1

N. J. A. Sloane, Hal Sampson (hals(AT)easynet.com)

Not multiplicative. Smallest counterexample a(5) = a(16) = 2, but a(80) = 2. - David W. Wilson, Jun 09 2005

Cf. A007733 (base 2), A007734 (3), A007735 (4), A007736 (5), A007737 (6), A007738 (7), A007739 (8), A007732 (10).

DigitCycleLength[r_Rational, b_Integer?Positive] := MultiplicativeOrder[b, FixedPoint[ Quotient[#, GCD[#, b]] &, Denominator[r]]]; DigitCycleLength[1, b_Integer?Positive] = 1; Array[ DigitCycleLength[1/#, 9] &, 80] (* Robert G. Wilson v, Jun 10 2011 *)
a[n_] := MultiplicativeOrder[9, n/3^IntegerExponent[n, 3]]; Array[a, 100] (* Amiram Eldar, Aug 26 2024 *)

A007739 Period of repeating digits of 1/n in base 8.

Original entry on oeis.org

1, 1, 2, 1, 4, 2, 1, 1, 2, 4, 10, 2, 4, 1, 4, 1, 8, 2, 6, 4, 2, 10, 11, 2, 20, 4, 6, 1, 28, 4, 5, 1, 10, 8, 4, 2, 12, 6, 4, 4, 20, 2, 14, 10, 4, 11, 23, 2, 7, 20, 8, 4, 52, 6, 20, 1, 6, 28, 58, 4, 20, 5, 2, 1, 4, 10, 22, 8, 22, 4, 35, 2, 3, 12, 20, 6, 10, 4, 13, 4, 18, 20, 82, 2, 8, 14, 28, 10, 11, 4, 4

Offset: 1

N. J. A. Sloane, Hal Sampson (hals(AT)easynet.com)

Cf. A007733 (base 2), A007734 (3), A007735 (4), A007736 (5), A007737 (6), A007738 (7), A007740 (9), A007732 (10).

DigitCycleLength[r_Rational, b_Integer?Positive] := MultiplicativeOrder[b, FixedPoint[ Quotient[#, GCD[#, b]] &, Denominator[r]]]; DigitCycleLength[1, b_Integer?Positive] = 1; Array[ DigitCycleLength[1/#, 8] &, 80] (* Robert G. Wilson v, Jun 10 2011 *)
a[n_] := MultiplicativeOrder[8, n/2^IntegerExponent[n, 2]]; Array[a, 100] (* Amiram Eldar, Aug 26 2024 *)

More terms from David W. Wilson

cp's OEIS Frontend

A046073 Number of squares in multiplicative group modulo n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Scheme

Formula

Extensions

A054705 Number of powers of 4 modulo n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A007737 Period of repeating digits of 1/n in base 6.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A066799 Square array read by antidiagonals of eventual period of powers of k mod n; period of repeating digits of 1/n in base k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A007740 Period of repeating digits of 1/n in base 9.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A007739 Period of repeating digits of 1/n in base 8.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions