A046073 -id:A046073 - cp's OEIS frontend

A002616 Reduced totient function (divided by 2).

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, 3, 8, 6, 5, 33, 8, 11, 6, 35, 3, 36, 18, 10, 9, 15, 6, 39, 2, 27, 20, 41, 3, 8, 21, 14, 5, 44, 6, 6

Offset: 3

N. J. A. Sloane

A046073 is a similar sequence (the first difference occurs at position 61). - Artur Jasinski, Apr 05 2008

D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, pp. 7-10.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Reinhard Zumkeller, Table of n, a(n) for n = 3..1000
A. Cauchy, Mémoire sur la résolution des équations indéterminées du premier degré en nombres entiers, Oeuvres Complètes. Gauthier-Villars, Paris, 1882-1938, Series (2), Vol. 12, pp. 9-47.

Cf. A002322.

a002616 = flip div 2 . a002322  -- Reinhard Zumkeller, Sep 02 2014

Table[CarmichaelLambda[k + 2]/2, {k, 130}] (* Artur Jasinski, Apr 05 2008 *)

a(n) = lcm(znstar(n)[2])/2; \\ Michel Marcus, May 22 2022

a(n) = A002322(n)/2.

More terms from Vladeta Jovovic, Apr 04 2002

A303704 Numbers k such that all coprime quadratic residues modulo k are squares.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 21, 24, 28, 40, 48, 56, 60, 72, 88, 120, 168, 240, 840

Offset: 1

Jianing Song, Apr 29 2018

Numbers k such that A046073(k) = A057828(k).
There are exactly 25 members in this sequence and this is the full list. Note that for other k, A046073(k) > A057828(k).
From Jianing Song, Feb 14 2019: (Start)
For the proof that this sequence is finite, we will show that there are no terms > 130729.
Let A(n) = A046073(n) be the number of coprime quadratic residues modulo n. By definition, if k is a term then A(k) <= sqrt(k), that is, A(k)/sqrt(k) <= 1. Let f(n) = A(n)/sqrt(n), then f(n) is multiplicative with f(2) = sqrt(2)/2, f(4) = 1/2, f(2^e) = 2^(e/2 - 3) for e >= 3, f(p^e) = ((p - 1)/2)*p^(e/2 - 1) when p > 2. Note that f(2^e) >= a(2^3), f(p^e) >= f(p), f(p) > 1 when p >= 7. For every number n, we have:
a) if n is divisible by a prime >= 127, then f(n) >= f(2^3)*f(3)*f(5)*f(127) = sqrt(1323/1270) > 1.
b) if n is divisible by two distinct primes >= 23, then f(n) >= f(2^3)*f(3)*f(5)*f(23)*f(29) = sqrt(11858/10005) > 1.
So if k > 130729 is a term, then all prime factors of k are no greater than 113, and k contains at most one prime factor >= 23. On the other hand, if all prime factors of k are no greater than 19, then 53881 is a coprime quadratic residue modulo k because 53881 is a coprime quadratic residue modulo 2^3, 3, 5, 7, 11, 13, 17 and 19, but 53881 is not a perfect square, a contradiction. As a result, k must contain exactly one prime factor p in [23, 113].
Now if a number m is a coprime quadratic residue modulo 2^3, 3, 5, 7, 11, 13, 17, 19 and p, then m is a coprime quadratic residue modulo k. Consider the numbers 53881, 86641, 87481, 102001, 117049 and 130729. At least one of them is a coprime quadratic residue modulo each prime p in [23, 113], so at least one of them is a coprime quadratic residue modulo k, but none of them is a square, a contradiction! (End)

			All coprime quadratic residues modulo 21 are 1, 4, 16 and they are all squares, so 21 is a term.
All coprime quadratic residues modulo 840 are 1, 121, 169, 289, 361, 529 and they are all squares, so 840 is a term.
249 == 23^2 is a coprime quadratic residue modulo 280 but 249 is not a square number, so 280 is not a term.

Cf. A046073, A057828, A214583.

A254328 is a subsequence.

