When is $\sum_{n=0}^{\infty}\frac{n^k}{3^n}$ an integer? The motivation for this was to find some nice expression for the sum
$$\sum_{n=0}^\infty\frac{P(n)}{b^n}$$
where $P(n)$ is a polynomial and $b$ is a positive integer greater than 1.
Clearly, it suffices to find sums of the form $\sum_{n=0}^\infty\frac{n^k}{b^n}$ for integer k.
If we set $b=2$, a simple translation and subtraction of the terms in the series shows that $f(k)=\sum_{n=0}^\infty\frac{n^k}{2^n}$ satisfies the recurrence relation $f(k)=\sum_{i=0}^{k-1}{k \choose i}f(i)$, producing the series $2,2,6,26,...$ (A076726 in OEIS).
If $b>2$, a similar argument shows that the recurrence is $$f(k)=\sum_{i=0}^{k-1}\frac{{k \choose i}f(i)}{b-1}$$
When b=3, the series is as follows:
$\frac{3}{2},\frac{3}{4},\frac{3}{2},\frac{33}{8},15,\frac{273}{4},\frac{1491}{4},\frac{38001}{16},17295,...$
The series takes on integer values at strange places; the first several such values are 4, 8, 12, 13, 16, 20, 24, 32, ... (not in OEIS)
Some unproved notes about the integer positions: They're usually multiples of 4, and most multiples of 4 seem to be on the list except powers of 2 minus 4. All powers of 2 larger than 2 that I've computed so far (up to 1024) are integers. The odd numbers that take on integer values are frequently separated by powers of 2; if I recall correctly, the next odd number after 13 is 77=13+64.
Curiously, there appear to be $no$ integer values for $b>3$. 
Does anyone know why these patterns should occur? If nothing else, more data on these values would be great (the few programming languages I'm competent in weren't able to handle large numbers very well, and I've lost the data up to 1024 that I used to have).
 A: The problems boils down to a rather simple question about Bernoulli numbers. We have:
$$ \sum_{n\geq 0}\frac{e^{nx}}{b^n} = \frac{b}{b-e^{x}}\tag{1} $$
hence:
$$ \sum_{n\geq 0}\frac{n^k}{b^n} = \frac{d^k}{dx^k}\left.\,\frac{b}{b-e^{x}}\right|_{x=0}=\frac{Q_k(b)}{(b-1)^{k+1}}\tag{2}$$
with $Q_k$ being a polynomial of degree $k$ with integer coefficients. 
In order to understand when the LHS of $(2)$ has some chance to be an integer, it is enough to recall the generating function for the Bernoulli numbers  and the Von-Staudt-Clausen theorem.
A: I tested whether $f(k) = \sum_{k=0}^\infty n^k \,3^{-n}$ is an integer for $k = 0$ to $50000$.  In this range, $f(k) \in \mathbb{Z}$ if and only if $k$ has one of the following forms (for $j \ge 0$):


*

*$4+4j$ (* with exceptions—see below)

*$13+64j$

*$122+256j$

*$379+1024j$

*$1529+2048j$

*$8181+32768j$


There are two sequences of exceptions to the first case (i.e., when $k$ is a positive multiple of $4$).  When $k$ has either of the forms


*

*$28+32j$

*$1016+1024j$


then $f(k) \notin \mathbb{Z}$.
How does this extend to all $k$?  A natural conjecture is that there is an infinite list of sequences like the ones above, as well as an infinite list of exception sequences to the multiple-of-$4$ case.  We would expect that they all have of a power-of-$2$ stride and that they begin at an integer smaller than their stride (except for the first sequence).
