A195637 -id:A195637 - cp's OEIS frontend

A202034 Number of distinct prime residues of k^n (mod n), k=0..n-1.

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

Offset: 1

Michel Lagneau, Dec 09 2011

nonn

If n is a prime number, a(n) = A000720(n) - 1 because the number of distinct residues of k^n (mod n) = n.

			a(7) = 3  because  k^7 == 0, 1, 2, 3, 4, 5, 6 (mod 7) including 3 prime residues  2, 3, 5.

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A000720, A132213, A195637.

for n from 1 to 100 do: W:={}:for k from 0 to n-1 do:z:= irem(k^n,n): if type(z,prime)=true then W:=W union {z}:else fi:od: x:=nops(W): printf(`%d, `,x): od:

Table[Length[Select[Union[Table[Mod[k^n, n], {k, 0, n - 1}]], PrimeQ]], {n, 81}] (* Alonso del Arte, Dec 10 2011 *)
Count[Union[#],?PrimeQ]&/@Table[PowerMod[k,n,n],{n,100},{k,0,n-1}] (* _Harvey P. Dale, Sep 24 2022 *)

A198020 Number of distinct residues of x^n (mod 2n+1), x=0..2n.

Original entry on oeis.org

1, 3, 3, 3, 4, 3, 3, 15, 3, 3, 8, 3, 6, 19, 3, 3, 12, 35, 3, 39, 3, 3, 12, 3, 8, 51, 3, 55, 20, 3, 3, 49, 8, 3, 24, 3, 3, 63, 24, 3, 28, 3, 27, 87, 3, 15, 32, 95, 3, 77, 3, 3, 16, 3, 3, 111, 3, 115, 28, 119, 12, 123, 51, 3, 44, 3, 8, 95, 3, 3, 48, 143, 16, 129

Offset: 0

Michel Lagneau, Oct 20 2011

nonn

a(n) = 3 if 2n+1 prime because the corresponding residues are 0, 1 and 2n (mod 2n+1).

			a(7) = 15 because x^7  == 0, 1, …,14  (mod 15) => 15 distinct residues.

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

Cf. A195637, A197929.

Table[Length[Union[PowerMod[Range[0, 2*n], n, 2*n+1]]], {n,0, 100}]

A330279 Numbers k such that x^k == k (mod k + 1) has multiple solutions for 0 <= x < k.

Original entry on oeis.org

27, 51, 65, 69, 75, 111, 123, 129, 147, 153, 171, 175, 185, 189, 195, 207, 231, 237, 243, 245, 267, 275, 279, 285, 291, 303, 309, 315, 321, 343, 363, 365, 369, 387, 395, 405, 411, 417, 425, 429, 435, 441, 447, 489, 495, 505, 507, 519, 531, 555, 567, 573, 591, 597

Offset: 1

Christopher Cormier, Dec 09 2019

nonn

All odd numbers have k^k == k (mod k + 1), but only some have other solutions in the least residue system (e.g. 3^27 and 19^27 == 27 (mod 28)).

Odd numbers k such that k and A000010(k+1) are not coprime. - Robert Israel, Jul 30 2023

			27 is in the list because x^27 == 27 (mod 28) has three solutions: 3, 19, and 27.

Robert Israel, Table of n, a(n) for n = 1..10000
Robert Israel et al, Even k such that x^k == -1 mod k has solutions

Cf. A000010, A014117, A096008, A195637.

select(t -> igcd(t,numtheory:-phi(t+1))>1, [seq(i,i=1..1000,2)]); # Robert Israel, Jul 30 2023

ok[k_] := Length[Select[Range[0, k-1], PowerMod[#, k, k + 1] == k &, 2]] > 1; Select[ Range@ 600, ok] (* Giovanni Resta, Dec 10 2019 *)

isok(k) = sum(i=0, k-1, Mod(i, k+1)^k == k) > 1; \\ Michel Marcus, Dec 10 2019

A366418 Number of distinct integers of the form (x^n + y^n) mod n.

Original entry on oeis.org

1, 2, 3, 3, 5, 6, 7, 3, 5, 10, 11, 9, 13, 14, 15, 3, 17, 6, 19, 9, 15, 22, 23, 9, 13, 26, 5, 21, 29, 30, 31, 3, 33, 34, 35, 9, 37, 38, 39, 9, 41, 18, 43, 33, 25, 46, 47, 9, 19, 10, 51, 30, 53, 6, 25, 21, 57, 58, 59, 27, 61, 62, 25, 3, 65, 66, 67, 39, 69, 70, 71, 9, 73, 74, 39

Offset: 1

Albert Mukovskiy, Oct 11 2023

nonn

a(p) = p when p is prime. It appears that a(n) stabilizes for the subsequences n = k^m for each fixed k > 1 at large enough m.

a(n) = n if there are more than n/2 distinct integers x^n mod n. - David A. Corneth, Oct 16 2023

David A. Corneth, PARI program

Cf. A121278, A366419, A195637.

{ a(n) = my(S,t); S=Set(); for(x=0, n-1, for(y=x, n-1, t=lift(Mod(x,n)^n+Mod(y,n)^n); S=setunion(S,[t]); ); ); #S }

a(n) = #setbinop((x,y)->Mod(x,n)^n+Mod(y,n)^n, [0..n-1]); \\ Michel Marcus, Oct 12 2023

See PARI link \\ David A. Corneth, Oct 16 2023

A196547 Nonprime numbers m such that the sum of the distinct residues of x^m (mod m) is divisible by m, x=0..m-1.

Original entry on oeis.org

1, 9, 14, 15, 21, 22, 25, 27, 28, 30, 33, 35, 38, 39, 45, 46, 49, 51, 52, 55, 57, 62, 63, 65, 66, 69, 70, 75, 77, 78, 81, 85, 86, 87, 91, 92, 93, 94, 95, 98, 99, 102, 105, 111, 115, 116, 117, 118, 119, 121, 123, 124, 125, 129, 132, 133, 134, 135, 138, 141, 142

Offset: 1

Michel Lagneau, Oct 03 2011

nonn

Subset of A196546.

			a(3) = 14 because x^14 == 0, 1, 2, 4, 7, 8, 9, 11
(mod 14), and the sum  0+1+2+4+7+8+9+11 = 42 is divisible by 14.

Cf. A195637, A196546.

with(numtheory):T:=array(1..150): for n from 1 to 150 do:for k from 1 to n do:T[k]:=irem(k^n,n):od:W:=convert(T,set):x:=nops(W):s:=0:for i from 1 to x do:s:=s+W[i]:od:if irem(s,n)=0 and type(n,prime)=false then printf(`%d, `,n):else fi:od:

A200046 Numbers n such that the equation x^n + (x+1)^n = (x+2)^n (mod n), x = 0..n-1 has no solution.

Original entry on oeis.org

15, 25, 33, 35, 39, 55, 57, 69, 75, 95, 99, 115, 117, 119, 121, 123, 125, 129, 135, 143, 145, 153, 155, 169, 175, 195, 203, 205, 209, 215, 217, 221, 225, 235, 247, 253, 255, 259, 273, 275, 285, 289, 295, 299, 305, 309, 315, 319, 321, 323, 325, 333, 335, 339

Offset: 1

Michel Lagneau, Nov 14 2011

nonn

All numbers are composites.

Cf. A195637, A200219.

for n from 1 to 340 do:ii:=0:for x from 0 to n-1 do:if x^n+(x+1)^n -(x+2)^n mod n =0 then ii:=ii+1:else fi:od: if ii=0 then printf(`%d, `,n):else fi:od:

A200219 Number of solutions of the equation x^n + (x+1)^n = (x+2)^n (mod n) for x = 0..n-1.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 3, 2, 1, 4, 1, 2, 0, 8, 1, 6, 1, 4, 1, 2, 1, 8, 0, 2, 9, 2, 1, 4, 1, 16, 0, 2, 0, 12, 1, 2, 0, 8, 1, 4, 1, 2, 3, 2, 1, 16, 7, 10, 2, 2, 1, 18, 0, 8, 0, 2, 1, 8, 1, 2, 3, 32, 2, 4, 1, 4, 0, 2, 1, 24, 1, 2, 0, 4, 6, 4, 1, 16, 27, 2, 1, 8

Offset: 1

Michel Lagneau, Nov 14 2011

nonn

a(n) = 0 for n = 15, 25, 33, 35, 39, 55, 57,… (see A200046).

a(n) = 1 if n prime.

			a(6) = 2 because:
for x = 3,  3^6 + 4^6 == 1(mod 6) and 5^6 == 1(mod 6).
for x = 5,  5^6 + 6^6 == 1 (mod 6) and (7)^6 == 1 (mod 6).

Michel Lagneau, Table of n, a(n) for n = 1..1000

Cf. A195637, A200046.

for n from 1 to 100 do:ii:=0:for x from 0 to n-1 do:if x^n+(x+1)^n -(x+2)^n mod n=0 then ii:=ii+1:else fi:od: printf(`%d, `,ii):od:

Array[Function[n,Count[Array[Mod[#^n+(#+1)^n-(#+2)^n,n]&,n,0],0]],84]

A195743 Number of distinct residues of prime(k)^n (mod n), prime(k) <= n.

Original entry on oeis.org

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

Offset: 1

Michel Lagneau, Sep 23 2011

nonn

If n = prime(k), then a(n) = k.

			a(11) = a(prime(5)) = 5, and we check:  2^11, 3^11, 5^11, 7^11, 11^11 == 2, 3, 5, 7, 0 (mod 11) respectively => 5 distinct residues;
a(18) = 3 because 2^18, 3^18, 5^18, 7^18, 11^18, 13^18, 17^18 == 10, 9, 1, 1, 1, 1, 1 (mod 18) respectively => 3 distinct residues.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
I. M. Vinogradov, On a general theorem concerning the distribution of the residues and non-residues of powers, Trans. American Math. Soc., 29 (1927), 209-217.

Cf. A195637.

a:= proc(n) local p, s; s:= {}; p:=2; while p<=n do s:= s union {p&^n mod n}; p:= nextprime(p) od; nops(s) end: seq(a(n), n=1..100);

a[n_] := PowerMod[#, n, n]& /@ Prime[Range[PrimePi[n]]] // Union // Length;
Array[a, 100] (* Jean-François Alcover, Nov 20 2020 *)

a(n) = #Set(vector(primepi(n), k, Mod(prime(k), n)^n)); \\ Michel Marcus, Nov 20 2020

A340806 a(n) = Sum_{k=1..n-1} (k^n mod n).

Original entry on oeis.org

0, 1, 3, 2, 10, 13, 21, 4, 27, 45, 55, 38, 78, 77, 105, 8, 136, 93, 171, 146, 210, 209, 253, 172, 250, 325, 243, 294, 406, 365, 465, 16, 528, 561, 595, 402, 666, 665, 741, 372, 820, 673, 903, 726, 945, 897, 1081, 536, 1029, 1125, 1275, 1170, 1378, 765, 1485

Offset: 1

Sebastian Karlsson, Jan 22 2021

nonn

Sebastian Karlsson, Table of n, a(n) for n = 1..10000

Cf. A010848, A048153, A048155, A094264, A121706, A195637, A195812, A202034.

a:= n-> add(k&^n mod n, k=1..n-1):
seq(a(n), n=1..55);  # Alois P. Heinz, Feb 13 2021

a(n) = sum(k=1, n-1, lift(Mod(k, n)^n)); \\ Michel Marcus, Jan 22 2021

def a(n):
    return sum([pow(k,n,n) for k in range(1, n)])
for n in range(1, 56):
    print(a(n), end=', ')

a(n) = n*A010848(n)/2, if n is odd.
a(n) = n*(n-1)/2, if n is both odd and squarefree.
a(p^e) = (1/2)*(p-1)*p^(2*e-1), if p is an odd prime.
a(2^e) = 2^(e-1).

A196330 Smallest number k such that the number of distinct residues of x^k (mod k) equals n.

Original entry on oeis.org

1, 2, 3, 6, 5, 10, 7, 14, 21, 68, 11, 22, 13, 26, 15, 114, 17, 34, 19, 38, 57, 164, 23, 46, 2525, 776, 657, 212, 29, 58, 31, 62, 33, 4112, 35, 102, 37, 74, 111, 380, 41, 82, 43, 86, 105, 356, 47, 94, 301, 388, 51, 404, 53, 106, 6275, 182, 1467, 452, 59, 118

Offset: 1

Michel Lagneau, Oct 01 2011

nonn

The values of x can be taken to be 1 to n.
Properties of the sequence: if n prime, a(n) = n and a(n+1) = 2n because x^n == 0,1,2,3,...,n-1 (mod n) and x^(2n) == 0, 1^2, 2^2, 3^2,...,(n-1)^2, n (mod 2n) with n+1 distinct residues.
There exists prime numbers, for example n = 7, 19, 37,... with the property: a(n) = n, a(n+1) = 2n, and a(n+2) = 3n.
There exists composite numbers, for example n = 15, 33, 35, 51,... with the property a(n) = n.

			a(6) = 10 because x^10 == 0, 1, 4, 5, 6, 9  (mod 10) => 6 distinct residues.

I. M. Vinogradov, On a general theorem concerning the distribution of the residues and non-residues of powers, Trans. American Math. Soc., 29 (1927), 209-217.

Cf. A195637.

a:= nops ({seq (k&^n mod n, k=0..n-1)}):for i from 1 to 60 do:id:=0:for j from 1 to 10000 while(id=0) do:if a(j)=i then id:=1:printf ( "%d %d \n",i,j):else fi:od:od:

nn = 10000; t = Table[Length[Union[PowerMod[Range[n], n, n]]], {n, nn}]; lim = Complement[Range[nn], Union[t]][[1]] - 1; Table[Position[t, n, 1, 1][[1, 1]], {n, lim}] (* T. D. Noe, Oct 03 2011 *)

a(n) such that A195637(a(n)) = n.

cp's OEIS Frontend

A202034 Number of distinct prime residues of k^n (mod n), k=0..n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A198020 Number of distinct residues of x^n (mod 2n+1), x=0..2n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A330279 Numbers k such that x^k == k (mod k + 1) has multiple solutions for 0 <= x < k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A366418 Number of distinct integers of the form (x^n + y^n) mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

PARI

A196547 Nonprime numbers m such that the sum of the distinct residues of x^m (mod m) is divisible by m, x=0..m-1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

A200046 Numbers n such that the equation x^n + (x+1)^n = (x+2)^n (mod n), x = 0..n-1 has no solution.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

A200219 Number of solutions of the equation x^n + (x+1)^n = (x+2)^n (mod n) for x = 0..n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A195743 Number of distinct residues of prime(k)^n (mod n), prime(k) <= n.

Views

Author

Keywords

Comments

Examples

Links