A327649 Maximum value of powers of 2 mod n.

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, 16, 28, 16, 16, 16, 32, 32, 32, 32, 36, 36, 32, 32, 40, 32, 42, 40, 38, 36, 42, 32, 46, 48, 32, 48, 52, 52, 52, 32, 56, 56, 58, 32, 60, 32, 32, 32, 64, 64, 66, 64, 64

Offset: 1

Author

Rémy Sigrist, Sep 21 2019

Keywords

• nonn
• look

Examples

			For n = 10:
- the first powers of 2 mod 10 are:
    k   2^k mod 10
    --  ----------
     0           1
     1           2
     2           4
     3           8
     4           6
     5           2
- those values are eventually periodic, the maximum being 8,
- hence a(10) = 8.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..8192
• Rémy Sigrist, Colored scatterplot of the ordinal transform of the first 2^16 terms (colored pixels correspond to n's such that a(n) is a power of 2)

Crossrefs

Cf. A000079, A062170, A047210, A327650.

Programs

Maple

f:= proc(n) local S,k,x,m;
  x:= 1; S:= {1}; m:= 1;
  for k from 1 do
    x:= 2*x mod n;
    if member(x,S) then return m fi;
    S:= S union {x};
    m:= max(m,x)
  od
end proc:
f(1):= 0:
map(f, [$1..100]); # Robert Israel, Feb 15 2023

Mathematica

a[n_] := PowerMod[2, Range[0, n-1], n] // Max;
Table[a[n], {n, 1, 1000}] (* Jean-François Alcover, May 14 2023 *)

PARI

a(n) = { my (p=1%n, mx=p); while (1, p=(2*p)%n; if (mx
				

Formula

a(2^k) = 2^(k-1) for any k > 0.

a(2^k+1) = 2^k for any k >= 0.

a(2^k-1) = 2^(k-1) for any k > 1.

If n = 2^j * r with r odd > 1 then a(n) = 2^j * a(r). - Robert Israel, Feb 15 2023