A000224 -id:A000224 - cp's OEIS frontend

A122905 Numbers m such that in Z/mZ the number of squares is strictly greater than the number of invertible elements.

2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 74, 78, 82, 86, 94, 98, 102, 106, 114, 118, 122, 134, 138, 142, 146, 150, 158, 162, 166, 174, 178, 186, 194, 202, 206, 214, 218, 222, 226, 242, 246, 250, 254, 258, 262, 274, 278, 282, 294, 298, 302

Offset: 1

Max Alekseyev, Sep 18 2006

nonn

Numbers m such that A000224(m) > A000010(m).

Ivan Neretin, Table of n, a(n) for n = 1..10000

Complement of A122906 in positive integers.

Cf. A000010, A000224, A122903, A122904, A122907.

Select[Range@310, Length@Union@Mod[Range[#]^2, #] > EulerPhi[#] &] (* Ivan Neretin, Dec 14 2016 *)
f1[p_, e_] := Floor[p^(e+1)/(2p + 2)] + 1; f1[2, e_] := Floor[2^e/6] + 2; f[p_, e_] := f1[p, e]/((p-1) * p^(e-1)); q[1] = False; q[k_] := Times @@ f @@@ FactorInteger[k] > 1; Select[Range[300], q] (* Amiram Eldar, Nov 11 2024 *)

A122907 Numbers m such that in Z/mZ the number of squares is greater than or equal to the number of invertible elements.

Original entry on oeis.org

1, 2, 3, 4, 6, 10, 12, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98, 102, 106, 114, 118, 122, 134, 138, 142, 146, 150, 158, 162, 166, 174, 178, 186, 194, 202, 206, 210, 214, 218, 222, 226, 242, 246, 250, 254, 258, 262, 274

Offset: 1

Max Alekseyev, Sep 18 2006

nonn

Numbers m such that A000224(m) >= A000010(m).

Ivan Neretin, Table of n, a(n) for n = 1..10000

Union of A122903 and A122905.
Complement of A122904 in positive integers.
Cf. A000010, A000224, A122906.

Select[Range@275, Length@Union@Mod[Range[#]^2, #] >= EulerPhi[#] &] (* Ivan Neretin, Dec 14 2016 *)
f1[p_, e_] := Floor[p^(e+1)/(2p + 2)] + 1; f1[2, e_] := Floor[2^e/6] + 2; f[p_, e_] := f1[p, e]/((p-1) * p^(e-1)); q[1] = True; q[k_] := Times @@ f @@@ FactorInteger[k] >= 1; Select[Range[300], q] (* Amiram Eldar, Nov 11 2024 *)

A304032 Number of ways to write 2*n as p + 2^k + 3^m with p prime and 2^k + 3^m a product of at most two distinct primes, where k and m are nonnegative integers.

Original entry on oeis.org

0, 1, 1, 3, 4, 4, 4, 6, 6, 5, 8, 9, 4, 6, 7, 4, 9, 10, 6, 9, 10, 6, 11, 14, 7, 9, 11, 5, 10, 9, 6, 12, 10, 3, 11, 15, 7, 12, 16, 7, 9, 14, 9, 12, 14, 8, 12, 16, 5, 12, 18, 10, 12, 16, 9, 12, 19, 10, 13, 17, 6, 10, 15, 6, 10, 16, 10, 12, 15, 10, 17, 20, 8, 14, 15, 8, 11, 18, 9, 12

Offset: 1

Zhi-Wei Sun, May 04 2018

nonn

The even number 58958 cannot be written as p + 2^k + 3^m with p and 2^k + 3^m both prime.
Clearly, a(n) <= A303702(n). We note that a(n) > 0 for all n = 2..5*10^8.
See also A304034 for a related conjecture.

			a(3) = 1 since 2*3 = 3 + 2^1 + 3^0 with 3 = 2^1 + 3^0 prime.

J. R. Chen, On the representation of a larger even integer as the sum of a prime and the product of at most two primes, Sci. Sinica 16(1973), 157-176.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Zhi-Wei Sun, Mixed sums of primes and other terms, in: Additive Number Theory (edited by D. Chudnovsky and G. Chudnovsky), pp. 341-353, Springer, New York, 2010.
Zhi-Wei Sun, Conjectures on representations involving primes, in: M. Nathanson (ed.), Combinatorial and Additive Number Theory II, Springer Proc. in Math. & Stat., Vol. 220, Springer, Cham, 2017, pp. 279-310. (See also arXiv:1211.1588 [math.NT], 2012-2017.)

Cf. A000040, A000079, A000224, A005117, A118955, A155216, A156695, A273812, A302982, A302984, A303233, A303234, A303338, A303363, A303389, A303393, A303399, A303428, A303401, A303432, A303434, A303539, A303540, A303541, A303543, A303601, A303637, A303639, A303656, A303660, A303702, A303821, A303932, A303934, A303949, A304031, A304034, A304081.

qq[n_]:=qq[n]=SquareFreeQ[n]&&Length[FactorInteger[n]]<=2;
tab={};Do[r=0;Do[If[qq[2^k+3^m]&&PrimeQ[2n-2^k-3^m],r=r+1],{k,0,Log[2,2n-1]},{m,0,Log[3,2n-2^k]}];tab=Append[tab,r],{n,1,80}];Print[tab]

A039302 Number of distinct quadratic residues mod 5^n.

Original entry on oeis.org

1, 3, 11, 53, 261, 1303, 6511, 32553, 162761, 813803, 4069011, 20345053, 101725261, 508626303, 2543131511, 12715657553, 63578287761, 317891438803, 1589457194011, 7947285970053, 39736429850261, 198682149251303, 993410746256511, 4967053731282553

Offset: 0

David W. Wilson

Number of distinct n-digit suffixes of base 5 squares.

J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 324.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,1,-5).

I:=[1, 3, 11]; [n le 3 select I[n] else 5*Self(n-1)+Self(n-2)-5*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Apr 21 2012

A039302 := proc(n)
    floor((5^n+3)*5/12) ;
end proc:
seq(A039302(n),n=0..10) ; # R. J. Mathar, Sep 28 2017

CoefficientList[Series[(1-2*x-5*x^2)/((1-x)*(1+x)*(1-5*x)),{x,0,30}],x] (* or *)LinearRecurrence[{5,1,-5},{1,3,11},30] (* Vincenzo Librandi, Apr 21 2012 *)

a(n) = floor((5^n+3)*5/12).
G.f.: (1-2*x-5*x^2)/((1-x)*(1+x)*(1-5*x)). - Colin Barker, Mar 14 2012
a(n) = 5*a(n-1) +a(n-2) -5*a(n-3). - Vincenzo Librandi, Apr 21 2012
a(n) = A000224(5^n). - R. J. Mathar, Sep 28 2017

A039304 Number of distinct quadratic residues mod 7^n.

Original entry on oeis.org

1, 4, 22, 151, 1051, 7354, 51472, 360301, 2522101, 17654704, 123582922, 865080451, 6055563151, 42388942054, 296722594372, 2077058160601, 14539407124201, 101775849869404, 712430949085822, 4987016643600751, 34909116505205251

Offset: 0

David W. Wilson

Number of distinct n-digit suffixes of base 7 squares.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Index entries for linear recurrences with constant coefficients, signature (7,1,-7).

Cf. A000224, A000420 (7^n).

[Floor((7^n+3)*7/16): n in [0..25]]; // Vincenzo Librandi, May 14 2011

I:=[1, 4, 22]; [n le 3 select I[n] else 7*Self(n-1)+Self(n-2)-7*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Apr 21 2012

A039304 := proc(n)
    floor((7^n+3)*7/16) ;
end proc:
seq(A039304(n),n=0..10) ; # R. J. Mathar, Sep 28 2017

CoefficientList[Series[(1-3*x-7*x^2)/((1-x)*(1+x)*(1-7*x)),{x,0,40}],x] (* Vincenzo Librandi, Apr 21 2012 *)
LinearRecurrence[{7,1,-7},{1,4,22},30] (* Harvey P. Dale, Aug 03 2016 *)

a(n) = floor( (7^n + 3)*7/16 ).
G.f.: (1 - 3*x - 7*x^2)/((1-x)*(1+x)*(1-7*x)). - Colin Barker, Mar 08 2012
a(n) = 7*a(n-1) + a(n-2) - 7*a(n-3). - Vincenzo Librandi, Apr 21 2012
a(n) = A000224(7^n). - R. J. Mathar, Sep 28 2017

A122903 Numbers m such that in Z/mZ the number of squares is equal to the number of invertible elements.

Original entry on oeis.org

1, 3, 4, 12, 70, 90, 210

Offset: 1

Max Alekseyev, Sep 18 2006

Numbers m such that A000224(m) = A000010(m).

Cf. A000010, A000224, A122904, A122905, A122906, A122907.

f1[p_, e_] := Floor[p^(e+1)/(2p + 2)] + 1; f1[2, e_] := Floor[2^e/6] + 2; f[p_, e_] := f1[p, e]/((p-1) * p^(e-1)); q[1] = True; q[k_] := Times @@ f @@@ FactorInteger[k] == 1; Select[Range[210], q] (* Amiram Eldar, Nov 11 2024 *)

A197929 Number of distinct residues of x^(n-1) (mod n), x=0..n-1.

Original entry on oeis.org

1, 2, 2, 3, 2, 6, 2, 5, 4, 10, 2, 9, 2, 14, 6, 9, 2, 14, 2, 15, 8, 22, 2, 15, 6, 26, 10, 9, 2, 30, 2, 17, 12, 34, 12, 21, 2, 38, 14, 25, 2, 42, 2, 33, 8, 46, 2, 27, 8, 42, 18, 15, 2, 38, 18, 35, 20, 58, 2, 45, 2, 62, 16, 33, 8, 18, 2, 51, 24, 30, 2, 35, 2, 74

Offset: 1

Michel Lagneau, Oct 19 2011

nonn

a(n) = 2 if n prime because the residues are 0 and 1 (Fermat's little theorem).

a(n) = n if n = 2p, p prime > 2. But there exists nonprime numbers q such that a(2q) = 2q, for example q = 1, 15, 21, 39,...

			a(8) = 5 because x^7 == 0, 1, 3, 5, 7  (mod 8) => 5 distinct residues.

Cf. A000224, A195637.

Length[Union[#]]& /@ Table[Mod[k^(n-1), n], {n, 74}, {k, n}]

A037046 Numbers that are not the number of quadratic residues mod n for any n.

Original entry on oeis.org

5, 13, 17, 25, 26, 29, 35, 39, 41, 43, 47, 50, 58, 59, 61, 65, 67, 71, 73, 78, 83, 85, 86, 89, 94, 95, 101, 103, 107, 109, 113, 116, 118, 119, 122, 123, 125, 127, 130, 131, 134, 143, 145, 146, 149, 155, 163, 167, 170, 173, 178, 179, 181, 183, 185, 188, 191, 193

Offset: 1

David W. Wilson

nonn

Complement of A037041. - Michel Marcus, Nov 11 2015

Cf. A000224, A096008, A111986 (number of numbers having n quadratic residues), A111987 (least number having n quadratic residues), A111988 (greatest number having n quadratic residues).

s = Length[Union@ #] & /@ Table[Mod[k^2, n], {n, 10000}, {k, 0, n - 1}]; Complement[Range@ Max@ #, #] &@ Take[Union@ s, 136] (* Michael De Vlieger, Nov 10 2015 *)

A068197 Number of squares (of another matrix) in M_2(n) - the ring of 2 X 2 matrices over Z_n.

Original entry on oeis.org

1, 10, 29, 48, 223, 290, 865, 344, 1587, 2230, 5341, 1392, 10459, 8650, 6467, 3182, 30745, 15870, 48061, 10704, 25085, 53410, 103489, 9976, 108035, 104590, 118179, 41520, 262291, 64670, 342721, 41736, 154889, 307450, 192895, 76176, 696655, 480610, 303311, 76712, 1051261, 250850, 1272349, 256368, 353901

Offset: 1

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

a(n) is multiplicative. This is the 2-dimensional analog of A000224.

Giovanni Resta, Table of n, a(n) for n = 1..210

Cf. A000224, A068516, A182039, A209411.

a(n)={my(M=Map()); for(a=0, n-1, for(b=0, n-1, for(c=0, n-1, for(d=0, n-1, mapput(M, lift(Mod([a, b; c, d], n)^2), 1))))); #M} \\ Andrew Howroyd, Aug 06 2018

def A68197(n):
    S = set()
    L = list(range(n))
    for a, b, c, d in cartesian_product([L, L, L, L]):
        M = Matrix([[a, b], [c, d]])
        N = tuple(x % n for x in (M * M).list())
        if N not in S:
           S.add(N)
    print(n, len(S)) # Manfred Scheucher, Jun 12 2015

More terms from Manfred Scheucher, Jun 12 2015
a(45) corrected by Giovanni Resta, Jun 12 2015
a(1) added by Andrew Howroyd, Aug 06 2018

A132213 Number of distinct primes among the squares mod n.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 2, 0, 1, 3, 0, 0, 2, 2, 4, 1, 1, 3, 3, 0, 2, 4, 3, 0, 4, 1, 4, 1, 2, 4, 2, 1, 3, 6, 2, 0, 5, 2, 6, 2, 2, 7, 5, 0, 6, 5, 3, 3, 8, 6, 3, 0, 3, 6, 8, 0, 6, 8, 3, 2, 2, 3, 7, 3, 3, 2, 7, 0, 9, 10, 3, 4, 6, 4, 9, 1, 10, 10, 11, 1, 2, 13, 3, 0, 10, 4, 5, 4, 4, 13, 4, 1, 11, 10, 4, 4

Offset: 1

T. D. Noe, Aug 13 2007, Aug 17 2007

It appears that a(n)=0 for only the 30 numbers in A065428, which appears to be related to idoneal numbers, A000926. The graph shows a(n) can be quite small even for large n. For example, a(9240)=7. Observe that the graph up to n=10000 appears to have 5 components. Why?
The logarithmic plot of the first 10^6 terms shows seven components.
From Rémy Sigrist, Nov 28 2017: (Start)
Empirically, in the logarithmic plot of the sequence:
- the set of indices of the first component (starting from the top), say S_1, is the union of A061345 and of A278568,
- the set of indices of the n-th component (for n > 1), say S_n, contains the numbers k not in a previous component and such that (omega(k) = n-1) or (omega(k) = n and val(k) = 0 or 2) or (omega(k) = n+1 and val(k) = 1) (where omega(k) = A001221(k) and val(k) = A007814(k)),
- see logarithmic scatterplot colored according to this scheme in Links section.
(End)

			For n=14, the squares (mod n) repeat 0,1,4,9,2,11,8,7,8,11,2,9,4,1,0,..., a sequence containing three distinct primes: 2, 7 and 11. Hence a(14)=3.

T. D. Noe, Table of n, a(n) for n = 1..10000
T. D. Noe, Logarithmic plot of 10^6 terms
Rémy Sigrist, Colored logarithmic plot of 2*10^6 terms

Cf. A000224 (number of squares mod n).

Cf. A000290, A001221, A007814, A010051, A061345, A278568.

import Data.List (nub, genericTake)
a132213 n = sum $ map a010051' $
            nub $ genericTake n $ map (`mod` n) $ tail a000290_list
-- Reinhard Zumkeller, Jun 23 2015, Oct 15 2011

Table[s=Union[Mod[Range[n]^2,n]]; Length[Select[s,PrimeQ]], {n,10000}]
Table[Count[Union[PowerMod[Range[n],2,n]],?PrimeQ],{n,100}] (* _Harvey P. Dale, Mar 02 2018 *)

cp's OEIS Frontend

A122905 Numbers m such that in Z/mZ the number of squares is strictly greater than the number of invertible elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A122907 Numbers m such that in Z/mZ the number of squares is greater than or equal to the number of invertible elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A304032 Number of ways to write 2*n as p + 2^k + 3^m with p prime and 2^k + 3^m a product of at most two distinct primes, where k and m are nonnegative integers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A039302 Number of distinct quadratic residues mod 5^n.

Views

Author

Keywords

Comments

References

Links

Programs

Magma

Maple

Mathematica

Formula

A039304 Number of distinct quadratic residues mod 7^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

Formula

A122903 Numbers m such that in Z/mZ the number of squares is equal to the number of invertible elements.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A197929 Number of distinct residues of x^(n-1) (mod n), x=0..n-1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A037046 Numbers that are not the number of quadratic residues mod n for any n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica