A270096 Smallest m such that 2^m == 2^n (mod n).

0, 1, 1, 2, 1, 2, 1, 3, 3, 2, 1, 2, 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 4, 5, 2, 9, 4, 1, 2, 1, 5, 3, 2, 11, 6, 1, 2, 3, 4, 1, 6, 1, 4, 9, 2, 1, 4, 7, 10, 3, 4, 1, 18, 15, 5, 3, 2, 1, 4, 1, 2, 3, 6, 5, 6, 1, 4, 3, 10, 1, 6, 1, 2, 15, 4, 17, 6, 1, 4

Offset: 1

Author

Thomas Ordowski, Mar 11 2016

Keywords

• nonn

Comments

a(n) = 1 iff n is a prime or a pseudoprime (odd or even) to base 2.

We have a(n) <= n - phi(n) and a(n) <= phi(n), so a(n) <= n/2.

From Robert Israel, Mar 11 2016: (Start)

If n is in A167791, then a(n) = A068494(n).

If n is odd, a(n) = n mod A002326((n-1)/2).

a(n) >= A007814(n).

a(p^k) = p^(k-1) for all k >= 1 and all odd primes p not in A001220.

Conjecture: a(n) <= n/3 for all n > 8. (End)

Links

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

Crossrefs

Cf. A000010, A001220, A002326, A007814, A051953, A068494, A167791.

Cf. A276976 (a generalization on all integer bases).

Programs

Maple

f:= proc(n) local d,b,t, m,c;
  d:= padic:-ordp(n,2);
  b:= n/2^d;
  t:= 2 &^ n mod n;
  m:= numtheory:-mlog(t,2,b,c);
  if m < d then m:= m + c*ceil((d-m)/c) fi;
  m
end proc:
f(1):= 0:
map(f, [$1..1000]; # Robert Israel, Mar 11 2016

Mathematica

Table[k = 0; While[PowerMod[2, n, n] != PowerMod[2, k, n], k++]; k, {n, 120}] (* Michael De Vlieger, Mar 15 2016 *)

PARI

a(n) = {my(m = 0); while (Mod(2, n)^m != 2^n, m++); m; } \\ Altug Alkan, Sep 23 2016

Formula

a(n) < n/2 for n > 4.

a(2^k) = k for all k >= 0.

a(2*p) = 2 for all primes p.

Extensions

More terms from Michel Marcus, Mar 11 2016