A000224 -id:A000224 - cp's OEIS frontend

A218578 The number of times n occurs in A095972.

2, 1, 3, 1, 1, 3, 2, 0, 2, 2, 2, 1, 2, 1, 3, 1, 2, 0, 4, 0, 2, 2, 1, 2, 0, 2, 2, 1, 3, 1, 2, 1, 2, 3, 0, 1, 2, 2, 1, 1, 2, 1, 2, 0, 3, 1, 2, 1, 2, 0, 4, 1, 2, 3, 2, 0, 2, 1, 2, 0, 2, 1, 0, 2, 0, 3, 3, 0, 4, 1, 2, 0, 2, 1, 3, 2, 0, 0, 3, 1, 0, 3, 2, 3, 0, 1, 3

Offset: 0

Dmitri Kamenetsky, Nov 03 2012

nonn

Alternative definition: a(n) = number of k such that A000224(k) = k - n.

			a(0) is 2, because 0 occurs only twice in A095972. a(1) is 1, because 1 occurs only once in A095972.

T. D. Noe, Table of n, a(n) for n = 0..10000

Cf. A000224, A095972, A218620 (greedy inverse).

A218578 := proc(n)
    local f;
    f := 0 ;
    for q from 1 to 2*n+2 do
        if A095972(q) = n then
            f := f+1 ;
        end if;
    end do:
    f ;
end proc: # R. J. Mathar, Nov 05 2012

nn = 100; t = Table[Length[Complement[Range[n-1], Union[Mod[Range[n]^2, n]]]], {n, 2*nn + 2}]; Table[Count[t, n], {n, 0, nn}] (* T. D. Noe, Nov 06 2012 *)

