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,4

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

Formula

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

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

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

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 *)

Prog

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

Crossrefs

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

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

Sequence in context: A056889 A275761 A232396 * A039636 A322866 A328847

Adjacent sequences: A270093 A270094 A270095 * A270097 A270098 A270099

Keyword

nonn

Author

Thomas Ordowski, Mar 11 2016

Extensions

More terms from Michel Marcus, Mar 11 2016

Status

approved