login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A270096 Smallest m such that 2^m == 2^n (mod n). 6
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 16 20:32 EDT 2021. Contains 345069 sequences. (Running on oeis4.)