from math import prod
from sympy import factorint
def A218578(n): return sum(1 for i in range(1,2*n+3) if n==i-prod((p**(e+1)//((p+1)*(q:=1+(p==2)))>>1)+q for p, e in factorint(i).items())) # Chai Wah Wu, Oct 07 2024

A232195 Product of distinct squares in Z_n (mod n), without the factor 0.

Original entry on oeis.org

0, 1, 1, 1, 4, 0, 1, 4, 1, 0, 1, 0, 12, 0, 0, 4, 16, 0, 1, 0, 0, 0, 1, 0, 24, 0, 9, 0, 28, 0, 1, 0, 0, 0, 0, 0, 36, 0, 0, 0, 40, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 52, 0, 0, 0, 0, 0, 1, 0, 60, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 72, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0

Offset: 1

Martin Schellenberg, Nov 20 2013

nonn

Up to n = 10000 a(n) is divisible by 4 except for the values 1 and 9 (a(27)).

Robert Israel, Table of n, a(n) for n = 1..10000

A071782 describes the sum of distinct squares in Z_n (mod n).
A000224 describes the number of distinct squares in Z_n (mod n).
Cf. A002144, A002145, A024619.

A232195:= proc (n) options operator, arrow; modp(convert(`minus`({seq(modp(k^2, n), k = 1 .. n-1)}, {0}), `*`), n) end proc; seq(A232195(i), i = 1 .. 30);

a(n) = if (n==1, 0, lift(vecprod(Set(select(x->(issquare(x) && (x!=0)), vector(n-1, k, Mod(k, n))))))); \\ Michel Marcus, Apr 01 2021

From Robert Israel, Apr 01 2021: (Start)
a(n) = 0 if n is in A024619, or if n = p^d with p > 3 prime and d >= 3, or if n = 2^d with d >= 5, or if n = 3^d with d >= 4.
a(p) = a(p^2) = 1 if p is in A002145.
a(p) = p-1 and a(p^2) = p^2-1 if p is in A002144.
(End)

A271586 Number of squares in Z_n[i].

Original entry on oeis.org

1, 2, 5, 4, 9, 10, 25, 8, 37, 18, 61, 20, 49, 50, 45, 24, 81, 74, 181, 36, 125, 122, 265, 40, 121, 98, 329, 100, 225, 90, 481, 88, 305, 162, 225, 148, 361, 362, 245, 72, 441, 250, 925, 244, 333, 530, 1105, 120, 1177, 242, 405, 196, 729, 658, 549, 200, 905, 450, 1741, 180, 961, 962, 925, 344, 441, 610, 2245

Offset: 1

José María Grau Ribas, Apr 10 2016

Equivalently, the number of distinct pairs (x^2-y^2, 2*x*y) mod n. - Andrew Howroyd, Aug 01 2018

			The squares in Z_3[i] are 0, i, 2i, 1 and 2, therefore a(3)=5.

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Cf. A000224.

GG[M_, s_] :=Table[Mod[(a +  b I)^s, M], {a, M}, {b, M}] // Flatten // Union // Length; Table[GG[M, 2], {M, 1, 144}]

a(n)={my(v=vector(n)); for(i=0, n-1, for(j=0, n-1, my(k=(i^2-j^2)%n + 1); v[k]=bitor(v[k], 1<<((2*i*j)%n)))); sum(j=1, n, hammingweight(v[j]))} \\ Andrew Howroyd, Aug 01 2018

Keyword:mult added by Andrew Howroyd, Aug 01 2018

A303997 Number of ways to write 2n as p + 3^k + binomial(2m,m), where p is a prime, and k and m are nonnegative integers.

Original entry on oeis.org

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

Offset: 1

Zhi-Wei Sun, May 04 2018

nonn

502743678 is the first value of n > 1 with a(n) = 0.

			a(2) = 1 since 2*2 = 2 + 3^0 + binomial(2*0,0) with 2 prime.
a(3) = 2 since 2*3 = 3 + 3^0 + binomial(2*1,1) = 2 + 3^1 + binomial(2*0,0) with 3 and 2 both prime.

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, A000224, A000984, A118955, 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, A303998.

c[n_]:=c[n]=Binomial[2n,n];
tab={};Do[r=0;k=0;Label[bb];If[c[k]>=2n,Goto[aa]];Do[If[PrimeQ[2n-c[k]-3^m],r=r+1],{m,0,Log[3,2n-c[k]]}];k=k+1;Goto[bb];Label[aa];tab=Append[tab,r],{n,1,90}];Print[tab]

A317623 Number of distinct values of X(3X-1) mod n.

Original entry on oeis.org

1, 1, 3, 2, 3, 3, 4, 4, 9, 3, 6, 6, 7, 4, 9, 8, 9, 9, 10, 6, 12, 6, 12, 12, 11, 7, 27, 8, 15, 9, 16, 16, 18, 9, 12, 18, 19, 10, 21, 12, 21, 12, 22, 12, 27, 12, 24, 24, 22, 11, 27, 14, 27, 27, 18, 16, 30, 15, 30, 18, 31, 16, 36, 32, 21, 18, 34, 18, 36, 12, 36

Offset: 1

Andrew Howroyd, Aug 01 2018

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

Cf. A000224, A290731, A290732.

f[2, e_] := 2^(e-1); f[3, e_] := 3^e; f[p_, e_] := 1 + Floor[p^(e+1)/(2*p+2)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 13 2020 *)

a(n)={my(v=vector(n)); for(i=0, n-1, v[i*(3*i-1)%n + 1]=1); vecsum(v)}

a(n)={my(f=factor(n)); prod(i=1, #f~, my([p,e]=f[i,]); if(p<=3, if(p==2, 2^(e-1), 3^e), 1 + p^(e+1)\(2*p+2)))}

Multiplicative with a(2^e) = 2^(e-1), a(3^e) = 3^e, a(p^e) = 1 + floor( p^(e+1)/(2*p+2) ) for prime p >= 5.

A212887 a(n) is the prime p corresponding to the smallest integer k such that k^2 == p (mod prime(n)).

Original entry on oeis.org

2, 5, 3, 2, 17, 2, 7, 5, 7, 23, 41, 2, 11, 5, 3, 59, 29, 71, 2, 17, 11, 3, 43, 41, 37, 7, 31, 17, 13, 7, 5, 47, 59, 47, 151, 2, 23, 17, 79, 5, 3, 59, 2, 113, 2, 29, 71, 23, 17, 83, 5, 67, 61, 131, 53, 47, 43, 41, 31, 17, 13, 11, 7, 67, 239, 53, 227, 47, 2, 107

Offset: 4

Michel Lagneau, May 29 2012

nonn

The corresponding values of k are {3, 4, 4, 6, 6, 5, 6, 6, 9, 8, 16, 7, 8, 8, 8, 27, …}

			a(8) = 17 because 17 == 6^2 mod 19 where 19 = prime(8) and 6 is the smallest k.
Remark : 11 == 7^2 mod 19, but 7 > 6.

Michel Lagneau, Table of n, a(n) for n = 4..10000

Cf. A000224, A095972.

for n from 2 to 100 do:p:=ithprime(n):i:=0:for k from 0 to p-1 while(i=0) do: q:=irem(k^2,p):if type(q,prime)=true then i:=1:printf(`%d, `,q):else fi:od:od:

A295784 Length of the longest arithmetic progression in squares mod n with slope coprime to n.

Original entry on oeis.org

2, 2, 3, 2, 3, 2, 2, 3, 3, 2, 4, 3, 2, 2, 5, 2, 4, 2, 2, 3, 5, 2, 3, 3, 2, 2, 4, 2, 4, 2, 2, 5, 3, 2, 4, 4, 2, 2, 5, 2, 5, 2, 2, 5, 5, 2, 3, 3, 2, 2, 6, 2, 3, 2, 2, 4, 5, 2, 5, 4, 2, 2, 3, 2, 6, 2, 2, 3, 7, 2, 9, 4, 2, 2, 3, 2, 6, 2, 2, 5, 7, 2, 3, 5, 2, 2, 5, 2, 3, 2, 2, 5, 3, 2, 9, 3, 2, 2, 7, 2, 7, 2, 2, 6, 6

Offset: 3

Tom Hejda, Nov 27 2017

nonn

The sequence reaches 2 infinitely many times as a(4*n)=2. (If we had a(4*n)>=3, it would imply a(4)>=3, but a(4)=2. This comes from the fact that a(m*n)<=a(m) for m,n>=3.)

			For n=17 we have residues {0,1,2,4,8,9,13,15,16} and the following arithmetic progressions of length 5: (15, 16, 0, 1, 2), (13, 15, 0, 2, 4), (9, 13, 0, 4, 8)

Tom Hejda, Table of n, a(n) for n = 3..20000
MathOverflow user Seva, Consecutive non-quadratic residues (Proves that a(n) is unbounded.)

Bounded by A000224.

Cf. A216869.

def a(n) :
    if n in [1,2] : return Infinity
    R = quadratic_residues(n)
    return max( next( m for m in itertools.count() if (a+(b-a)*m)%n not in R ) \
      for a,b in zip(R,R[1:]+R[:1]) if gcd(b-a,n) == 1 )

A307550 Irregular array of distinct terms read by rows: for n > 0, row n = [r(1),...,r(k)] with r(1) = n^2 (mod prime(n)), r(2) = r(1)^2 (mod prime(n)), ..., r(k) = r(k-1)^2 (mod prime(n)), where r(k) is the last term of the cycle.

Original entry on oeis.org

1, 1, 4, 1, 2, 4, 3, 9, 4, 5, 10, 9, 3, 15, 4, 16, 1, 7, 11, 12, 6, 13, 8, 18, 2, 4, 16, 3, 9, 13, 24, 25, 16, 28, 9, 19, 20, 33, 16, 34, 9, 7, 12, 5, 25, 10, 18, 37, 16, 24, 17, 31, 15, 10, 14, 37, 6, 36, 27, 24, 12, 3, 9, 34, 28, 32, 44, 28, 42, 15, 13, 10

Offset: 1

Michel Lagneau, Apr 14 2019

Consider the map of quadratic residues x -> x^2 (mod prime(n)) with the initial term x = r(1) = n^2 (mod prime(n)) needed to reach the end of the cycle. Row n contains all distinct quadratic residues r(i) such that r(i) = r(j)^2 (mod prime(n)) for some i, j.

The corresponding row lengths are given by the sequence {b(n)} = {1, 1, 2, 2, 4, 3, 4, 2, 10, 4, 4, 6, 6, 6, 11, 12, 28, 5, 10, 3, 4, 12, 20, 12, 5, 21, ...} with b(n) = A307551(n) + 1. We observe the following property: if prime(n) = 2p + 1 with p prime, b(n) = p - 1 if 2 is a primitive root mod p; that is, p is in A001122 (see A141305). Example: b(17) = 28 because prime(17) = 59 = 2*29 + 1 with 28 = 29 - 1, and 2 is a primitive root mod 29.

			Row 5 = [3, 9, 4, 5] because prime(5) = 11, and 3 = 5^2 (mod 11), 9 = 3^2 (mod 11), 4 = 9^2 (mod 11) and 5 = 4^2 (mod 11).
Irregular array starts:
  [1];
  [1];
  [4, 1];
  [2, 4];
  [3, 9, 4, 5];
  [10, 9, 3];
  [15, 4, 16, 1];
   ...

Cf. A000040, A001122, A000224, A046071, A063987, A096008, A141305, A307551.

nn:=30:T:=array(1..280):j:=0 :
for n from 1 to nn do:
p:=ithprime(n):lst0:={}:lst1:={}:ii:=0:r:=n:
for k from 1 to 10^6 while(ii=0) do:
  r1:=irem(r^2,p):lst0:=lst0 union {r1}:j:=j+1:T[j]:=r1:
      if lst0=lst1
       then
        ii:=1:
        else
        r:=r1:lst1:=lst0:
      fi:
     od:
   if lst0 intersect {r1} = {r1}
    then
    j:=j-1:else fi:
od:
print(T):

s[n_] := Module[{p = Prime[n]}, f[x_] := Mod[x^2, p]; Most[NestWhileList[f, f[n], Unequal, All]]]; seq = {}; Do[AppendTo[seq, s[n]], {n, 20}]; seq // Flatten (* Amiram Eldar, Jul 05 2019 *)

A307551 Number of iterations of the map of quadratic residues x -> x^2 (mod prime(n)) with the initial term x = n^2 (mod prime(n)) needed to reach the end of the cycle.

Original entry on oeis.org

0, 0, 1, 1, 3, 2, 3, 1, 9, 3, 3, 5, 5, 5, 10, 11, 27, 4, 9, 2, 3, 11, 19, 11, 4, 20, 7, 51, 17, 2, 5, 11, 9, 10, 35, 19, 11, 5, 81, 13, 10, 3, 35, 6, 21, 29, 11, 35, 27, 18, 27, 7, 5, 99, 7, 129, 65, 35, 10, 2, 22, 9, 23, 19, 13, 38, 19, 8, 171, 27, 13, 177, 59

Offset: 1

Michel Lagneau, Apr 14 2019

nonn

Let L(n) be the number of elements in row n of A307550. Then a(n) = L(n) - 1.

			a(5) = 3 because prime(5) = 11, and 5^2 (mod 11) = 3 -> 3^2 (mod 11) = 9 ->  9^2 (mod 11) = 4 -> 4^2 (mod 11) = 5 with 3 iterations, where 5 is the last term of the cycle.

Cf. A000040, A000224, A046071, A063987, A096008, A307550.

nn:=100:T:=array(1..3000):j:=0 :
for n from 1 to nn do:
p:=ithprime(n):lst0:={}:lst1:={}:ii:=0:r:=n:
for k from 1 to 10^6 while(ii=0) do:
  r1:=irem(r^2,p):lst0:=lst0 union {r1}:j:=j+1:T[j]:=r1:
      if lst0=lst1
       then
        ii:=1: printf(`%d, `,nops(lst0)-1):
        else
        r:=r1:lst1:=lst0:
      fi:
     od:
   if lst0 intersect {r1} = {r1}
    then
    j:=j-1:else fi:
od:

a[n_] := Module[{p = Prime[n]}, f[x_] := Mod[x^2, p]; Length[NestWhileList[f, f[n], Unequal, All]] - 2]; Array[a, 100] (* Amiram Eldar, Jul 05 2019 *)

A328699 Start with 0, a(n) is the smallest number of iterations: x -> (x^2+1) mod n needed to run into a cycle.

Original entry on oeis.org

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

Offset: 1

Jianing Song, Oct 26 2019

nonn

Let f(0) = 0, f(k+1) = (f(k)^2+1) mod n, then a(n) is the smallest i such that f(i) = f(j) for some j > i.
Obviously a(n) <= A000224(n): f(1), f(2), ..., f(A000224(n)+1) are all of the form (s^2+1) mod n, so there must exists 0 <= i < j <= A000224(n)+1 such that f(i) = f(j), and a(n) <= i <= A000224(n). The equality seems to hold only for n = 3.
k divides A003095(m) for some m > 0 if and only if a(k) = 0, in which case all the indices m such that k divides A003095(m) are m = t*A248218(k), t = 0, 1, 2, 3, ...

			A003095(n) mod 3: 0, 1, (2). {A003095(n) mod 3} enters into the cycle (2) from the 2nd term on, so a(3) = 2.
A003095(n) mod 7: 0, 1, 2, (5). {A003095(n) mod 7} enters into the cycle (5) from the 3rd term on, so a(7) = 3.
A003095(n) mod 29: 0, 1, 2, 5, 26, 10, 14, 23, 8, (7, 21). {A003095(n) mod 29} enters into the cycle (7, 21) from the 9th term on, so a(29) = 9.
A003095(n) mod 37: 0, 1, 2, 5, 26, (11). {A003095(n) mod 37} enters into the cycle (11) from the 5th term on, so a(37) = 5.
A003095(n) mod 41: (0, 1, 2, 5, 26, 21, 32). {A003095(n) mod 41} enters into the cycle (0, 1, 2, 5, 26, 21, 32) from the very beginning, so a(41) = 0.

Cf. A003095, A248218 (cycle length), A328700, A000224.

a(n) = my(v=[0],k); for(i=2, n+1, k=(v[#v]^2+1)%n; v=concat(v, k); for(j=1, i-1, if(v[j]==k, return(j-1))))

cp's OEIS Frontend

A218578 The number of times n occurs in A095972.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

A232195 Product of distinct squares in Z_n (mod n), without the factor 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

A271586 Number of squares in Z_n[i].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A303997 Number of ways to write 2*n as p + 3^k + binomial(2*m,m), where p is a prime, and k and m are nonnegative integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A317623 Number of distinct values of X*(3*X-1) mod n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A212887 a(n) is the prime p corresponding to the smallest integer k such that k^2 == p (mod prime(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A295784 Length of the longest arithmetic progression in squares mod n with slope coprime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

A307550 Irregular array of distinct terms read by rows: for n > 0, row n = [r(1),...,r(k)] with r(1) = n^2 (mod prime(n)), r(2) = r(1)^2 (mod prime(n)), ..., r(k) = r(k-1)^2 (mod prime(n)), where r(k) is the last term of the cycle.

Views

Author

A303997 Number of ways to write 2n as p + 3^k + binomial(2m,m), where p is a prime, and k and m are nonnegative integers.

A317623 Number of distinct values of X(3X-1) mod n.