login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A270096 Smallest m such that 2^m == 2^n (mod n). 6

%I #53 Aug 03 2017 11:53:35

%S 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,

%T 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,

%U 1,4,3,10,1,6,1,2,15,4,17,6,1,4

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

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

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

%C From _Robert Israel_, Mar 11 2016: (Start)

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

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

%C a(n) >= A007814(n).

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

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

%H Robert Israel, <a href="/A270096/b270096.txt">Table of n, a(n) for n = 1..10000</a>

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

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

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

%p f:= proc(n) local d,b,t, m,c;

%p d:= padic:-ordp(n,2);

%p b:= n/2^d;

%p t:= 2 &^ n mod n;

%p m:= numtheory:-mlog(t,2,b,c);

%p if m < d then m:= m + c*ceil((d-m)/c) fi;

%p m

%p end proc:

%p f(1):= 0:

%p map(f, [$1..1000]; # _Robert Israel_, Mar 11 2016

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

%o (PARI) a(n) = {my(m = 0); while (Mod(2, n)^m != 2^n, m++); m; } \\ _Altug Alkan_, Sep 23 2016

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

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

%K nonn

%O 1,4

%A _Thomas Ordowski_, Mar 11 2016

%E More terms from _Michel Marcus_, Mar 11 2016

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 16:00 EDT 2024. Contains 371254 sequences. (Running on oeis4.)