for(k=1, 130729, if(eulerphi(k)/2^#znstar(k)[2]<=sqrt(k), for(j=1, k, if(gcd(j,k)==1&&!issquare(j^2%k), break()); if(j==k, print1(k, ", "))))) \\ Jianing Song, Feb 15 2019

A081754 Numbers n such that the number of noncongruent solutions to x^(2^m) == 1 (mod n) is the same for any m>=1.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 18, 19, 21, 22, 23, 24, 27, 28, 31, 33, 36, 38, 42, 43, 44, 46, 47, 49, 54, 56, 57, 59, 62, 63, 66, 67, 69, 71, 72, 76, 77, 79, 81, 83, 84, 86, 88, 92, 93, 94, 98, 99, 103, 107, 108, 114, 118, 121, 124, 126, 127, 129, 131, 132, 133, 134

Offset: 1

Benoit Cloitre, Apr 08 2003

nonn

Numbers n such that the multiplicative group of residues modulo n does not contain C4 as a subgroup. Equivalently, numbers not divisible by 16 or by any primes of the form 4k+1. - Ivan Neretin, Aug 02 2016
From Jianing Song, Oct 18 2021: (Start)
Numbers k such that psi(k) = A002322(k) is not divisible by 4.
Numbers k such that there are an odd number of coprime squares modulo k, i.e., numbers k such that A046073(k) is odd. (End)

Ivan Neretin, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Modulo Multiplication Group.

Cf. A060594, A002322, A046073.

filter:= n -> n mod 16 <> 0 and not member(1,numtheory:-factorset(n) mod 4):
select(filter, [$1..1000]); # Robert Israel, Aug 02 2016

Select[Range@135, ! Divisible[#, 16] && FreeQ[Mod[FactorInteger[3 #][[All, 1]], 4], 1] &] (* Ivan Neretin, Aug 02 2016 *)

isA081754(n) = if(n>2, znstar(n)[2][1]%4==2, 1) \\ Jianing Song, Oct 18 2021

A271547 Decimal expansion of Product_{p prime} (1+1/(2p))*sqrt(1-1/p), a constant related to the asymptotic average number of squares modulo n.

Original entry on oeis.org

8, 1, 2, 1, 0, 5, 7, 1, 1, 1, 6, 3, 1, 2, 2, 5, 1, 1, 7, 0, 6, 2, 5, 0, 9, 6, 4, 5, 8, 1, 8, 8, 7, 1, 7, 6, 5, 6, 0, 5, 7, 7, 1, 0, 0, 4, 8, 3, 6, 6, 9, 9, 2, 4, 3, 6, 0, 9, 2, 1, 8, 2, 0, 0, 3, 7, 8, 0, 9, 4, 0, 6, 2, 0, 4, 2, 5, 3, 2, 2, 0, 7, 5, 5, 8, 0, 2, 5, 4, 0, 2, 3, 5, 0, 4, 0, 2, 9, 9, 8

Offset: 0

Jean-François Alcover, Apr 10 2016

			0.81210571116312251170625096458188717656057710048366992436092182...

Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.

Cf. A046073, A105612.

digits = 100; Exp[NSum[-( (-1)^n + 2^(n - 1))*PrimeZetaP[n]/(n* 2^n), {n, 2, Infinity}, NSumTerms -> 3 digits, WorkingPrecision -> digits + 10]] // RealDigits[#, 10, digits]& // First

Equals exp(Sum_{n>=2} -((-1)^n + 2^(n-1))*P(n)/(n*2^n)), where P(n) is the prime zeta P function.

A348418 a(n) is the smallest k with rank((Z/kZ)*) = n such that there are an odd number of coprime squares modulo k.

Original entry on oeis.org

1, 3, 8, 24, 168, 1848, 35112, 807576, 25034856, 1076498808, 50595443976, 2985131194584, 200003790037128, 14200269092636088, 1121821258318250952, 93111164440414829016, 9590449937362727388648, 1026178143297811830585336, 130324624198822102484337672

Offset: 0

Jianing Song, Oct 18 2021

The rank of a finitely generated group rank(G) is defined to be the size of the minimal generating sets of G. In particular, rank((Z/kZ)*) = 0 if k <= 2 and A046072(k) otherwise.
The number of coprime squares modulo a(n) is given by A046073(a(n)) = A348420(n-2) for n >= 2.
a(n) is the least k such that the Sylow 2-subgroup of (Z/kZ)* is (C_2)^n. - Jianing Song, Aug 13 2023

			a(2) = 8;
a(3) = 8 * 3 = 24;
a(4) = 8 * 3 * 7 = 168;
a(5) = 8 * 3 * 7 * 11 = 1848;
a(6) = 8 * 3 * 7 * 11 * 19 = 35112.

Jianing Song, Table of n, a(n) for n = 0..200

Cf. A046072, A046073, A348420, A002145, A102476.

a(n) = if(n<=2, [1, 3, 8][n+1], my(t=8); forprime(p=2, , if(p%4==3, t*=p; if(n--<3, return(t))))) \\ following Charles R Greathouse IV's program for A078586

a(n) = 8 * A078586(n-2) = 8 * (Product_{k=1..n-2} A002145(k)) for n > 2.

A348420 a(n) = Product_{k=1..n} (p_k - 1)/2 where p_1, p_2, ..., p_n are the first n primes congruent to 3 modulo 4.

Original entry on oeis.org

1, 1, 3, 15, 135, 1485, 22275, 467775, 10758825, 312005925, 10296195525, 360366843375, 14054306891625, 576226582556625, 29387555710387875, 1557540452650557375, 98125048516985114625, 6378128153604032450625, 440090842598678239093125

Offset: 0

Jianing Song, Oct 18 2021

a(n) is the number of coprime squares modulo A348418(n+2), where A348418(n) is the smallest k with rank((Z/kZ)*) = n such that there are an odd number of coprime squares modulo k. (The rank of a finitely generated group rank(G) is defined to be the size of the minimal generating sets of G. In particular, rank((Z/kZ)*) = 0 if k <= 2 and A046072(k) otherwise.)

			A348418(2) = 8, and the number of coprime squares modulo 8 is a(0) = 1;
A348418(3) = 8 * 3 = 24, and the number of coprime squares modulo 24 is a(1) = (3-1)/2 = 1;
A348418(4) = 8 * 3 * 7 = 168, and the number of coprime squares modulo 168 is a(2) = ((3-1)/2) * ((7-1)/2) = 3;
A348418(5) = 8 * 3 * 7 * 11 = 1848, and the number of coprime squares modulo 1848 is a(3) = ((3-1)/2) * ((7-1)/2) * ((11-1)/2) = 15;
A348418(6) = 8 * 3 * 7 * 11 * 19 = 35112, and the number of coprime squares modulo 35112 is a(4) = ((3-1)/2) * ((7-1)/2) * ((11-1)/2) * ((19-1)/2) = 135.

Jianing Song, Table of n, a(n) for n = 0..200

Cf. A002145, A046073, A348418, A046072, A323739.

a(n) = my(t=1); forprime(p=2, , if(p%4==3, t*=(p-1)/2; if(n--<1, return(t)))) \\ following Charles R Greathouse IV's program for A078586

a(n) = Product_{k=1..n} (A002145(k) - 1)/2.

a(n) = A046073(A348418(n+2)).

A366935 Moduli k for which the number of quadratic residues mod k coprime to k is equal to phi(k)/2^(phi(k)/lambda(k)), where lambda is Carmichael's function.

Original entry on oeis.org

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

Offset: 1

Miles Englezou, Oct 29 2023

Numbers k such that A046073(k) = A000010(k)/2^A034380(k).

An empirical observation, calculated for 2 <= k <= 10^5. The number of quadratic residues mod k coprime to k is |Q_k| = phi(k)/2^r, r = A046072(k) <= phi(k)/lambda(k). Up to 10^5, the equality holds for 37758 moduli, and the inequality holds for 62241.

			k = 3 is a term: |Q_3| = phi(3)/2^1 = 1, so r = 1 = phi(3)/lambda(3).

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

Miles Englezou, MATLAB script

Cf. A000010, A002322, A046073, A034380, A033948, A046072.

isok(n) = my(z=znstar(n).cyc); #z == eulerphi(n)/lcm(z) \\ Andrew Howroyd, Oct 29 2023

{ k : |Q_k| = phi(k)/2^(phi(k)/lambda(k)) }, where lambda is Carmichael's function (A002322).

A068516 Number of squares (of another matrix) in the group GL(2,Z_n) described in sequence A000252.

Original entry on oeis.org

3, 16, 16, 162, 48, 696, 104, 1236, 486, 4680, 256, 9366, 2088, 2592, 1342, 28296, 3708, 44640, 2592, 11136, 14040, 97416, 1664, 100410, 28098, 99936, 11136, 250110, 7776, 327840, 20924, 74880, 84888, 112752, 19776, 671346, 133920, 149856, 16848

Offset: 2

Sharon Sela (sharonsela(AT)hotmail.com), Mar 19 2002

The sequence is multiplicative. This is the 2-dimensional analog of A046073.

Cf. A000252, A046073, A068197.

Terms a(21) and beyond from Andrey Zabolotskiy, Jul 02 2022

A096103 Table read by rows: row n contains the quadratic residues modulo n which are coprime to n.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 2, 4, 1, 1, 4, 7, 1, 9, 1, 3, 4, 5, 9, 1, 1, 3, 4, 9, 10, 12, 1, 9, 11, 1, 4, 1, 9, 1, 2, 4, 8, 9, 13, 15, 16, 1, 7, 13, 1, 4, 5, 6, 7, 9, 11, 16, 17, 1, 9, 1, 4, 16, 1, 3, 5, 9, 15, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18, 1, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24, 1, 3, 9, 17, 23, 25, 1, 4

Offset: 2

Cino Hilliard, Jul 21 2004

Each '1' begins a row.

Row lengths are A046073. - Geoffrey Critzer, Jan 02 2015

			1;
1;
1;
1,4;
1;
1, 2, 4;
1;
1, 4, 7;
1, 9;
1, 3, 4, 5, 9;
1;
1, 3, 4, 9, 10, 12;
1, 9, 11;
1, 4;

Eric Weisstein's World of Mathematics, Quadratic Residue

Cf. A046071, A046073.

Table[Union[Mod[Select[Range[n], CoprimeQ[#, n] &]^2, n]], {n, 2, 20}] // Grid (* Geoffrey Critzer, Jan 02 2015 *)

maybesqgcd1(n) = { for(x=2,n, b=floor(x/2); a=vector(b+1); for(y=1,b, z=y^2%x; if(z<>0, a[y]=z; ) ); s=vecsort(a); c=1; for(j=2,b+1, if(s[j]<>s[j-1], c++; if(gcd(x,s[j])==1,print1(s[j]",")) ) ); ) }

Edited by Don Reble, Apr 16 2007

A269472 Decimal expansion of Product_{p prime} (1-(p^2+2)/(2(p^2+1)(p+1))) / sqrt(1-1/p), a constant related to the asymptotic average number of squares modulo n.

Original entry on oeis.org

1, 2, 5, 6, 9, 1, 3, 6, 1, 0, 2, 1, 0, 1, 8, 8, 5, 9, 5, 9, 4, 9, 2, 1, 1, 5, 7, 6, 9, 4, 6, 8, 6, 0, 8, 9, 4, 9, 4, 0, 4, 5, 9, 8, 8, 6, 8, 0, 7, 5, 0, 8, 7, 6, 7, 7, 9, 8, 5, 7, 1, 8, 1, 9, 3, 4, 7, 5, 1, 8, 2, 3, 8, 4, 5, 7, 4, 5, 4, 1, 4, 8, 7, 5, 5, 3, 9, 7, 5, 4, 8, 9, 7, 8, 6, 4, 9, 1, 1, 5, 7, 6, 4, 5, 0, 9, 9, 6

Offset: 1

Jean-François Alcover, Apr 13 2016

			1.2569136102101885959492115769468608949404598868075...

Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.

Cf. A046073, A105612, A271547.

digits = 104; m0 = 100; Clear[s]; s[m_] := s[m] = Sum[(1 + 2*(-1)^n - 4*(-1)^n*ChebyshevT[n, 1/4] + 4*Switch[Mod[n, 4], 2, -1, 3, 0, 0, 1, 1, 0])/(2*n) PrimeZetaP[n], {n, 2, m}] // N[#, digits]& // Exp; s[m0]; s[m = 2 m0]; While[RealDigits[s[m], 10, digits] != RealDigits[s[m/2], 10, digits], m = 2 m; Print[m]]; RealDigits[s[m]][[1]]
(* Second program: *)
$MaxExtraPrecision = 1000; Clear[f]; f[p_] := (1 - (p^2 + 2)/(2 (p^2 + 1) (p + 1)))/ Sqrt[1 - 1/p]; Do[c = Rest[CoefficientList[Series[Log[f[1/x]], {x, 0, m}], x]]; Print[f[2] * Exp[N[Sum[Indexed[c, n]*(PrimeZetaP[n] - 1/2^n), {n, 2, m}], 112]]], {m, 100, 1000, 100}] (* Vaclav Kotesovec, Jun 19 2020 *)

sqrt(prodeulerrat((1-(p^2+2)/(2*(p^2+1)*(p+1)))^2/(1-1/p))) \\ Amiram Eldar, May 29 2021

Formula in name and last digit corrected by Vaclav Kotesovec, Jun 19 2020

cp's OEIS Frontend

A002616 Reduced totient function (divided by 2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A303704 Numbers k such that all coprime quadratic residues modulo k are squares.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A081754 Numbers n such that the number of noncongruent solutions to x^(2^m) == 1 (mod n) is the same for any m>=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A271547 Decimal expansion of Product_{p prime} (1+1/(2p))*sqrt(1-1/p), a constant related to the asymptotic average number of squares modulo n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A348418 a(n) is the smallest k with rank((Z/kZ)*) = n such that there are an odd number of coprime squares modulo k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A348420 a(n) = Product_{k=1..n} (p_k - 1)/2 where p_1, p_2, ..., p_n are the first n primes congruent to 3 modulo 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A366935 Moduli k for which the number of quadratic residues mod k coprime to k is equal to phi(k)/2^(phi(k)/lambda(k)), where lambda is Carmichael's function.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A068516 Number of squares (of another matrix) in the group GL(2,Z_n) described in sequence A000252.