A239063 -id:A239063 - cp's OEIS frontend

A239061 Number of integers x, 1 <= x <= n, such that x^x == 1 (mod n).

1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 5, 2, 4, 1, 4, 1, 4, 1, 3, 3, 2, 1, 2, 3, 2, 2, 4, 1, 3, 1, 5, 1, 6, 1, 3, 2, 4, 1, 5, 1, 6, 3, 5, 1, 2, 1, 4, 1, 6, 2, 3, 1, 5, 2, 3, 3, 3, 1, 5, 3, 3, 1, 9, 2, 5, 1, 5, 2, 4, 1, 5, 3, 5, 3, 10, 1, 5, 1, 2, 1, 3, 1, 10, 3

Offset: 1

José María Grau Ribas, Mar 09 2014

nonn

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

Cf. A239062, A239063 (indices of 1's).

gg1[n_] := Sum[If[PowerMod[x, x, n] == Mod[1, n], 1, 0], {x, n}];Array[gg1,200]

A239062 Number of integers x, 1 <= x <= n, such that x^x == 0 (mod n).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 3, 3, 1, 1, 2, 1, 1, 1, 7, 1, 3, 1, 2, 1, 1, 1, 4, 5, 1, 9, 2, 1, 1, 1, 15, 1, 1, 1, 6, 1, 1, 1, 4, 1, 1, 1, 2, 3, 1, 1, 8, 7, 5, 1, 2, 1, 9, 1, 4, 1, 1, 1, 2, 1, 1, 3, 31, 1, 1, 1, 2, 1, 1, 1, 12, 1, 1, 5, 2, 1, 1, 1, 8, 26, 1, 1, 2, 1, 1, 1, 4, 1, 3, 1, 2, 1, 1, 1, 16, 1, 7, 3, 10, 1, 1, 1, 4, 1

Offset: 1

José María Grau Ribas, Mar 09 2014

nonn

			From _Michael De Vlieger_, Sep 23 2017: (Start)
Table of records a(n) and first positions n:
   i       n    a(n)
-------------------
   1       1      1
   2       4      2
   3       8      3
   4      16      7
   5      27      9
   6      32     15
   7      64     31
   8     128     62
   9     243     80
  10     256    126
  11     512    253
  12    1024    509
  13    2048   1020
  14    4096   2044
  15    6561   2185
  16    8192   4092
  17   16384   8188
(End)

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A239061, A239063, A005117 (indices of 1's).

gg0[n_] := Sum[If[Mod[x^x , n] == 0, 1, 0], {x, n}];Array[gg0,200]
(* or *)
Array[Sum[Boole[PowerMod[x, x, #] == 0], {x, #}] &, 10^4] (* or *)
Table[Count[Range@ n, k_ /; PowerMod[k, k, n] == 0], {n, 200}] (* Michael De Vlieger, Sep 23 2017 *)

A239062(n) = sum(x=1,n, if(0 == Mod(x^x, n), 1, 0)); \\ Antti Karttunen, Sep 23 2017, after the Mathematica-program.

More terms from Antti Karttunen, Sep 23 2017

A343073 a(n) is the number of integers 0 < b < n such that b^^x == 1 (mod n) has a solution; ^^ denotes the tetration operation (cf. A321312).

Original entry on oeis.org

1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 6, 2, 5, 1, 9, 1, 5, 1, 3, 3, 2, 1, 3, 3, 2, 2, 5, 1, 3, 1, 5, 1, 8, 1, 9, 2, 5, 1, 8, 1, 6, 3, 5, 1, 2, 1, 4, 1, 17, 2, 5, 1, 5, 2, 3, 3, 3, 1, 7, 3, 3, 1, 15, 2, 5, 1, 5, 2, 4, 1, 16, 4, 5, 3, 10, 1, 5

Offset: 2

Bernat Pagès Vives, Apr 04 2021

nonn

If the same definition were used, but with b^x instead of b^^x, then a(n) would be A000010(n), the Euler Totient Function.
A019434 plays a special role for this sequence. a(A019434(n)) = (A019434(n)+1)/2, since all even numbers b satisfy the condition, and b=1 is the only odd number that satisfies it. This can be easily proved with the Fermat-Euler Theorem.
a(n) <= A000010(n), since gcd(b,n)=1 is a necessary condition. There is equality when n = 2 and n = 3. It is a conjecture that there are no more equality cases.
The sequence A239063 gives exactly the numbers n where a(n) = 1. This means that if b^^2 == 1 (mod n) has no solutions with 1 < b < n, then neither will b^^x == 1 (mod n).

			For n = 5,
Setting b = 1, x = 1 gives 1^^1 == 1 (mod 5).
Setting b = 2, x = 3 gives 2^^3 == 2^8 == 1 (mod 5).
Setting b = 3 has no solutions, since 3^^x == 2 (mod 5) for all x > 1.
Setting b = 4, x = 2 gives 4^^2 == 1 (mod 5).
Thus there are 3 possible values of b, and that is the value of a(5).

Bernat Pagès Vives, Table of n, a(n) for n = 2..500
Wikipedia, Tetration
Wikipedia, Carmichael Function

Cf. A000010, A019434, A239063, A317905, A321312.

Tetration[a_,b_,mod_]:=
    Which[
        Mod[a,mod]==0, 0,
        b == 1,Mod[a,mod],
        b==2,PowerMod[a,a,mod],
        b==3&&a==2,Mod[16,mod],
        True,PowerMod[a,Mod[(Tetration[a,b-1,EulerPhi[mod]]-Floor[Log[2,mod]]),EulerPhi[mod]]+Floor[Log[2,mod]],mod]]
TetraInv[n_,mod_,it_]:=
    Which[
        GCD[n,mod]!=1 ,0,
        it==LambdaRoot[mod]+1,0,
        Tetration[n,it,mod]==1,it,
        True,TetraInv[n,mod,it+1]
]
LambdaRoot[n_]:=Module[{counter,it},
    counter = 0;
    it = n;
    While[it!=1,
        it = CarmichaelLambda[it];
        counter++;
    ];
    counter
]
a[n_] := Module[{counter ,t},
    counter = 0;
    For[j=1,j<=n,j++,
        t =TetraInv[j,n,1];
        If[t!=0,counter++]
    ];
    counter
]

If n is a Fermat prime, a(n) = (n+1)/2.

If n is a power of 2, a(n) = 1.

A338445 Numbers m with integer solution to x^x == (x+1)^(x+1) (mod m) with 1<=x

Original entry on oeis.org

3, 11, 13, 19, 23, 29, 31, 43, 49, 53, 57, 59, 61, 67, 71, 73, 77, 79, 83, 85, 89, 91, 93, 97, 101, 103, 109, 113, 127, 129, 131, 133, 141, 143, 147, 149, 151, 157, 161, 163, 167, 169, 173, 177, 179, 183, 187, 197, 199, 201, 203, 205, 211, 217, 229, 235, 237, 239

Offset: 1

Owen C. Keith, Oct 28 2020

nonn

Some values of m have multiple solutions.
For example, for m = 49, 25^25 == 26^26 (mod 49) and 37^37 == 38^38 (mod 49).
All terms are odd. - Robert Israel, Nov 25 2020

			3 is a term because 1^1 == 2^2 (mod 3).
11 is a term because 8^8 == 9^9 (mod 11).
13 is a term because 8^8 == 9^9 (mod 13).

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

Similar sequences: A174824, A239061, A239062, A239063.

filter:= proc(n) local x,y,z;
  y:= 1;
  for x from 2 to n-1 do
    z:= x &^ x mod n;
    if z = y then return true fi;
    y:= z
  od;
  false
end proc:
select(filter, [$2..1000]); # Robert Israel, Nov 25 2020

seqQ[n_] := AnyTrue[Range[n - 1], PowerMod[#, #, n] == PowerMod[# + 1, # + 1, n] &]; Select[Range[240], seqQ] (* Amiram Eldar, Oct 28 2020 *)

isok(m)=sum(i=1, m-1, Mod(i,m)^i == Mod((i+1),m)^(i+1)) \\ Andrew Howroyd, Oct 28 2020

cp's OEIS Frontend

A239061 Number of integers x, 1 <= x <= n, such that x^x == 1 (mod n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A239062 Number of integers x, 1 <= x <= n, such that x^x == 0 (mod n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A343073 a(n) is the number of integers 0 < b < n such that b^^x == 1 (mod n) has a solution; ^^ denotes the tetration operation (cf. A321312).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A338445 Numbers m with integer solution to x^x == (x+1)^(x+1) (mod m) with 1<=x

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI