cp's OEIS Frontend

A327649 Maximum value of powers of 2 mod n.

%I A327649 #31 May 14 2023 09:17:13
%S A327649 0,1,2,2,4,4,4,4,8,8,10,8,12,8,8,8,16,16,18,16,16,20,18,16,24,24,26,
%T A327649 16,28,16,16,16,32,32,32,32,36,36,32,32,40,32,42,40,38,36,42,32,46,48,
%U A327649 32,48,52,52,52,32,56,56,58,32,60,32,32,32,64,64,66,64,64
%N A327649 Maximum value of powers of 2 mod n.
%H A327649 Rémy Sigrist, <a href="/A327649/b327649.txt">Table of n, a(n) for n = 1..8192</a>
%H A327649 Rémy Sigrist, <a href="/A327649/a327649.png">Colored scatterplot of the ordinal transform of the first 2^16 terms</a> (colored pixels correspond to n's such that a(n) is a power of 2)
%F A327649 a(2^k) = 2^(k-1) for any k > 0.
%F A327649 a(2^k+1) = 2^k for any k >= 0.
%F A327649 a(2^k-1) = 2^(k-1) for any k > 1.
%F A327649 If n = 2^j * r with r odd > 1 then a(n) = 2^j * a(r). - _Robert Israel_, Feb 15 2023
%e A327649 For n = 10:
%e A327649 - the first powers of 2 mod 10 are:
%e A327649     k   2^k mod 10
%e A327649     --  ----------
%e A327649      0           1
%e A327649      1           2
%e A327649      2           4
%e A327649      3           8
%e A327649      4           6
%e A327649      5           2
%e A327649 - those values are eventually periodic, the maximum being 8,
%e A327649 - hence a(10) = 8.
%p A327649 f:= proc(n) local S,k,x,m;
%p A327649   x:= 1; S:= {1}; m:= 1;
%p A327649   for k from 1 do
%p A327649     x:= 2*x mod n;
%p A327649     if member(x,S) then return m fi;
%p A327649     S:= S union {x};
%p A327649     m:= max(m,x)
%p A327649   od
%p A327649 end proc:
%p A327649 f(1):= 0:
%p A327649 map(f, [$1..100]); # _Robert Israel_, Feb 15 2023
%t A327649 a[n_] := PowerMod[2, Range[0, n-1], n] // Max;
%t A327649 Table[a[n], {n, 1, 1000}] (* _Jean-François Alcover_, May 14 2023 *)
%o A327649 (PARI) a(n) = { my (p=1%n, mx=p); while (1, p=(2*p)%n; if (mx<p, mx=p, mx==p || p==0, return (mx))) }
%Y A327649 Cf. A000079, A062170, A047210, A327650.
%K A327649 nonn,look
%O A327649 1,3
%A A327649 _Rémy Sigrist_, Sep 21 2019