OFFSET
1,1
COMMENTS
The Zeckendorf representation of a positive integer n is a unique sum
c(k-2)F(k) + c(k-3)F(k-1) + ... + c(1)F(3) + c(0)F(2),
where F=A000045 (Fibonacci numbers), c(k-2)=1, and for j=0,1,...,k-3, there are two restrictions on coefficients: c(j) is 0 or 1, and c(j)c(j+1)=0; viz., no two consecutive Fibonacci numbers appear. The Zeckendorf polynomial Z(n,x) is introduced here as
c(k-2)x^(k-2) + c(k-3)x^(k-3) + ... + c(1)x + c(0).
The name refers to irreducibility over the field of rational numbers.
EXAMPLE
n k Z(n) Z(n,x) irreducible
1 2 1 1 no
2 3 10 x yes
3 4 100 x^2 no
4 4 101 x^2 + 1 yes
5 5 1000 x^3 no
6 5 1001 x^3 + 1 no
7 5 1010 x^3 + x no
8 5 10000 x^4 no
9 5 10001 x^4 + 1 yes
MATHEMATICA
fb[n_] := Block[{k = Ceiling[Log[GoldenRatio, n*Sqrt[5]]],
t = n, fr = {}}, While[k > 1, If[t >= Fibonacci[k],
AppendTo[fr, 1]; t = t - Fibonacci[k],
AppendTo[fr, 0]]; k--]; fr]; t = Table[fb[n],
{n, 1, 350}];
b[n_] := Reverse[Table[x^k, {k, 0, n}]]
p[n_, x_] := t[[n]].b[-1 + Length[t[[n]]]]
Table[p[n, x], {n, 1, 40}] (* Zeckendorf polynomials *)
u = {}; Do[n++; If[IrreduciblePolynomialQ[p[n, x]],
AppendTo[u, n]], {n, 300}]; u (* A207813 *)
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Clark Kimberling, Feb 20 2012
STATUS
approved