A364811 Number of distinct residues x^4 (mod 2^n), x=0..2^n-1.

1, 2, 2, 2, 2, 4, 6, 10, 18, 36, 70, 138, 274, 548, 1094, 2186, 4370, 8740, 17478, 34954, 69906, 139812, 279622, 559242, 1118482, 2236964, 4473926

Offset: 0

Author

Albert Mukovskiy, Sep 14 2023

Keywords

• nonn
• more

Comments

For n>=4, A319281(a(n)) == 2^n + [(n mod 4)>0].

It appears that for n>4: a(n)=2*a(n-1)-2*[(n mod 4)==2]; a(n) = ceiling(2^n/15) - [(n mod 4)==0] + 1.

Crossrefs

Cf. A319281, A023105, A046630, A365103.

Programs

Mathematica

a[n_]:=CountDistinct[Table[PowerMod[x-1, 4, 2^(n-1)], {x, 1, 2^(n-1)}]]; Array[a, 24]

PARI

a(n) = #Set(vector(2^(n-1), x, Mod(x-1, 2^(n-1))^4))

Python

def A364811(n): return len({pow(x,4,1<Chai Wah Wu, Sep 17 2023