For real irrational $C > 1 $ and natural $n,b$, define 
$a(C,n,b)=\lfloor C^n \rfloor \mod b$

>Q1 For which $C,b$ is $a(C,n,b)$ computable in time polynomial
in $\log{n}$?

Searching in OEIS suggests that for $C \in \{1+\sqrt{2},1+\sqrt{3},(1+\sqrt{5})/2\}$, $a(C,n,b)$ satisfy linear recurrence with constant coefficients and
so it is efficiently computable over the integers and all bases $b$.

In OEIS:
[a(n) = floor(phi^n)](https://oeis.org/A014217)

[a(n) = floor((1+sqrt(2))^n)](https://oeis.org/A080039)

[a(n) = floor((1+sqrt(3))^n)](https://oeis.org/A080041)

For natural $k$, $a(b^{1/k},n,b)$ is related to the base
$b$ representation of $b^{1/k}$ so it is probably hopeless.

>Q2 Is $a(1+\sqrt{6},n,b)$ efficiently computable in some base $b$?

(We couldn't find linear recurrence for it)

>Q3 Except linear recurrences, are there other islands of tractability
for algebraic $C$?