Re: [math-fun] Factorization of 1 + n + n^2 + . . . + n^k

The first simple remark is that x^n-1 = prod_{d|n} phi_d(x) where phi_d is the d-th cyclotomic polynomial. So, in your notation, S(n,k) = prod_{1 != d|k} phi_d(n) So for 111,111 we would have 111111 = phi_2(10)phi_3(10) phi_6(10) = (10+1)*(10^2-10+1)*(10^+10+1) = 11*91*111. The factorization of 91 = 7*13 could be predicted since any prime factor (except for those dividing d) of phi_d(r) must be == 1 mod d. -- Victor S. Miller | " ... Meanwhile, those of us who can compute can hardly victor@idaccr.org | be expected to keep writing papers saying 'I can do the CCR, Princeton, NJ | following useless calculation in 2 seconds', and indeed 08540 USA | what editor would publish them?" -- Oliver Atkin