login
A327649
Maximum value of powers of 2 mod n.
2
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,3
LINKS
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)
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
EXAMPLE
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.
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 *)
PROG
(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))) }
CROSSREFS
KEYWORD
nonn,look
AUTHOR
Rémy Sigrist, Sep 21 2019
STATUS
approved