A291674 a(n) is the smallest k such that 2^psi(k) == 2^phi(n) (mod n).

1, 1, 3, 2, 3, 3, 2, 2, 4, 3, 19, 3, 6, 2, 3, 3, 7, 4, 10, 3, 4, 19, 43, 3, 19, 6, 10, 2, 39, 3, 19, 4, 19, 7, 6, 4, 18, 10, 6, 3, 19, 4, 13, 19, 6, 43, 137, 3, 26, 19, 7, 6, 103, 10, 19, 2, 10, 39, 173, 3, 38, 19, 4, 4, 6, 19, 86, 7, 43, 6, 139, 4, 10, 18, 19, 10, 25, 6, 206, 3, 34, 19, 163

Offset

1,3

Comments

Remainders when 2^phi(n) is divided by n are 0, 0, 1, 0, 1, 4, 1, 0, 1, 6, 1, 4, 1, 8, 1, 0, 1, 10, 1, 16, 1, 12, ... (i.e., the values of "1" come from Euler's totient theorem).

If n is odd, a(n) is the least k such that psi(k) is divisible by A002326((n-1)/2). - Robert Israel, Aug 29 2017

Links

Table of n, a(n) for n=1..83.

Example

a(11) = 19 because 2^psi(19) == 2^phi(11) (mod 11) and 19 is the least number with this property.

Maple

N:= 1000: # to get terms before the first term > N
Psis:= Vector([$1..N]):
for p in select(isprime, [2, seq(i, i=3..N, 2)]) do
  pm:= p*[$1..N/p];
  Psis[pm]:= map(`*`, Psis[pm], 1+1/p);
od:
for n from 1 do
  r:= 2 &^ numtheory:-phi(n) mod n;
  for k from 1 to N do
    if 2 &^ Psis[k] mod n = r then A[n]:= k; break fi
  od:
  if not assigned(A[n]) then break fi
od:
seq(A[i], i=1..n-1); # Robert Israel, Aug 29 2017

Mathematica

psi[n_] := If[n == 1, 1, n Times @@ (1 + 1/First /@ FactorInteger@ n)]; a[n_] := Block[{k = 1, v = PowerMod[2, EulerPhi[n], n]}, While[ PowerMod[2, psi[k], n] != v, k++]; k]; Array[a, 83] (* Giovanni Resta, Aug 30 2017 *)

Prog

(PARI) a001615(n) = my(f=factor(n)); prod(i=1, #f~, f[i, 1]^f[i, 2] + f[i, 1]^(f[i, 2]-1));
a(n) = {my(k=1); while (Mod(2, n)^a001615(k) != 2^eulerphi(n), k++); k; } \\ after Charles R Greathouse IV at A001615

Crossrefs

Cf. A000010, A001615, A002326.

Sequence in context: A165601 A324030 A275821 * A265157 A054263 A308656

Adjacent sequences: A291671 A291672 A291673 * A291675 A291676 A291677

Keyword

nonn

Author

Altug Alkan, Aug 29 2017

Status

approved