cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A096008 Irregular triangle read by rows where n-th row contains all quadratic residues (including zero) mod n.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 1, 0, 1, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 4, 0, 1, 4, 7, 0, 1, 4, 5, 6, 9, 0, 1, 3, 4, 5, 9, 0, 1, 4, 9, 0, 1, 3, 4, 9, 10, 12, 0, 1, 2, 4, 7, 8, 9, 11, 0, 1, 4, 6, 9, 10, 0, 1, 4, 9, 0, 1, 2, 4, 8, 9, 13, 15, 16, 0, 1, 4, 7, 9, 10, 13, 16, 0, 1, 4, 5, 6, 7, 9, 11, 16, 17, 0, 1, 4, 5, 9, 16
Offset: 1

Views

Author

Cino Hilliard, Jul 20 2004

Keywords

Examples

			The table starts:
  [1]  [0]
  [2]  [0, 1]
  [3]  [0, 1]
  [4]  [0, 1]
  [5]  [0, 1, 4]
  [6]  [0, 1, 3, 4]
  [7]  [0, 1, 2, 4]
  [8]  [0, 1, 4]
  [9]  [0, 1, 4, 7]
  [10] [0, 1, 4, 5, 6, 9]
  ...

Links

Crossrefs

Cf. A046071 (without zeros), A000224 (row lengths), A063987.
Last elements of rows give A047210.
Row sums give A165909.

Programs

  • Haskell
    a096008 n k = a096008_tabf !! (n-1) !! (k-1)
a096008_row n = a096008_tabf !! (n-1)
a096008_tabf = [0] : map (0 :) a046071_tabf
-- Reinhard Zumkeller, May 10 2015
  • Maple
    q := n -> sort(convert({seq(i^2 mod n, i=0..n-1)}, list));
# N. J. A. Sloane, Feb 09 2011
# Alternative:
QR := (a, n) -> NumberTheory:-QuadraticResidue(a, n):
for n from 1 to 10 do print(select(a -> 1 = QR(a, n), [seq(0..n-1)])) od:
# Peter Luschny, Jun 02 2024
  • Mathematica
    row[n_] := Table[PowerMod[k, 2, n], {k, 0, n-1}] // Union; Table[row[n], {n, 1, 20}] // Flatten (* Jean-François Alcover, Sep 09 2013 *)
ResourceFunction["QuadraticResidues"] /@ Range[20] // Flatten  (* Peter Luschny, May 23 2024 *)
  • PARI
    T(n) = {local(v,r,i,j,k); v=vector(n,i,0); for(i=0,floor(n/2),v[i^2%n+1]=1); k=sum(i=1,n,v[i]); j=0; r=vector(k); for(i=1,n, if(v[i], j++; r[j]=i-1)); r}
  • SageMath
    for n in range(1, 11): print(quadratic_residues(n)) # Peter Luschny, Jun 02 2024

Extensions

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

A334819 Largest quadratic nonresidue modulo n (with n >= 3).

Original entry on oeis.org

2, 3, 3, 5, 6, 7, 8, 8, 10, 11, 11, 13, 14, 15, 14, 17, 18, 19, 20, 21, 22, 23, 23, 24, 26, 27, 27, 29, 30, 31, 32, 31, 34, 35, 35, 37, 38, 39, 38, 41, 42, 43, 44, 45, 46, 47, 48, 48, 50, 51, 51, 53, 54, 55, 56, 56, 58, 59, 59, 61, 62, 63, 63, 65, 66, 67
Offset: 3

Views

Author

Peter Schorn, May 12 2020

Keywords

Comments

The largest nonnegative integer less than n which is not a square modulo n.
If p is a prime congruent 3 modulo 4 then a(p) = p-1 since -1 is not a quadratic residue for such primes.

Examples

			The squares modulo 3 are 0 and 1. Therefore a(3) = 2. The nonsquares modulo 4 are 2 and 3 which makes a(4) = 3. Modulo 5 we have 0, 1 and 4 as squares giving a(5) = 3. 0, 1 and 4 are also the squares modulo 6 resulting in a(6) = 5. Since 10007 is a prime of the form 4*k + 3, a(10007) = 10006.

Links

Crossrefs

Cf. A020649, A047210 (the largest square modulo n), A192450 (a(n)=n-1).

Programs

  • Maple
    f:= proc(n) local k;
  for k from n-1 by -1 do if numtheory:-msqrt(k,n)=FAIL then return k fi
  od
end proc:
map(f, [$3..100]); # Robert Israel, May 14 2020
  • Mathematica
    a[n_] := Module[{r}, For[r = n-1, r >= 1, r--, If[!IntegerQ[Sqrt[Mod[r, n]] ], Return[r]]]];
a /@ Range[3, 100] (* Jean-François Alcover, Aug 15 2020 *)
  • PARI
    a(n) = forstep(r = n - 1, 1, -1, if(!issquare(Mod(r, n)), return(r)))

A327649 Maximum value of powers of 2 mod n.

Original entry on oeis.org

0, 1, 2, 2, 4, 4, 4, 4, 8, 8, 10, 8, 12, 8, 8, 8, 16, 16, 18, 16, 16, 20, 18, 16, 24, 24, 26, 16, 28, 16, 16, 16, 32, 32, 32, 32, 36, 36, 32, 32, 40, 32, 42, 40, 38, 36, 42, 32, 46, 48, 32, 48, 52, 52, 52, 32, 56, 56, 58, 32, 60, 32, 32, 32, 64, 64, 66, 64, 64
Offset: 1

Views

Author

Rémy Sigrist, Sep 21 2019

Keywords

Examples

			For n = 10:
- the first powers of 2 mod 10 are:
    k   2^k mod 10
    --  ----------
     0           1
     1           2
     2           4
     3           8
     4           6
     5           2
- those values are eventually periodic, the maximum being 8,
- hence a(10) = 8.

Links

Crossrefs

Cf. A000079, A062170, A047210, A327650.

Programs

  • Maple
    f:= proc(n) local S,k,x,m;
  x:= 1; S:= {1}; m:= 1;
  for k from 1 do
    x:= 2*x mod n;
    if member(x,S) then return m fi;
    S:= S union {x};
    m:= max(m,x)
  od
end proc:
f(1):= 0:
map(f, [$1..100]); # Robert Israel, Feb 15 2023
  • Mathematica
    a[n_] := PowerMod[2, Range[0, n-1], n] // Max;
Table[a[n], {n, 1, 1000}] (* Jean-François Alcover, May 14 2023 *)
  • PARI
    a(n) = { my (p=1%n, mx=p); while (1, p=(2*p)%n; if (mx

Formula

a(2^k) = 2^(k-1) for any k > 0.
a(2^k+1) = 2^k for any k >= 0.
a(2^k-1) = 2^(k-1) for any k > 1.
If n = 2^j * r with r odd > 1 then a(n) = 2^j * a(r). - Robert Israel, Feb 15 2023
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.